In multi-criterion decision making applications,a skyline query narrows the search range,as it returns only the points that are not dominated by others.Unfortunately,in high-dimensional/large-cardinal datasets there e...In multi-criterion decision making applications,a skyline query narrows the search range,as it returns only the points that are not dominated by others.Unfortunately,in high-dimensional/large-cardinal datasets there exist too many skyline points to offer interesting insights.In this paper,we propose a novel structure,called the dominance tree (Do-Tree),to effectively index and retrieve the skyline.Do-Tree is a straightforward and flexible tree structure,in which skyline points are resident on leaf nodes,while the internal nodes contain the entries that dominate their children.As Do-Tree is built on a dominance relationship,it is suitable for the retrieval of specified skyline via dominance-based predicates customized by users.We discuss the topology of Do-Tree and propose the construction methods.We also present the scan scheme of Do-Tree and some useful queries based on it.Extensive experiments confirm that Do-Tree is an effcient and scalable index structure for the skyline.展开更多
In the XML community, exact queries allow users to specify exactly what they want to check and/or retrieve in an XML document. When they are applied to a semi-structured document or to a document with an overly comple...In the XML community, exact queries allow users to specify exactly what they want to check and/or retrieve in an XML document. When they are applied to a semi-structured document or to a document with an overly complex model, the lack or the ignorance of the explicit document model (DTD—Document Type Definition, Schema, etc.) increases the risk of obtaining an empty result set when the query is too specific, or, too large result set when it is too vague (e.g. it contains wildcards such as “*”). The reason is that in both cases, users write queries according to the document model they have in mind;this can be very far from the one that can actually be extracted from the document. Opposed to exact queries, preference queries are more flexible and can be relaxed to expand the search space during their evaluations. Indeed, during their evaluation, certain constraints (the preferences they contain) can be relaxed if necessary to avoid precisely empty results;moreover, the returned answers can be filtered to retain only the best ones. This paper presents an algorithm for evaluating such queries inspired by the TreeMatch algorithm proposed by Yao et al. for exact queries. In the proposed algorithm, the best answers are obtained by using an adaptation of the Skyline operator (defined in relational databases) in the context of documents (trees) to incrementally filter into the partial solutions set, those which satisfy the maximum of preferential constraints. The only restriction imposed on documents is No-Self-Containment.展开更多
基金Project supported by the National Natural Science Foundationof China (Nos.60803003 and 60970124)the Changjiang Schol-ars and Innovative Research Grant (No.IRT0652) at Zhejiang Universitythe Fundamental Research Funds for the CentralUniversities (No.2010QNA5051),China
文摘In multi-criterion decision making applications,a skyline query narrows the search range,as it returns only the points that are not dominated by others.Unfortunately,in high-dimensional/large-cardinal datasets there exist too many skyline points to offer interesting insights.In this paper,we propose a novel structure,called the dominance tree (Do-Tree),to effectively index and retrieve the skyline.Do-Tree is a straightforward and flexible tree structure,in which skyline points are resident on leaf nodes,while the internal nodes contain the entries that dominate their children.As Do-Tree is built on a dominance relationship,it is suitable for the retrieval of specified skyline via dominance-based predicates customized by users.We discuss the topology of Do-Tree and propose the construction methods.We also present the scan scheme of Do-Tree and some useful queries based on it.Extensive experiments confirm that Do-Tree is an effcient and scalable index structure for the skyline.
文摘In the XML community, exact queries allow users to specify exactly what they want to check and/or retrieve in an XML document. When they are applied to a semi-structured document or to a document with an overly complex model, the lack or the ignorance of the explicit document model (DTD—Document Type Definition, Schema, etc.) increases the risk of obtaining an empty result set when the query is too specific, or, too large result set when it is too vague (e.g. it contains wildcards such as “*”). The reason is that in both cases, users write queries according to the document model they have in mind;this can be very far from the one that can actually be extracted from the document. Opposed to exact queries, preference queries are more flexible and can be relaxed to expand the search space during their evaluations. Indeed, during their evaluation, certain constraints (the preferences they contain) can be relaxed if necessary to avoid precisely empty results;moreover, the returned answers can be filtered to retain only the best ones. This paper presents an algorithm for evaluating such queries inspired by the TreeMatch algorithm proposed by Yao et al. for exact queries. In the proposed algorithm, the best answers are obtained by using an adaptation of the Skyline operator (defined in relational databases) in the context of documents (trees) to incrementally filter into the partial solutions set, those which satisfy the maximum of preferential constraints. The only restriction imposed on documents is No-Self-Containment.
