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: 1620
Venue: PODS
Year: 2014
Pagerank: 8.5754434e-05
Overall Rank: 2,443 | 83.25%
DOI: 10.1145/2594538.2594545

Incoming Non-self Citations Over Time

Authors

1. Xiaocheng Hu (Chinese University of Hong Kong)
2. Miao Qiao (Chinese University of Hong Kong)
3. Yufei Tao (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{hu_pods14,
        address = {New York, NY, USA},
        series = {{PODS} '14},
        title = {{Independent Range Sampling}},
        url = {https://dl.acm.org/doi/10.1145/2594538.2594545},
        doi = {10.1145/2594538.2594545},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hu, Xiaocheng and Qiao, Miao and Tao, Yufei},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
593	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00016027871
3,623	Fair Near Neighbor Search: Independent Range Sampling in High Dimensions	2020	PODS	7.2463734e-05
3,741	Spatial Online Sampling and Aggregation	2016	VLDB	7.1586403e-05
5,527	Algorithmic Techniques for Independent Query Sampling	2022	PODS	6.1861709e-05
5,692	Spatial Independent Range Sampling	2021	SIGMOD	6.119196e-05
7,142	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB	5.6917227e-05
8,790	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	5.3722049e-05
8,988	Towards Systematic Index Dynamization	2024	VLDB	5.3384135e-05
9,732	External Memory Stream Sampling	2015	PODS	5.2279411e-05
10,093	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	5.1530576e-05
10,244	FIRAS: A Framework for Interval Range Search and Sampling	2026	SIGMOD	5.093636e-05
11,484	Approximate Queries over Concurrent Updates	2023	VLDB	5.093636e-05
11,751	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	5.093636e-05
12,112	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	5.093636e-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
9	Online Aggregation	1997	SIGMOD	0.00077458002
553	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016590619
1,064	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012336248
1,435	Online Maintenance of Very Large Random Samples on Flash Storage	2008	VLDB	0.00010800274
4,285	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS	6.7812351e-05
5,891	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	6.0495154e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,163	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS
2	12,302	Space-Efficient Range Reporting for Categorical Data	2012	PODS
3	7,142	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB
4	12,303	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS
5	8,750	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS
6	1,611	Indexing Moving Points (Extended Abstract)	2000	PODS
7	8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
8	5,692	Spatial Independent Range Sampling	2021	SIGMOD
9	8,173	Dynamic Top-K Range Reporting in External Memory	2012	PODS
10	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS