Database Paper Browser

Back to papers

FITing-Tree: A Data-aware Index Structure

Summary: FITing-Tree presents a data-aware index that uses piecewise-linear approximations bounded by a tunable error. A cost model selects the error to balance lookup latency and storage, delivering near full-index performance with orders of magnitude less memory on real datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5673
Venue
SIGMOD
Year
2019
Pagerank
0.00012379754
Overall Rank
1,365 | 90.52%
DOI
10.1145/3299869.3319860

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 64 citing papers.

Rank Citing Paper Year Venue Pagerank
819 ALEX: An Updatable Adaptive Learned Index 2020 SIGMOD 0.00016237497
844 The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds 2020 VLDB 0.00015964123
1,438 Benchmarking Learned Indexes 2021 VLDB 0.00011965956
1,887 Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads 2021 VLDB 0.00010201938
2,550 Updatable Learned Index with Precise Positions 2021 VLDB 8.5569576e-05
2,676 Effectively Learning Spatial Indices 2020 VLDB 8.326321e-05
3,136 FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems 2022 VLDB 7.4926368e-05
3,419 LeCo: Lightweight Compression via Learning Serial Correlations 2024 SIGMOD 7.1127752e-05
3,614 SNARF: A Learning-Enhanced Range Filter 2022 VLDB 6.9124805e-05
3,777 Instance-Optimized Data Layouts for Cloud Analytics Workloads 2021 SIGMOD 6.7713324e-05
3,801 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 6.7528979e-05
3,945 APEX: A High-Performance Learned Index on Persistent Memory 2022 VLDB 6.605467e-05
4,056 Are Updatable Learned Indexes Ready? 2022 VLDB 6.4905689e-05
4,086 The Case for a Learned Sorting Algorithm 2020 SIGMOD 6.4579358e-05
4,377 HUNTER: An Online Cloud Database Hybrid Tuning System for Personalized Requirements 2022 SIGMOD 6.2331947e-05
4,404 TreeLine: An Update-In-Place Key-Value Store for Modern Storage 2023 VLDB 6.2052645e-05
4,830 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 5.8884997e-05
5,072 Learned Index: A Comprehensive Experimental Evaluation 2023 VLDB 5.7121108e-05
5,154 Hist-Tree: Those Who Ignore It Are Doomed to Learn 2021 CIDR 5.6548237e-05
5,250 One Model to Rule them All: Towards Zero-Shot Learning for Databases 2022 CIDR 5.6007779e-05
5,310 The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures 2022 SIGMOD 5.5713508e-05
5,327 DILI: A Distribution-Driven Learned Index 2023 VLDB 5.5660777e-05
5,601 PLIN: A Persistent Learned Index for Non-Volatile Memory with High Performance and Instant Recovery 2023 VLDB 5.4158958e-05
5,655 NFL: Robust Learned Index via Distribution Transformation 2022 VLDB 5.3877506e-05
5,769 Oasis: An Optimal Disjoint Segmented Learned Range Filter 2024 VLDB 5.3326049e-05
5,868 GRF: A Global Range Filter for LSM-Trees with Shape Encoding 2024 SIGMOD 5.2928769e-05
5,925 HMAB: Self-Driving Hierarchy of Bandits for Integrated Physical Database Design Tuning 2023 VLDB 5.2669029e-05
6,298 Towards instance-optimized data systems 2021 VLDB 5.1182917e-05
6,442 Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices 2023 SIGMOD 5.0541252e-05
6,488 FILM: a Fully Learned Index for Larger-than-Memory Databases 2023 VLDB 5.0378878e-05
6,723 A Critical Analysis of Recursive Model Indexes 2022 VLDB 4.9449538e-05
6,806 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 4.917024e-05
6,883 PilotScope: Steering Databases with Machine Learning Drivers 2024 VLDB 4.8918682e-05
7,389 Making In-Memory Learned Indexes Efficient on Disk 2024 SIGMOD 4.7386163e-05
7,392 MOST: Model-Based Compression with Outlier Storage for Time Series Data 2023 SIGMOD 4.737456e-05
7,870 SALI: A Scalable Adaptive Learned Index Framework based on Probability Models 2023 SIGMOD 4.6271153e-05
8,079 Accelerating String-key Learned Index Structures via Memoization-based Incremental Training 2024 VLDB 4.5873372e-05
8,100 Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction 2024 SIGMOD 4.5821762e-05
8,221 Sieve: A Learned Data-Skipping Index for Data Analytics 2023 VLDB 4.5511941e-05
8,624 Limousine: Blending Learned and Classical Indexes to Self-Design Larger-than-Memory Cloud Storage Engines 2024 SIGMOD 4.4786127e-05
8,653 Adaptive Hybrid Indexes 2022 SIGMOD 4.4696663e-05
8,668 Algorithmic Complexity Attacks on Dynamic Learned Indexes 2024 VLDB 4.4671214e-05
8,811 Tuning Hierarchical Learned Indexes on Disk and Beyond 2022 SIGMOD 4.4398976e-05
8,952 One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting 2024 SIGMOD 4.4195459e-05
9,290 PriPL-Tree: Accurate Range Query for Arbitrary Distribution under Local Differential Privacy 2024 VLDB 4.358174e-05
9,351 Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs 2024 SIGMOD 4.3490308e-05
9,618 A New Paradigm in Tuning Learned Indexes: A Reinforcement Learning Enhanced Approach 2025 SIGMOD 4.3131993e-05
9,745 Why Are Learned Indexes So Effective but Sometimes Ineffective? 2025 VLDB 4.2856385e-05
9,891 DBMS Fitting: Why should we learn what we already know? 2020 CIDR 4.2573619e-05
9,947 SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index 2026 SIGMOD 4.2391999e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
44 The Design Of Postgres 1986 SIGMOD 0.00071946446
101 The Case for Learned Index Structures 2018 SIGMOD 0.00049778866
367 Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing 1998 VLDB 0.00025518228
382 FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs 2010 SIGMOD 0.00024888997
407 Database Cracking 2007 CIDR 0.00023941779
608 Monkey: Optimal Navigable Key-Value Store 2017 SIGMOD 0.00019233548
821 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00016232579
1,033 Bitmap Index Design and Evaluation 1998 SIGMOD 0.0001453376
1,212 RDF-3X: a RISC-style Engine for RDF 2008 VLDB 0.00013255692
1,300 Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes 2016 SIGMOD 0.00012711153
1,909 BF-Tree: Approximate Tree Indexing 2014 VLDB 0.00010123661
1,955 Performance Measurements of Compressed Bitmap Indices 1999 VLDB 9.9641178e-05
2,046 Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units 2011 VLDB 9.6922338e-05
2,141 Online Piece-wise Linear Approximation of Numerical Streams with Precision Guarantees* 2009 VLDB 9.4561227e-05
2,841 Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies 2009 VLDB 8.0396876e-05
3,906 Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems 2017 VLDB 6.6413008e-05
4,020 Revisiting Reuse for Approximate Query Processing 2017 VLDB 6.5209063e-05
5,118 Design Tradeoffs of Data Access Methods 2016 SIGMOD 5.6781464e-05
5,341 UpBit: Scalable In-Memory Updatable Bitmap Indexing 2016 SIGMOD 5.5592799e-05
Previous Page 1 / 1 Next

Semantically Similar Papers