The onion technique

TLDR

Linear optimization queries retrieve top‑N records by maximizing or minimizing a linear weighted sum of attributes, a common operation in many linear‑model applications such as ranking the top‑50 colleges. The paper introduces the Onion technique, a specialized indexing structure for linear optimization queries. The Onion indexing constructs layered convex hulls, using the convex‑hull property that optimal values lie at vertices, and indexes records by layer depth, enabling queries to be evaluated from the outermost layer inward and extendable to a hierarchical organization for global and local queries. Experiments show that the Onion technique yields orders‑of‑magnitude speedup over sequential scans for small N and supports progressive retrieval of ranked results.

Abstract

This paper describes the Onion technique, a special indexing structure for linear optimization queries. Linear optimization queries ask for top-N records 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, such as the top-50 ranked colleges. The Onion indexing is based on a geometric property of convex hull, which guarantees that the optimal value can always be found at one or more of its vertices. The Onion indexing makes use of this property to construct convex hulls in layers with outer layers enclosing inner layers geometrically. A data record is indexed by its layer number or equivalently its depth in the layered convex hull. Queries with linear weightings issued at run time are evaluated from the outmost layer inwards. We show experimentally that the Onion indexing achieves orders of magnitude speedup against sequential linear scan when N is small compared to the cardinality of the set. The Onion technique also enables progressive retrieval, which processes and returns ranked results in a progressive manner. Furthermore, the proposed indexing can be extended into a hierarchical organization of data to accommodate both global and local queries.