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: h769396e9e18fd02f
Venue: PODS
Year: 2014
Pagerank: 8.3873598e-05
Overall Rank: 2,495 | 83.23%
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
596	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015785583
3,690	Fair Near Neighbor Search: Independent Range Sampling in High Dimensions	2020	PODS	7.0936701e-05
3,818	Spatial Online Sampling and Aggregation	2016	VLDB	7.0060535e-05
5,638	Algorithmic Techniques for Independent Query Sampling	2022	PODS	6.0565637e-05
5,819	Spatial Independent Range Sampling	2021	SIGMOD	5.9832748e-05
7,246	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB	5.5750011e-05
8,944	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	5.2542285e-05
9,149	Towards Systematic Index Dynamization	2024	VLDB	5.2186338e-05
9,903	External Memory Stream Sampling	2015	PODS	5.1107042e-05
10,315	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	5.0377739e-05
10,458	FIRAS: A Framework for Interval Range Search and Sampling	2026	SIGMOD	4.9793485e-05
11,794	Approximate Queries over Concurrent Updates	2023	VLDB	4.9793485e-05
12,054	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.9793485e-05
12,405	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	4.9793485e-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.00076195956
564	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016296665
1,090	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012077577
1,460	Online Maintenance of Very Large Random Samples on Flash Storage	2008	VLDB	0.0001058438
4,374	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS	6.6300924e-05
6,011	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.9143905e-05

Semantically Similar Papers

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