Full Text:
<2567>
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: 6615
Index and retrieve the skyline based on dominance relationship
| |||||||||||||
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",
volume="12",
number="1",
pages="62-75",
year="2011",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C0900003"
}
%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
TY - JOUR
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
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.
[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
<1>