Indexing continual range queries for location-aware mobile services

Abstract

We study a new main memory-based approach to indexing continual range queries to support location-aware mobile services. The query index is used to efficiently answer the following question repeatedly: "Which moving objects are currently located inside the boundaries of individual queries? " We present a covering tile-based (COVET) query index, where adjacent covering tiles touch each other only at the edges. 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 covering tiles and queries. It allows query evaluation to take advantage of incremental changes in object locations. Simulations are conducted to evaluate the effectiveness of the COVET index and compare virtual tiles of different shapes and sizes.