CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

An Algorithm for Retrieving Skyline Points based on User Specified Constraints using the Skyline Ordering

by Jasna S, Manu J Pillai
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 104 - Number 11
Year of Publication: 2014
Authors: Jasna S, Manu J Pillai
10.5120/18248-9320

Jasna S, Manu J Pillai . An Algorithm for Retrieving Skyline Points based on User Specified Constraints using the Skyline Ordering. International Journal of Computer Applications. 104, 11 ( October 2014), 24-29. DOI=10.5120/18248-9320

@article{ 10.5120/18248-9320,
author = { Jasna S, Manu J Pillai },
title = { An Algorithm for Retrieving Skyline Points based on User Specified Constraints using the Skyline Ordering },
journal = { International Journal of Computer Applications },
issue_date = { October 2014 },
volume = { 104 },
number = { 11 },
month = { October },
year = { 2014 },
issn = { 0975-8887 },
pages = { 24-29 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume104/number11/18248-9320/ },
doi = { 10.5120/18248-9320 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:35:54.772630+05:30
%A Jasna S
%A Manu J Pillai
%T An Algorithm for Retrieving Skyline Points based on User Specified Constraints using the Skyline Ordering
%J International Journal of Computer Applications
%@ 0975-8887
%V 104
%N 11
%P 24-29
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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.
  2. I. Bartolini, P. Ciaccia, and M. Patella, "Efficient Sort-Based Skyline Evaluation," ACM Trans. Database Systems, vol. 33, no. 4, pp. 1-49, 2008.
  3. 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.
  4. H. Blunck and J. Vahrenhold, "In-Place Algorithms for Computing (Layers of) Maxima," Proc. Scandinavian Workshop Algorithm Theory (SWAT), pp. 363-374, 2006.
  5. S. Borzonyi, D. Kossmann, and K. Stocker, "The Skyline Operator," Proc. Int'l Conf. Data Eng. (ICDE), pp. 421-430, 2001.
  6. 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.
  7. 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.
  8. 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.
  9. J. Chomicki, "Preference Formulas in Relational Queries," ACM Trans. Database Systems, vol. 28, no. 4, pp. 427-466, 2003.
  10. J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, "Skyline with Presorting," Proc. Int'l Conf. Data Eng. (ICDE), pp. 717-719, 2003.
  11. 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.
  12. 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.
  13. G. Hjaltason and H. Samet, "Distance Browsing in Spatial Database," ACM Trans. Database Systems, vol. 24, no. 2, pp. 265- 318, 1999.
  14. 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.
  15. 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.
  16. 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.
  17. V. Koltun and C. H. Papadimitriou, "Approximately Dominating Representatives," Proc. Int'l Conf. Data Theory (ICDT), pp. 204-214, 2005.
  18. 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.
  19. 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.
  20. P. Larson and H. Z. Yang, "Computing Queries from Derived Relations," Proc. Int'l Conf. Very Large Data Bases (VLDB), pp. 259- 269, 1985.
  21. 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.
  22. D. Papadias, Y. Tao, G. Fu, and B. Seeger, "An Optimal and Progressive Algorithm for Skyline Queries," Proc. SIGMOD, pp. 467-478, 2003.
  23. 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.
  24. Y. Tao, L. Ding, X. Lin, and J. Pei, "Distance-Based Representative Skyline," Proc. Int'l Conf. Data Eng. (ICDE), pp. 892-903, 2009.
  25. 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.
  26. 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.
  27. T. Xia, D. Zhang, and Y. Tao, "On Skylining with Flexible Dominance Relation," Proc. Int'l Conf. Data Eng. (ICDE), pp. 1397- 1399, 2008.
  28. 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.
  29. 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.
  30. S. Zhang, N. Mamoulis, and D. W. Cheung, "Scalable Skyline Computation Using Object-Based Space Partitioning," Proc. SIGMOD, pp. 483-494, 2009.
  31. 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.
Index Terms

Computer Science
Information Sciences

Keywords

Constrained Skyline Query Skyline Queries Skyline Order

Powered by PhDFocusTM