Efficiently Processing Skyline Query on Multi-Instance Data
2
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
Related to the maximum vector problem, a skyline query is to discover dominating tuples from a set of tuples,where each defines an object (such as a hotel) in several dimensions (such as the price and the distance to thebeach). A tuple, an instance of an object, dominates another tuple if it is equally good or better in alldimensions and better in at least one dimension. Traditionally, skyline queries are defined upon singleinstancedata or upon objects each of which is associated with an instance. However, in some cases, an objectis not associated with a single instance but rather by multiple instances. For example, on a review website,many users assign scores to a product or a service, and a user’s score is an instance of the object representingthe product or the service. Such data is an example of multi-instance data. Unlike most (if not all) othersconsidering the traditional setting, we consider skyline queries defined upon multi-instance data. We definethe dominance calculation and propose an algorithm to reduce its computational cost. We use synthetic andreal data to evaluate the proposed methods, and the results demonstrate their utility.
Abstract
Related to the maximum vector problem, a skyline query is to discover dominating tuples from a set of tuples,where each defines an object (such as a hotel) in several dimensions (such as the price and the distance to thebeach). A tuple, an instance of an object, dominates another tuple if it is equally good or better in alldimensions and better in at least one dimension. Traditionally, skyline queries are defined upon singleinstancedata or upon objects each of which is associated with an instance. However, in some cases, an objectis not associated with a single instance but rather by multiple instances. For example, on a review website,many users assign scores to a product or a service, and a user’s score is an instance of the object representingthe product or the service. Such data is an example of multi-instance data. Unlike most (if not all) othersconsidering the traditional setting, we consider skyline queries defined upon multi-instance data. We definethe dominance calculation and propose an algorithm to reduce its computational cost. We use synthetic andreal data to evaluate the proposed methods, and the results demonstrate their utility.
참고문헌 (30)
- X. Liu, "U-skyline : a new skyline query for uncertain databases", IEEE Transactions on Knowledge and Data Engineering, 25(4), pp.945~960 (2013)
- S. Borzsony, "The skyline operator", Proceedings of the 17th International Conference on Data Engineering, pp.421~430 (2001)
- J. Chomicki, "Intelligent Information Processing and Web Mining", pp.595~604 (2005), Springer
- K. L. Tan, "Efficient progressive skyline computation", Proceedings of the 27th International Conference on Very Large Data Bases, pp.301~310 (2001)
- D. Papadias, "An optimal and progressive algorithm for skyline queries", Proceedings of ACM SIGMOD International Conference on Management of Data, pp.467~478 (2003)
- S. I. Chiu, "Skyline query processing for rating data", Proceedings of the Pacific Asia Conference on Information Systems, pp.305~ (2016)
- D. Papadias, "Progressive skyline computation in database systems", ACM Transactions on Database Systems, 30(1), pp.41~82 (2005)
- J. Chomicki, "Skyline with presorting", Proceedings of the 19th International Conference on Data Engineering, pp.717~719 (2003)
- P. Godfrey, "Maximal vector computation in large data sets", Proceedings of the 31st International Conference on Very Large Data Bases, pp.229~240 (2005)
- S. Zhang, "Scalable skyline computation using object-based space partitioning", Proceedings of ACM SIGMOD International Conference on Management of Data, pp.483~494 (2009)
- D. Kossmann, "Shooting stars in the sky: an online algorithm for skyline queries", Proceedings of the 28th International Conference on Very Large Data Bases, pp.275~286 (2002)
- I. Bartolini, "Efficient sort-based skyline evaluation", ACM Transactions on Database Systems, 33(4), pp.1~45 (2008)
- J. L. Bentley, "Fast linear expected-time algorithms for computing maxima and convex hulls", Algorithmica, 9(2), pp.168~183 (1993)
- H. T. Kung, "On finding the maxima of a set of vectors", Journal of the ACM, 22(4), pp.469~476 (1975)
- F. P. Preparata, "Computational Geometry", pp.1~35 (1985), Springer
- M. J. Atallah, "Computing all skyline probabilities for uncertain data", Proceedings of the 28th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp.279~287 (2009)
- J. Pei, "Probabilistic skylines on uncertain data", Proceedings of the 33rd International Conference on Very Large Data Bases, pp.15~26 (2007)
- B. Jiang, "Probabilistic skylines on uncertain data : model and boundingpruning-refining methods", Journal of Intelligent Information Systems, 38(1), pp.1~39 (2012)
- M. J. Atallah, "Asymptotically efficient algorithms for skyline probabilities of uncertain data", ACM Transactions on Database Systems (TODS), 36(2) (2011)
- Q. Zhang, "Skyline probability over uncertain preferences", Proceedings of the 16th International Conference on Extending Database Technology, pp.395~405 (2013)
- J. B. Rocha-Junior, "Efficient processing of top-k spatial preference queries", Proceedings of the 37th International Conference on Very Large Data Bases, pp.93~104 (2010)
- A. Cosgaya-Lozano, "Parallel computation of skyline queries", Proceedings of the 21st International Symposium on High Performance Computing Systems and Applications, pp.12~ (2007)
- P. Wu, "Parallelizing skyline queries for scalable distribution", Proceedings of the 10th International Conference on Extending Database Technology, pp.112~130 (2006)
- B. Cui, "Parallel distributed processing of constrained skyline queries by filtering", Proceedings of the IEEE 24th International Conference on Data Engineering, pp.546~555 (2008)
- H. Kohler, "Efficient parallel skyline processing using hyperplane projections", Proceedings of the ACM SIGMOD International Conference on Management of Data, pp.85~96 (2011)
- A. Vlachou, "Angle-based space partitioning for efficient parallel skyline computation", Proceedings of the ACM SIGMOD International Conference on Management of Data, pp.227~238 (2008)
- W. Bryc, "The Normal Distribution: Characterizations with Applications" (1995), Springer
- G. Casella, "Statistical Inference" (2001), Duxbury Press
- H. Wang, "Latent aspect rating analysis without aspect keyword supervision", Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.618~626 (2011)
- H. Wang, "Latent aspect rating analysis on review text data: a rating regression approach", Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.783~792 (2010)