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: 5282
Venue: SIGMOD
Year: 2016
Pagerank: 4.1905499e-05
Overall Rank: 11,863 | 17.56%
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,363	Approximate Range Thresholding	2022	SIGMOD	4.1905499e-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.0032118946
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
41	NiagaraCQ: A Scalable Continuous Query System for Internet Databases	2000	SIGMOD	0.00073944756
204	Monitoring Streams – A New Class of Data Management Applications	2002	VLDB	0.00034696955
244	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.00031037999
259	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00030155645
374	Continuous Queries over Append-Only Databases	1992	SIGMOD	0.00025325855
497	Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems	2001	SIGMOD	0.00021667647
619	Towards an Internet-Scale XML Dissemination Service	2004	VLDB	0.00018983711
945	Cayuga: A General Purpose Event Monitoring System	2007	CIDR	0.0001512921
1,623	Monitoring XML Data on the Web	2001	SIGMOD	0.00011100632
2,967	Processing a Large Number of Continuous Preference Top-k Queries	2012	SIGMOD	7.7975455e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,801	Threshold Queries in Theory and in the Wild	2022	VLDB	4.2777144e-05
1,183	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013444058
11,443	Frequent Elements with Witnesses in Data Streams	2021	PODS	4.1905499e-05
8,478	Optimization of Threshold Functions over Streams	2021	VLDB	4.4968401e-05
4,328	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	6.2765138e-05
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.380727e-05
1,904	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS	0.00010144623
8,592	Stream Frequency over Interval Queries	2019	VLDB	4.4848323e-05
2,952	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8230109e-05
11,363	Approximate Range Thresholding	2022	SIGMOD	4.1905499e-05