CONTINUOUS MULTIQUERIES K-DOMINANT SKYLINE ON ROAD NETWORK

Syukron Rifail Muttaqi, Bagus Jati Santoso

Abstract


The increasing use of mobile devices makes spatial data worthy of consideration. To get maximum results, users often look for the best from a collection of objects. Among the algorithms that can be used is the skyline query. The algorithm looks for all objects that are not dominated by other objects in all of its attributes. However, data that has many attributes makes the query output a lot of objects so it is less useful for the user. k-dominant skyline queries can be a solution to reduce the output. Among the challenges is the use of skyline queries with spatial data and the many user preferences in finding the best object. This study proposes IKSR: the k-dominant skyline query algorithm that works in a road network environment and can process many queries that have the same subspace in one processing. This algorithm combines queries that operate on the same subspace and set of objects with different k values by computing from the smallest to the largest k. Optimization occurs when some data for larger k are precomputed when calculating the result for the smallest k so the Voronoi cell computing is not repeated. Testing is done by comparing with the naïve algorithm without precomputation. IKSR algorithm can speed up computing time two to three times compared to naïve algorithm.


Full Text:

PDF

References


S. Borzsony, D. Kossmann, and K. Stocker, "The Skyline operator," in Proc. International Conference on Data Engineering, 2001.

H. T. Kung, F . Luccio, and F. Preparata, "On finding the maxima of a set of vectors," Journal of the ACM, vol. 22, no. 4, p. 469–76, 1975.

B. Xu, J. Feng, and J. Lu, "Continuous Skyline Queries for Moving Objects in Road Network based on MSO," in Proc. International Conference on Ubiquitous Information Management and Communication, 2018.

Y.-K. Huang, C.-H. Chang, and C. Lee, "Continuous distance-based skyline queries in road networks," Information Systems, vol. 37, 2012.

X. Fu, X. Miao, J. Xu, and Y. Gao, "Continuous range-based skyline queries in road networks," World Wide Web, vol. 20, no. 6, pp. 1443-1467, 2017.

C.-Y. Chan, H. V. Jagadish, K.-L. Tan, A. K. H. Tung, and Z. Zhang, "Finding k-dominant skylines in high dimensional space," in Proc. ACM SIGMOD international conference on Management of data, 2006.

M. Kontaki, A. N. Papadopoulos, and Y. Manolopoulos, "Continuous k-dominant skyline computation on multidimensional data streams," in Proc. ACM symposium on Applied computing, 2008.

A. Zaman, M. M. Islam, M. A. Siddique, and Y. Morimoto, "Distributed k-dominant skyline queries," in Proc. International Conference on Computer and Information Technology, 2012.

H. Tian, M. A. Siddique, and Y. Morimoto, "An Efficient Processing of k-Dominant Skyline Query in MapReduce," in Proc. International Workshop on Bringing the Value of "Big Data" to Users , 2014.

M. Erwig, "The graph Voronoi diagram with applications," Networks, vol. 36, pp. 156-163, 2000.

F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, and S.-H. Teng, "On Trip Planning Queries in Spatial Databases," in Proc. International Symposium on Spatial and Temporal Databases, 2005.




DOI: http://dx.doi.org/10.12962/j24068535.v18i2.a999

Refbacks

  • There are currently no refbacks.


Creative Commons License
JUTI (Jurnal Ilmiah Teknologi Informasi) by Department of Informatics, ITS is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. JUTI is accordance with CC BY-SA.