Main Memory Evaluation of Monitoring Queries Over Moving Objects. Appeared in Distributed and Parallel Databases, An International Journal, vol. 15(2), Mar 2004. Dmitri V. Kalashnikov, Sunil Prabhakar, and Susanne E. Hambrusch 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 or fraction of objects that move at any moment in time. 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-rate. 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 index, location-aware computing, sensor databases, cache conscious algorithms Downloadable files: Paper: DAPD04_dvk.pdf Thesis, Chapter 3 (more detailed) Source code: DAPD04_dvk.src.zip See also a disk-based solution to the same problem. BibTeX entry: @article{DAPD04::dvk, author = {Dmitri V. Kalashnikov and Sunil Prabhakar and Susanne Hambrusch}, title = {Main memory evaluation of monitoring queries over moving objects}, journal = {Distributed and Parallel Databases, An International Journal}, volume = 15, number = 2, pages = {117--135}, month = mar, year = 2004 } Back to Kalashnikov's homepage