Optimization of Spatio Temporal Aggregate Queries using Semantic Load shedding and Shared Cluster Based Execution
Optimization of Spatio Temporal Aggregate Queries using Semantic Load shedding and Shared Cluster Based Execution |
||
 |
 |
|
| © 2023 by IJETT Journal | ||
| Volume-71 Issue-6 |
||
| Year of Publication : 2023 | ||
| Author : Nishad A, K P Noufal, Rajesh N, Deepa Mary Mathews |
||
| DOI : 10.14445/22315381/IJETT-V71I6P218 | ||
How to Cite?
Nishad A, K P Noufal, Rajesh N, Deepa Mary Mathews, "Optimization of Spatio Temporal Aggregate Queries using Semantic Load shedding and Shared Cluster Based Execution," International Journal of Engineering Trends and Technology, vol. 71, no. 6, pp. 152-168, 2023. Crossref, https://doi.org/10.14445/22315381/IJETT-V71I6P218
Abstract
The problem of moving object data modelling secured a great deal of attention due to the wide acceptance of context-based computing frameworks and related applications. This digital revolution has geared momentum in spatio-temporal data mining and continuous query processing research. Efficient approaches in representation, storage, processing and querying of spatio-temporal trajectory are the need of time for providing cost-effective solutions to many problems, especially in transportation systems. The mobility data requires additional considerations in storage and processing due to its dynamic nature. Besides the explicit geographical and temporal data, the trajectory of a moving object contains crucial information about the object's movement and behavior. These semantic features are the factors that connect the meaning and objective of the move. The findings arrived at based on explicit data can give better insights into the moving entity. Aggregation is another effective approach to make use of in this scenario in order to get the collective behaviour of moving objects or the region of travel. In this paper, we propose methods for the convenient representation and effective processing of moving entities. The moving object aggregate queries are grouped into two classes static spatiotemporal aggregate query and continuous spatiotemporal aggregate query. Here, we utilize the semantic-based load shedding over the moving object clusters to reduce the computational overhead. Shared cluster-based execution is incorporated for the effective computation of moving object aggregate queries. Different data structures for representing moving object clusters are also introduced in this paper. Various evaluations are provided to showcase the effectiveness of the approach.
Keywords
Data load shedding, Moving object queries, Semantic processing, Spatio temporal knowledge data extraction, Trajectory processing.
References
[1] A. Nishad, and Sajimon Abraham, “Contact Tracing and Mobility Pattern Detection during Pandemics – A Trajectory Cluster Based Approach,” International Journal of Pervasive Computing and Communications, 2022.
[CrossRef] [Google Scholar] [Publisher Link]
[2] Yufei Tao, and Dimitris Papadiass, “Historical Spatio-Temporal Aggregation,” ACM Transactions on Information Systems (TOIS), vol. 23, no. 1, pp. 61–102, 2005.
[CrossRef] [Google Scholar] [Publisher Link]
[3] Christian S. Jensen, Dan Lin, and Beng Chin Ooi, “Continuous Clustering of Moving Objects,” IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 9, pp. 1161–1174, 2007.
[CrossRef] [Google Scholar] [Publisher Link]
[4] Rimma V. Nehme, and Elke A. Rundensteiner, “SCUBA: Scalable Cluster-Based Algorithm for Evaluating Continuous Spatio-temporal Queries on Moving Objects,” in Advances in Database Technology - EDBT 2006, Y. Ioannidis, M. H. Scholl, J. W. Schmidt, F. Matthes, M. Hatzopoulos, K. Boehm, A. Kemper, T. Grust, and C. Boehm, Eds., in Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, pp. 1001–1019, 2006.
[CrossRef] [Google Scholar] [Publisher Link]
[5] A. Nishad, and Sajimon Abraham, “SemTraClus: an algorithm for clustering and prioritizing semantic regions of spatio-temporal trajectories,” International Journal of Computers and Applications, vol. 43, no. 8, pp. 841–850, 2021.
[CrossRef] [Google Scholar] [Publisher Link]
[6] Yousuke Watanabe, and Hiroyuki Kitagawa, “A Multiple Continuous Query Optimization Method Based on Query Execution Pattern Analysis,” Database Systems for Advanced Applications, Y. Lee, J. Li, K.-Y. Whang, and D. Lee, Eds., in Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, pp. 443–456, 2004.
[CrossRef] [Google Scholar] [Publisher Link]
[7] Medhane Darshan Vishwasrao, and Arun Kumar Sangaiah, “ESCAPE: Effective Scalable Clustering Approach for Parallel Execution of Continuous Position-Based Queries in Position Monitoring Applications,” IEEE Transactions on Sustainable Computing, vol. 2, no. 2, pp. 49–61, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[8] Pingfu Chao et al., “Efficient Trajectory Contact Query Processing,” Database Systems for Advanced Applications, C. S. Jensen, E.-P. Lim, D.-N. Yang, W.-C. Lee, V. S. Tseng, V. Kalogeraki, J.-W. Huang, and C.-Y. Shen, Eds., in Lecture Notes in Computer Science. Cham: Springer International Publishing, pp. 658–666, 2021.
[CrossRef] [Google Scholar] [Publisher Link]
[9] Joachim Gudmundsson, Patrick Laube, and Thomas Wolle, “Movement Patterns in Spatio-Temporal Data,” Encyclopedia of GIS, vol. 726, p. 732, 2008.
[Google Scholar] [Publisher Link]
[10] B. Babcock, M. Datar, and R. Motwani, “Load Shedding for Aggregation Queries Over Data Streams,” Proceedings 20th International Conference on Data Engineering, pp. 350–361, 2004.
[CrossRef] [Google Scholar] [Publisher Link]
[11] Zhang Longbo et al., “Semantic Load Shedding for Sliding Window Join-Aggregation Queries over Data Streams,” 2007 International Conference on Convergence Information Technology, pp. 2152-2155, 2007.
[CrossRef] [Google Scholar] [Publisher Link]
[12] Mario José Diván & María Laura Sánchez Reynoso, “A Load-Shedding Technique Based on the Measurement Project Definition,” Recent Trends in Intelligent Computing, Communication and Devices, pp. 1027-1033, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[13] E. N. Tatbul, “Load Shedding Techniques for Data Stream Management Systems,” Ph.D. Thesis, Providence, RI, USA. AAI3272068, 2007.
[CrossRef] [Google Scholar] [Publisher Link]
[14] J. Park and H. Cho, “Semantic Load Shedding for Prioritized Continuous Queries over Data Streams,” Computer and Information Sciences - ISCIS 2005, pInar Yolum, T. Güngör, F. Gürgen, and C. Özturan, Eds., in Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, pp. 813–822, 2005.
[CrossRef] [Google Scholar] [Publisher Link]
[15] Fethi Belghaouti et al., “Graph-Oriented Load-Shedding for Semantic Data Stream Processing,” 2015 International Workshop on Computational Intelligence for Multimedia Understanding, pp. 1-5, 2015.
[CrossRef] [Google Scholar] [Publisher Link]
[16] Xiaopeng Xiong et al., “Scalable Spatio-Temporal Continuous Query Processing for Location-Aware Services,” Proceedings 16th International Conference on Scientific and Statistical Database Management, pp. 317–326, 2004.
[CrossRef] [Google Scholar] [Publisher Link]
[17] X. Xiong, M. F. Mokbel, and W. G. Aref, “SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-Temporal Databases,” 21st International Conference on Data Engineering, pp. 643-654, 2005.
[CrossRef] [Google Scholar] [Publisher Link]
[18] Jianjun Chen et al., “Niagaracq: A Scalable Continuous Query System for Internet Databases,” Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, in SIGMOD ’00. New York, NY, USA: Association for Computing Machinery, pp. 379-390, 2000.
[CrossRef] [Google Scholar] [Publisher Link]
[19] Jidong Chen et al., “Clustering Moving Objects in Spatial Networks,” Advances in Databases: Concepts, Systems and Applications, R. Kotagiri, P. R. Krishna, M. Mohania, and E. Nantajeewarawat, Eds., in Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, pp. 611–623, 2007.
[CrossRef] [Google Scholar] [Publisher Link]
[20] Rimma V. Nehme, and Elke A. Rundensteiner, “ClusterSheddy: Load Shedding Using Moving Clusters over Spatio-temporal Data Streams,” Advances in Databases: Concepts, Systems and Applications, R. Kotagiri, P. R. Krishna, M. Mohania, and E. Nantajeewarawat, Eds., in Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, pp. 637–651, 2007.
[CrossRef] [Google Scholar] [Publisher Link]
[21] Zhenhui Li et al., “Incremental Clustering for Trajectories,” International Conference on Database Systems for Advanced Applications, Springer, pp. 32–46, 2010.
[CrossRef] [Google Scholar] [Publisher Link]
[22] Steven Young et al., “A Fast and Stable Incremental Clustering Algorithm,” 2010 Seventh International Conference on Information Technology: New Generations, pp. 204–209, 2010.
[CrossRef] [Google Scholar] [Publisher Link]
[23] Jianqiu Xu, Hua Lu, and Ralf Hartmut Güting, “Range Queries on Multi-Attribute Trajectories,” IEEE Transactions on Knowledge and Data Engineering, vol. 30, no. 6, pp. 1206–1211, 2018.
[CrossRef] [Google Scholar] [Publisher Link]
[24] M.S. Vinmathi, V. Sathiya, and M. Maheswari, "A Predictive-Reactive Procedure for Improving the Strength of Simultaneous Data Services," SSRG International Journal of Computer Science and Engineering, vol. 1, no. 10, pp. 1-5, 2014.
[CrossRef] [Publisher Link]
[25] Douglas Terry et al., “Continuous Queries Over Append-Only Databases,” ACM SIGMOD Record, vol. 21, no. 2, pp. 321–330, 1992.
[CrossRef] [Google Scholar] [Publisher Link]
[26] Dimitris Papadias, “Nearest Neighbor Query,” Encyclopedia of Database Systems, L. LIU and M. T. ÖZSU, Eds., Boston, MA: Springer US, p. 1890, 2009.
[CrossRef] [Publisher Link]
[27] Mohammad R. Kolahdouzan, and Cyrus Shahabi, “Alternative Solutions for Continuous K Nearest Neighbor Queries in Spatial Network Databases,” GeoInformatica, vol. 9, no. 4, pp. 321–341, 2005.
[CrossRef] [Google Scholar] [Publisher Link]
[28] Elke Achtert et al., “Efficient Reverse k-Nearest Neighbor Estimation,” Informatik - Forschung und Entwicklung, vol. 21, no. 3, pp. 179–195, 2007.
[CrossRef] [Google Scholar] [Publisher Link]
[29] Gabriel Kuper, Leonid Libkin, and Jan Paredaens, Constraint Databases, Springer Science & Business Media, 2013.
[Google Scholar] [Publisher Link]
[30] Martin Ester et al., “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise,” Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, pp. 226–231, 1996.
[Google Scholar] [Publisher Link]
[31] Luis Otavio Alvares et al., “A Model for Enriching Trajectories with Semantic Geographical Information,” Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems, 2007.
[CrossRef] [Google Scholar] [Publisher Link]
[32] Lucas Santos De Oliveira, Pedro O. S. Vaz-De-Melo, and Aline Carneiro Viana, “Assessing Large-Scale Power Relations among Locations from Mobility Data,” ACM Transactions on Knowledge Discovery from Data, vol. 16, no. 2, pp. 1-31, 2021.
[CrossRef] [Google Scholar] [Publisher Link]
[33] Li Wan et al., “Density-Based Clustering of Data Streams at Multiple Resolutions,” ACM Transactions on Knowledge Discovery from Data, vol. 3, no. 3, pp. 1-28, 2009.
[CrossRef] [Google Scholar] [Publisher Link]
[34] A. Nishad, and Sajimon Abraham, “A Method for Continuous Clustering and Querying of Moving Objects,” Advanced Informatics for Computing Research, A. K. Luhach, D. S. Jat, K. B. G. Hawari, X.-Z. Gao, and P. Lingras, Eds., in Communications in Computer and Information Science. Singapore: Springer, pp. 172–183, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[35] Aristides Gionis, Heikki Mannila, and Panayiotis Tsaparas, “Clustering Aggregation,” ACM Transactions on Knowledge Discovery from Data, vol. 1, no. 1, 2007.
[CrossRef] [Google Scholar] [Publisher Link]
[36] Christian Düntgen, Thomas Behr, and Ralf Hartmut Güting, “BerlinMOD: A Benchmark for Moving Object Databases,” The VLDB Journal, vol. 18, no. 6, pp. 1335-1368, 2009.
[CrossRef] [Google Scholar] [Publisher Link]
[37] Soheila Ghane, Lars Kulik, and Kotagiri Ramamoharao, “A Differentially Private Algorithm for Range Queries on Trajectories,” Knowledge and Information Systems, vol. 63, no. 2, pp. 277–303, 2021.
[CrossRef] [Google Scholar] [Publisher Link]