SEA-CNN: Scalable processing of continuous K-nearest neighbor queries in spatio-temporal databases

Xiaopeng Xiong, Mohamed F. Mokbel, Walid G. Aref

Research output: Chapter in Book/Report/Conference proceedingConference contribution

241 Scopus citations

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 SEACNN 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.

Original languageEnglish (US)
Title of host publicationProceedings - 21st International Conference on Data Engineering, ICDE 2005
Pages643-654
Number of pages12
DOIs
StatePublished - Dec 12 2005
Event21st International Conference on Data Engineering, ICDE 2005 - Tokyo, Japan
Duration: Apr 5 2005Apr 8 2005

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627

Other

Other21st International Conference on Data Engineering, ICDE 2005
CountryJapan
CityTokyo
Period4/5/054/8/05

Fingerprint Dive into the research topics of 'SEA-CNN: Scalable processing of continuous K-nearest neighbor queries in spatio-temporal databases'. Together they form a unique fingerprint.

Cite this