The Onion technique: Indexing for linear optimization queries

This paper describes the Onion technique, a special indexing structure for linear optimization queries. Linear optimization queries ask for top-N reco rds subject to the maximization or minimization of linearly weighted sum of record attribute values. Such query appears in many applications employing linear models and is an effective way to summarize representative cases, s uch as the top-50 ranked colleges. The Onion indexing is based on a geometr ic property of curves hull, which guarantees that the optimal value can alw ays be found at one or more of its vertices. The Onion indexing makes use o f this property to construct convex hulls in layers with outer layers enclo sing inner layers geometrically. A data record is indexed by its layer numb er or equivalently its depth in the layered convex hull. Queries with linea r weightings issued at run time are evaluated from the outmost layer inward s. We show experimentally that the Onion indexing achieves orders of magnit ude speedup against sequential linear scan when N is small compared to the cardinality of the set. The Onion technique also enables progressive retrie val, which processes and returns ranked results in a progressive manner. Fu rthermore, the proposed indexing can be extended into a hierarchical organi zation of data to accommodate both global and local queries.