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: 5281
Venue: SIGMOD
Year: 2016
Pagerank: 4.1945683e-05
Overall Rank: 11,855 | 17.53%
DOI: 10.1145/2882903.2915965

Incoming Non-self Citations Over Time

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

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,361	Approximate Range Thresholding	2022	SIGMOD	4.1945683e-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.0032169493
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
41	NiagaraCQ: A Scalable Continuous Query System for Internet Databases	2000	SIGMOD	0.00073964959
205	Monitoring Streams – A New Class of Data Management Applications	2002	VLDB	0.00034731577
244	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.00031066222
259	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00030174924
373	Continuous Queries over Append-Only Databases	1992	SIGMOD	0.00025341527
500	Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems	2001	SIGMOD	0.00021637423
622	Towards an Internet-Scale XML Dissemination Service	2004	VLDB	0.00019000333
944	Cayuga: A General Purpose Event Monitoring System	2007	CIDR	0.00015141297
1,620	Monitoring XML Data on the Web	2001	SIGMOD	0.00011111426
2,976	Processing a Large Number of Continuous Preference Top-k Queries	2012	SIGMOD	7.789303e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,798	Threshold Queries in Theory and in the Wild	2022	VLDB	4.2818172e-05
1,182	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013455963
11,440	Frequent Elements with Witnesses in Data Streams	2021	PODS	4.1945683e-05
8,480	Optimization of Threshold Functions over Streams	2021	VLDB	4.5011552e-05
4,080	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	6.4652983e-05
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.3849295e-05
1,904	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS	0.00010154528
8,594	Stream Frequency over Interval Queries	2019	VLDB	4.4891331e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
11,361	Approximate Range Thresholding	2022	SIGMOD	4.1945683e-05