On Skyline Groups
- 16 July 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 26 (4), 942-956
- https://doi.org/10.1109/tkde.2013.119
Abstract
We formulate and investigate the novel problem of finding the skyline k-tuple groups from an n-tuple data set-i.e., groups of k tuples which are not dominated by any other group of equal size, based on aggregate-based group dominance relationship. The major technical challenge is to identify effective anti-monotonic properties for pruning the search space of skyline groups. To this end, we first show that the anti-monotonic property in the well-known Apriori algorithm does not hold for skyline group pruning. Then, we identify two anti-monotonic properties with varying degrees of applicability: order-specific property which applies to SUM, MIN, and MAX as well as weak candidate-generation property which applies to MIN and MAX only. Experimental results on both real and synthetic data sets verify that the proposed algorithms achieve orders of magnitude performance gain over the baseline method.Keywords
This publication has 16 references indexed in Scilit:
- Preference queries over setsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Finding a team of experts in social networksPublished by Association for Computing Machinery (ACM) ,2009
- Distance-Based Representative SkylineInternational Conference on Data Engineering, 2009
- Monochromatic and bichromatic reverse skyline search over uncertain databasesPublished by Association for Computing Machinery (ACM) ,2008
- MOOLAP: Towards Multi-Objective OLAPPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Selecting Stars: The k Most Representative Skyline OperatorPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Refreshing the skyPublished by Association for Computing Machinery (ACM) ,2006
- Skyline with presortingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Shooting Stars in the SkyPublished by Elsevier BV ,2002
- On Finding the Maxima of a Set of VectorsJournal of the ACM, 1975