Range query methods and apparatus

摘要

Range query techniques are disclosed for use in accordance with data stream processing systems. A technique is provided for incrementally processing continual range queries against moving objects. This technique is applicable for location-aware services and applications. A technique for evaluating one or more continual range queries over one or more moving objects comprises maintaining a query index with one or more containment-encoded virtual constructs associated with the one or more continual range queries over the one or more moving objects, and incrementally evaluating the one or more continual range queries using the query index.

主权项

1. A computer-implemented method of evaluating one or more continual range queries over one or more moving objects, comprising the steps of:
maintaining a range query index with one or more containment-encoded virtual constructs associated with the one or more continual range queries over the one or more moving objects; and incrementally evaluating the one or more continual range queries using the range query index; wherein the range query index comprises a decomposition of at least one range query into a minimal number of containment-encoded squares of varying sizes; wherein the step of incrementally evaluating the one or more continual range queries further comprises: identifying the largest containment-encoded square covering previous locations of one or more objects resulting from evaluation of the one or more continual range queries; identifying the largest containment-encoded square covering current locations of the one or more objects; and based on the previous locations and the current locations of the one or more objects, refraining from performing one or more computations for object locations that are within same containment-encoded square boundaries; and determining a current location of a given one of the one or more moving objects relative to a previous location of the given moving object, wherein the steps are performed by a computer system.