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 efficient and scalable index structure for the skyline.

关键词： Spatial database,  Skyline,  Preference queries