Continuous K-Nearest Neighbor Processing Based on Speed and Direction of Moving Objects in a Road Network

Area of Science:

• Database Systems
• Spatial Databases
• Computational Geometry

Background:

• Continuous K-Nearest Neighbor (CKNN) queries are crucial for analyzing moving objects in dynamic road networks.
• Frequent object movement and location updates pose significant challenges for accurate and efficient CKNN query processing.
• Existing methods struggle with the complexity introduced by arbitrary object trajectories.

Purpose of the Study:

• To develop a novel approach for processing Continuous K-Nearest Neighbor (CKNN) queries on moving objects in road networks.
• To address the challenges of frequent location updates and arbitrary object movements.
• To improve the accuracy and efficiency of CKNN query processing.

Main Methods:

• A Moving State of Object (MSO) model is proposed to characterize the relative movement between objects and the query point.
• A novel Object Candidate Processing (OCP) algorithm is introduced, featuring pruning and refining phases.
• The pruning phase excludes objects that cannot be K-Nearest Neighbors (KNNs) within the time interval.
• The refining phase determines specific time subintervals for definitive KNN results.

Main Results:

• The proposed MSO model effectively captures object-query point relative motion.
• The OCP algorithm significantly reduces repetitive query costs through effective pruning and refining.
• Experimental results demonstrate the effectiveness and efficiency of the proposed methods.

Conclusions:

• The MSO model and OCP algorithm provide an accurate and efficient solution for CKNN queries in road networks.
• The approach successfully handles the complexities of moving objects and dynamic environments.
• This research contributes to advancing spatial database query processing for moving objects.