Index and retrieve the skyline based on dominance relationship

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 p...

Full description

Saved in:
Bibliographic Details
Published in:Frontiers of information technology & electronic engineering 2011, Vol.12 (1), p.62-75
Main Authors: Xu, Chang, Shou, Li-dan, Chen, Gang, Gao, Yun-jun
Format: Article
Language:English
Subjects:
Children
Communications Engineering
Computer Hardware
Computer Science
Computer Systems Organization and Communication Networks
Construction
Decision making
Dominance
Electrical Engineering
Electronics and Microelectronics
Instrumentation
Networks
Nodes
Query processing
Searching
Topology
Trees
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1869-1951
2095-9184
1869-196X
2095-9230
DOI:10.1631/jzus.C0900003