2026-07-23T20:16:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22951 2025-10-02T12:19:29Z ddc:004 open_access

Maximizing the Optimality Streak of Deferred Data Structuring (a.k.a. Database Cracking) Tao, Yufei Deferred Data Structuring Database Cracking Data Structures This paper studies how to minimize the total cost of answering r queries over n elements in an online manner (i.e., the next query is given only after the previous query’s result is ready) when the value r ≤ n is unknown in advance. Traditional indexing, which first builds a complete index on the n elements before answering queries, may be unsuitable because the index’s construction time - usually Ω(n log n) - can become the performance bottleneck. In contrast, for many problems, a lower bound of Ω(n log (1+r)) holds on the total cost of r queries for every r ∈ [1, n]. Matching this lower bound is a primary objective of deferred data structuring (DDS), also known as database cracking in the system community. For a wide class of problems, we present generic reductions to convert traditional indexes into DDS algorithms that match the lower bound for a long range of r. For a decomposable problem, if a data structure can be built in O(n log n) time and has Q(n) query search time, our reduction yields an algorithm that runs in O(n log (1+r)) time for all r ≤ (n log n)/(Q(n)), where the upper bound (n log n)/(Q(n)) is asymptotically the best possible under mild constraints. In particular, if Q(n) = O(log n), then the O(n log (1+r))-time guarantee extends to all r ≤ n, with which we optimally settle a large variety of DDS problems. Our results can be generalized to a class of "spectrum indexable problems", which subsumes the class of decomposable problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yufei Tao 2025 Is Part Of LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2025.10 urn:nbn:de:0030-drops-229512 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.10 eng https://creativecommons.org/licenses/by/4.0/legalcode