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.2896559e-05
Overall Rank: 2,207 | 84.67%
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
941	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015147831
4,032	Spatial Online Sampling and Aggregation	2016	VLDB	6.5131946e-05
4,599	Fair Near Neighbor Search: Independent Range Sampling in High Dimensions	2020	PODS	6.0532073e-05
5,955	Spatial Independent Range Sampling	2021	SIGMOD	5.2539404e-05
6,457	Algorithmic Techniques for Independent Query Sampling	2022	PODS	5.0488247e-05
8,609	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB	4.4810481e-05
9,632	External Memory Stream Sampling	2015	PODS	4.3093476e-05
9,760	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	4.2838028e-05
9,902	Towards Systematic Index Dynamization	2024	VLDB	4.2539423e-05
9,945	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	4.240067e-05
11,287	Approximate Queries over Concurrent Updates	2023	VLDB	4.1905499e-05
11,558	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1905499e-05
11,921	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	4.1905499e-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.0010813443
736	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00017414831
1,425	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012044433
1,472	Online Maintenance of Very Large Random Samples on Flash Storage	2008	VLDB	0.00011798842
3,989	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS	6.5545373e-05
6,192	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.1596405e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,973	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS	4.1905499e-05
12,113	Space-Efficient Range Reporting for Categorical Data	2012	PODS	4.1905499e-05
8,609	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB	4.4810481e-05
12,114	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	4.1905499e-05
8,761	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	4.4520434e-05
1,764	Indexing Moving Points (Extended Abstract)	2000	PODS	0.0001062234
8,764	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.4520434e-05
5,955	Spatial Independent Range Sampling	2021	SIGMOD	5.2539404e-05
7,851	Dynamic Top-K Range Reporting in External Memory	2012	PODS	4.6320876e-05
1,183	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013444058