1. A computer implemented method for indexing a data stream having attribute values, comprising: parsing the data stream; 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, the index being formed to have a plurality of layers of convex hulls; and 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.