Indexing continual range queries with covering tiles for fast locating of moving objects

Abstract

We present a COVEering Tile-based (COVET) query index for fast locating of moving objects. A set of virtual tiles are predefined, each with a unique ID. One or more of the virtual tiles are used to strictly cover individual range queries. A COVET index maintains a direct mapping between tiles and queries. The use of covering tiles has two important properties. First, it makes the search of all range queries containing an object efficient. Second, more importantly, it allows query evaluation to take advantage of incremental changes in object locations. Simulations are conducted to evaluate the effectiveness of the COVET index.