Topics — What a work is about. Nucleation holds whatever reading the owner files here, whether or not an Anthology of the SOTA topic could also hold it; instruction for ML practice belongs to the anthology (ADR-048). The words are seeded from the clusters the reading-time triage of 2026-09-25 found, and grow by decision.
Databases and data structures — how stored data is organized so that it can be found and kept current — 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, caching and paging; and the cost of organizing ahead of use against organizing in use. Read for itself, not as ML practice: learned indexes and other machine-learning approaches go to the anthology (ADR-045).
36 of 2004 LIT documents. Back to the full index.
| # | Title | Summary | Status |
|---|---|---|---|
| LIT-1080 | Selection of Views to Materialize in a Data Warehouse | Gupta and Mumick (2005), IEEE TKDE. The journal paper merges Gupta’s 1997 space-budget results and the 1999 maintenance-budget results into one article; it adds proofs, not new problems or new guarantees. Theorem 8 (the conference Theorem 1: inverted-tree greedy on OR view graphs, at most 2S of maintenance, at least 1 − 1/e of an optimum with the same maintenance, assuming no inverted-tree piece of the optimum exceeds S) and Theorem 10 (A* is exact on AND-OR graphs) are now proved, while Theorem 9 (the assumption-free half-density bound) is referred to Gupta’s thesis. The maintenance-budget guarantee stays confined to OR view graphs, the greedy stays exponential in the worst case, and the two constraints are never combined. The only place upkeep is traded against query cost is the 1997 formulation carried over, query cost plus maintenance cost minimized under a space budget, with a guarantee only for AND view graphs in which every view is queried more often than it is updated; build cost and staleness are not modelled anywhere. | Active — read in full 2026-10-15 from the first author’s manuscript of the journal paper, linked from Gupta’s publication list (www3.cs.stonybrook.edu/~hgupta/ps/sel-views-tkde.pdf, 41 single-column pages, read by OCR; not compared with IEEE’s typeset pp. 24–43). Worth reading as the consolidated, proved account of Gupta’s 1997 space-budget results (LIT-1091) and Gupta and Mumick’s 1999 maintenance-budget results (LIT-1092): it is the journal version of both papers, not of the 1999 paper alone, and it adds proofs, not new problems or guarantees. The inverted-tree greedy’s 1 − 1/e guarantee for OR view graphs under a maintenance budget (now Theorem 8, still bicriteria at up to 2S and still assuming no tree-piece of the optimum exceeds S) and the exactness of A* on AND-OR graphs (Theorem 10) are now proved; the assumption-free half-density bound (Theorem 9) is referred to Gupta’s thesis; the guarantee is still for OR graphs only and the greedy still exponential in the worst case, data cubes included. For QUESTION-114 it changes nothing: the article holds two separate models, upkeep in the objective under a space budget (guaranteed only for AND view graphs in which every view is queried more often than updated, a lemma it now says fails for OR graphs) and upkeep as a budget with query cost alone in the objective, never both constraints together, and no build cost or staleness. LIT-1095 remains the closest to a joint model. |
| LIT-1083 | An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server | Chaudhuri and Narasayya (1997), VLDB ‘97. The AutoAdmin tool picks at most k indexes (single- or two-column, clustered or not) for a given workload of SQL statements, minimising the unweighted sum of the optimizer’s estimated costs of those statements, with hypothetical (“what-if”) indexes made visible to the optimizer by loading their statistics into the catalog. Its contribution is search efficiency: candidates are restricted to indexes in some single query’s best configuration, enumeration is Greedy(m, k) (an exhaustive seed of m indexes, then greedy additions), costs of most configurations are derived from a few “atomic” ones, and two-column indexes are generated only from winning single columns. On five TPC-D workloads this cut running time to 10–24% of a baseline, with estimated-cost quality 0–7% worse, and Greedy(2, 4) matched the exhaustive optimum on four of five workloads and was within 1% on the fifth. The cost model has no build cost, no storage term and no frequency weights, the budget is a count of indexes, the workload is fixed, there is no guarantee for the greedy step, and quality is never measured by executing anything. | Active — read in full 2026-10-15 from the VLDB Endowment’s proceedings PDF (www.vldb.org/conf/1997/P146.PDF, pp. 146–155, a scan with an OCR layer; tables and figures read from page images), which refuses plain requests from this environment (HTTP 403) and was served when the request carried a browser User-Agent. Worth reading as the founding paper of optimizer-driven (“what-if”) index selection in practice: at most k indexes chosen for a fixed workload of SQL statements to minimise the unweighted sum of the optimizer’s estimated costs, made affordable by per-query candidate selection, Greedy(m, k) enumeration with an exhaustive seed, derived costs from atomic configurations, and two-column indexes grown from single-column winners (4–10 times faster than a baseline, 0–7% worse by estimated cost, on five TPC-D workloads). For QUESTION-114 it prices organizing ahead no differently from Finkelstein et al. (LIT-1084), and in fewer terms: upkeep through the workload’s update statements, but no build cost, no storage term, no frequency weights and no changing workload, so “paid once” and staleness stay unpriced; what it adds is that deciding the arrangement has its own cost, and evidence (not a bound) that greedy choice works when index interactions are few and local. For CLAIM-310 it is consistent with the dependence on the query mix by construction and says nothing about what stands out within a bin; its heuristics (consider only sortings best for some search, choose the first carefully and add the rest greedily) carry over to a builder’s bins only by analogy. |
| LIT-1084 | Physical database design for relational databases | Finkelstein, Schkolnick and Tiberio (1988), ACM TODS 13(1). DBDSGN chooses, for each table, one clustered (ordering) index and a set of nonclustered indices to minimise a frequency-weighted sum of per-statement costs (access, tuple update, index maintenance) plus a weighted storage term, under an optional page limit, taking every cost from the System R optimizer’s own estimates rather than an external model. Statement costs for any configuration are computed exactly from “atomic” configurations with at most one index per table (Propositions 1 and 2), so the optimizer is consulted a linear rather than exponential number of times per table; with no elimination heuristics and a full search the tool finds the optimum, but only with respect to the optimizer’s estimates. The paper gives one worked example and no measurement of actual execution, and its claims that the heuristics usually find the best solutions are not backed by reported data. The model is steady-state over a period: it has no term for the one-time cost of building an index or sorting a table, so it prices upkeep against retrieval, not a one-off sort against later retrievals. | Active — read in full 2026-10-15 from the publisher’s typeset PDF (ACM TODS 13(1), pp. 91–128), which ACM serves free at dl.acm.org/doi/pdf/10.1145/42201.42205 (bronze) but which refused requests from this environment (HTTP 403; the Internet Archive capture could not be fetched), so the copy was the same ACM PDF as posted by the University of Crete course CS-460 (www.csd.uoc.gr/~hy460/pdf/p91-finkelstein.pdf). Worth reading as the classic statement of index selection as a workload-weighted cost model: one clustered order per table (“records can be ordered only one way”) plus secondary indices, chosen to minimise the weighted sum of access, tuple-update and index-maintenance costs plus weighted storage under a page limit, with every cost taken from the optimizer’s own estimates; exact over atomic configurations and optimal only relative to those estimates, with heuristic pruning and no measurement of actual execution. For QUESTION-114 it supplies the joint model for standing arrangements (bins, filed items), but it has no term for the one-time cost of sorting or building an index and does not cover precomputed answers (speed bugs, reused inferences); for CLAIM-310 it is an instance of “one arrangement” and of dependence on the query mix, has no analogue of a bin budget k, and nothing corresponding to pop-out within a bin. |
| LIT-1085 | Designing Access Methods: The RUM Conjecture | Athanassoulis et al. (2016), EDBT. The paper names three per-operation overheads of an access method, each a ratio to the base data alone (read, update and space amplification, each minimum 1.0), and conjectures that bounding any two forces a lower bound on the third. Its evidence is three one-line propositions about extreme designs over an integer array (a direct-address array, an append-only log, an unindexed dense array), a placement of known structures on a triangle, and a table of asymptotic I/O costs; nothing is proved, and the formal statement does not say how large the forced bound is, so as worded it is close to empty. The extremes themselves show the overheads are not symmetric: the space-minimal design is also update-minimal, and the read-minimal design keeps updates at 2.0, so the clean conflicts are read against space and update against both. Build cost appears in the table but is outside the triangle, there is no workload weighting, no time or deadline, and no cost of examining an item other than reading it. | Active — read in full 2026-10-15 from the publisher’s open-access PDF on OpenProceedings (openproceedings.org/2016/conf/edbt/paper-12.pdf, pp. 461–466, CC BY-NC-ND 4.0), the URL DataCite registers for the DOI. Worth reading as the source of the vocabulary of read, update and space amplification, each a ratio to the base data alone with a floor of 1.0, and of the conjecture that bounding two forces a lower bound on the third. It is a vision paper: the conjecture is unproved, its formal wording does not say how large the forced bound is, and its evidence is three extreme designs on an integer array, which show conflicts between particular pairs (read against space, update against read) rather than a symmetric triangle, since the space-minimal design is also update-minimal. For QUESTION-114 it shows that “organizing ahead” is two trades, auxiliary structure paid in space and sorting the base data paid in upkeep, but it has no workload, no build cost inside the trade and no time, so it is not the joint cost model the question lacks. For CLAIM-310 and CLAIM-307 it supports counting search as read overhead (items examined per item wanted), puts a bin budget nearer read cost on a directory than memory cost, and has no term for items that pop out, which both claims turn on. |
| LIT-1086 v2 | The difficulty of optimum index selection | Comer (1978), ACM TODS 3(4). Registered for QUESTION-114 as the result usually cited as “optimal index selection is NP-complete”. Unfetched, so that description is unverified: a secondary account describes the problem as choosing at most p of a file’s attributes that together tell every pair of records apart, which has no workload or cost model. | Unfetched — filed 2026-10-15, not read. No NOTE is filed, and it stays Unfetched until it is read, not on merit. Lawful full texts exist but could not be fetched from this environment on 2026-10-15 (“found but could not be fetched”). Unpaywall, OpenAlex (W2058765797) and Semantic Scholar (CorpusId 1606952) all report it bronze open access, publishedVersion, at the ACM Digital Library (dl.acm.org/doi/pdf/10.1145/320289.320296); OpenAlex reports no repository full text. ACM returned HTTP 403 to every request from this environment (the /doi/pdf/, ?download=true, /doi/epdf/ and landing-page forms, by curl and by WebFetch). The Wayback Machine has no capture of the ACM PDF URL. A precursor exists as a Purdue technical report: Douglas E. Comer, “The Difficulty of Optimum Index Solution” [sic], Purdue Department of Computer Science Technical Report 77-248, 11 pp., in Purdue’s institutional repository (docs.lib.purdue.edu/cstech/182; the record’s date field, 1975, conflicts with the 1977 report number). The record page loaded, but its PDF (docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1181&context=cstech, and the /context/cstech/article/1181/viewcontent forms) returned a Cloudflare challenge (403) to curl, with and without browser headers and the landing page’s cookie, and to WebFetch. The Wayback Machine holds a capture of that Purdue PDF (snapshot 20240708123022), but web.archive.org is blocked by this environment’s egress policy (“Blocked by egress policy”; connection resets), and WebFetch refuses that host. Whether the technical report is the same text as the TODS article was not checked. Also tried: scholar.archive.org (no matching result), CORE (403 and 429), CiteSeerX (redirect, no record found), Google Scholar (no version other than ACM’s surfaced), pdfs.semanticscholar.org (no file), cs.purdue.edu technical-report paths (404), and web searches for a course-hosted copy (none found). No shadow library was consulted. Finkelstein, Schkolnick and Tiberio 1988 (LIT-1084, read) cite it only as “Even a restricted version of the index-selection problem is in the class of NP-hard problems”, so the record’s description of it as proving “optimal index selection NP-complete” rests on secondary accounts, and its model, reduction and conditions are unconfirmed. |
| LIT-1089 | The optimal selection of secondary indices is NP-complete | Piatetsky-Shapiro (1983), ACM SIGMOD Record 13(2). For one relation, a known mix of equality queries and updates, single-attribute secondary indexes, and a fixed upkeep charge per index on each update, choosing the index set that minimizes average transaction cost is NP-hard: minimum set cover reduces to it, each subset becoming an attribute and each element a query that any one of its attributes’ indexes can answer. The paper calls the problem NP-complete but states only the optimization version, and the proof is a sketch of about half a page. Storage is not in the model; the only price of an index is upkeep on updates. A variant with off-line updates under an update-cost budget is asserted NP-complete without proof. The paper does not cite or discuss Comer 1978. | Active — read in full 2026-10-15 from the scan SIGMOD serves openly on sigmodrecord.org (sigmodrecord.org/publications/sigmodRecord/8301/pdfs/984523.984530.pdf, linked from the January 1983 issue page), 4 pp., printed pages 72–75; the ACM Digital Library refused requests from this environment, and Unpaywall and OpenAlex list no open copy. Worth reading as the first proof that choosing secondary indexes for a known mix of queries and updates, to minimize average transaction cost, is NP-hard, by a half-page reduction from minimum set cover: attributes are the sets, queries the elements, and each index pays a fixed upkeep on updates. For QUESTION-114 it shows that the trade of upkeep against per-query savings under a known workload can be stated exactly and cannot be solved exactly in general, but only as the number of attributes and query types grows; storage, build cost and the file’s own order are outside its model, and it does not mention Comer 1978 (LIT-1086), so it is the citation for workload-based hardness and says nothing about what Comer proved. |
| LIT-1090 | Database Cracking | Idreos, Kersten and Manegold (2007), CIDR. Database cracking builds an index as a by-product of answering range queries. Each select partitions, in place, the part of a copy of the column that the query had to touch, so that the qualifying values lie contiguously, and records the new boundaries in a small tree; later queries touch only the pieces at the edges of their range, so per-query cost falls as the column is split into more pieces. On a 10^7-value column under uniformly random range queries, the first cracking select costs 0.38 s against 0.27 s for a scan and about 3.3 s for sort-then-search, and cumulative cost stays below sorting’s until about 10^5 queries, after which upfront sorting wins. The authors claim that only ranges of past interest get organized, but every experiment uses uniformly random ranges, so that claim is not measured; there is no cost model, no rule for when a reorganization is worth making, and updates, concurrency and out-of-memory data are left as open problems. | Active — read in full 2026-10-15 from the paper as published in the CIDR 2007 proceedings (cidrdb.org/cidr2007/papers/cidr07p07.pdf, which redirects to www.cidrdb.org; printed pp. 68–78, CC BY 2.5). Worth reading as the founding account of indexing by query: each range select partitions in place the part of a column copy it had to scan, records the new boundaries in an AVL tree, and so makes later queries touch only the pieces at the edges of their range. On 10^7 values under uniformly random ranges the first cracking query costs 0.38 s against 0.27 s for a scan and about 3.3 s for sort-then-search, and upfront sorting overtakes cracking only after about 10^5 queries. For QUESTION-114 it shows sorting as amortized search in a literal sense, with a measured break-even, but gives no cost model and no rule for when a reorganization is worth making; the claim that only ranges of interest get organized is not tested, since every workload is uniform. For CASE-094 the analogy holds for organizing as a by-product of retrieval and fails on the mechanism: cracking splits everything it searched around an ordered key, and reorganizes on every query whatever the chance of reuse, where the case sets aside only the found brick, and only when it is rare and often used. |
| LIT-1091 | Selection of views to materialize in a data warehouse | Gupta (1997), ICDT ‘97. Gupta states view selection on general AND-OR view graphs as minimizing frequency-weighted query cost plus update-frequency-weighted maintenance cost under a space budget. He proves greedy guarantees of 1 − 1/e (about 63%) of the optimal benefit, with the budget overrun by one view or up to double, but almost all of them assume no updates. Maintenance cost enters exactly one theorem: AND view graphs (each view has one way of being computed) in which every view is queried more often than it is updated. For OR view graphs, which include Harinarayan, Rajaraman and Ullman’s data cube, the paper sets update costs aside outright, so it does not add upkeep to that problem. Maintenance is an abstract per-update charge for keeping a view consistent. Nothing prices building a view, tolerated staleness or deferred refresh, and there are no experiments. | Active — read in full 2026-10-15 from the author’s PostScript copy on the Stanford InfoLab papers server (infolab.stanford.edu/pub/papers/SelectionViews.ps, 15 pp., dated March 1997, linked from the warehousing project’s publication page; Unpaywall and OpenAlex report the DOI closed). Worth reading as the general statement of view selection: AND-OR view graphs with query and update frequencies, and an objective of frequency-weighted query cost plus update-frequency-weighted maintenance cost under a space budget, with greedy guarantees of 1 − 1/e of the optimal benefit when space may overrun. For QUESTION-114 it gives the joint objective in form: reuse against per-update upkeep under capacity. It charges no build cost, leaves the maintenance cost abstract, and models only keeping views consistent, not tolerating or acting on stale ones. Its guarantees with maintenance cost hold only for AND view graphs in which every view is queried more often than it is updated. For the data cube of LIT-1094 it assumes no updates, so it does not add upkeep to that problem. That came in Gupta and Mumick’s maintenance-time-constrained follow-up (ICDT 1999), read afterwards as LIT-1092. |
| LIT-1092 | Selection of Views to Materialize Under a Maintenance Cost Constraint | Gupta and Mumick (1999), ICDT ‘99. Gupta and Mumick choose views to materialize so as to minimize frequency-weighted query cost subject to a cap S on total maintenance time, the sum over chosen views of update frequency times a per-update maintenance cost that depends on which other views are stored. Because storing one view can make another cheaper to maintain, benefit per unit of maintenance is not monotone and the single-view greedy of earlier work can be arbitrarily bad. For OR view graphs (each view computed from one other, as in data cubes) a greedy that adds whole “inverted tree sets” gets at least 1 − 1/e (63%) of the benefit of an optimal solution that may use as much maintenance as the greedy did, the greedy using up to 2S, assuming no inverted-tree piece of the optimum alone exceeds S (Theorem 1, unproved here); without that assumption it gets half the optimum’s benefit per unit of maintenance (Theorem 2). Each greedy stage enumerates exponentially many sets in general; for general AND-OR graphs there is only an exact A* search with exponential worst case. Upkeep is a budget, not a term traded against query savings; build cost, storage and staleness are not modelled, and the experiments are on random graphs of 10 to 25 nodes. | Active — read in full 2026-10-15 from the authors’ PostScript copy on Stanford InfoLab’s papers server (infolab.stanford.edu/pub/papers/update.ps, 18 pages, dated 8 October 1998, the ICDT ‘99 camera-ready, not the 2005 TKDE journal version; not compared with Springer’s typeset pages). Worth reading as the first view-selection result that budgets maintenance time instead of space, and for its demonstration that upkeep is not additive: storing one view can make others cheaper to maintain, so benefit per unit of maintenance is not monotone and single-view greedy can be arbitrarily bad. For QUESTION-114 it shows upkeep priced as a budget, U(M) = Σ update frequency × per-update maintenance cost given the other stored views, with query cost the only objective; build cost, storage and staleness are not modelled (every view is refreshed in a nightly batch). Its guarantee answers the open problem of LIT-1091 only for OR view graphs: 1 − 1/e of an optimum’s benefit while using up to twice the budget, under an assumption on the optimum, or half the optimum’s benefit per unit of maintenance without it, with the theorems stated but not proved and a greedy whose stages are exponential in general (including on data cubes). General AND-OR graphs get only an exact A* search. It does not close the question, and comes no closer to a joint cost model than LIT-1095. |
| LIT-1093 | Amortized efficiency of list update and paging rules | Sleator and Tarjan (1985), CACM 28(2). For a list searched sequentially from the front, where reaching the i-th item costs i, moving each accessed item to the front costs at most twice what any other rule costs on the same sequence, including rules that know the whole sequence in advance (four times, counting move-to-front’s own moves), with no probabilistic assumption. A fixed list sorted by access frequency, and the transpose and frequency-count rules, are not within any constant factor of that. Rearranging ahead of need never pays in this model (Theorem 3). For paging, where only a small fast memory is cheap, no rule that cannot see the future can do better in the worst case than n/(n − n_MIN + 1) times the offline optimum MIN, and LRU and FIFO attain that bound up to an additive n_MIN; with equal memories the ratio is the memory size. The model is a single linear list (or a two-level memory) with uniform items and access cost depending only on position; it says nothing about partitions, bins or search that is not a scan. | Active — read in full 2026-10-15 from the scan of the published CACM article (pp. 202–208, with ACM’s running heads and copyright line) on Sleator’s CMU page (www.cs.cmu.edu/~sleator/papers/amortized-efficiency.pdf); the ACM Digital Library’s open-access PDF refused direct requests from this environment. Worth reading as the founding worst-case comparison of an online rule with the best offline one: on a sequentially scanned list where reaching position i costs i, move-to-front costs at most twice what any rule in the class costs on the same sequence, even one that knows the future (four times counting its own moves), while a fixed list sorted by frequency, transpose and frequency count are not within any constant; and for paging no online rule beats n/(n − n_MIN + 1) times Belady’s MIN, a bound LRU and FIFO meet up to an additive n_MIN. For QUESTION-114 it shows that in a single pile searched from the top, putting the found item on top is within 2 of the best dynamic policy, not of the best arrangement, and that sorting ahead of need never pays (Theorem 3); bins are outside its model. For QUESTION-095 it prices one term, retrieval misses under a fixed cache size and the cost of not knowing future requests, and nothing on precomputation, upkeep or staleness. |
| LIT-1094 | Implementing data cubes efficiently | Harinarayan, Rajaraman and Ullman (1996), SIGMOD ‘96. Treats a data cube’s group-by queries as a lattice in which a query can be answered from any stored ancestor, prices a query at the number of rows of the smallest materialized ancestor, and chooses which views to precompute. Choosing k views to maximize the total reduction in query cost (the “benefit”) is NP-complete; a greedy rule that adds the view of largest marginal benefit gets at least 1 − ((k−1)/k)^k ≥ (e−1)/e ≈ 63% of the optimal benefit, a bound that is tight, holds unchanged with query-frequency weights, and weakens to 0.63 − f under a space budget when no view takes more than a fraction f of it. The cost of building views is represented only by their size, maintenance and updates are not modelled, the data are static, and the bound is on benefit, not on query cost. On TPC-D data the greedy order reaches nearly the minimum total query time with five views and barely more space than the base view. | Active — read in full 2026-10-15 from the authors’ 25-page version on Stanford InfoLab’s papers server (infolab.stanford.edu/pub/papers/cube.ps, TeX run of 8 January 1996), not the SIGMOD typesetting, which the ACM Digital Library refused (403); the two were not compared. Worth reading as the standard source on choosing which precomputed answers to store when each query is answered from its cheapest stored ancestor: the lattice of group-by views, the linear cost model (rows of the ancestor scanned), NP-completeness, and a greedy rule whose total benefit, the saving against storing the base view alone, is at least 1 − ((k−1)/k)^k ≥ (e−1)/e ≈ 63% of the optimum for a budget of k views, tight, unchanged with fixed query frequencies, and only 0.63 − f under a space budget when no view exceeds a fraction f of it. For QUESTION-114 and QUESTION-095 it shows the precomputed-answer term the four earlier readings lacked, with a stored answer’s value counted over every query it serves and marginal on what is already stored (sharpening CLAIM-303’s break-even); it does not price build cost (space is a proxy), upkeep or staleness (the data are static and derived answers exact), timing or deadlines, uncertain workloads, or the medium of retrieval, so it is a model of the speed bugs only in naming the category, an analogy with one usable term for filed arguments, silent on the bias of reused inferences, and not about LEGO bins. |
| LIT-1095 | An Online Approach to Physical Design Tuning | Bruno and Chaudhuri (2007), ICDE. An always-on index tuner for SQL Server. It keeps, for each candidate or existing index, the running sum of what each query would have saved with it (what-if optimizer estimates, with update costs counted as losses). It creates an index once that sum has risen by the index’s build cost above its lowest point, and drops it once the sum has fallen by the build cost from its highest point. For one index with no space limit, the authors call this 3-competitive against the optimal schedule that knows the workload in advance. The proof only gives a workload on which the ratio approaches 3, and the paper cites no competitive-analysis work, ski rental included. The general case (many interacting indexes and a storage limit) uses heuristics with no guarantee. All costs in the experiments are optimizer estimates, on synthetic and TPC-H workloads. | Active — read in full 2026-10-15 from the accepted-version PDF that Microsoft Research’s publication page for the paper links (www.microsoft.com/en-us/research/wp-content/uploads/2007/01/continuous.pdf, 10 pp., no IEEE pagination). The authors were both at MSR; Unpaywall, OpenAlex and Semantic Scholar list no open copy. Worth reading as the first model in the record that prices organizing ahead and organizing on demand on one schedule. It has a one-time build cost that depends on what is already built, per-statement savings, upkeep as the cost of update statements, a space limit, and a workload known only up to now. Its online rule builds an index once the benefit missed since the last low point equals the build cost, and drops it once the loss since the last high point equals the build cost. For QUESTION-114 it shows that the rule is rent-or-buy in structure but cites no competitive-analysis work, ski rental or Karlin et al. included. Its “three-competitive” result covers one index with no space limit, and is supported only by an example where the ratio approaches 3. By a check of my own it fails when a single statement’s saving is large next to the build cost. The general case with space and interacting indexes is heuristic, dropping is free, there is no staleness or deadline, and all costs are optimizer estimates. For CASE-094 it endorses making a bin at once when the bin costs almost nothing, and adds a matching rule for removing one. For CLAIM-307 it replaces “carve when retrieval fails” with “carve when the extra search already spent equals the bin’s cost”: a cumulative-cost criterion with no deadline. |
| LIT-1096 | Competitive snoopy caching | Karlin, Manasse, Rudolph and Sleator (1988), Algorithmica 3. For a shared-bus multiprocessor whose caches can either keep a replicated block (and pay one bus cycle for every write to it) or drop it (and pay p to fetch it again if it is read), the paper gives counter-based on-line algorithms whose total bus cost on every request sequence is at most twice that of the best off-line algorithm, and proves that no deterministic on-line algorithm can guarantee better than 2. The rule is: drop a copy once the writes it has caused since it was last read have cost as much as refetching it. With a third option (reading or writing through without fetching) the lower bound rises to 3, and the algorithm given is 3-competitive ignoring writebacks, 4 counting them; with associative caches the bound becomes the paging ratio. The paper never names rent-or-buy or ski rental; its rent is upkeep paid on an idle copy, and its purchase is the refetch after dropping, the reverse orientation of building a bin. Costs are fixed constants, the guarantees are worst case only, and the authors call the practical significance “unclear”. | Active — read in full 2026-10-15 (NOTE for this LIT) from a scan of the published Algorithmica article (pp. 79–119, Springer-Verlag copyright line) posted among the reading handouts of MIT course 6.896, Spring 2004 (courses.csail.mit.edu/6.896/spring04/class/www/handouts/papers/snoopy-cache.pdf); no author or repository copy was found (Unpaywall and OpenAlex: closed; not on Sleator’s CMU or Karlin’s UW pages). Worth reading as the first competitive analysis of a rent-or-buy decision: a cache keeping a shared block pays 1 per write to keep its copy current, or drops it and pays p to fetch it again if it reads; dropping once the writes charged since the last read have cost p is within 2 of the off-line optimum on every sequence (Theorem 4.1), and no deterministic on-line rule does better (Theorem 3.1); with a third option the bound rises to 3 (Theorem 3.3). The paper states the principle generally (change state when the extra cost of staying equals the cost of changing) but never names rent-or-buy or ski rental, and its instance is the decision to stop maintaining a copy, the mirror of building a bin. For QUESTION-114 and CASE-094 it gives a worst-case rule for when a bin pays without knowing future use: make it when the extra search already spent equals its cost; for CLAIM-303 it shows that a recurrence count weighted by reconstruction cost is, in the worst case, the right criterion and within 2, and that the second-occurrence rule is that rule only when filing costs about one reconstruction; for QUESTION-095 it prices upkeep against re-retrieval and nothing on precomputation or staleness, which it forbids rather than prices. |
| LIT-1097 | Should Tables Be Sorted? | Yao (1981), JACM 28(3). For storing a set of n keys from a universe {1,…,m} in a table so that the membership query (is x in S?) is answered with the fewest worst-case adaptive probes, Yao proves that when the table cells may hold only keys of S or a bounded number of pointer symbols, sorted order with binary search (⌈lg(n+1)⌉ probes) is optimal once m exceeds a Ramsey-number threshold N(n, p, q), whatever the arrangement rule, table size or hashing scheme. The threshold is astronomically large, and for small universes sorted order is beaten (one probe suffices for m = 3 with n = 2, and for m ≤ 2n − 2 with n > 2). The optimality also fails as soon as one cell may hold an arbitrary value from the universe: with a single extra “directory” cell, two probes suffice for m ≥ 2^{16n²}. Only query cost is counted; building the table is free and unconstrained, so the paper says nothing about the cost of arranging or about trading arrangement cost against lookups. | Active — read in full 2026-10-15 from the published Journal of the ACM version (28(3), pp. 615–628), which ACM serves free (OpenAlex/Unpaywall: bronze) but refused to this environment with 403, fetched instead as the copy on a University of Maryland course page (www.cs.umd.edu/users/gasarch/COURSES/858/S13/tables.pdf) and compared with the author’s Stanford report STAN-CS-79-753 (i.stanford.edu/pub/cstr/reports/cs/tr/79/753/CS-TR-79-753.pdf), which has the same results. Worth reading as the paper that set up what is now called the cell-probe model, with lookup cost counted as the worst-case number of cells read and arrangement and search strategy left arbitrary: for static membership, sorted order with binary search (⌈lg(n+1)⌉ probes) is optimal once the key space exceeds a Ramsey-number threshold, provided cells hold only stored keys or pointer symbols; it is beaten for small key spaces (one probe for m ≤ 2n − 2), and for large ones as soon as one cell may hold an encoded value (two probes for m ≥ 2^{16n²}). For QUESTION-114 it shows that “founding cell-probe paper” holds but “when storage in sorted order beats other arrangements” does not as worded: the theorem says nothing beats sorting under a no-encoding restriction for huge universes, and the rest of the paper shows other arrangements beating it. It counts lookup probes only; building the arrangement is free, so it bears nothing on whether sorting is amortized search or on the cost of organising set against lookups later. |
| LIT-1099 | When Is “Nearest Neighbor” Meaningful? | Beyer et al. (1999), ICDT ‘99. For a fixed number n of data points and a query drawn independently of them, if the variance of the p-th power of the query-to-point distance, divided by its mean, goes to zero as dimension m grows, then the farthest point is, with probability tending to one, within any factor 1 + ε of the nearest (Theorem 1). The condition holds for IID dimensions and for several correlated or non-identical workloads, and fails when data and queries lie on a low-dimensional subspace or when queries fall inside well-separated clusters. Simulations put the collapse of contrast within 10 to 20 dimensions for IID data, and two real image-feature sets showed weak contrast. The condition is sufficient, not shown necessary; the theorem is about the ratio of distances with n held fixed, and says nothing about real data of low intrinsic dimension except that such data can escape it. | Active — read in full 2026-10-15 from the authors’ University of Wisconsin–Madison technical report of the same title (CS TR #1377, June 1998, 19 pp.), served by the department’s archive (research.cs.wisc.edu/techreports/1998/TR1377.pdf) and, byte-identical, by the MINDS@UW repository (minds.wisconsin.edu/handle/1793/60174), which OpenAlex lists as the submitted version. The ICDT ‘99 chapter itself is closed (Unpaywall, OpenAlex, Semantic Scholar) and was not seen; the CiteSeerX copy redirects to the Internet Archive, which was unreachable. The report is a scan, read by OCR and page images. Worth reading as the source of the sufficient condition for nearest-neighbour contrast to vanish: if the variance of the p-th power of the query-to-point distance, divided by its mean, goes to zero, then with a fixed number of points the farthest is within any factor 1 + ε of the nearest with probability tending to one. IID coordinates satisfy it, and so do several correlated or non-identical workloads. Data on a low-dimensional subspace, and queries that land in well-separated clusters, do not. Simulations put the loss of contrast within 10 to 20 dimensions for IID data. The condition is sufficient and not shown necessary, n is held fixed, the result concerns the ratio of distances, and the paper measures no index. For CLAIM-309 it has no bearing, and the filing’s “no arrangement by similarity discriminates” overstates it. For CLAIM-310 it corroborates that what serves retrieval depends on the query distribution: the same clustered data is meaningful for queries inside clusters and not for uniform ones, and the meaningful answer there is the whole cluster. For QUESTION-114 it sets a precondition: under its condition there is no nearest neighbour worth organizing to find. |
| LIT-1100 | Answering Queries Using Views | Levy et al. (1995), PODS 1995. For conjunctive queries and views, a view can be used in an equivalent rewriting of a query exactly when there is a containment mapping (a homomorphism of bodies) from the view into the query, so every possible use of a stored view is found among those mappings. Without comparison predicates, a minimal rewriting needs no more literals than the query and no new variables, which puts the search in NP; deciding whether some rewriting uses a given set of views (with comparisons only in the query), whether a rewriting with fewer than k literals exists, and whether a rewriting using only the views exists are each NP-complete, and with comparisons in both query and views existence is Π2p-complete. The hardness has two independent sources, the number of mappings and the choice of which query literals to drop, and a polynomial algorithm removes the redundant literals for a given mapping, exactly under stated conditions. Only equivalent rewritings are studied; contained rewritings, the cost of the resulting plan and the size of view collections are outside it. | Active — read in full 2026-10-15 from the authors’ camera-ready of the PODS 1995 extended abstract (pp. 95–104), linked from Alberto Mendelzon’s University of Toronto publications page and fetched from www.cs.toronto.edu/pub/papers/pods95LMSS.ps.Z, because ACM’s open-access PDF refused requests from this environment. Worth reading as the paper that reduces reuse of stored views to query containment: a view can be used in an equivalent rewriting exactly when its body maps homomorphically into the query’s, a minimal rewriting is no longer than the query, and finding a rewriting, a shorter one or one using only the views is NP-complete for conjunctive queries without comparisons (Π2p-complete for existence with comparisons in both), with two independent sources of hardness (THEORY-389). For CLAIM-303 and CLAIM-308 it shows that recognizing that stored answers cover a new question is a worst-case NP-complete search in the size of the question and the stored items’ definitions, not in the stored data, so the per-use cost c_a has a recognition term that varies with the question and the store; it says nothing about prose arguments, contained (partial) reuse, or whether recognized reuse pays. |
| LIT-1101 | Effective Page Refresh Policies for Web Crawlers | Cho and Garcia-Molina (2003), ACM TODS 2003. Unavailable: a lawful copy exists but could not be fetched. | Unavailable — filed 2026-10-15, not read. Looked for a lawful full text of the journal version (ACM TODS 28(4), 2003) on 2026-10-15 and found one that could not be fetched. The authors’ own copy is listed at oak.cs.ucla.edu/~cho/papers/cho-tods03.pdf (a web search returns it with the title “Effective Page Refresh Policies For Web Crawlers”), but that server did not answer from this environment: nine requests over about seven minutes each returned 503 with an upstream connection timeout, and WebFetch got the same; the author’s index page there, and the old Stanford address infolab.stanford.edu/~cho/ (which redirects to it), behaved the same, and web.cs.ucla.edu/~cho/papers/cho-tods03.pdf is 404. The ACM Digital Library returned 403. Unpaywall and Semantic Scholar report it closed; OpenAlex reports it closed and lists two CiteSeerX records (10.1.1.3.7723, 10.1.1.89.8050), which could not be reached (connection reset, then a redirect to the Internet Archive, which is unreachable from here). ResearchGate’s page returned 403, and who uploaded its copy is unknown. Stanford’s InfoLab technical-report server (ilpubs.stanford.edu:8090) timed out. The University of Crete course page holds slides about the paper, not the paper. What is lawfully available is the other version: the SIGMOD 2000 conference paper (LIT-1119, read), and the authors’ October 1999 Stanford technical report of it on a KTH course page, which lacks what the journal adds (by its abstract and secondary accounts, among other things, refresh weighted by page importance). Found but could not be fetched. |
| LIT-1102 | Lower Bounds on Near Neighbor Search via Metric Expansion | Panigrahy et al. (2010), FOCS 2010. Cell-probe lower bounds for near-neighbour search follow from the expansion of the graph joining points within distance r: a deterministic t-probe structure with m cells of w bits must have (mwt/n)^t at least the vertex expansion, and a randomized one must have m^t w/n at least the robust expansion at measure 1/m^t, on random data sets with weakly overlapping neighbourhoods. For the hypercube this recovers known bounds and gives, for example, space n^{1+Ω(1/(ct))} for approximation c and n^{Ω(1/(tε²))} for 1 + ε; for symmetric (Cayley) graphs a one-probe structure matches the bound, and for dynamic low-contention structures the update time must be at least the robust expansion over poly(t). The bounds are average case, for approximate decision search, and weak in t: they fall off exponentially in the number of probes, so they are tight only for a constant number of probes and say little about structures that probe n^ρ cells. | Active — read in full 2026-10-15 from the authors’ arXiv preprint (arXiv:1005.0418v1, 3 May 2010, 29 pp.); the FOCS 2010 text was not seen and has no open copy. Worth reading as the framework that turns the expansion of a metric’s neighbourhood graph into cell-probe lower bounds for approximate near-neighbour search: (mwt/n)^t ≥ vertex expansion for deterministic t-probe structures, m^t w/n ≥ robust expansion at measure 1/m^t for randomized ones, on random data with weakly overlapping neighbourhoods, giving for the hypercube space n^{1+Ω(1/(ct))} at approximation c and n^{Ω(1/(tε²))} at 1 + ε, a matching one-probe upper bound on Cayley graphs, and an update-time lower bound for dynamic low-contention structures. The bounds are average case, approximate, and fall off exponentially in the number of probes, so they are tight only for constant t. For THEORY-340 it is the similarity analogue of Yao’s lookup floor, holding with arbitrary cell encoding where Yao’s sorted-order optimality did not; for QUESTION-114 it puts a floor under fast per-query search priced in space, and the only lower bound on upkeep among the readings, in a restricted class, with no workload, amortization or build time; for CLAIM-310 its dependence on expansion is consistent with attribute bins working for discrete lookup (the record’s reading); no bearing on THEORY-345 or CLAIM-309. |
| LIT-1104 | Why and Where: A Characterization of Data Provenance | Buneman et al. (2001), ICDT 2001. The paper separates two meanings of the provenance of a piece of output data. Why-provenance is the witness basis: for each valuation of the query that produces the value, the part of the source the query’s patterns matched, one witness per derivation. Where-provenance is the location in the source a value was copied from. For a hierarchical data model and a query language that covers positive (SPJU) relational queries, the witness basis is preserved by the paper’s query rewriting, and the minimal witness basis is the same for equivalent queries with equality conditions, while where-provenance is not invariant over equivalent queries in general and is preserved by rewriting only for a restricted class it calls traceable. Proofs are omitted, and nothing covers negation, aggregation, updates or additions to the source. | Active — read in full 2026-10-15 (NOTE-920) from the authors’ postprint in the University of Pennsylvania’s ScholarlyCommons repository (repository.upenn.edu/handle/20.500.14332/6246, file k50.pdf, 15 pp., camera-ready text of October 2000 without LNCS page numbers), found through Unpaywall and OpenAlex (green, submittedVersion) and fetched through the repository’s API because the landing page is script-only; the Edinburgh repository handle (hdl.handle.net/20.500.11820/46e660d2-8247-4d26-ae49-65fd1bf8364b) returned an error. Worth reading as the source of the distinction between why-provenance, a set of witnesses with one per derivation, and where-provenance, the location a value was copied from, and of the result that only the first can be made independent of how a positive query is written (minimal witness basis, for queries with equality conditions; where-provenance only for “traceable” queries; proofs omitted) (THEORY-367). For QUESTION-105 it shows that a minimal witness basis is a retained state that decides survival under deletion of source facts in set semantics, and that “provenance” names two structures of which only one is invariant; it covers no additions, no negation or aggregation, no strengths of support and no measure of how much is retained. For CLAIM-303 it shows that why-provenance can be recomputed on demand from the query and the source rather than filed; for CLAIM-306 it has nothing for absence, since both notions are defined only for what is in the output. |
| LIT-1105 | Balancing Performance and Data Freshness in Web Database Servers | Labrinidis and Roussopoulos (2003), VLDB 2003. The paper poses Online View Selection for a web server whose database takes updates while serving requests: choose, as the workload runs, which page fragments (WebViews) to keep stored and refreshed on every update and which to cache and invalidate, so as to minimize mean response time while the fraction of fresh fragments served (QoD) stays above a threshold θ. Its algorithm, OVIS(θ), estimates per fragment the response-time and QoD change of switching, and periodically switches up to MAX_CHANGE fragments greedily, spending a QoD surplus on speed or buying back a deficit; it materializes everything when it detects backlog. Nothing is proved: optimality of the greedy step is asserted, and the evidence is one synthetic simulation with fixed costs, in which OVIS kept QoD near θ, answered faster than caching alone, and recovered from overload. Upkeep and query savings share one cost, but staleness is a constraint set by the user, not a priced term, and build cost, switching cost and storage are absent. | Active — read in full 2026-10-15 (NOTE-911) from the VLDB Endowment’s copy of the 2003 conference paper (www.vldb.org/conf/2003/papers/S13P01.pdf, 12 pp.; Crossref pages 393–404), whose bitmap fonts made OCR necessary; the 2004 VLDB Journal version was not read. Worth reading as the first online view-selection algorithm that trades response time against a measured freshness: OVIS(θ) periodically moves up to a fixed number of page fragments between cached-and-invalidated and stored-and-refreshed, greedily, to keep the share of fresh fragments served above θ at the least response time, and materializes everything when it detects backlog. For QUESTION-114 it is not the joint model: query savings and upkeep share one cost and staleness is measured, but staleness is a threshold, not a price, switching and storage are free, the greedy’s optimality is asserted without proof, and the evidence is one synthetic simulation with fixed costs; set beside Bruno and Chaudhuri (THEORY-332), which has build cost and no staleness, neither contains the other. For CLAIM-303 it adds a third option, keep the result and invalidate it on change, and measures staleness as a share of uses, not a cost. |
| LIT-1106 | Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality | Indyk and Motwani (1998), STOC 1998. Approximate nearest-neighbour search in d dimensions reduces, with small overhead, to a decision problem (is there a point within r, or none within (1+ε)r), and that decision problem is solved by locality-sensitive hashing: if hash functions make near pairs collide with probability at least p1 and far pairs with at most p2, then n^ρ random hash tables with ρ = ln(1/p1)/ln(1/p2) answer queries with O(n^ρ) hash evaluations in O(dn + n^{1+ρ}) space, with constant success probability. For Hamming space by bit sampling, and for ℓ_p with p in [1, 2] by embedding, ρ ≤ 1/(1+ε) in the 1999 text (1/ε, for ε > 1, in STOC). The paper also gives the other end of the trade: Õ(d) query time for n·O(1/ε)^d or (nd)^{O(1)} preprocessing. It is an upper bound only: it proves no lower bound, does not claim its exponents are best, solves only the approximate problem with constant probability, and counts preprocessing as space. | Active — read in full 2026-10-15 from the authors’ expanded “preliminary version” of December 30, 1999, served from Indyk’s MIT directory (people.csail.mit.edu/indyk/nndraft.ps), with its statements compared against the STOC 1998 printed text (pp. 604–613) as posted on a Princeton course page (cs.princeton.edu/courses/archive/spr04/cos598B/bib/IndykM-curse.pdf); the ACM copy refused requests and Unpaywall and OpenAlex list no open copy. The 2012 Theory of Computing journal version (with Har-Peled) was not read. Worth reading as the origin of locality-sensitive hashing and of the reduction from approximate nearest neighbour to its decision version: hash functions that make near pairs collide more often than far ones give n^ρ tables, O(dn + n^{1+ρ}) space and O(n^ρ) hash evaluations per query, ρ = ln(1/p1)/ln(1/p2), which for Hamming bit sampling is at most 1/(1+ε) in the 1999 text (1/ε, for ε > 1, in STOC), with constant success probability; bucketing gives Õ(d) queries for n·O(1/ε)^d preprocessing. Upper bounds only, approximate only, and preprocessing is counted as space. For QUESTION-114 it is the first price list for organizing a collection for similarity queries, space paid once against hash evaluations per query, with no amortization over queries and no workload; for CLAIM-310 it shows the single-arrangement constraint escaped by keeping many random partitions and storing every point in each, paid for in space; it neither extends nor narrows THEORY-340 and has no bearing on THEORY-345 or CLAIM-309. |
| LIT-1107 | A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces | Weber et al. (1998), VLDB 1998. Under uniformly distributed, independent data and queries in the unit cube with Euclidean distance, the paper estimates the average fraction of blocks that an optimal nearest-neighbour search must read in a partitioned or clustered index. That fraction reaches the 20% at which a sequential scan wins, given an assumed five-fold sequential advantage, at about 15–20 dimensions for rectangular regions, 26 for spherical ones, and below a crude 610 for any partitioning into convex clusters of two or more points. The “around 10” in the abstract is the measured crossover for an R*-tree and an X-tree on 50,000 uniform points and on 45-dimensional image features. As an alternative it proposes the VA-file, a scanned file of compact per-vector approximations that filters out all but a few vectors. The analysis says nothing about data with low intrinsic dimension; that the results carry over by fractal dimension is a conjecture. | Active — read in full 2026-10-15 from the VLDB Endowment’s open copy of the proceedings paper (www.vldb.org/conf/1998/p194.pdf, pp. 194–205, a scan with an OCR text layer, fetched with a browser User-Agent header). Worth reading as the standard average-case analysis of why partitioned indexes for nearest-neighbour search lose to a sequential scan as dimension grows, and as the source of the VA-file. Under uniform, independent data in the unit cube with Euclidean distance, an assumed five-fold sequential advantage and a 20% line, the fraction of blocks an optimal search reads crosses that line at about 15–20 dimensions for rectangular bounding regions, 26 for spherical ones, and below a crude 610 for any partition into convex clusters of two or more points. The “around 10” usually cited is the measured crossover for an R*-tree and an X-tree on 50,000 uniform points and 45-dimensional image features. The bounds substitute the expected nearest-neighbour distance for each query’s own, and they are evaluated by Monte Carlo. Data of low intrinsic dimension are outside the analysis except by an untested fractal-dimension conjecture. For QUESTION-114 it shows a regime where organizing into bins does not pay even with building free, and where the remedy is a scanned file of compact per-item approximations, not a better partition. For CLAIM-310 it marks where arrangement stops doing work: similarity over many coordinates the query does not name, unlike LEGO bins, where queries name a few discrete attributes. It has no bearing on CLAIM-309. |
| LIT-1108 v2 | Combining Fuzzy Information from Multiple Systems | Fagin (1996), PODS 1996. Unfetched: a lawful copy exists but could not be fetched. | Unfetched — filed 2026-10-15, not read. Registered at the owner’s request as one of 22 works at the intersection of database theory and semantic search, as the predecessor of LIT-1115. A lawful full text exists for both versions but could not be fetched from this environment on 2026-10-15 (“found but could not be fetched”). The JCSS 1999 journal version (10.1006/jcss.1998.1600) is in Elsevier’s open archive: Unpaywall, OpenAlex and Semantic Scholar all give sciencedirect.com/science/article/pii/S0022000098916002/pdf (bronze, publishedVersion), which returned 403, as did the article page and the download variant; linkinghub.elsevier.com resolves to that page, and the Elsevier API refused unauthenticated requests (429). The PODS 1996 extended abstract (10.1145/237661.237715) is open on the ACM Digital Library (Unpaywall and Semantic Scholar: gold), but dl.acm.org/doi/pdf/10.1145/237661.237715 returned 403. CORE lists a CiteSeerX-harvested copy (oai:citeseerx.psu:10.1.1.55.2172) whose abstract matches the journal paper; CiteSeerX reset the connection and redirected to web.archive.org, which is unreachable, and CORE does not serve its full text to the public API. OpenAlex also lists a CiteSeerX record 10.1.1.386.6808 (submittedVersion), likewise unreachable. IBM Research’s publication page (research.ibm.com/publications/combining-fuzzy-information-from-multiple-systems) links only the DOI; guessed author paths on researcher.watson.ibm.com returned 404 and the old almaden.ibm.com host returned 503; CORE’s download path returned 403. Web searches for the title with and without “pdf” found no author, institutional or course copy. Fagin, Lotem and Naor (LIT-1115, read) state this paper’s main result as they report it: Fagin’s Algorithm finds the top k with O(N^((m−1)/m) k^(1/m)) accesses with arbitrarily high probability when the lists’ orderings are independent, and is optimal in that sense for strict combining functions. It stays Unfetched until it is read, not on merit; fetching the Elsevier open-archive PDF from a browser would settle it. |
| LIT-1109 | Adaptive Precision Setting for Cached Approximate Values | Olston et al. (2001), SIGMOD 2001. Olston, Loo and Widom set the width of each cached interval adaptively to minimize total refresh traffic. A narrow interval is escaped often (value-initiated refreshes, cost C_vr); a wide one is too imprecise for queries more often (query-initiated refreshes, cost C_qr). Under a model in which these probabilities go as 1/W² and W, the expected cost rate is least where ρ·P_vr = P_qr, ρ = 2C_vr/C_qr, and a rule that widens on value-initiated and narrows on query-initiated refreshes, with probabilities set by ρ, reached within 1% to 5% of the best fixed width in simulation. That the rule converges is argued, not proved. With exact copies required it matched an adaptive exact-caching algorithm, and where imprecision was allowed it beat it. Staleness is priced as refresh traffic only: there is no build cost, no cost of a wrong answer, and the interval is never wrong. | Active — read in full 2026-10-15 from the copy in the University of Pennsylvania’s repository (ScholarlyCommons cis_papers 1351, repository.upenn.edu/server/api/core/bitstreams/92340f91-673c-435e-9b4e-b24072d4d96b/content), the camera-ready text with printed pages 355–366. Worth reading as the one model the record holds in which staleness and upkeep are traded in a single objective: a cached interval of width W is escaped (a pushed refresh, cost C_vr) more often when narrow and is too loose for queries (an exact fetch, cost C_qr) more often when wide, and under the paper’s model the least expected cost is where ρ·P_vr = P_qr with ρ = 2C_vr/C_qr (THEORY-386); a rule that widens on one kind of refresh and narrows on the other came within 1–5% of the best fixed width in simulation and, restricted to exact copies, matched an adaptive cache-or-not algorithm (THEORY-377). For QUESTION-114 it prices staleness as refresh traffic, with no build cost, no stored answers and no cost of a wrong answer, since the source guarantees validity. For CLAIM-303 it gives upkeep and per-use verification a common dial, but only where a source sees every change; for CLAIM-308 its exact-caching case is a forecast-free counting rule justified in expectation, not in the worst case, and once staleness is admitted the two-state choice becomes a continuum with an interior optimum. |
| LIT-1110 | Provenance Semirings | Green et al. (2007), PODS 2007. Annotating each input tuple with an element of a commutative semiring, and computing union and projection with + and join with ·, gives one positive relational algebra (RA+) that is set semantics over the Booleans, bag semantics over the naturals, c-tables over positive Boolean expressions, event tables over sets of outcomes, and lineage over sets of tuple ids. The polynomials N[X] in the tuple ids are the most general such annotation: for any RA+ query and any commutative semiring K, the K-annotated answer is the provenance polynomial evaluated at the input’s K-annotations (Theorem 4.3). For datalog the paper needs ω-continuous semirings and formal power series N∞⟦X⟧, with the analogous factorization (Theorem 6.4) and a criterion for infinite coefficients (Theorem 6.5). Everything is positive: no negation, difference or aggregation, and revaluing inputs can only remove output tuples, never add them; trust and deletion propagation are not treated. | Active — read in full 2026-10-15 (NOTE-913) from the authors’ postprint in the University of Pennsylvania’s ScholarlyCommons repository (repository.upenn.edu/handle/20.500.14332/8764, file pods07.pdf, 10 pp., posted by permission of ACM), found through Unpaywall and OpenAlex (green, submittedVersion) and fetched through the repository’s API because the landing page is script-only. Worth reading as the source of semiring provenance: for positive relational algebra over any commutative semiring the annotated answer is the provenance polynomial in N[X] evaluated at the input annotations, and for datalog over ω-continuous semirings the same holds with formal power series in N∞⟦X⟧ (THEORY-373, THEORY-380). For QUESTION-105 it shows that retaining one polynomial per output suffices for every revision that re-annotates input facts in a commutative semiring, deletion included, without rerunning the query; it proves no minimality, and it excludes added facts, negation and contraction. Its “why-provenance” is one set of contributing tuples per output, coarser than the witness basis of LIT-1104 that it cites as the same notion, and its structure for it fails its own semiring axioms. Deletion propagation and trust are not in the paper; deletion follows from Theorem 4.3 as the record’s application. For CLAIM-293 the polynomial separates joint from alternative support but, like topology, leaves the strengths to the valuation; for CLAIM-306 it has no account of absence. |
| LIT-1111 | Optimal Implementation of Conjunctive Queries in Relational Data Bases | Chandra and Merlin (1977), STOC 1977. Defines conjunctive queries (existentially quantified conjunctions of atoms, no equality, constants naming distinct elements) and proves that two are equivalent exactly when there are homomorphisms each way between their natural models (Lemma 13). Every conjunctive query has a minimal equivalent query, unique up to isomorphism, reached by folding (Theorem 12), and that minimal query yields an evaluation program within a constant factor of optimal in the paper’s cost model (Theorem 16). The hardness results are that evaluating a boolean conjunctive query on a database is NP-complete when the query is part of the input (Theorem 7), and that deciding whether one query is a folding of another is NP-complete (Theorem 11). The paper does not state a containment theorem or the NP-completeness of containment or equivalence as such; both are standard corollaries of Lemma 13’s proof and Theorem 11’s construction, and later papers cite them to it. | Active — read in full 2026-10-15 from a scan of the published STOC 1977 paper (pp. 77–90) hosted in the directory of UBC’s course CPSC 504 (www.cs.ubc.ca/~laks/cpsc504/chandra-merlin-1977.pdf), because ACM’s open-access PDF refused requests from this environment; key statements checked against page images, the OCR layer being poor. Worth reading as the source of the homomorphism criterion for conjunctive queries: two are equivalent iff homomorphisms run both ways between the queries read as small databases (Lemma 13), every one has a minimal equivalent unique up to isomorphism (Theorem 12), and evaluating a conjunctive query with the query as input is NP-complete (Theorem 7), as is recognizing a folding (Theorem 11) (THEORY-371). It states equivalence, not containment, and does not state that containment is NP-complete; both are corollaries later work attributes to it. For CLAIM-303 it gives the base procedure, and the worst-case cost, of deciding that a stored answer covers a new question, in the size of the two descriptions; it says nothing about prose arguments or typical cost. |
| LIT-1112 | Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations | Indyk and Xu (2023), NeurIPS 2023. For DiskANN’s “slow preprocessing” graph (each point linked to the points that survive α-pruning of all other points, naively O(n³) time), greedy search from any start with no backtracking reaches a ((α+1)/(α−1) + ε)-approximate nearest neighbour in O(log_α(∆/((α−1)ε))) steps, each costing O((4α)^d log ∆) for doubling dimension d and aspect ratio ∆; the ratio is tight and the dependence on ∆ cannot be replaced by log n. For DiskANN with its practical “fast preprocessing”, HNSW, NSG and seven other graph indexes, the paper constructs two-dimensional point sets (constant doubling dimension) on which, in experiments with the authors’ code at the authors’ recommended parameters, the search queue must hold about 10% of the points before recall@5 becomes non-zero or the approximation ratio becomes reasonable. The linear lower bounds are empirical, for one query per constructed instance, with an informal Ω(n/R) argument for fast-preprocessing DiskANN; no theorem bounds HNSW or NSG. | Active — read in full 2026-10-15 (NOTE for LIT-1112) from the authors’ arXiv preprint (arxiv.org/abs/2310.19126v1, the only version, which carries the NeurIPS 2023 line and is the camera-ready text), including Appendices A–C. Worth reading as the first worst-case analysis of graph-based nearest neighbour indexes: DiskANN built by “slow preprocessing” (every point pruned against all others with α > 1, naively O(n³)) is proved to give a ((α+1)/(α−1) + ε)-approximate neighbour in O(log_α(∆/((α−1)ε))) greedy steps of cost O((4α)^d log ∆), for doubling dimension d and aspect ratio ∆, with both the ratio and the ∆ dependence shown tight; for DiskANN as implemented, HNSW, NSG and seven others, two-dimensional constructed instances made recall@5 zero or near zero until the search queue held about 10% of the points, an empirical result with no theorem behind it for those algorithms. For CLAIM-310, with LIT-1103, it shows on one fixed point set that the graph built over it, not the points, decides between finding the nearest neighbour in two steps and scanning a tenth of the collection, and that the guarantee rests on a stated property of the arrangement (from every point, some edge gets α times closer to any target); for QUESTION-114 it is a case where an expensive build buys a worst-case guarantee, without a measured break-even or upkeep. |
| LIT-1113 | Semantic Data Caching and Replacement | Dar et al. (1996), VLDB 1996. A client cache described by the selection predicates of past queries can answer a new selection query partly from cache (the probe query, Q ∧ V) and fetch only the rest from the server (the remainder query, Q ∧ ¬V), and can evict by semantic region rather than by page or tuple. In one simulator, one client and one server, read-only selection queries on a single 10,000-tuple relation, this matched page caching on a clustered index, beat it heavily when clustering was bad, answered over 60% of small queries on an unindexed attribute with no server contact, and let a value function based on semantic distance beat LRU on a skewed workload. No replacement rule won everywhere: on regular cyclic paths MRU was best. Everything is measured, nothing is proved; updates, joins, and the CPU cost of reasoning about cache contents were not modelled. | Active — read in full 2026-10-15 from the VLDB Endowment’s copy of the proceedings paper (www.vldb.org/conf/1996/P330.PDF, pp. 330–341, a scan with an OCR layer; tables, formulas and figures read from page images). Worth reading as the source of semantic caching: a cache described by the predicates of past queries answers a new selection query partly from storage (probe, Q ∧ V) and fetches only the remainder (Q ∧ ¬V), and evicts whole query-shaped regions ranked by recency or by distance from the current query (THEORY-376, THEORY-375). All results are from one simulator with one client, one server, read-only selection queries on one relation, and no charge for reasoning about the cache. For CLAIM-303 it shows that reuse of a stored answer can be partial, with savings set by the overlap with the new question, and that the access term c_a takes the form of a containment test the paper does not cost; it says nothing on staleness. For CLAIM-308 and THEORY-348 its replacement rules are forecasts, not break-even rules, and none dominates: distance beat LRU where queries had semantic locality, MRU beat both on regular cycles, and no rule weighs refetch cost. |
| LIT-1114 | Maintaining Views Incrementally | Gupta et al. (1993), SIGMOD 1993. Two algorithms compute the changes to a stored derived relation (a view) from changes to the base relations, without recomputing it. Counting stores, for each derived tuple, the number of its derivations and propagates signed counts through delta rules stratum by stratum; it is stated correct for nonrecursive Datalog or SQL views with stratified negation and aggregation, under set or duplicate semantics, and is argued to cost little beyond evaluating the view. DRed (delete and rederive), for recursive views under set semantics only, deletes an overestimate of what a deletion invalidates, puts back those tuples that still have a derivation from what remains, then adds what insertions derive; it is stated to yield exactly the tuples derivable from the new base. The paper is an extended abstract: the theorems are stated without proof (proofs are referred to a 1992 AT&T report), cost claims are argued, not measured, and there are no experiments. | Active — read in full 2026-10-15 from the ACM’s typeset PDF of the SIGMOD ‘93 extended abstract (pp. 157–166), as posted on Columbia University’s Ph.D. candidacy exam reading list in database systems (www.cs.columbia.edu/~gravano/Qual/Papers/13%20-%20Maintaining%20Views%20Incrementally.pdf); a scan with an OCR layer, so definitions and theorems were read from page images. The full version with the proofs (AT&T Bell Labs TR 921214-19-TM, 1992) was not found. Worth reading as the source of the two standard incremental view maintenance algorithms: counting, which stores one derivation count per derived tuple and is stated correct for nonrecursive views with stratified negation and aggregation under set or duplicate semantics (THEORY-362), and DRed, which for recursive views under set semantics overdeletes, rederives what still has a derivation and then inserts, and is stated to give exactly what the new base derives (THEORY-387). The theorems are stated without proof here, and cost claims are argued, not measured. For QUESTION-105 it shows that, for revisions given as changes to base facts under a fixed program, the retained state can be a count per conclusion when support is acyclic and nothing beyond the materialization when it is not, with support rechecked at revision time; neither is provenance or a record of defeated alternatives. For CLAIM-303 it shows the dependency-tracking cost can sit at derivation time (counting) or at revision time (DRed), without measuring either, and that a view kept this way never goes stale. |
| LIT-1115 | Optimal Aggregation Algorithms for Middleware | Fagin et al. (2001), PODS 2001. 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. | Active — 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. |
| LIT-1116 | Answering Queries Using Views: A Survey | Halevy (2001), VLDB Journal 2001. A survey that separates two problems of answering queries from stored views: finding an equivalent rewriting, which query optimization needs, and finding a maximally-contained rewriting or all certain answers, which data integration needs when sources are incomplete. Its theoretical findings, mostly reported from other papers: an equivalent conjunctive rewriting exists only if one exists no longer than the query, so finding one is NP-complete in the size of the query and view definitions, and checking a candidate is itself NP-complete; the inverse-rules algorithm builds the maximally-contained rewriting, as a possibly recursive datalog program, in time polynomial in the query and views; and finding all certain answers is polynomial in the size of the stored data in many open-world cases, but co-NP-hard in that size under the closed-world assumption even for conjunctive views and queries, or open-world with union in the views or ≠ in the query. Choosing which views to store is left as the next problem; cost-based choice among rewritings is described for practical optimizers, without guarantees. | Active — read in full 2026-10-15 from the publisher’s PDF (VLDB Journal 10: 270–294) hosted on Columbia’s database Ph.D. candidacy-exam reading list (www.cs.columbia.edu/~gravano/Qual/Papers/halevy01.pdf); reference list scanned, not read. Worth reading as the map of answering queries from stored views: equivalent rewritings for optimization against maximally-contained rewritings and certain answers for incomplete sources, with the complexity results of the field as it reports them (THEORY-374). For CLAIM-303 and CLAIM-308 it shows that recognizing reuse is graded: certifying that stored answers settle a question exactly is NP-complete in the size of the question and definitions, extracting what they do give is polynomial (inverse rules) without saying whether it is all, and finding all certain answers from the stored contents is co-NP-hard in their size under the closed-world assumption. For QUESTION-114 it puts this recognition step upstream of view selection, which it names as the open problem. Its results on certain answers and inverse rules are reported from papers the record has not read. |
| LIT-1117 | Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data | Olston and Widom (2000), VLDB 2000. Olston and Widom propose TRAPP: caches hold, for each numeric value, an interval its source guarantees to contain the current value, the source pushing a refresh whenever the value leaves it. A query carries a precision constraint R, and the system chooses which values to fetch exactly so that the answer interval is at most R wide whatever the true values, at least total refresh cost. For SUM (and AVG without a predicate) that choice is a 0/1 knapsack problem, NP-complete in general and polynomial with equal costs; COUNT and MIN have simple rules. Staleness becomes bounded imprecision, never error, and the cost of the source-side upkeep that guarantees this, and of setting the bound widths, is outside the optimization. The one experiment is 90 stock prices with random costs. | Active — read in full 2026-10-15 from the VLDB Endowment’s open copy of the proceedings paper (www.vldb.org/conf/2000/P144.pdf, pp. 144–155; the server needs a browser User-Agent). Worth reading as the source of the idea that a cached value can be held as an interval its source guarantees, so that staleness becomes a bounded, stated imprecision instead of an unknown error, and a query buys precision down by paying for exact reads; for SUM, choosing the cheapest reads that meet a width R is a 0/1 knapsack problem (THEORY-364). For QUESTION-114 it gives staleness a unit (bound width against a query’s tolerance) and prices only the query side: the source’s upkeep that makes the bound a guarantee, and the choice of bound widths, are assumed and uncosted, imprecision is a hard constraint rather than a loss, and a stale read can never be wrong. For CLAIM-303 it sharpens “verification” into a per-use decision against a stated tolerance, but rests on a source that watches every copy, which a filed argument lacks, so it does not price the cost of reusing an obsolete conclusion; it does not bear on CLAIM-308’s rent-or-buy argument. LIT-1109 prices the upkeep side. |
| LIT-1118 | WebView Materialization | Labrinidis and Roussopoulos (2000), SIGMOD 2000. For a page built from database queries, the paper compares three ways to serve it on a server with online updates: compute it on each request (virt), store the query result in the DBMS and refresh it on every update (matdb), or store the finished page as a file at the web server and rewrite it on every update (matweb). It gives a cost model summing access and update costs by their frequencies and states the selection problem (choose a policy per page to minimize mean response time, no space limit, no staleness allowed), but gives no algorithm for it. On one Apache/Informix testbed with cheap indexed queries, matweb answered 10 to 230 times faster than the other two at all loads tried, and matdb was slower than virt whenever there were updates, because reading the stored result cost about as much as recomputing it. Staleness is defined as the delay from update to reply, sketched, and never measured; build cost and storage are outside the model. | Active — read in full 2026-10-15 (NOTE-908) from the authors’ camera-ready copy on the University of Maryland Opsis project page (www.cs.umd.edu/projects/opsis/papers/2000/webviews.pdf, 12 pp., dated 1 March 2000); the ACM Digital Library copy returned 403. Worth reading as the first cost model for choosing, per database-generated web page, between computing it on request, storing the query result in the DBMS, and storing the finished page at the web server, with every stored copy refreshed on each update; on one Apache/Informix testbed the page stored at the web server answered 10 to 230 times faster, and the result stored in the DBMS lost to recomputation whenever there were updates, because reading it cost about as much as rebuilding it. For QUESTION-114 it prices access and upkeep by frequency and adds where the copy is stored, but forbids staleness, has no build cost or storage term, and states the selection problem without an algorithm; for CLAIM-303 it shows filing failing through access cost alone, and upkeep slowing the unfiled reads that share its resource (by 236% in its model check). |
| LIT-1119 | Synchronizing a Database to Improve Freshness | Cho and Garcia-Molina (2000), SIGMOD 2000. For a local copy of N items, each changing as an independent Poisson process with a known rate and refreshed at fixed intervals under a fixed total refresh rate, refreshing every item equally keeps the copy fresher and younger on average than refreshing in proportion to change rate, under any distribution of rates (proved in the technical report by convexity). The freshness-optimal allocation is neither: it rises and then falls with change rate, and gives no refresh at all to items that change too fast for the budget, while the age-optimal allocation rises slowly with change rate. On estimates from 270 web sites, proportional, uniform and optimal refresh give freshness 0.12, 0.57 and 0.62. Every item matters equally, staleness is a time average with no access or query model, the refresh budget is fixed rather than priced, and refresh, change and its detection are free of any other cost. | Active — read in full 2026-10-15 from the conference version as published, the PDF of SIGMOD 2000 pp. 117–128 served by ACM SIGMOD’s SIGMOD Record site for the June 2000 proceedings issue (sigmodrecord.org/publications/sigmodRecord/0006/pdfs/Synchronizing%20a%20Database%20to%20Improve%20Freshness.pdf), with the proofs it defers checked in the authors’ 1999 Stanford technical report as hosted on a KTH course page. Worth reading as the standard definition of a copy’s freshness and age under Poisson change, and for the result that, under a fixed refresh budget, refreshing every item equally beats refreshing in proportion to change rate for any distribution of rates, while the freshness-optimal allocation gives nothing to items that change too fast to follow. For QUESTION-114 it is the first reading that prices staleness instead of forbidding it, but as an objective under a fixed budget, with no reads, no query savings and no build cost, so it supplies the staleness term and not the joint model; for CLAIM-303 it models the re-checking term per unit time and by rate of change, not per use, and does not price the cost of a stale use. |
| LIT-1120 | Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors | Andoni et al. (2017), SODA 2017. For c-approximate near-neighbour search (find a point within cr when one lies within r) over n points in Euclidean space, the paper gives a data structure for every pair of exponents with c²√ρq + (c²−1)√ρu ≥ √(2c²−1), using space n^{1+ρu+o(1)} + O(dn) and query time n^{ρq+o(1)} + dn^{o(1)}, on worst-case data (for Hamming and ℓ_1, c√ρq + (c−1)√ρu ≥ √(2c−1)). It proves the curve cannot be beaten by list-of-points structures, the model of all known data-independent hashing schemes, on random instances, and unconditionally in the cell-probe model only at one end (query n^{o(1)}) for one or two probes. So the exact trade between space spent organizing and per-query time is known within the hashing model; outside that model, for more than two probes, it is not, and data-dependent schemes are covered only by conjecture. | Active — read in full 2026-10-15 from the authors’ arXiv full version (arXiv:1608.03580v2, 21 May 2017, 62 pp.), which merges the two preprints behind the SODA 2017 extended abstract; the SODA text itself was not seen, and the quantum-information steps of the two-probe proof were followed, not checked. Worth reading as the exact time–space curve for approximate near-neighbour search: for every c > 1, space n^{1+ρu+o(1)} and query time n^{ρq+o(1)} whenever c²√ρq + (c²−1)√ρu ≥ √(2c²−1) in Euclidean space (c√ρq + (c−1)√ρu ≥ √(2c−1) in Hamming and ℓ_1), on worst-case data, and optimal for list-of-points (hashing-based) structures on random instances, with unconditional cell-probe matches only for one or two probes at the n^{o(1)}-query end (n^{(c/(c−1))²−o(1)} words). For QUESTION-114 it prices organizing against per-query cost exactly within the hashing model, as replication of each point into n^{ρu} lists against n^{ρq} lists scanned, and its closest-pair remark makes the best point depend on the number of queries; it says nothing about workloads, query mixes, build cost beyond space, exact nearest neighbours or structured data, and data-dependent schemes are covered only by conjecture. For CLAIM-310 it shows overlapping bins are needed for fast similarity queries; for THEORY-340 it gives the similarity analogue of Yao’s lookup floor in the unrestricted cell-probe model at one and two probes; no bearing on THEORY-345 or CLAIM-309. |
| LIT-1158 v4 | A neural algorithm for a fundamental computing problem | Dasgupta, Stevens & Navlakha (2017), Science 358(6364): 793–796. The fly olfactory circuit assigns an odour a tag by a sparse binary random projection from about 50 glomeruli to about 2,000 Kenyon cells, then keeps the top 5% by winner-take-all. Read as locality-sensitive hashing, this beats standard LSH on nearest-neighbour search benchmarks. Unread. | Unfetched — unread, registered 2026-10-14 for QUESTION-120. A reading was attempted on 2026-10-14 and failed on access, not availability: the bioRxiv preprint (10.1101/180471, CC BY-NC-ND) returned HTTP 429 to this client on six tries over twenty minutes, Europe PMC’s full text for it (PPR21674) returned 500, and the Science author referrer link on Dasgupta’s UCSD page returned 403. Science itself is paywalled and OpenAlex lists no other open copy. A browser fetch of the bioRxiv PDF would unblock it. |