Query Indexing and Velocity Constrained Indexing.

Appeared in Encyclopedia of GIS, Springer Science, 2008.


Sunil Prabhakar, Dmitri V. Kalashnikov, and Yuni Xia

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

Abstract

Moving object environments are characterized by large numbers of moving objects and numerous concurrent continuous queries over these objects. Efficient evaluation of these queries in response to the movement of the objects is critical for supporting acceptable response times. In such environments the traditional approach of building an index on the objects (data) suffers from the need for frequent updates and thereby results in poor performance. In fact, a brute force, no-index strategy yields better performance in many cases. Neither the traditional approach, nor the brute force strategy achieve reasonable query processing times. The efficient and scalable evaluation of multiple continuous queries on moving objects can be achieved by leveraging two complimentary techniques: Query Indexing and Velocity Constrained Indexing (VCI). Query Indexing relies on i) incremental evaluation; ii) reversing the role of queries and data; and iii) exploiting the relative locations of objects and queries. VCI takes advantage of the maximum possible speed of objects in order to delay the expensive operation of updating an index to reflect the movement of objects. In contrast to techniques that require exact knowledge about the movement of the objects, VCI does not rely on such information. While Query Indexing outperforms VCI, it does not efficiently handle the arrival of new queries. Velocity constrained indexing, on the other hand, is unaffected by changes in queries. A combination of Query Indexing and Velocity Constrained Indexing enables the scalable execution of insertion and deletion of queries in addition to processing ongoing queries.


Keywords:

Moving objects, query indexing, Q-index, velocity constrained indexing, VCI, continuous queries, long-running queries, monitoring queries, continuous range queries, location-aware computing


Downloadable files:

Paper: EncGIS08_dvk.pdf


BibTeX entry:

@incollection{GISEnc08::dvk,
  author     = {Sunil Prabhakar and Dmitri V. Kalashnikov and Yuni Xia},
  editor     = {Shashi Shekhar and Hui Xiong},
  title      = {Query Indexing and Velocity Constrained Indexing},
  booktitle  = {Encyclopedia of GIS},
  publisher  = {{Springer Science}},
  year       = 2008
}


Back to Kalashnikov's homepage