The Acquisition Complexity of Exact Ordered Top-k Retrieval

Certifying an exact top-k answer is a shared-cost acquisition problem: the cheapest information for each comparison need not give the cheapest certificate. We formulate this problem for realized instances and solve it by separating ordered-answer constraints from shared physical reads. A winner path and an exclusion star reduce the logical constraints to a small conditioning interface. For point actions, this gives at most 2^(⌈k/2⌉) evaluations of any nonnegative monotone cost oracle, with a matching deterministic black-box dependence up to one call. For independent refinement and point files, each completion is a global minimum cut. Cost-preserving domain reduction sharpens the search to the minimum retained-domain product Ω over a residual comparison cover, with 2^τ ≤ Ω ≤ 3^τ. Three arbitrary-owner paid files already make top-1 verification hard, whereas coordinated layouts restore exact allocation structure. On eight SciFact instances, residual conditioning recovers every exact optimum in 13 cuts, and shared costs reverse 39 standalone precision preferences. The optimum identifies a 24.05% modeled acquisition gap in the executed cascade, with only 0.69% remaining after counterfactual consolidation and redundant-action removal. Matched execution studies independently demonstrate a 33.86% complete-CPU reduction from selective certificate work and a 39.09% source-byte reduction from jointly using fixed stored fields. The framework makes the acquisition plan an explicit optimization target and identifies where an exact retrieval system can gain from better information, acquisition scheduling or certificate computation.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-13
DOI
https://doi.org/10.5281/zenodo.24198965
Primary Topic
Advanced Database Systems and Queries
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The Acquisition Complexity of Exact Ordered Top-k Retrieval

Xu Cao, Wenxuan Xiao
Zenodo (CERN European Organization for Nuclear Research)
Advanced Database Systems and Queries
preprint

The Acquisition Complexity of Exact Ordered Top-k Retrieval

Xu Cao, Wenxuan Xiao
preprint en

Abstract

Certifying an exact top-k answer is a shared-cost acquisition problem: the cheapest information for each comparison need not give the cheapest certificate. We formulate this problem for realized instances and solve it by separating ordered-answer constraints from shared physical reads. A winner path and an exclusion star reduce the logical constraints to a small conditioning interface. For point actions, this gives at most 2^(⌈k/2⌉) evaluations of any nonnegative monotone cost oracle, with a matching deterministic black-box dependence up to one call. For independent refinement and point files, each completion is a global minimum cut. Cost-preserving domain reduction sharpens the search to the minimum retained-domain product Ω over a residual comparison cover, with 2^τ ≤ Ω ≤ 3^τ. Three arbitrary-owner paid files already make top-1 verification hard, whereas coordinated layouts restore exact allocation structure. On eight SciFact instances, residual conditioning recovers every exact optimum in 13 cuts, and shared costs reverse 39 standalone precision preferences. The optimum identifies a 24.05% modeled acquisition gap in the executed cascade, with only 0.69% remaining after counterfactual consolidation and redundant-action removal. Matched execution studies independently demonstrate a 33.86% complete-CPU reduction from selective certificate work and a 39.09% source-byte reduction from jointly using fixed stored fields. The framework makes the acquisition plan an explicit optimization target and identifies where an exact retrieval system can gain from better information, acquisition scheduling or certificate computation.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Database Systems and Queries
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon