Context
Five works were registered and read on 2026-10-15 for QUESTION-114, which asks whether sorting a collection is amortized search:
- Finkelstein, Schkolnick and Tiberio 1988 (LIT-1084), index selection;
- Yao 1981 (LIT-1097), lower bounds on lookup;
- Idreos, Kersten and Manegold 2007 (LIT-1090), database cracking;
- Sleator and Tarjan 1985 (LIT-1093), self-organizing lists and paging;
- Harinarayan, Rajaraman and Ullman 1996 (LIT-1094), which answers to precompute.
No topic fitted. They were tagged information-retrieval, whose blurb is
“finding what is relevant to a need — document and query representation,
relevance and aboutness, ranking and feedback”. That is a different
problem: these works take the query as given and ask how the data should be
arranged to answer it cheaply. The curation entry of 2026-10-15 03:31
flagged the stopgap, and the owner answered: “don’t hesitate to extend the
vocabulary as needed”.
A search of the record’s titles found no earlier work, LIT or THEORY, whose subject this is.
Decision
Add databases (Databases and data structures). It covers:
- physical database design and index selection;
- materialized views and the choice of which answers to precompute;
- adaptive and self-organizing structures;
- lower bounds on lookup (cell-probe and the like);
- caching and paging;
- the cost of organizing ahead of use against organizing in use.
Machine-learning approaches (learned indexes, learned physical design) go to the anthology, as for every topic here.
How it is applied:
- Primary on the five works above, replacing
information-retrieval, which none of them is about. Where a second topic fits it is added:operations-researchfor the two optimization papers (LIT-1084, LIT-1094),mathematicsfor the two that prove bounds (LIT-1097, LIT-1093). - Added to QUESTION-114, the question they were read for.
Alternatives
- Keep
information-retrieval. It is free, but it puts relevance ranking and index selection on one page, and a reader browsing either finds the other. data-structures, narrower. It would leave physical design, materialized views and the cost models of database systems without a word, and those are most of what was read.operations-researchalone. It fits the two optimization papers and not the bounds or the adaptive structures.