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.