Indexing for linear model-based information retrieval

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 maximisation or minimization of a linearly weighted sum of record attribute values. Such a query appears in many applications employing linear models and is an effective way of summarising representative cases, such as the top-50 ranked colleges. Onion indexing is based on a geometric property of a convex hull, which guarantees that the optimal value can always be found at one or more of its vertices. 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 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