On range query indexing for efficient stream processing

To monitor a large number of continual range queries against a rapid data stream, each incoming data item should only be evaluated against relevant queries, not all the queries. Generally speaking, a main memory-based query index with a small storage cost and a fast search time is needed. In this paper, we study a 2D range query index that meets both criteria. It centers around a set of predefined, containment-encoded squares, or CES's. CES's are multi-layered, virtual constructs used to decompose range queries and maintain the query index. With containment-encoding, the search process is extremely efficient; most of the operations can be carried out by a simple logical-shift instruction. Simulations show that, with a small index storage cost, the CES-based query index substantially outperforms other alternatives in search time. © 2006 IEEE.