Document Open Access Logo

K-Dominance in Multidimensional Data: Theory and Applications

Authors Thomas Schibler, Subhash Suri

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.65.pdf
  • Filesize: 470 kB
  • 13 pages

Document Identifiers

Author Details

Thomas Schibler
Subhash Suri

Cite As Get BibTex

Thomas Schibler and Subhash Suri. K-Dominance in Multidimensional Data: Theory and Applications. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.65

Abstract

We study the problem of k-dominance in a set of d-dimensional vectors, prove bounds on the number of maxima (skyline vectors), under both worst-case and average-case models, perform experimental evaluation using synthetic and real-world data, and explore an application of k-dominant skyline for extracting a small set of top-ranked vectors in high dimensions where the full skylines can be unmanageably large.

Subject Classification

Keywords
  • Dominance
  • skyline
  • database search
  • average case analysis
  • random vectors

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. Agarwal, N. Kumar, S. Sintos, and S. Suri. Efficient algorithms for k-regret minimizing sets. In Proc. of 16th Int. Symp. on Experimental Algorithms, 2017, to appear. Google Scholar
  2. Basketball Data. URL: http://databasebasketball.com/.
  3. J. L. Bentley. Multidimensional Divide and Conquer. Communications of the ACM, 23(4):214-229, 1980. Google Scholar
  4. J. L. Bentley, H. T. Kung, M. Schkolnick, and C. D. Thompson. On the Average Number of Maxima in a Set of Vectors and Applications. Journal of the ACM, 25(4):536-543, 1978. Google Scholar
  5. S. Börzsönyi, D. Kossmann, and K. Stocker. The skyline operator. In Proceedings of the 17th International Conference on Data Engineering, pages 421-430, 2001. Google Scholar
  6. C. Buchta. On the average number of maxima in a set of vectors. Information Processing Letters, 33(2):63-65, 1989. Google Scholar
  7. C. Y. Chan, H. V. Jagadish, K. L. Tan, A. K. H. Tung, and Z. Zhang. Finding K-dominant Skylines in High Dimensional Space. In Proceedings of the ACM SIGMOD International Conference on Management, pages 503-514, 2006. Google Scholar
  8. C. Y. Chan, H. V. Jagadish, K. L. Tan, A. K. H. Tung, and Z. Zhang. On High Dimensional Skylines. In Proc. 10th International Conference on Extending Database Technology (EDBT), pages 478-495, 2006. Google Scholar
  9. S. Chester and I. Assent. Explanations for Skyline Query Results. In Proc. International Conference on Extending Database Technology (EDBT), pages 349-360, 2015. Google Scholar
  10. S. Chester, A. Thomo, S. Venkatesh, and S. Whitesides. Computing k-regret Minimizing Sets. PVLDB, 7(5):389-400, 2014. Google Scholar
  11. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 2nd edition. MIT Press, McGraw-Hill Book Company, 2000. Google Scholar
  12. UCI Data Repository. http://archive.ics.uci.edu/ml/. Google Scholar
  13. M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer, 3rd edition, 2008. Google Scholar
  14. P. Godfrey. Skyline cardinality for relational processing. In Proc. Foundations of Information and Knowledge Systems (FoIKS), pages 78-97, 2004. Google Scholar
  15. P. Godfrey, R. Shipley, and J. Gryz. Algorithms and analyses for maximal vector computation. VLDB J., 16(1):5-28, 2007. Google Scholar
  16. F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems, 5(4):1-19, 2015. Google Scholar
  17. H. K. Hwang, T. H. Tsai, and W. M. Chen. Threshold phenomena in k-dominant skylines of random samples. SIAM Journal on Computing, 42(2):405-441, 2013. Google Scholar
  18. V. Koltun and C. H. Papadimitriou. Approximately Dominating Representatives. Theoretical Computer Science, 371(3):148-154, 2007. Google Scholar
  19. D. Kossmann, F. Ramsak, and S. Rost. Shooting stars in the sky: An online algorithm for skyline queries. In Proceedings of 28th International Conference on Very Large Data Bases (VLDB), pages 275-286, 2002. Google Scholar
  20. H. T. Kung, Fabrizio Luccio, and F. P. Preparata. On Finding the Maxima of a Set of Vectors. Journal of the ACM, 22(4):469-476, 1975. Google Scholar
  21. Yang Lu, Jiakui Zhao, Lijun Chen, Bin Cui, and Dongqing Yang. Effective skyline cardinality estimation on data streams. In 19th International Conference on Database and Expert Systems Applications, pages 241-254, 2008. Google Scholar
  22. J. Matousek. Computing dominances in Eⁿ. Information Processing Letters, 38(5):277-278, 1991. Google Scholar
  23. Movie Lens Data. URL: http://grouplens.org/datasets/movielens/.
  24. D. Nanongkai, A. D. Sarma, A. Lall, R. J. Lipton, and J. Xu. Regret-Minimizing Representative Databases. PVLDB, 3(1):1114-1124, 2010. Google Scholar
  25. D. Papadias, Y. Tao, G. Fu, and B. Seeger. An optimal and progressive algorithm for skyline queries. In Proc. ACM SIGMOD, pages 467-478, 2003. Google Scholar
  26. P. Peng and R. C-W. Wong. Geometry approach for k-regret query. In Proc. International Conference on Data Engineering (ICDE), pages 772-783, 2014. Google Scholar
  27. F. P. Preparata and M. I. Shamos. Computational Geometry - An Introduction. Springer, 1985. Google Scholar
  28. E. Tiakas, A. N. Papadopoulos, and Y. Manolopoulos. On estimating the maximum domination value and the skyline cardinality of multi-dimensional data sets. Int. J. Knowledge-Based Organ., 3(4):61-83, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact