SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases

TLDR

Location‑aware environments contain many objects and continuous queries that both move over time. The study focuses on continuous k‑nearest neighbor queries (CKNN). SEA‑CNN is a new algorithm for continuously answering concurrent CKNN queries, featuring incremental evaluation, shared execution, no assumptions on object or query movement, and a theoretical analysis of its execution costs, memory usage, and tunable parameters. Experiments demonstrate that SEA‑CNN is highly scalable and outperforms other R‑tree‑based CKNN techniques in both I/O and CPU costs while maintaining efficiency for concurrent queries.

Abstract

Location-aware environments are characterized by a large number of objects and a large number of continuous queries. Both the objects and continuous queries may change their locations over time. In this paper, we focus on continuous k-nearest neighbor queries (CKNN, for short). We present a new algorithm, termed SEA-CNN, for answering continuously a collection of concurrent CKNN queries. SEA-CNN has two important features: incremental evaluation and shared execution. SEA-CNN achieves both efficiency and scalability in the presence of a set of concurrent queries. Furthermore, SEA-CNN does not make any assumptions about the movement of objects, e.g., the objects velocities and shapes of trajectories, or about the mutability of the objects and/or the queries, i.e., moving or stationary queries issued on moving or stationary objects. We provide theoretical analysis of SEA-CNN with respect to the execution costs, memory requirements and effects of tunable parameters. Comprehensive experimentation shows that SEA-CNN is highly scalable and is more efficient in terms of both I/O and CPU costs in comparison to other R-tree-based CKNN techniques.