NFL: Robust Learned Index via Distribution Transformation

Summary: NFL: a two-stage learned index that first applies Numerical Normalizing Flow to transform skewed key distributions into near-uniform, then builds the index on transformed keys. Introduces After-Flow Learned Index (AFLI) for robustness, with experiments showing higher throughput and lower tail latency than state-of-the-art learned indexes on synthetic and real workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hcb14c5c13f6950cf
Venue: VLDB
Year: 2022
Pagerank: 6.613814e-05
Overall Rank: 4,385 | 70.61%
DOI: 10.14778/3547305.3547322
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Shangyu Wu (City University of Hong Kong)
2. Yufei Cui (City University of Hong Kong)
3. Jinghuan Yu (City University of Hong Kong)
4. Xuan Sun (City University of Hong Kong)
5. Tei-Wei Kuo (National Taiwan University)
6. Chun Jason Xue (City University of Hong Kong)

BibTeX Citation

@article{wu_vldb22,
        title = {{NFL: Robust Learned Index via Distribution Transformation}},
        author = {Wu, Shangyu and Cui, Yufei and Yu, Jinghuan and Sun, Xuan and Kuo, Tei-Wei and Xue, Chun Jason},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {10},
        pages = {2188--2200},
        doi = {10.14778/3547305.3547322},
        url = {https://doi.org/10.14778/3547305.3547322},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,632	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	7.1274345e-05
4,389	DILI: A Distribution-Driven Learned Index	2023	VLDB	6.6111249e-05
5,397	Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices	2023	SIGMOD	6.1347527e-05
6,622	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	5.7136886e-05
6,802	SALI: A Scalable Adaptive Learned Index Framework based on Probability Models	2023	SIGMOD	5.6623052e-05
6,889	Accelerating String-key Learned Index Structures via Memoization-based Incremental Training	2024	VLDB	5.6393954e-05
8,223	Algorithmic Complexity Attacks on Dynamic Learned Indexes	2024	VLDB	5.3584214e-05
8,903	Why Are Learned Indexes So Effective but Sometimes Ineffective?	2025	VLDB	5.238416e-05
9,814	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	5.1121061e-05
10,417	Replace or Augment: Rethinking the Role of Learned Indexes in Relational Databases	2027	VLDB	4.9605343e-05
10,552	LINE: A Learned Index with Group-Enhanced Leaves and Cache-Optimized Inner Tree	2026	SIGMOD	4.9605343e-05
10,557	Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions	2026	SIGMOD	4.9605343e-05
10,566	On Self-Designing Learned Indexes	2026	SIGMOD	4.9605343e-05
10,649	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD	4.9605343e-05
11,191	VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity	2025	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046249672
427	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018429918
461	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017835351
670	SharedDB: Killing One Thousand Queries With One Stone	2012	VLDB	0.00014929358
774	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014063511
870	Learning Multi-dimensional Indexes	2020	SIGMOD	0.0001332034
1,190	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011564169
1,232	BatchDB: Efficient Isolated Execution of Hybrid OLTP+OLAP Workloads for Interactive Applications	2017	SIGMOD	0.00011406847
1,445	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	0.00010607118
1,529	Updatable Learned Index with Precise Positions	2021	VLDB	0.00010320909
2,237	Shared Workload Optimization	2014	VLDB	8.7777395e-05
2,247	Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?	2019	SIGMOD	8.7591557e-05
2,870	APEX: A High-Performance Learned Index on Persistent Memory	2022	VLDB	7.9033232e-05
5,807	OLTPShare: The Case for Sharing in OLTP Workloads	2018	VLDB	5.9709922e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,566	On Self-Designing Learned Indexes	2026	SIGMOD
2	9,627	Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs	2024	SIGMOD
3	10,552	LINE: A Learned Index with Group-Enhanced Leaves and Cache-Optimized Inner Tree	2026	SIGMOD
4	2,590	Are Updatable Learned Indexes Ready?	2022	VLDB
5	4,389	DILI: A Distribution-Driven Learned Index	2023	VLDB
6	9,814	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD
7	10,649	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD
8	6,622	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD
9	3,632	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB
10	834	Benchmarking Learned Indexes	2021	VLDB