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) Abstract 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. Keywords: 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: @inproceedings{DEXA02::dvk, 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