nucleation

LIT-1115: Optimal Aggregation Algorithms for Middleware

2 min read

Properties4
StatusActive — read in full 2026-10-15 from the authors' arXiv preprint (arXiv cs/0204046v1, arxiv.org/pdf/cs/0204046v1), which is the full version of which the PODS 2001 paper is the extended abstract; neither the PODS text nor the JCSS 2003 journal text was obtained (both returned 403), so the theorems read are the full version's and the preprint's Table 1, which halves the random-access term the theorems state, could not be checked against the journal. Worth reading as the source of the threshold algorithm's guarantee: for top-k retrieval under any monotone combining function from m lists each sorted by one attribute, TA is within m + m(m−1)c_R/c_S of every correct algorithm that makes no wild guesses, on every database, and that ratio is best possible when the function is strict (conjunction-like). For CLAIM-310 and THEORY-358 it shows that a query on one attribute costs about k accesses whatever the collection's size, while a conjunction whose distractors each carry one of the target's two features is the paper's own counterexample (Example 6.3, Theorem 6.4), costing about half the objects for any algorithm; Fagin's sublinear N^((m−1)/m)k^(1/m) holds only when the lists' orderings are independent, which Treisman's displays are built not to be. It says nothing about search times, the 1:2 present/absent ratio or whether vision reads sorted lists. For QUESTION-114 it prices querying a given set of single-attribute orders, with no build, upkeep or space cost.
Tagsdatabases, information-retrieval
Cited as “paper” byNOTE-924 — Fagin, Lotem & Naor — Optimal aggregation algorithms for middleware
Cited as “source” byTHEORY-361 — When every object but one has full grade in exactly one of two attribute-sorted lists and the one has full grade in both, finding it under min takes at least about half the objects' worth of accesses for any algorithm that only reads the lists from the top and looks up objects already seen, and, with the tied objects in random order, about as many in expectation even for algorithms that may look up any object; a query on one attribute alone costs k accesses whatever the number of objects, THEORY-363 — For finding the top k objects under a monotone combining function from m lists each sorted by one attribute, with sorted and random accesses the only costs, the threshold algorithm is correct and on every database costs at most a constant times what any correct algorithm that makes no wild guesses costs; the constant is m + m(m−1)c_R/c_S, no deterministic algorithm does better when the function is strict, and once wild guesses are allowed no algorithm has such a guarantee on databases with ties, THEORY-379 — Fagin's Algorithm finds the top k of N objects held in m attribute-sorted lists under any monotone combining function, and when the lists' orderings are independent with at least m − 1 of them uniformly random it does so with O(N^((m−1)/m) k^(1/m)) sorted and random accesses with arbitrarily high probability; with dependent orderings the bound can fail, THEORY-832 — For strict combining functions and m attribute-sorted lists of N objects whose orderings are probabilistically independent, no correct top-k algorithm does essentially better than Fagin's Algorithm in the worst case with high probability: every one needs on the order of N^((m−1)/m) k^(1/m) accesses

Graph View

Fagin, R., Lotem, A. and Naor, M. (2001). Optimal aggregation algorithms for middleware. In Proc. PODS 2001, pp. 102–113. DOI 10.1145/375551.375567. Journal version: Journal of Computer and System Sciences 66(4), 614–656 (2003), DOI 10.1016/S0022-0000(03)00026-6

Key takeaways

Read in full (NOTE-924). Given m lists of the same N objects, each sorted by one attribute’s grade, and a monotone function combining the grades, the threshold algorithm (TA) reads the lists in parallel, random-accesses each newly seen object’s other grades, and stops once k seen objects score at least the combined score of the last grades read. It is correct for every monotone combining function, needs constant buffers, and is instance optimal among correct algorithms that make no “wild guesses”: on every database its cost is within a constant factor of any such algorithm’s, the factor being m + m(m−1)c_R/c_S, which is best possible when the combining function is strict (conjunction-like). Without the no-wild-guesses restriction no algorithm is instance optimal, and the counterexample is a two-list conjunction whose target sits in the middle of both lists, which any algorithm must search linearly. Fagin’s Algorithm’s sublinear cost O(N^((m−1)/m) k^(1/m)) is cited from Fagin, not proved here, and holds only when the lists’ orderings are probabilistically independent. The model prices queries over a given set of single-attribute sorted lists. It does not price building or keeping the lists, choosing an arrangement, or any computation beyond accesses.

Why this is here

CLAIM-310 and THEORY-358 (Treisman and Gelade): the Threshold Algorithm finds the best objects under a monotone combined score from lists each sorted by one feature, and is instance-optimal against algorithms that make no wild guesses. A conjunctive query’s cost depends on how the features co-occur, from about k accesses to about half the collection when they are anti-correlated, as in Treisman’s conjunction displays. Read from the authors’ full version.

Backlinks