VCR indexing for fast event matching for highly-overlapping range predicates

Abstract

Fast matching of events against a large number of range predicates is important for many applications. We present a novel VCR indexing scheme for highly-overlapping 2D range predicates. VCR stands for virtual construct rectangle. Each predicate is decomposed into one or more VCRs, which are then considered to be activated. The predicate ID is then stored in the ID lists associated with these activated VCRs. Event matching is conceptually simple. For each event point, the search result is stored in the ID lists associated with the activated VCRs that cover the event point. However, it is computationally nontrivial to identify the activated covering VCRs. We define a covering VCR set for each event point and present an algorithm for fast event matching. Simulations are conducted to study the performance of VCR indexing.