Optimization of Threshold Functions over Streams

Summary: A stream-processing algorithm exactly monitors threshold predicates over temporal joins of multiple streams for the broad quasiconvex class, retaining only a few tuples per stream and never missing alarms. Proven optimal, it sharply reduces normal and failure-mode buffering. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12791
Venue: VLDB
Year: 2021
Pagerank: 5.3830471e-05
Overall Rank: 8,697 | 40.34%
DOI: 10.14778/3447689.3447693

Incoming Non-self Citations Over Time

Authors

1. Walter Cai (University of Washington)
2. Philip A. Bernstein (Microsoft)
3. Wentao Wu (Microsoft)
4. Badrish Chandramouli (Microsoft)

BibTeX Citation

@article{cai_vldb21,
        title = {{Optimization of Threshold Functions over Streams}},
        author = {Cai, Walter and Bernstein, Philip A. and Wu, Wentao and Chandramouli, Badrish},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {6},
        pages = {878--889},
        doi = {10.14778/3447689.3447693},
        url = {https://doi.org/10.14778/3447689.3447693},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,847	TSUBASA: Climate Network Construction on Historical and Real-Time Data	2022	SIGMOD	5.2094004e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
671	Load Shedding in a Data Stream Manager	2003	VLDB	0.00015154516
710	Trill: A High-Performance Incremental Query Processor for Diverse Analytics	2015	VLDB	0.00014715033
983	Integrating Scale Out and Fault Tolerance in Stream Processing using Operator State Management	2013	SIGMOD	0.0001283214
1,016	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00012645699
1,171	Photon: Fault-tolerant and Scalable Joining of Continuous Data Streams	2013	SIGMOD	0.00011826434
1,190	Structured Streaming: A Declarative API for Real-Time Applications in Apache Spark	2018	SIGMOD	0.00011743246
1,397	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010906135
2,596	A Geometric Approach to Monitoring Threshold Functions Over Distributed Data Streams	2006	SIGMOD	8.3627764e-05
2,802	General Incremental Sliding-Window Aggregation	2015	VLDB	8.1093063e-05
3,255	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB	7.591663e-05
4,596	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.6133976e-05
4,989	Shape Sensitive Geometric Monitoring	2008	PODS	6.4106441e-05
8,029	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	5.5045998e-05
8,501	Prediction-Based Geometric Monitoring Over Distributed Data Streams	2012	SIGMOD	5.4132745e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	551	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD
2	1,656	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS
3	5,669	Data Streams with Bounded Deletions	2018	PODS
4	7,711	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB
5	8,029	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB
6	9,318	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB
7	1,397	Approximate Join Processing Over Data Streams	2003	SIGMOD
8	3,657	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB
9	12,056	Range Thresholding on Streams	2016	SIGMOD
10	2,596	A Geometric Approach to Monitoring Threshold Functions Over Distributed Data Streams	2006	SIGMOD