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.展开更多
基金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.
