information-retrieval.
19 of 1538 NOTE documents. Back to the full index.
| # | Title | Summary | Status |
|---|---|---|---|
| NOTE-211 v2 | Knowledge Sheaves (sheaf-theoretic KG embedding) | Knowledge-graph embedding can be recast as learning an approximate global section of a cellular sheaf on the schema graph, which subsumes Structured Embedding and TransE/TransR-style models and yields, via harmonic extension, a training-free way to answer composite multi-hop queries. | Superseded — by NOTE-843 |
| NOTE-239 | The Geometry of Information Retrieval | 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. | Read |
| NOTE-242 v2 | Attention Approximates Sparse Distributed Memory | 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). | Read |
| NOTE-779 | Kanerva — Sparse Distributed Memory and Related Models | SDM is a two-layer memory: a fixed random address matrix selects a few of many hard locations near the cue, and an outer-product contents matrix stores the word there. Recall of uniform random data has signal pM against noise pM[1 + pT(1 + p²M)], best at p = (2MT)^−1/3, and capacity tends to 1/[Φ⁻¹(φ)]² of the hard locations, about 0.1 at fidelity 0.999. An ordinary RAM is the special case of radius zero. | Read |
| NOTE-843 | Gebhart, Hansen and Schrater — Knowledge Sheaves | A knowledge-graph embedding is a knowledge sheaf on the schema (one pair of restriction maps per relation type) with a 0-cochain of its pullback to the graph. The summed Structured Embedding score is the sheaf Laplacian form xᵀLx; adding a relation vector gives TransR, and identity maps TransE. Since the zero cochain is always a section, training needs negative triples and a margin. A multi-hop query is scored by harmonic extension, a Schur complement of the query graph’s Laplacian, which beats summing TransE vectors on ip and pi queries. | Read |
| NOTE-904 | Dar, Franklin, Jónsson, Srivastava & Tan — Semantic data caching and replacement | 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. | Read |
| NOTE-905 | Indyk & Motwani — Approximate nearest neighbors: towards removing the curse of dimensionality | 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. | Read |
| NOTE-906 | Cho & Garcia-Molina — Synchronizing a database to improve freshness (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. | Read |
| NOTE-910 | Indyk & Xu — Worst-case performance of popular approximate nearest neighbor search implementations | 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. | Read |
| NOTE-916 | Malkov & Yashunin — Hierarchical navigable small world graphs for approximate nearest neighbour search | 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. | Read |
| NOTE-917 | Beyer, Goldstein, Ramakrishnan & Shaft — When is “nearest neighbor” meaningful? | 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. | Read |
| NOTE-918 | Andoni, Laarhoven, Razenshteyn & Waingarten — Optimal hashing-based time–space trade-offs for approximate near neighbors | 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. | Read |
| NOTE-919 | Weber, Schek & Blott — Similarity search in high-dimensional spaces: when partitioning loses to a scan | 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. | Read |
| NOTE-923 | Kleinberg — The small-world phenomenon: an algorithmic perspective | 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. | Read |
| NOTE-924 | Fagin, Lotem & Naor — Optimal aggregation algorithms for middleware | 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. | Read |
| NOTE-1176 | Blei, Griffiths and Jordan — The nested Chinese restaurant process and hLDA | The nCRP puts a prior on infinitely deep, infinitely branching trees as a nested sequence of CRP partitions, exchangeable in its customers. In hLDA each document is one root-to-leaf path and spreads its words over that path’s topics by a GEM draw, so general topics settle near the root and documents share topics only as shared ancestry. A collapsed Gibbs sampler finds an approximate posterior mode. It recovered eight of ten simulated three-level trees exactly, gave readable hierarchies of JACM, Psychological Review and PNAS abstracts, and beat LDA in held-out likelihood near its own topic count on JACM, by a harmonic-mean estimate. No identifiability result is given: the authors say recovery depends on data size and “how identifiable the topics are”. | Read |
| NOTE-1180 | Rosen-Zvi, Chemudugunta, Griffiths, Smyth and Steyvers — Learning author-topic models from text corpora | Each word of a document is assigned to one of its observed authors uniformly, then to a topic from that author’s distribution over a fixed number of topics, so the document–word matrix factors as ΦΘA with A the known authorship. A blocked collapsed Gibbs sampler fits it to NIPS, CiteSeer and 121,298 Enron emails. On NIPS it beats LDA in perplexity only while sixteen or fewer of a test document’s words are seen, and a per-document fictitious author helps throughout. Topics are identified only up to permutation, by the authors’ account, and about 80 of 100 aligned across two runs. Authorship is given, never inferred. | Read |
| NOTE-1454 | Flynn, Kanerva & Bhadkamkar — SDM principles and operation | Kanerva and co-authors state SDM’s critical distance in words and do not derive it: a cue within it converges on the stored pattern under iterated reads, a cue beyond it wanders and may settle on another pattern, the distance shrinks as the memory fills, and in a sparsely filled memory it is below the sum of the write and read radii. For single patterns convergence and divergence are “easy to distinguish in practice”; for stored sequences they are not. The rest of the report is a hardware design. | Skimmed |
| NOTE-1460 | Mitra, Singhal & Buckley — Improving automatic query expansion | Pseudo-relevance feedback expands a short query with terms from its top-ranked documents, and hurts when those documents are off-topic: the authors name the harm query drift, “the alteration of the focus of a search topic caused by improper expansion”. Reranking the top documents before feedback, by hand-made Boolean filters or by an automatic score that rewards matches on uncorrelated query terms, raises average precision over plain expansion on TREC 3–6, by 7–22% for the manual and 6–13% for the automatic method, and cuts the queries that expansion hurts from 64 of 199 to 43 or 50. | Read |