Index and retrieve the skyline based on dominance relationship

Chang XU; Li-dan SHOU; Gang CHEN; Yun-jun GAO

doi:10.1631/jzus.C0900003

Your Location：

Home >

Browse articles >

Index and retrieve the skyline based on dominance relationship

计算机与自动化 | Updated：2022-08-31

- Index and retrieve the skyline based on dominance relationship
- Index and retrieve the skyline based on dominance relationship
- 信息与电子工程前沿（英文） 2011年12卷第1期页码：62-75
- Affiliations：
  
  School of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
- Author bio：
  
  E-mail:chinawraith@163.com
  ‡Corresponding Author
- Funds：
- DOI：10.1631/jzus.C0900003
  中图分类号：
- 收稿：2009-12-17，
  
  修回：2010-12-06，
  
  录用：2010-08-12，
  
  纸质出版：2011-01
- Accepted：
Scan QR Code
Index and retrieve the skyline based on dominance relationship[J]. 信息与电子工程前沿（英文）, 2011,12(1):62-75.

Chang XU, Li-dan SHOU, Gang CHEN, et al. Index and retrieve the skyline based on dominance relationship[J]. Frontiers of Information Technology & Electronic Engineering, 2011, 12(1): 62-75.
Index and retrieve the skyline based on dominance relationship[J]. 信息与电子工程前沿（英文）, 2011,12(1):62-75. DOI： 10.1631/jzus.C0900003.

Chang XU, Li-dan SHOU, Gang CHEN, et al. Index and retrieve the skyline based on dominance relationship[J]. Frontiers of Information Technology & Electronic Engineering, 2011, 12(1): 62-75. DOI： 10.1631/jzus.C0900003.

摘要

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 oﬀer interesting insights. In this paper

we propose a novel structure

called the dominance tree (Do-Tree)

to eﬀectively index and retrieve the skyline. Do-Tree is a straightforward and ﬂexible 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 speciﬁed 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 conﬁrm that Do-Tree is an eﬃcient and scalable index structure for the skyline.

关键词

Keywords

references

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

PRISMO: predictive skyline query processing over moving objects