Approximate Range Thresholding

Summary: FastRTS: approximate RT on streaming d-dimensional points; supports many RT queries and captures a moment between (1−ε)τ and τ. Key: reduces QGT exponent from d+1 to d, with near-linear space; practical optimizations yield speedups and memory savings. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6499
Venue: SIGMOD
Year: 2022
Pagerank: 5.093636e-05
Overall Rank: 11,559 | 20.70%
DOI: 10.1145/3514221.3526123

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Zhuo Zhang (University of Melbourne)
2. Junhao Gan (University of Melbourne)
3. Zhifeng Bao (Royal Melbourne Institute of Technology)
4. Seyed Mohammad Hussein Kazemi (University of Melbourne)
5. Guangyong Chen (Zhejiang Lab; Zhejiang University)
6. Fengyuan Zhu (Kaifeng Investment)

BibTeX Citation

@inproceedings{zhang_sigmod22,
        title = {{Approximate Range Thresholding}},
        author = {Zhang, Zhuo and Gan, Junhao and Bao, Zhifeng and Kazemi, Seyed Mohammad Hussein and Chen, Guangyong and Zhu, Fengyuan},
        series = {{SIGMOD} '22},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3514221.3526123},
        url = {https://dl.acm.org/doi/10.1145/3514221.3526123},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
25	NiagaraCQ: A Scalable Continuous Query System for Internet Databases	2000	SIGMOD	0.00054667018
193	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.00025964286
229	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00023927582
441	Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems	2001	SIGMOD	0.00018407547
732	Cayuga: A General Purpose Event Monitoring System	2007	CIDR	0.00014536846
875	Towards an Internet-Scale XML Dissemination Service	2004	VLDB	0.00013478623
1,853	Monitoring XML Data on the Web	2001	SIGMOD	9.6123436e-05
2,427	Processing a Large Number of Continuous Preference Top-k Queries	2012	SIGMOD	8.5915976e-05
4,423	Dynamic Structural Clustering on Graphs	2021	SIGMOD	6.7107949e-05
12,056	Range Thresholding on Streams	2016	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	261	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD
2	3,241	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
3	3,700	Approximate MaxRS in Spatial Databases	2013	VLDB
4	3,593	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD
5	11,638	Frequent Elements with Witnesses in Data Streams	2021	PODS
6	12,176	Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams	2014	SIGMOD
7	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
8	82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD
9	4,472	Relative Error Streaming Quantiles	2021	PODS
10	12,056	Range Thresholding on Streams	2016	SIGMOD