Independent Range Sampling

Summary: Dynamic RAM solution for independent range sampling on 1D: O(n) space, O(log n + t) expected query time, O(log n) updates. Static external-memory solution: O(n/B) space, queries in O(log*(n/B)+log_B n+(t/B) log_{M/B}(n/B)) I/Os, with a lower bound showing the multiplicative log_{M/B}(n/B) factor is necessary. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1621
Venue: PODS
Year: 2014
Pagerank: 9.2981095e-05
Overall Rank: 2,203 | 84.68%
DOI: 10.1145/2594538.2594545

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
943	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015145883
4,029	Spatial Online Sampling and Aggregation	2016	VLDB	6.51315e-05
4,596	Fair Near Neighbor Search: Independent Range Sampling in High Dimensions	2020	PODS	6.0590268e-05
5,953	Spatial Independent Range Sampling	2021	SIGMOD	5.2589924e-05
6,462	Algorithmic Techniques for Independent Query Sampling	2022	PODS	5.0536751e-05
8,610	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB	4.4853485e-05
9,632	External Memory Stream Sampling	2015	PODS	4.313481e-05
9,758	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	4.2879116e-05
9,903	Towards Systematic Index Dynamization	2024	VLDB	4.258022e-05
9,949	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	4.2421586e-05
11,285	Approximate Queries over Concurrent Updates	2023	VLDB	4.1945683e-05
11,554	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1945683e-05
11,913	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
14	Online Aggregation	1997	SIGMOD	0.0010801504
739	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00017401518
1,425	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012051353
1,475	Online Maintenance of Very Large Random Samples on Flash Storage	2008	VLDB	0.00011806921
3,991	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS	6.5553055e-05
6,190	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.1645517e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,965	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS	4.1945683e-05
12,105	Space-Efficient Range Reporting for Categorical Data	2012	PODS	4.1945683e-05
8,610	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB	4.4853485e-05
12,106	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	4.1945683e-05
8,546	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	4.4937074e-05
1,766	Indexing Moving Points (Extended Abstract)	2000	PODS	0.000106236
8,767	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.456315e-05
5,953	Spatial Independent Range Sampling	2021	SIGMOD	5.2589924e-05
7,846	Dynamic Top-K Range Reporting in External Memory	2012	PODS	4.6365341e-05
1,182	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013455963