Range Thresholding on Streams

Summary: Introduces range thresholding on streams (RTS) and the first algorithm beating quadratic time, achieving O(n + m) up to polylog factors for processing stream elements and queries. Generalizes to weighted, d-dimensional queries, with experiments showing practical, scalable performance gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5343
Venue: SIGMOD
Year: 2016
Pagerank: 5.093636e-05
Overall Rank: 12,056 | 17.29%
DOI: 10.1145/2882903.2915965

Incoming Non-self Citations Over Time

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

Authors

1. Miao Qiao (Massey University)
2. Junhao Gan (University of Queensland)
3. Yufei Tao (University of Queensland)

BibTeX Citation

@inproceedings{qiao_sigmod16,
        title = {{Range Thresholding on Streams}},
        author = {Qiao, Miao and Gan, Junhao and Tao, Yufei},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915965},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915965},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,559	Approximate Range Thresholding	2022	SIGMOD	5.093636e-05

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
167	Monitoring Streams – A New Class of Data Management Applications	2002	VLDB	0.0002757283
193	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.00025964286
229	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00023927582
368	Continuous Queries over Append-Only Databases	1992	SIGMOD	0.00019968151
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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
2	11,638	Frequent Elements with Witnesses in Data Streams	2021	PODS
3	8,697	Optimization of Threshold Functions over Streams	2021	VLDB
4	3,599	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB
5	9,318	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB
6	1,656	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS
7	5,669	Data Streams with Bounded Deletions	2018	PODS
8	8,603	Stream Frequency over Interval Queries	2019	VLDB
9	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
10	11,559	Approximate Range Thresholding	2022	SIGMOD