SEA-CNN: scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases

Get BibTex-formatted data

Download

PDF

Author

X Xiong, MF Mokbel, WG Aref

Entry type

article

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.

Download

PDF

Date

2005 – 04

Journal

Data Engineering, 2005. ICDE 2005. Proceedings. 21st International Conference on

Key alpha

Aref

Pages

643-654

Publication Date

2005-04-01

Keywords

mobile computing, query processing, temporal databases, tree data structures, visual databases SEA-CNN algorithm, continuous k-nearest neighbor queries, incremental evaluation, location-aware environment, scalable processing, shared execution, spatio-temporal databases

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Article{ Aref,
	title = " SEA-CNN: scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases",
	author = "X Xiong, MF Mokbel, WG Aref   ",
	year = "2005",
	month = "04",
	journal = "Data Engineering, 2005. ICDE 2005. Proceedings. 21st International Conference on",
	pages = "643-654",
	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.",
	keywords = "mobile computing, query processing, temporal databases, tree data structures, visual databases SEA-CNN algorithm, continuous k-nearest neighbor queries, incremental evaluation, location-aware environment, scalable processing, shared execution, spatio-temporal databases",
}