Finding the influence set through skylines

ABSTRACT

Given a set P of products, a set O of customers, and a product p ε P, a bichromatic reverse skyline query retrieves all the customers in O that do not find any other product in P to be absolutely better than p. More specifically, a customer o ε O is in the reverse skyline of p ε P if and only no other product in P better matches the preference of o on all dimensions.

The only existing bichromatic reverse skyline algorithm, which we refer to as basic, is designed for uncertain data. This paper focuses on traditional datasets, where each object is a precise point. Since a precise point can be regarded as a special uncertain object, basic can still be applied. However, as precise data are inherently easier to handle than uncertain data, one should expect that basic can be further improved by taking advantage of the reduced problem complexity. Indeed, we observe several non-trivial heuristics that can optimize the access order to achieve stronger pruning power. Motivated by this, we propose a new algorithm called BRS, and prove that BRS never entails more I/Os than basic. Besides our theoretical analysis, we also perform extensive experiments to show that in practice BRS usually outperforms basic by a large factor. For example, when both P and O follow the anti-correlated distribution, BRS is faster than basic by an order of magnitude. Finally, we address a new variation of bichromatic reverse skyline search where the conventional definition of dynamic skylines no longer makes sense.

REFERENCES

• 1: W.-T. Balke, U. Güntzer, and J. X. Zheng. Efficient distributed skylining for web information systems. In EDBT, pages 256--273, 2004.
• 2: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 3: Stephan Börzsönyi , Donald Kossmann , Konrad Stocker, The Skyline Operator, Proceedings of the 17th International Conference on Data Engineering, p.421-430, April 02-06, 2001
• 4: Chee-Yong Chan , Pin-Kwang Eng , Kian-Lee Tan, Stratified computation of skylines with partially-ordered domains, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066181]
• 5: Chee-Yong Chan , H. V. Jagadish , Kian-Lee Tan , Anthony K. H. Tung , Zhenjie Zhang, Finding k-dominant skylines in high dimensional space, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142530]
• 6: C. Y. Chan, H. V. Jagadish, K.-L. Tan, A. K. H. Tung, and Z. Zhang. On high dimensional skylines. In EDBT, pages 478--495, 2006.
• 7: Surajit Chaudhuri , Nilesh Dalvi , Raghav Kaushik, Robust Cardinality and Cost Estimation for Skyline Operator, Proceedings of the 22nd International Conference on Data Engineering, p.64, April 03-07, 2006 [doi>10.1109/ICDE.2006.131]
• 8: Bee-Chung Chen , Kristen LeFevre , Raghu Ramakrishnan, Privacy skyline: privacy with multidimensional adversarial knowledge, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 9: J. Chomicki, P. Godfrey, J. Gryz, and D. Liang. Skyline with presorting. In ICDE, pages 717--719, 2003.
• 10: B. Cui, H. Lu, Q. Xu, L. Chen, Y. Dai, and Y. Zhou. Parallel distributed processing of constrained skyline queries by filtering. In ICDE, pages 546--555, 2008.
• 11: Evangelos Dellis , Bernhard Seeger, Efficient computation of reverse skyline queries, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 12: K. Deng, X. Zhou, and H. T. Shen. Multi-source skyline query processing in road networks. In ICDE, pages 796--805, 2007.
• 13: Parke Godfrey , Ryan Shipley , Jarek Gryz, Maximal vector computation in large data sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 14: Zhiyong Huang , Christian S. Jensen , Hua Lu , Beng Chin Ooi, Skyline Queries Against Mobile Lightweight Devices in MANETs, Proceedings of the 22nd International Conference on Data Engineering, p.66, April 03-07, 2006 [doi>10.1109/ICDE.2006.142]
• 15: W. Jin, M. Ester, Z. Hu, and J. Han. The multi-relational skyline operator. In ICDE, pages 1276--1280, 2007.
• 16: Donald Kossmann , Frank Ramsak , Steffen Rost, Shooting stars in the sky: an online algorithm for skyline queries, Proceedings of the 28th international conference on Very Large Data Bases, p.275-286, August 20-23, 2002, Hong Kong, China
• 17: Ken C. K. Lee , Baihua Zheng , Huajing Li , Wang-Chien Lee, Approaching the skyline in Z order, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 18: Cuiping Li , Beng Chin Ooi , Anthony K. H. Tung , Shan Wang, DADA: a data cube for dominant relationship analysis, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142547]
• 19: Xiang Lian , Lei Chen, Monochromatic and bichromatic reverse skyline search over uncertain databases, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376641]
• 20: Xuemin Lin , Yidong Yuan , Wei Wang , Hongjun Lu, Stabbing the Sky: Efficient Skyline Computation over Sliding Windows, Proceedings of the 21st International Conference on Data Engineering, p.502-513, April 05-08, 2005 [doi>10.1109/ICDE.2005.137]
• 21: X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang. Selecting stars: The k most representative skyline operator. In ICDE, pages 86--95, 2007.
• 22: Michael Morse , Jignesh M. Patel , H. V. Jagadish, Efficient skyline computation over low-cardinality domains, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 23: Michael Morse , Jignesh M. Patel , William I. Grosky, Efficient Continuous Skyline Computation, Proceedings of the 22nd International Conference on Data Engineering, p.108, April 03-07, 2006 [doi>10.1109/ICDE.2006.56]
• 24: Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, Progressive skyline computation in database systems, ACM Transactions on Database Systems (TODS), v.30 n.1, p.41-82, March 2005 [doi>10.1145/1061318.1061320]
• 25: J. Pei, A. W.-C. Fu, X. Lin, and H. Wang. Computing compressed multidimensional skyline cubes efficiently. In ICDE, pages 96--105, 2007.
• 26: Jian Pei , Bin Jiang , Xuemin Lin , Yidong Yuan, Probabilistic skylines on uncertain data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 27: Jian Pei , Wen Jin , Martin Ester , Yufei Tao, Catching the best views of skyline: a semantic approach based on decisive subspaces, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 28: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 29: Nikos Sarkas , Gautam Das , Nick Koudas , Anthony K. H. Tung, Categorical skylines for streaming data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376643]
• 30: Mehdi Sharifzadeh , Cyrus Shahabi, The spatial skyline queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 31: M. A. Soliman, I. F. Ilyas, and N. Koudas. Finding skyline and top-k bargaining solutions. In ICDE, pages 1263--1267, 2007.
• 32: 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
• 33: Yufei Tao , Xiaokui Xiao , Jian Pei, SUBSKY: Efficient Computation of Skylines in Subspaces, Proceedings of the 22nd International Conference on Data Engineering, p.65, April 03-07, 2006 [doi>10.1109/ICDE.2006.149]
• 34: Akrivi Vlachou , Christos Doulkeridis , Yannis Kotidis, Angle-based space partitioning for efficient parallel skyline computation, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376642]
• 35: A. Vlachou, C. Doulkeridis, Y. Kotidis, and M. Vazirgiannis. Skypeer: Efficient subspace skyline computation over distributed data. In ICDE, pages 416--425, 2007.
• 36: S. Wang, B. C. Ooi, A. K. H. Tung, and L. Xu. Efficient skyline query processing on peer-to-peer networks. In ICDE, pages 1126--1135, 2007.
• 37: P. Wu, D. Agrawal, Ö. Egecioglu, and A. E. Abbadi. Deltasky: Optimal maintenance of skyline deletions without exclusive dominance region generation. In ICDE, pages 486--495, 2007.
• 38: P. Wu, C. Zhang, Y. Feng, B. Y. Zhao, D. Agrawal, and A. E. Abbadi. Parallelizing skyline queries for scalable distribution. In EDBT, pages 112--130, 2006.
• 39: Tian Xia , Donghui Zhang, Refreshing the sky: the compressed skycube with efficient support for frequent updates, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142529]
• 40: Yidong Yuan , Xuemin Lin , Qing Liu , Wei Wang , Jeffrey Xu Yu , Qing Zhang, Efficient computation of the skyline cube, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway