Efficient Evaluation of Continuous Range Queries on Moving Objects.

Appeared in DEXA 2002 Conference.

Dmitri V. Kalashnikov, Sunil Prabhakar, Susanne Hambrusch, and Walid Aref

Department of Computer Sciences
Purdue University
PLACE project (http://www.cs.purdue.edu/place)


In this paper we evaluate several in-memory algorithms for efficient and scalable processing of continuous range queries over collections of moving objects. Constant updates to the index are avoided by query indexing. No constraints are imposed on the speed or path of moving objects. We present a detailed analysis of a grid approach which shows the best results for both skewed and uniform data. A sorting based optimization is developed for significantly improving the cache hit ratio. Experimental evaluation establishes that indexing queries using the Grid index yields orders of magnitude better performance than other index structures such as R*-trees.


Moving objects, query indexing, Q-indexing, continuous queries, long-running queries, monitoring queries, in-memory processing, main memory processing, continuous range queries, region queries, grid, location-aware computing, sensor databases, cache conscious algorithms

Downloadable files:

Paper: DEXA02_dvk.ext.pdf (extended version)
Thesis, Chapter 3 (more detailed)
Source code: DEXA02_dvk.src.zip
See also a disk-based solution to the same problem.

BibTeX entry:

   author    = {Dmitri V. Kalashnikov and Sunil Prabhakar and 
                Susanne Hambrusch and Walid Aref},
   title     = {Efficient Evaluation of Continuous Range Queries on Moving Objects},
   booktitle = {Proc. of Int'l Conf. on Database and Expert Systems 
                Applications (DEXA 2002)},
   year      = {2002},
   month     = {September 2--6},
   address   = {Aix en Provence, France}

Back to Kalashnikov's homepage