Stratified computation of skylines with partially-ordered domains

ABSTRACT

In this paper, we study the evaluation of skyline queries with partially-ordered attributes. Because such attributes lack a total ordering, traditional index-based evaluation algorithms (e.g., NN and BBS) that are designed for totally-ordered attributes can no longer prune the space as effectively. Our solution is to transform each partially-ordered attribute into a two-integer domain that allows us to exploit index-based algorithms to compute skyline queries on the transformed space. Based on this framework, we propose three novel algorithms: BBS⁺ is a straightforward adaptation of BBS using the framework, and SDC (Stratification by Dominance Classification) and SDC⁺ are optimized to handle false positives and support progressive evaluation. Both SDC and SDC⁺ exploit a dominance relationship to organize the data into strata. While SDC generates its strata at run time, SDC⁺ partitions the data into strata offline. We also design two dominance classification strategies (MinPC and MaxPC) to further optimize the performance of SDC and SDC⁺. We implemented the proposed schemes and evaluated their efficiency. Our results show that our proposed techniques outperform existing approaches by a wide margin, with SDC⁺-MinPC giving the best performance in terms of both response time as well as progressiveness. To the best of our knowledge, this is the first paper to address the problem of skyline query evaluation involving partially-ordered attribute domains.

REFERENCES

• 1: R. Agrawal , A. Borgida , H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.253-262, June 1989, Portland, Oregon, United States
• 2: Rakesh Agrawal , Edward L. Wimmers, A framework for expressing and combining preferences, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.297-306, May 15-18, 2000, Dallas, Texas, United States
• 3: W. Balke, U. Güntzer, and X. Zheng. Efficient distributed skylining for web information systems. In EDBT'04.
• 4: S. Börzsönyi, D. Kossmann, and K. Stocker. The skyline operator. In ICDE'01.
• 5: Michael J. Carey , Donald Kossmann, On saying “Enough already!” in SQL, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.219-230, May 11-15, 1997, Tucson, Arizona, United States
• 6: Jan Chomicki, Querying with Intrinsic Preferences, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.34-51, March 25-27, 2002
• 7: Jan Chomicki, Preference formulas in relational queries, ACM Transactions on Database Systems (TODS), v.28 n.4, p.427-466, December 2003 [doi>10.1145/958942.958946]
• 8: Vagelis Hristidis , Nick Koudas , Yannis Papakonstantinou, PREFER: a system for the efficient execution of multi-parametric ranked queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.259-270, May 21-24, 2001, Santa Barbara, California, United States
• 9: W. Kießling. Foundations of preferences in database systems. In VLDB'02.
• 10: W. Kießling and G. Köstler. Preference SQL - design, implementation, experiences. In VLDB'02.
• 11: D. Kossmann, F. Ramsak, and S. Rost. Shooting stars in the sky: an online algorithm for skyline queries. In VLDB'02.
• 12: H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
• 13: Jiří Matoušek, Computing dominances inEn (short communication), Information Processing Letters, v.38 n.5, p.277-278, June 14, 1991 [doi>10.1016/0020-0190(91)90071-O]
• 14: Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, An optimal and progressive algorithm for skyline queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872814]
• 15: Christos H. Papadimitriou , Mihalis Yannakakis, Multiobjective query optimization, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.52-59, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375560]
• 16: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 17: I. Stojmenovic and M. Miyakawa. An optimal parallel algorithm for solving the maximal elements problem in the plane. Parallel Computing, 7(2), June 1988.
• 18: Kian-Lee Tan , Pin-Kwang Eng , Beng Chin Ooi, Efficient Progressive Skyline Computation, Proceedings of the 27th International Conference on Very Large Data Bases, p.301-310, September 11-14, 2001
• 19: R. Torlone and P. Ciaccia. Which are my preferred items? In Workshop on Recommendation and Personalization in E-Commerce, May 2002.
• 20: Yoav Zibin , Joseph Yossi Gil, Efficient subtyping tests with PQ-encoding, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.96-107, October 14-18, 2001, Tampa Bay, FL, USA