Practical Dynamic Extension for Sampling Indexes

Summary: Dynamic framework for shard-based sampling indexes with periodic rebuilds to support updates. Extends three static sampling indexes, enabling updates via shard decomposition and periodic rebuild, and analyzes concurrency and memory implications. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h790c2273591affa5
Venue: SIGMOD
Year: 2023
Pagerank: 5.2517412e-05
Overall Rank: 8,953 | 39.83%
DOI: 10.1145/3626744

Incoming Non-self Citations Over Time

Authors

1. Douglas B. Rumbaugh (Pennsylvania State University)
2. Dong Xie (Pennsylvania State University)

BibTeX Citation

@inproceedings{rumbaugh_sigmod23,
        title = {{Practical Dynamic Extension for Sampling Indexes}},
        author = {Rumbaugh, Douglas B. and Xie, Dong},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3626744},
        url = {https://dl.acm.org/doi/10.1145/3626744},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,121	LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR	2024	SIGMOD	5.8779092e-05
9,159	Towards Systematic Index Dynamization	2024	VLDB	5.2161634e-05
10,469	FIRAS: A Framework for Interval Range Search and Sampling	2026	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
175	Simple Random Sampling from Relational Databases	1986	VLDB	0.00026776696
400	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00019124757
478	Random Sampling from B+ trees	1989	VLDB	0.00017625093
753	Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging	2018	SIGMOD	0.00014232329
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.0001409096
841	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00013543
889	SuRF: Practical Range Query Filtering with Fast Succinct Tries	2018	SIGMOD	0.00013243846
1,422	The Log-Structured Merge-Bush & the Wacky Continuum	2019	SIGMOD	0.00010720711
2,003	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.2071735e-05
2,495	Independent Range Sampling	2014	PODS	8.3834888e-05
2,664	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	8.1532061e-05
2,868	Spooky: Granulating LSM-Tree Compactions Correctly	2022	VLDB	7.9205462e-05
3,692	Fair Near Neighbor Search: Independent Range Sampling in High Dimensions	2020	PODS	7.090312e-05
4,306	The Adversarial Robustness of Sampling	2020	PODS	6.6735594e-05
5,641	Algorithmic Techniques for Independent Query Sampling	2022	PODS	6.0536966e-05
5,821	Spatial Independent Range Sampling	2021	SIGMOD	5.9804424e-05
6,687	Query Sampling in DB2 Universal Database	2004	SIGMOD	5.7060981e-05
8,560	Sampling Big Ideas in Query Optimization	2023	PODS	5.3133806e-05
9,910	External Memory Stream Sampling	2015	PODS	5.1082848e-05
10,317	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	5.0363234e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,582	Are Updatable Learned Indexes Ready?	2022	VLDB
2	6,751	Progressive Indexes: Indexing for Interactive Data Analysis	2019	VLDB
3	242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB
4	11,957	Index-Based Join Size Estimation Using Adaptive Sampling	2021	SIGMOD
5	7,157	Adaptive Hybrid Indexes	2022	SIGMOD
6	9,110	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
7	9,601	Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs	2024	SIGMOD
8	11,371	Benchmarking Adaptive Multidimensional Indices	2025	VLDB
9	9,159	Towards Systematic Index Dynamization	2024	VLDB
10	8,747	Modeling High-Dimensional Index Structures using Sampling	2001	SIGMOD