Social Science
A Distributed Hybrid Indexing for Continuous KNN Query Processing over Moving Objects
rnfinity
Imene Bareche
Imene Bareche
School of Computer Science and Technology, Chongqing University of Posts and Telecommunications,
Abstract
The magnitude of highly dynamic spatial data is expanding rapidly due to the instantaneous evolution of mobile technology, resulting in challenges for continuous queries. We propose a novel indexing approach model, namely, the Velocity SpatioTemporal indexing approach (VeST), for continuous queries, mainly Continuous K-nearest Neighbor (CKNN) and continuous range queries using Apache Spark. The proposed structure is based on a selective velocity partitioning method, i.e., since different objects have varying speeds, we divide the objects into two sets according to the actual mean speed we calculate before building the index and accessing data. Then the adopted indexing structure base unit comprises a nonoverlapping R-tree and a two dimension grid. The tree divides the space into nonoverlapping minimum bounding regions that point to the grids. Then, the uniform grid stores the object data of leaf nodes. This access method reduces the update cost and improves response time and query precision. In order to enhance performances for large-scale processing, we design a compact multilayer index structure on a distributed setting and propose a CKNN search algorithm for accurate results using a candidate cell identification process. We provide a comprehensive vision of our indexing model and the adopted query technique. The simulation results show that for query intervals of 100, the proposed approach is 13.59 times faster than the traditional approach, and the average time of the VeST approach is less than 0.005 for all query intervals. This proposed method improves response time and query precision. The precision of the VeST algorithm is almost equal to 100% regardless of the length of the query interval.
Key Questions
What problem does the study address in the context of moving objects?
The study addresses the challenge of efficiently processing k-nearest neighbors (KNN) queries for moving objects in dynamic environments, where the objects' positions continuously change over time.
What is the proposed solution for KNN query processing?
The solution involves a distributed hybrid indexing method that combines spatial and temporal components to efficiently handle continuous KNN queries over moving objects, ensuring scalability and faster response times.
How does the hybrid indexing method work?
The hybrid indexing technique optimizes both spatial and temporal information by dynamically updating the positions of moving objects in a distributed environment, ensuring quick retrieval of KNN results even as objects move.
What are the benefits of using a distributed approach?
The distributed approach ensures scalability, meaning the system can efficiently process a large number of KNN queries in real-time, handling large datasets without compromising performance.
What impact does the study’s approach have on real-world applications?
The proposed approach enhances real-world applications such as geographic information systems (GIS), location-based services, and autonomous vehicles, where real-time processing of dynamic data is critical for decision-making.
