Research map / Learning theory and algorithms / Sample complexity
On Distribution Dependent Sub-Logarithmic Query Time of Learned Indexing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PCA Index with O(n^{1+\epsilon}) space overhead instead of binary search | Rank queries under bounded p.d.f. · Rank queries | expected query time: O(log n) -> O(1) | Helped |
| Use RDA Index with O(n\log n) space overhead instead of binary search | Rank queries under bounded, non-zero p.d.f. · Rank queries | expected query time: O(log n) -> O(log log n) | Helped |
| Use RDS Algorithm with constant space instead of binary search | Rank queries with efficiently computable c.d.f. · Rank queries | expected query time: O(log n) -> O(log log n) | Helped |
Closest papers by meaning
- Learning-Augmented Search Data Structures (ICLR 2025 · similarity 0.87)
- Theoretical Analysis of Learned Database Operations under Distribution Shift through Distribution Learnability (ICML 2024 · similarity 0.86)
- On the Power of Learning-Augmented Search Trees (ICML 2025 · similarity 0.84)
- Discovering Data Structures: Nearest Neighbor Search and Beyond (NeurIPS 2025 · similarity 0.84)
- Towards Establishing Guaranteed Error for Learned Database Operations (ICLR 2024 · similarity 0.83)
- Binary Search with Distributional Predictions (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.