Algorithmic Complexity Attacks on Dynamic Learned Indexes

Summary: First systematic study of algorithmic complexity attacks on dynamic learned index ALEX, introducing space and time ACAs that exploit gapped-array layouts, catastrophic-cost mitigation, and model mismatch. Space ACAs use a Multiple-Choice Knapsack-based insertion plan to maximize memory (triggering OOM with only hundreds of adversarial inserts); time ACAs craft pathological insertions that worsen model fit and slow runtime up to 1,641×. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: haaa5bc704b21654f
Venue: VLDB
Year: 2024
Pagerank: 5.3761984e-05
Overall Rank: 8,208 | 44.84%
DOI: 10.14778/3636218.3636232
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Rui Yang (University of Virginia)
2. Evgenios M. Kornaropoulos (George Mason University)
3. Yue Cheng (University of Virginia)

BibTeX Citation

@article{yang_vldb24,
        title = {{Algorithmic Complexity Attacks on Dynamic Learned Indexes}},
        author = {Yang, Rui and Kornaropoulos, Evgenios M. and Cheng, Yue},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {4},
        pages = {780--793},
        doi = {10.14778/3636218.3636232},
        url = {https://doi.org/10.14778/3636218.3636232},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,159	Towards Systematic Index Dynamization	2024	VLDB	5.2161634e-05
9,782	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	5.129066e-05
10,491	Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions	2026	SIGMOD	4.9769913e-05
10,586	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 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.00046363107
78	Automatic Database Management System Tuning Through Large-scale Machine Learning	2017	SIGMOD	0.00036675568
92	CrowdDB: Answering Queries with Crowdsourcing	2011	SIGMOD	0.00034670735
266	Human-powered Sorts and Joins	2012	VLDB	0.00022735106
422	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018488849
458	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017880664
555	SageDB: A Learned Database System	2019	CIDR	0.0001650754
768	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014107655
835	Benchmarking Learned Indexes	2021	VLDB	0.00013575971
869	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013363241
1,188	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011598149
1,525	Updatable Learned Index with Precise Positions	2021	VLDB	0.00010355133
2,270	FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems	2022	VLDB	8.7166469e-05
2,430	Deco: A System for Declarative Crowdsourcing	2012	VLDB	8.4763599e-05
2,582	Are Updatable Learned Indexes Ready?	2022	VLDB	8.2641447e-05
2,861	APEX: A High-Performance Learned Index on Persistent Memory	2022	VLDB	7.9295281e-05
3,621	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	7.1510804e-05
4,362	NFL: Robust Learned Index via Distribution Transformation	2022	VLDB	6.6357559e-05
4,618	The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures	2022	SIGMOD	6.4981355e-05
4,635	PLIN: A Persistent Learned Index for Non-Volatile Memory with High Performance and Instant Recovery	2023	VLDB	6.4904555e-05
5,405	FILM: a Fully Learned Index for Larger-than-Memory Databases	2023	VLDB	6.1435108e-05
7,915	Tastes Great! Less Filling! High Performance and Accurate Training Data Collection for Self-Driving Database Management Systems	2022	SIGMOD	5.4258674e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,525	Updatable Learned Index with Precise Positions	2021	VLDB
2	6,613	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD
3	4,618	The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures	2022	SIGMOD
4	8,382	Tuning Hierarchical Learned Indexes on Disk and Beyond	2022	SIGMOD
5	3,621	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB
6	835	Benchmarking Learned Indexes	2021	VLDB
7	10,500	On Self-Designing Learned Indexes	2026	SIGMOD
8	6,867	Accelerating String-key Learned Index Structures via Memoization-based Incremental Training	2024	VLDB
9	422	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD
10	10,586	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD