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.
Information retrieval — finding what is relevant to a need — document and query representation, relevance and aboutness, ranking and feedback, and the geometric, probabilistic and logical models of retrieval.
23 of 2004 LIT documents. Back to the full index.
| # | Title | Summary | Status |
|---|---|---|---|
| LIT-232 v2 | Knowledge Sheaves: A Sheaf-Theoretic Framework for Knowledge Graph Embedding | Gebhart, Hansen and Schrater (2021; AISTATS 2023), ARXIV-2110.03789. A knowledge-graph embedding is a cellular sheaf of vector spaces on the schema graph, with restriction maps per relation type, plus a 0-cochain of its pullback to the knowledge graph. The summed Structured Embedding score is the sheaf Laplacian form, and TransE, TransR and RotatE are special cases; bilinear models are not. Since the zero cochain is always a section, training needs negatives and a margin. Composite multi-hop queries are scored without extra training by harmonic extension, a Schur complement, which beats naive TransE summation on ip and pi queries in untuned experiments. | Active — read 2026-10-14 (NOTE-843) in full; worth reading as the clean dictionary between coboundary-type knowledge-graph scores (Structured Embedding, TransE, TransR, RotatE) and cellular sheaves on the schema, with the summed score as a sheaf Laplacian form and multi-hop queries scored by harmonic extension, a Schur complement. Read it knowing that bilinear models fall outside it, that the zero cochain is always a section so all content is in the contrastive margin, that “approximate global section” means only small Laplacian energy, and that the experiments are preliminary, untuned and well below query-embedding baselines. It shares the word “sheaf” with the contextuality line and nothing else of substance. The account is THEORY-299. |
| LIT-262 v2 | The Geometry of Information Retrieval | van Rijsbergen (2004), DOI-10.1017/CBO9780511543333. The book recasts IR’s vector-space, probabilistic and logical models in one Hilbert-space language. Documents are state vectors. Relevance and aboutness are Hermitian observables that need not commute. Subspaces carry a non-distributive logic whose conditional is shown to be a Stalnaker conditional equal to the Sasaki hook (ch. 5). Gleason’s theorem makes tr(ρP) the probability of a subspace, which ch. 6 uses to rewrite cosine matching, cluster representatives, relevance and pseudo-relevance feedback, dynamic clustering and ostensive retrieval. It is a proposed language, not a tested model: no experiment is reported, and its “content hypothesis” that the probability of a concept is cos²θ is argued, not tested. | Active — read in full 2026-09-27 (NOTE-239); worth reading as the founding statement of the Hilbert-space (quantum-probability) programme in IR. It is short, self-contained and mathematically careful at the level it works at, and its ch. 5 proof that the subspace conditional is a Stalnaker conditional and its ch. 6 trace-formula recastings of standard IR operations are the parts to take away. Read it as a language, not as evidence: it reports no experiment, and every IR payoff it names is a reformulation or a research direction. |
| LIT-269 v2 | Attention Approximates Sparse Distributed Memory | Bricken & Pehlevan (2021), ARXIV-2111.05498. Kanerva’s SDM read weights each stored pointer by the number of neurons in the intersection of two Hamming balls of radius d. The paper shows that this weight is roughly log-linear in Hamming distance for close patterns. As a result, with L²-normalised vectors and a regression-fitted β, softmax attention reproduces SDM’s retrieval behaviour on random and learnt-projection data (App. B.7). Two things are weaker than they look. The analytic derivation (App. B.2, Eqs. 16–21) gets the exponent wrong: by my recomputation its β is ≈2–2.5× too small. The biological case is Kanerva’s 1988 cerebellar mapping, restated rather than re-argued. It also needs r = 2⁶⁴ ≈ 1.8×10¹⁹ neurons in the Attention setting, which the paper itself calls “biologically implausible” (App. B.5). | Active — read in full 2026-09-27 (NOTE-242); worth reading as the clearest statement of the SDM–attention correspondence. Its exact circle-intersection formula and its eight-algorithm convergence comparison are the parts to take away. Treat its analytic exponential derivation, its GPT-2 “confirmation” and its cerebellar implementation of attention as argument, not demonstration. |
| LIT-316 v4 | Quantum Models of Cognition and Decision | Busemeyer & Bruza (2012), DOI-10.1017/CBO9780511997716. Per publisher description: a book-length introduction to modelling human cognition and decision-making with the probability and dynamics of quantum theory, applied to judgment paradoxes, decision-making, concept combination and memory, as an alternative to classical (Kolmogorov) probability models. | Unavailable — filed 2026-09-29 from metadata and published descriptions, not read: no lawful full text has been reachable. Tried again on 2026-10-09 at the owner’s request (manuscript bibliography of that day): OpenAlex still reports it closed, the Internet Archive and HathiTrust hold no copy, Open Library lists no e-book, and Cambridge’s excerpt PDF reset the connection. No NOTE is filed. It stays Unavailable until a copy is supplied. |
| LIT-921 v2 | Sparse Distributed Memory and Related Models | Kanerva (1992), RIACS TR 92.10, in Hassoun (ed.) 1993. SDM restated as a matrix memory, with the RAM as its zero-radius case, and related to correlation-matrix memories, feed-forward nets, the cerebellar cortex and the models of Marr and Albus. For uniform random data and exact cues it gives bit fidelity, the optimal activation p = (2MT)^−1/3 and a capacity near a tenth of the hard locations. Also held in the anthology as ANTH-LIT-669. | Active — read 2026-10-14 (NOTE-779) in full; worth reading as the compact statement of sparse distributed memory in matrix form, with the ordinary RAM as its zero-radius special case and a simple signal-to-noise analysis: fidelity Φ(ρ) with ρ² = pM/[1 + pT(1 + p²M)], best at p = (2MT)^−1/3, and capacity near a tenth of the hard locations at fidelity 0.999. Read it knowing that every number assumes uniform random data and exact retrieval cues, that the noisy-cue case and the critical distance are not analysed here, and that it relates SDM to the Hopfield net only through a cited capacity comparison. |
| LIT-928 v3 | Sparse Distributed Memory | Kanerva (1988), MIT Press. An associative memory in a high-dimensional binary space, addressed by content: a pattern is written to every hard location within a radius of its address and read back from the locations within that radius of a cue. Iterated reads converge on a stored pattern only from cues within a critical distance of it. Also held in the anthology as ANTH-LIT-666. Not read here. | Unavailable — searched 2026-10-14 for a lawful full text, none reached, so it is not read and no NOTE is filed. The book has no DOI; the MIT Press page and MIT Press Direct returned Cloudflare 403 checks, and no open-access edition was found; the Internet Archive has no scan of the book; NASA’s Technical Reports Server holds Kanerva’s public-domain RIACS and Stanford reports on SDM, which are different works (LIT-921 is one of them). What the book says about cues beyond the critical distance, which CLAIM-180 leans on, is therefore still unchecked here. It stays Unavailable until a copy is supplied. |
| LIT-1079 v3 | Improving automatic query expansion | Mitra, Singhal and Buckley (1998), SIGIR. Names query drift, “the alteration of the focus of a search topic caused by improper expansion”, and traces it in pseudo-relevance feedback to off-topic documents among the top-ranked: expansion then pulls the query toward one aspect of the topic. Reranking the top documents before feedback, by manual Boolean filters or an automatic term-correlation score, cuts the queries expansion hurts from 64 of 199 to 43–50 and improves average precision over plain expansion on TREC 3–6. | Active — read 2026-10-30 (NOTE-1460) in full, from the ACM proceedings text re-hosted by SciSpace (https://typeset.io/pdf/improving-automatic-query-expansion-cmfn0svc0j.pdf), a copy the owner ruled lawful on 2026-10-30; worth reading as the source of the term query drift, “the alteration of the focus of a search topic caused by improper expansion”, with its cause (off-topic documents at the top of a blind-feedback set) and a measure of how often expansion hurts. Read it knowing that its remedy is to rerank the feedback documents, that it is tested only on TREC 3–6 with SMART, and that it reports no significance tests. |
| LIT-1098 | Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs | Malkov and Yashunin (2020), IEEE TPAMI 2020. HNSW is a stack of proximity graphs on nested random subsets of the data. Each element’s top layer is drawn from a geometric distribution, and new neighbours are chosen by a pruning rule that favours diverse directions. Searching from the sparse top layer down makes per-query cost grow about logarithmically with N on uniform random data in 4 and 8 dimensions, which flat NSW graphs did not. The logarithmic bound is derived only for exact Delaunay graphs of bounded mean degree, which HNSW does not build. For the graphs it does build, logarithmic scaling is measured, at low dimension only, and on 200M SIFT vectors the paper reports the scaling “deviates from the pure logarithm”. The neighbour-selection rule is what keeps clustered data searchable: in the paper’s synthetic test with 100 isolated clusters, linking each element to its nearest neighbours fails to reach high recall. There is no worst-case or recall guarantee, no deletion, and no analysis of query distributions unlike the data. | Active — read in full 2026-10-15 from the authors’ arXiv preprint, version 4 of 14 August 2018 (arxiv.org/pdf/1603.09320v4, 13 pp., the last arXiv version, whose abstract matches the published one apart from copy-editing; the TPAMI body was not seen). Version 1 (2016) was compared: it claimed deletion, which v4 drops and lists as future work. Unpaywall and OpenAlex list no open-access copy of the TPAMI version. Worth reading as the source of the hierarchical graph index: nested proximity graphs on geometrically sampled layers, with a neighbour rule that keeps links between clusters. Its logarithmic search cost is derived only for exact Delaunay graphs of bounded degree, which it does not build, and is measured only on uniform random data in 4 and 8 dimensions; on 200M SIFT the scaling “deviates from the pure logarithm”. It gives no worst-case or recall guarantee and no deletion. For CLAIM-310 it shows, with bins replaced by graphs, that the arrangement of fixed data under a fixed distance decides cost and, on clustered data, whether items can be found at all; it narrows part 2, since the index is built without any query mix and every test drew its queries from the data. For QUESTION-114 it supplies a measured build-time against query-time curve and O(N log N) construction argued at low dimension, with insertion upkeep only. |
| 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-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-1103 | The Small-World Phenomenon: An Algorithmic Perspective | Kleinberg (2000), STOC 2000. On an n × n lattice where each node also gets q long-range links drawn with probability proportional to d^(−r), short paths exist for r = 0, but no algorithm that sees only the links of nodes the message has visited finds them faster than about n^(2/3) steps in expectation. At r = 2 the greedy rule (pass to the contact nearest the target in lattice distance) delivers in O((log n)²) expected steps (proved for p = q = 1); for 0 ≤ r < 2 every such algorithm needs Ω(n^((2−r)/3)) and for r > 2 Ω(n^((r−2)/(r−1))). So efficient decentralized search depends on how the long-range links are distributed relative to the lattice, not on the links’ existence or on the graph’s diameter. The k-dimensional version (r = k) is stated without proof, and the model is a lattice with a known distance that every node can compute to the target. | Active — read in full 2026-10-15 (NOTE for LIT-1103) from the author’s own copy on Kleinberg’s Cornell page (www.cs.cornell.edu/home/kleinber/swn.pdf), a 14-page manuscript linked there under the STOC 2000 citation and footnoted as the version that is also Cornell CS Technical Report 99-1776; the ACM typeset proceedings (pp. 163–170) returned 403, and the Nature 2000 letter is a different work, not read. Worth reading as the source of the result that a network can have short paths that no searcher using local information can find: on an n × n lattice with long-range links drawn with probability proportional to d^(−r), greedy routing delivers in O((log n)²) expected steps at r = 2 (proved for one local and one long-range contact per node), every decentralized algorithm needs Ω(n^((2−r)/3)) steps for 0 ≤ r < 2 and Ω(n^((r−2)/(r−1))) for r > 2, and r = k in k dimensions is stated without proof. For CLAIM-310 it shows that findability, with nodes, lattice and link count fixed, turns on how the links are arranged relative to a distance every node can compute, which supports the claim’s “as arrangements” half; it narrows “only one distribution” to this family of inverse power laws and to polylogarithmic delivery, and it prices no cost of building the arrangement, so it adds nothing to QUESTION-114’s organizing 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-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-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-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. |
| LIT-1542 v2 | The nested Chinese restaurant process and Bayesian nonparametric inference of topic hierarchies | Blei, Griffiths & Jordan (2010), J. ACM 57(2). The nested Chinese restaurant process (nCRP) assigns probability distributions to infinitely deep, infinitely branching trees and serves as a prior in a nonparametric model of document collections: each document is a path down a random tree, its words are allocated to levels along the path, and the nCRP’s preferential attachment clusters documents by topics shared at several levels of abstraction. Posterior inference over trees, topics and allocations is demonstrated on scientific abstracts. | Active — read 2026-10-26 (NOTE-1176) in full, from arXiv 0710.0845v3, the authors’ revision; worth reading for the nested Chinese restaurant process as a prior on trees of unbounded depth and branching (THEORY-969), for hLDA’s single-path model of a document and what that does to overlap, and for a careful simulated-recovery test (THEORY-1010). Read it knowing that §5.1’s level conditional does not match §2.4’s parameterization of the GEM and §6.2’s hyperparameters are out of range as printed, that it has no identifiability result, that its comparison with LDA rests on harmonic-mean estimates on one corpus (THEORY-989, Proposed), and that the typeset JACM text was not compared. |
| LIT-1546 v2 | Learning author-topic models from text corpora | Rosen-Zvi, Chemudugunta, Griffiths, Smyth & Steyvers (2010), ACM TOIS 28(1). Each author is a probability distribution over topics and each topic a distribution over words; a multi-author document mixes its authors’ topic distributions. Both are learned by MCMC and applied to CiteSeer abstracts, NIPS papers and 121,000 Enron emails, with perplexity and retrieval experiments showing systematic differences from alternatives. | Active — read 2026-10-26 (NOTE-1180) in full, from the typeset article on Griffiths’s lab page at Princeton; worth reading for the author–topic model as the plain-text case of members’ overlapping participation in themes, for its factorization of the document–word matrix as ΦΘA (THEORY-972), and for the measured trade between pooling by author and per-document flexibility (THEORY-1003). Read it knowing that authorship is observed, never inferred, that the number of topics and the hyperparameters are fixed, that an author’s topics are proportions summing to one, that identifiability is claimed only up to permutation when the likelihood allows a continuum, and that its readings of Enron employees’ roles are by inspection. |
| LIT-1848 | Sparse Distributed Memory: Principles and Operation | Flynn, Kanerva & Bhadkamkar (1989), RIACS TR 89.53 / Stanford CSL-TR-89-400. A non-mathematical account of sparse distributed memory and the design of a Stanford prototype (256-bit words, 8,192 hard locations, up to 16 folds, 50 reads or writes a second). A word is written to every hard location within a Hamming radius of its address and read by summing and thresholding the counters of the locations near a cue. Used autoassociatively, a cue within a critical distance of a stored pattern converges on it in about ten iterated reads; beyond it the reads wander and may settle on another pattern. The critical distance falls as the memory fills and, in a sparsely filled memory, is below the sum of the write and read radii. The mathematics is referred to Kanerva’s book. | Active — read 2026-10-30 (NOTE-1454), Skimmed: chapter 1 in full (pp. 1–28) and chapters 2–3 looked over, from NASA’s public-domain NTRS copy (ntrs.nasa.gov/api/citations/19920001076/downloads/19920001076.pdf, 60 scanned pages with an OCR text layer). Worth reading as a short, first-hand statement by Kanerva and two co-authors of what SDM’s critical distance is: a cue closer than it is pulled toward the stored pattern by iterated reads; one farther away “will not converge” and wanders, possibly into another pattern’s attracting zone; the distance shrinks as the memory fills; and in an autoassociative memory the two outcomes are “easy to distinguish in practice”. Read it knowing that the critical distance is asserted, not derived (the derivation is referred to Kanerva’s book, LIT-928, still unread), that no simulation data are given for the convergence figures, and that most of the report describes the Stanford hardware prototype. |