Call for Paper - May 2015 Edition
IJCA solicits original research papers for the May 2015 Edition. Last date of manuscript submission is April 20, 2015. Read More
An Algorithm for Retrieving Skyline Points based on User Specified Constraints using the Skyline Ordering
International Journal of Computer Applications
© 2014 by IJCA Journal
Volume 104 - Number 11
Year of Publication: 2014
|
10.5120/18248-9320 |
Jasna S and Manu J Pillai. Article: An Algorithm for Retrieving Skyline Points based on User Specified Constraints using the Skyline Ordering. International Journal of Computer Applications 104(11):24-29, October 2014. Full text available. BibTeX
@article{key:article,
author = {Jasna S and Manu J Pillai},
title = {Article: An Algorithm for Retrieving Skyline Points based on User Specified Constraints using the Skyline Ordering},
journal = {International Journal of Computer Applications},
year = {2014},
volume = {104},
number = {11},
pages = {24-29},
month = {October},
note = {Full text available}
}
Abstract
Given a multidimensional data set, a skyline query returns the interesting points that are not dominated by other points. The actual cardinality (s) of a skyline query result may vary substantially from the desired result cardinality (k). An approach called skyline ordering is used that forms a skyline based partitioning of a given data set, it provides an ordering among the partitions. The constrained skyline query results the skyline points that may be too small in some cases. The paper proposes a new method for finding the arbitrary number of points for the constrained skyline query. The skyline ordering algorithm and size constrained skyline ordering algorithm are used for developing the algorithm. The results of experiments of algorithm show that the proposed scheme yields an efficient and scalable resolution of arbitrary size constraints on constrained skyline queries. By comparing the existing and proposed system, the proposed system is efficient in returning the arbitrary number of skyline points.
References
- J. L. Bentley, K. L. Clarkson, and D. B. Levine, "Fast Linear Expected-Time Algorithms for Computing Maxima and Convex Hulls," Proc. First Ann. ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 179-187, 1990.
- I. Bartolini, P. Ciaccia, and M. Patella, "Efficient Sort-Based Skyline Evaluation," ACM Trans. Database Systems, vol. 33, no. 4, pp. 1-49, 2008.
- 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," J. ACM, vol. 25, no. 4, pp. 536-543, 1978.
- H. Blunck and J. Vahrenhold, "In-Place Algorithms for Computing (Layers of) Maxima," Proc. Scandinavian Workshop Algorithm Theory (SWAT), pp. 363-374, 2006.
- S. Borzonyi, D. Kossmann, and K. Stocker, "The Skyline Operator," Proc. Int'l Conf. Data Eng. (ICDE), pp. 421-430, 2001.
- C. -Y. Chan, H. Jagadish, K. -L. Tan, A. K. Tung, and Z. Zhang, "Finding K-Dominant Skylines in High Dimensional Space," Proc. ACM SIGMOD, pp. 503-514, 2006.
- C. -Y. Chan, H. Jagadish, K. -L. Tan, A. K. Tung, and Z. Zhang, "On High Dimensional Skylines," Proc. Int'l Conf. Extending Database Technology (EDBT), pp. 478-495, 2006.
- Y. -C. Chang, L. Bergman, V. Castelli, C. -S. Li, M. -L. Lo, and J. R. Smith, "The Onion Technique: Indexing for Linear Optimization Queries," Proc. ACM SIGMOD, pp. 391-402, 2000.
- J. Chomicki, "Preference Formulas in Relational Queries," ACM Trans. Database Systems, vol. 28, no. 4, pp. 427-466, 2003.
- J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, "Skyline with Presorting," Proc. Int'l Conf. Data Eng. (ICDE), pp. 717-719, 2003.
- B. Cui, H. Lu, Q. Xu, L. Chen, Y. Dai, and Y. Zhou, "Parallel Distributed Processing of Constrained Skyline Queries by Filtering," Proc. Int'l Conf. Data Eng. (ICDE), pp. 546-555, 2008.
- P. Godfrey, R. Shipley, and J. Gryz, "Maximal Vector Computation in Large Data Sets," Proc. Int'l Conf. Very Large Data Bases (VLDB), pp. 229-240, 2005.
- G. Hjaltason and H. Samet, "Distance Browsing in Spatial Database," ACM Trans. Database Systems, vol. 24, no. 2, pp. 265- 318, 1999.
- Z. Huang, C. S. Jensen, H. Lu, and B. C. Ooi, "Skyline Queries against Mobile Lightweight Devices in MANETs," Proc. Int'l Conf. Data Eng. (ICDE), p. 66, 2006.
- W. Jin, M. Ester, and J. Han, "Efficient Processing of Ranked Queries with Sweeping Selection," Proc. European Conf. Principles and Practice of Knowledge Discovery in Databases (PKDD), pp. 527- 535, 2005.
- W. Jin, J. Han, and M. Ester, "Mining Thick Skylines over Large Databases," Proc. European Conf. Principles and Practice of Knowledge Discovery in Databases (PKDD), pp. 255-266, 2004.
- V. Koltun and C. H. Papadimitriou, "Approximately Dominating Representatives," Proc. Int'l Conf. Data Theory (ICDT), pp. 204-214, 2005.
- D. Kossmann, F. Ramsak, and S. Rost, "Shooting Stars in the Sky: An Online Algorithm for Skyline Queries," Proc. Int'l Conf. Very Large Data Bases (VLDB), pp. 275-286, 2002.
- H. T. Kung, F. Luccio, and F. P. Preparata, "On Finding the Maxima of a Set of Vectors," J. ACM, vol. 22, no. 4, pp. 469-476, 1975.
- P. Larson and H. Z. Yang, "Computing Queries from Derived Relations," Proc. Int'l Conf. Very Large Data Bases (VLDB), pp. 259- 269, 1985.
- X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang, "Selecting Stars: The k Most Representative Skyline Operator," Proc. Int'l Conf. Data Eng. (ICDE), pp. 86-95, 2007.
- D. Papadias, Y. Tao, G. Fu, and B. Seeger, "An Optimal and Progressive Algorithm for Skyline Queries," Proc. SIGMOD, pp. 467-478, 2003.
- D. Papadias, Y. Tao, G. Fu, and B. Seeger, "Progressive Skyline Computation in Database Systems," ACM Trans. Database Systems, vol. 30, no. 1, pp. 41-82, 2005.
- Y. Tao, L. Ding, X. Lin, and J. Pei, "Distance-Based Representative Skyline," Proc. Int'l Conf. Data Eng. (ICDE), pp. 892-903, 2009.
- K. L. Tan, P. K. Eng, and B. C. Ooi, "Efficient Progressive Skyline Computation," Proc. Int'l Conf. Very Large Data Bases (VLDB), pp. 301-310, 2001.
- A. Vlachou, C. Doulkeridis, K. Nørva°g, and M. Vazirgiannis, "Skyline-Based Peer-To-Peer Top-k Query Processing," Proc. Int'l Conf. Data Eng. (ICDE), pp. 1421-1423, 2008.
- T. Xia, D. Zhang, and Y. Tao, "On Skylining with Flexible Dominance Relation," Proc. Int'l Conf. Data Eng. (ICDE), pp. 1397- 1399, 2008.
- M. L. Yiu and N. Mamoulis, "Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data," Proc. Int'l Conf. Very Large Data Bases (VLDB), pp. 483-494, 2007.
- Z. Zhang, X. Guo, H. Lu, A. K. Tung, and N. Wang, "Discovering Strong Skyline Points in High Dimensional Spaces," Proc. ACM Int'l Conf. Information and Knowledge Management (CIKM), pp. 247- 248, 2005.
- S. Zhang, N. Mamoulis, and D. W. Cheung, "Scalable Skyline Computation Using Object-Based Space Partitioning," Proc. SIGMOD, pp. 483-494, 2009.
- Hua Lu, Christian S. Jensen, Zhenjie Zhang. "Flexible and Efficient Resolution of Skyline Query Size Constraints. " IEEE Transactions on Knowledge and Data Engineering (TKDE). 23(7): 991. 1005, 2011.