Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2011, Vol. 12 Issue (1): 62-75    DOI: 10.1631/jzus.C0900003
    
Index and retrieve the skyline based on dominance relationship
Chang XU, Li-dan SHOU*, Gang CHEN, Yun-jun GAO
School of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
Index and retrieve the skyline based on dominance relationship
Chang XU, Li-dan SHOU*, Gang CHEN, Yun-jun GAO
School of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
 全文: PDF(1057 KB)  
摘要： 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    
Abstract: 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.
Key words: Spatial database    Skyline    Preference queries
收稿日期: 2009-12-17 出版日期: 2010-01-10
CLC:  TP391  
基金资助: Project supported by the National Natural Science Foundation of China (Nos. 60803003 and 60970124), the Changjiang Scholars and Innovative Research Grant (No. IRT0652) at Zhejiang University, and the Fundamental Research Funds for the Central Universities (No. 2010QNA5051), China
通讯作者: Li-dan SHOU     E-mail: should@zju.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Chang XU
Li-dan SHOU
Gang CHEN
Yun-jun GAO

引用本文:

Chang XU, Li-dan SHOU, Gang CHEN, Yun-jun GAO. Index and retrieve the skyline based on dominance relationship. Front. Inform. Technol. Electron. Eng., 2011, 12(1): 62-75.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/jzus.C0900003    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2011/V12/I1/62

[1] Nan Chen, Li-dan Shou, Gang Chen, Yun-jun Gao, Jin-xiang Dong. PRISMO: predictive skyline query processing over moving objects[J]. Front. Inform. Technol. Electron. Eng., 2012, 13(2): 99-117.