Abstract
The top-k dominating query returns k data objects which dominate the highest number of objects in a dataset. This query is an important tool for decision support since it provides data analysts an intuitive way for finding significant objects. In addition, it combines the advantages of top-k and skyline queries without sharing their disadvantages: (i) the output size can be controlled, (ii) no ranking functions need to be specified by users, and (iii) the result is independent of the scales at different dimensions. Despite their importance, top-k dominating queries have not received adequate attention from the research community. This paper is an extensive study on the evaluation of top-k dominating queries. First, we propose a set of algorithms that apply on indexed multi-dimensional data. Second, we investigate query evaluation on data that are not indexed. Finally, we study a relaxed variant of the query which considers dominance in dimensional subspaces. Experiments using synthetic and real datasets demonstrate that our algorithms significantly outperform a previous skyline-based approach. We also illustrate the applicability of this multi-dimensional analysis query by studying the meaningfulness of its results on real data.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Balke, W.-T., Güntzer, U., Zheng, J.X.: Efficient distributed skylining for web information systems. In: EDBT (2004)
Börzsönyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: ICDE (2001)
Butz A.R.: Alternative algorithm for Hilbert’s space-filling curve. IEEE Trans. Comput. C-20(4), 424–426 (1971)
Chan, C.-Y., Eng, P.-K., Tan, K.-L.: Stratified computation of skylines with partially-ordered domains. In: SIGMOD (2005)
Chan, C.-Y., Jagadish, H., Tan, K.-L., Tung, A., Zhang, Z.: Finding k-dominant skylines in high dimensional space. In: SIGMOD (2006)
Chan, C.-Y., Jagadish, H., Tan, K.-L., Tung, A., Zhang, Z.: On high dimensional skylines. In: EDBT (2006)
Chaudhuri, S., Dalvi, N., Kaushik, R.: Robust cardinality and cost estimation for skyline operator. In: ICDE (2006)
Chomicki, J., Godfrey, P., Gryz, J., Liang, D.: Skyline with presorting. In: ICDE (2003)
Fagin, R., Lotem, A., Naor, M.: Optimal aggregation algorithms for middleware. In: PODS (2001)
Godfrey, P.: Skyline cardinality for relational processing. In: FoIKS (2004)
Godfrey, P., Shipley, R., Gryz, J.: Maximal vector computation in large data sets. In: VLDB (2005)
Guttman, A.: R-Trees: A dynamic index structure for spatial searching. In: SIGMOD (1984)
Hjaltason G.R., Samet H.: Distance browsing in spatial databases. TODS 24(2), 265–318 (1999)
Hristidis, V., Koudas, N., Papakonstantinou, Y.: PREFER: a system for the efficient execution of multiparametric ranked queries. In: SIGMOD (2001)
Huang, Z., Jensen, C.S., Lu, H., Ooi, B.C.: Skyline queries against mobile lightweight devices in MANETs. In: ICDE (2006)
Kossmann, D., Ramsak, F., Rost, S.: Shooting stars in the sky: an online algorithm for skyline queries. In: VLDB (2002)
Lazaridis, I., Mehrotra, S.: Progressive approximate aggregate queries with a multi-resolution tree structure. In: SIGMOD (2001)
Leutenegger, S.T., Edgington, J.M., Lopez, M.A.: STR: a simple and efficient algorithm for R-Tree packing. In: ICDE (1997)
Li, C., Chang, K.C.-C., Ilyas, I.F.: Supporting ad hoc ranking aggregates. In: SIGMOD (2006)
Li, C., Ooi, B.C., Tung, A., Wang, S.: DADA: a data cube for dominant relationship analysis. In: SIGMOD (2006)
Lin, X., Yuan, Y., Wang, W., Lu, H.: Stabbing the sky: efficient skyline computation over sliding windows. In: ICDE (2005)
Lin, X., Yuan, Y., Zhang, Q., Zhang, Y.: Selecting stars: The k most representative skyline operator. In: ICDE (2007)
Papadias, D., Kalnis, P., Zhang, J., Tao, Y.: Efficient OLAP operations in spatial data warehouses. In: SSTD (2001)
Papadias D., Tao Y., Fu G., Seeger B.: Progressive skyline computation in database systems. TODS 30(1), 41–82 (2005)
Pei, J., Fu, A.W.-C., Lin, X., Wang, H.: Computing compressed multidimensional skyline cubes efficiently. In: ICDE (2007)
Pei, J., Jin, W., Ester, M., Tao, Y.: Catching the best views of skyline: a semantic approach based on decisive subspaces. In: VLDB (2005)
Pei J., Yuan Y., Lin X., Jin W., Ester M., Liu Q., Wang W., Tao Y., Yu J.X., Zhang Q.: Towards multidimensional subspace skyline analysis. TODS 31(4), 1335–1381 (2006)
Tan, K.-L., Eng, P.-K., Ooi, B.C.: Efficient progressive skyline computation. In: VLDB (2001)
Tao, Y., Xiao, X., Pei, J.: SUBSKY: efficient computation of skylines in subspaces. In: ICDE (2006)
Theodoridis, Y., Sellis, T.K.: A model for the prediction of R-tree performance. In: PODS (1996)
Yiu, M.L., Mamoulis, N.: Efficient processing of top-k dominating queries on multi-dimensional data. In: VLDB (2007)
Yuan, Y., Lin, X., Liu, Q., Wang, W., Yu, J.X., Zhang, Q.: Efficient computation of the skyline cube. In: VLDB (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Yiu, M.L., Mamoulis, N. Multi-dimensional top-k dominating queries. The VLDB Journal 18, 695–718 (2009). https://doi.org/10.1007/s00778-008-0117-y
Received:
Revised:
Accepted:
Published:
Issue date:
DOI: https://doi.org/10.1007/s00778-008-0117-y
