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: 13754
Venue: VLDB
Year: 2024
Pagerank: 4.4671214e-05
Overall Rank: 8,668 | 39.76%
DOI: 10.14778/3636218.3636232

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,902	Towards Systematic Index Dynamization	2024	VLDB	4.2539423e-05
10,038	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	4.1905499e-05
10,087	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD	4.1905499e-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
94	CrowdDB: Answering Queries with Crowdsourcing	2011	SIGMOD	0.00051273089
101	The Case for Learned Index Structures	2018	SIGMOD	0.00049778866
183	Automatic Database Management System Tuning Through Large-scale Machine Learning	2017	SIGMOD	0.00036859633
266	Human-powered Sorts and Joins	2012	VLDB	0.00029884758
796	SageDB: A Learned Database System	2019	CIDR	0.00016541749
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,365	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00012379754
1,438	Benchmarking Learned Indexes	2021	VLDB	0.00011965956
1,464	Learning Multi-dimensional Indexes	2020	SIGMOD	0.0001184772
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,814	Deco: A System for Declarative Crowdsourcing	2012	VLDB	8.0807229e-05
3,136	FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems	2022	VLDB	7.4926368e-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
5,072	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	5.7121108e-05
5,310	The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures	2022	SIGMOD	5.5713508e-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
6,488	FILM: a Fully Learned Index for Larger-than-Memory Databases	2023	VLDB	5.0378878e-05
8,036	Tastes Great! Less Filling! High Performance and Accurate Training Data Collection for Self-Driving Database Management Systems	2022	SIGMOD	4.5965825e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,038	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	4.1905499e-05
2,550	Updatable Learned Index with Precise Positions	2021	VLDB	8.5569576e-05
7,389	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	4.7386163e-05
5,310	The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures	2022	SIGMOD	5.5713508e-05
8,811	Tuning Hierarchical Learned Indexes on Disk and Beyond	2022	SIGMOD	4.4398976e-05
5,072	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	5.7121108e-05
1,438	Benchmarking Learned Indexes	2021	VLDB	0.00011965956
8,079	Accelerating String-key Learned Index Structures via Memoization-based Incremental Training	2024	VLDB	4.5873372e-05
819	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00016237497
10,087	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD	4.1905499e-05