Patent ID: 7552099

Claim:
A method for indexing a data stream having attribute values, comprising: storing the data stream in a hardware memory device; parsing the data stream in the hardware memory device; forming a Stream Approximate Onion (SAO) index of tuples for a subset of attribute values of the data stream, the index being configured for retrieving top-K tuples that optimize linearly weighted sums of at least some of the attribute values in the subset; and configuring the index to track a subset of the top-K tuples in a sliding window applied to the data stream; wherein said forming step comprises forming the index to have a plurality of layers of convex hulls, and the method further comprises: maintaining in the index a number of the plurality of layers of convex hulls less than a number of convex hull layers maintained in an Onion index; storing the index in the hardware memory device or another hardware memory device; and providing a user-discernable output based on the index in response to an optimization query directed to the data stream, the user discernable output including the top-K tuples that optimize the linearly weighted sums of at least some of the attribute values in the subset with respect to the optimization query.