Document retrieval in external memory
summary
Builds an external-memory top-k document-retrieval index by turning suffix-tree document links into a geometric query and then shaving one constraint into a three-sided problem via interval stabbing with priorities. Uses a centroid path decomposition plus a preorder relabeling trick and per-path catalogs, then bootstraps with grouped leaves and fringe trees to drive the additive I/O down. Claims optimal I/Os with only N log* N space (or linear space with a small additive K/B term) and reports successful theoretical bounds for colored range maxima variants.
AI-written summary · about
chapters (10)
- 0:00External memory document retrieval
- 1:10Problem definition and suffix trees
- 3:05Top-k retrieval with relevance scores
- 6:00Overlay links and frequency tracking
- 9:09Query constraints in external memory
- 10:15Three problem formulations
- 12:05Centroid path decomposition
- 15:30Inter-path and co-path links
- 16:15Bootstrapping for optimal I/Os
- 18:07Results and open problems
related talks
29mSpotting Trees with Few Leaves
01h 02mFine-Grained Counting Complexity I
45mTurning Off‑the‑Shelf Tools into a Petabyte‑Scale System
29mColor Coding-Related Techniques
01h 01mExact Algorithms from FPT Algorithms
20mText Search on Images with Quantized ColPali
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)
38mLower Bounds on the Space Complexity of Dynamic Programming