Full Text:   <1242>

CLC number: TP391

On-line Access: 2010-01-10

Received: 2009-12-17

Revision Accepted: 2010-08-12

Crosschecked: 2010-12-06

Cited: 0

Clicked: 3138

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2011 Vol.12 No.1 P.62-75


Index and retrieve the skyline based on dominance relationship

Author(s):  Chang XU, Li-dan SHOU, Gang Chen, Yun-jun Gao

Affiliation(s):  School of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China

Corresponding email(s):   chinawraith@163.com, should@zju.edu.cn

Key Words:  Spatial database, Skyline, Preference queries

Chang XU, Li-dan SHOU, Gang Chen, Yun-jun Gao. Index and retrieve the skyline based on dominance relationship[J]. Journal of Zhejiang University Science C, 2011, 12(1): 62-75.

@article{title="Index and retrieve the skyline based on dominance relationship",
author="Chang XU, Li-dan SHOU, Gang Chen, Yun-jun Gao",
journal="Journal of Zhejiang University Science C",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Index and retrieve the skyline based on dominance relationship
%A Chang XU
%A Li-dan SHOU
%A Gang Chen
%A Yun-jun Gao
%J Journal of Zhejiang University SCIENCE C
%V 12
%N 1
%P 62-75
%@ 1869-1951
%D 2011
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C0900003

T1 - Index and retrieve the skyline based on dominance relationship
A1 - Chang XU
A1 - Li-dan SHOU
A1 - Gang Chen
A1 - Yun-jun Gao
J0 - Journal of Zhejiang University Science C
VL - 12
IS - 1
SP - 62
EP - 75
%@ 1869-1951
Y1 - 2011
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C0900003

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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Bartolini, I., Ciaccia, P., Patella, M., 2008. Efficient sort-based skyline evaluation. ACM Trans. Database Syst., 33(4).

[2]Börzsönyi, S., Kossmann, D., Stocker, K., 2001. The Skyline Operator. ICDE, p.421-430.

[3]Brando, C., Goncalves, M., González, V., 2007. Evaluating Top-k Skyline Queries over Relational Databases. DEXA, p.254-263.

[4]Chan, C.Y., Jagadish, H.V., Tan, K.L., Tung, A.K.H., Zhang, Z.J., 2006a. On High Dimensional Skylines. EDBT, p.478-495.

[5]Chan, C.Y., Jagadish, H.V., Tan, K.L., Tung, A.K.H., Zhang, Z.J., 2006b. Finding k-Dominant Skylines in High Dimensional Space. SIGMOD, p.503-514.

[6]Chomicki, J., Godfrey, P., Gryz, J., Liang, D.M., 2003. Skyline with Presorting. ICDE, p.717-816.

[7]Goncalves, M., Vidal, M.E., 2005. Top-k Skyline: a Unified Approach. OTM Workshops, p.790-799.

[8]Goncalves, M., Vidal, M.E., 2009. Reaching the Top of the Skyline: an Efficient Indexed Algorithm for Top-k Skyline Queries. DEXA, p.471-485.

[9]Guttman, A., 1984. R-trees: a dynamic index structure for spatial searching. ACM SIGMOD Rec., 14(2):47-57.

[10]Hjaltason, G.R., Samet, H., 1999. Distance browsing in spatial databases. ACM Trans. Database Syst., 24(2):265-318.

[11]Kamel, I., Faloutsos, C., 1993. On Packing R-Trees. CIKM, p.490-499.

[12]Kossmann, D., Ramsak, F., Rost, S., 2002. Shooting Stars in the Sky: an Online Algorithm for Skyline Queries. VLDB, p.275-286.

[13]Lee, J.W., You, G.W., Sohn, I.C., Hwang, S.W., Ko, K., Lee, Z., 2007a. Supporting Personalized Top-k Skyline Queries Using Partial Compressed Skycube. WIDM, p.65-72.

[14]Lee, K.C.K., Zheng, B.H., Li, H.J., Lee, W.C., 2007b. Approaching the Skyline in Z Order. VLDB, p.279-290.

[15]Leutenegger, S.T., Edgington, J.M., Lopez, M.A., 1997. STR: a Simple and Efficient Algorithm for R-Tree Packing. ICDE, p.497-506.

[16]Lin, X.M., Yuan, Y.D., Zhang, Q., Zhang, Y., 2007. Selecting Stars: the k Most Representative Skyline Operator. ICDE, p.86-95.

[17]Papadias, D., Tao, Y.F., Fu, G., Seeger, B., 2003. An Optimal and Progressive Algorithm for Skyline Queries. SIGMOD, p.467-478.

[18]Pei, J., Jin, W., Ester, M., Tao, Y.F., 2005. Catching the Best Views of Skyline: a Semantic Approach Based on Decisive Subspaces. VLDB, p.253-264.

[19]Pei, J., Fu, A.W.C., Lin, X.M., Wang, H.X., 2007. Computing Compressed Multidimensional Skyline Cubes Efficiently. ICDE, p.96-105.

[20]Tan, K.L., Eng, P.K., Ooi, B.C., 2001. Efficient Progressive Skyline Computation. VLDB, p.301-310.

[21]Tao, Y.F., Xiao, X.K., Pei, J., 2006. Subsky: Efficient Computation of Skylines in Subspaces. ICDE, p.65.

[22]Tao, Y.F., Xiao, X.K., Pei, J., 2007. Efficient skyline and top-k retrieval in subspaces. IEEE Trans. Knowl. Data Eng., 19(8):1072-1088.

[23]Yiu, M.L., Mamoulis, N., 2007. Efficient Processing of Top-k Dominating Queries on Multi-dimensional Data. VLDB, p.483-494.

[24]Yuan, Y.D., Lin, X.M., Liu, Q., Wang, W., Yu, J.X., Zhang, Q., 2005. Efficient Computation of the Skyline Cube. VLDB, p.241-252.

[25]Zhang, Z.J., Guo, X.Y., Lu, H., Tung, A.K.H., Wang, N., 2005. Discovering Strong Skyline Points in High Dimensional Spaces. CIKM, p.247-248.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE