Monitoring Continual Range Queries

This paper provides an overview of a query indexing method, called VCR indexing, for monitoring continual range queries. A VCR based query index enables fast matching of events against a large number of range predicates. We first describe VCR indexing for general event matching against a set of 2D range predicates. We then show how VCR indexing can be used for efficient processing of continual range queries over moving objects. VCR stands for virtual construct rectangle. A set of VCRs are predefined, each with a unique ID. Each region defined by the range predicate is decomposed into or covered by one or more activated VCRs. The predicate ID is then stored in the ID lists associated with these activated VCRs. The use of VCRs provides an indirect and cost effective way of pre-computing the search result for any given event or object position. Event matching becomes very efficient.
DATE OF REPORT: 02/18/2004