Characterizing Memory Requirements for Queries over Continuous Data Streams

Summary: Decide when conjunctive queries with arithmetic comparisons over multiple continuous streams admit bounded-memory evaluation for all stream instances. Provide an algorithm that tests this decidability and synthesizes execution strategies using constant-sized synopses when possible. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1266
Venue: PODS
Year: 2002
Pagerank: 0.00010097487
Overall Rank: 1,656 | 88.64%
DOI: 10.1145/543613.543642

Incoming Non-self Citations Over Time

Authors

1. Arvind Arasu (Stanford University)
2. Brian Babcock (Stanford University)
3. Shivnath Babu (Stanford University)
4. Jon McAlister (Stanford University)
5. Jennifer Widom (Stanford University)

BibTeX Citation

@inproceedings{arasu_pods02,
        address = {New York, NY, USA},
        series = {{PODS} '02},
        title = {{Characterizing Memory Requirements for Queries over Continuous Data Streams}},
        url = {https://dl.acm.org/doi/10.1145/543613.543642},
        doi = {10.1145/543613.543642},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Arasu, Arvind and Babcock, Brian and Babu, Shivnath and McAlister, Jon and Widom, Jennifer},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
150	Query Processing, Resource Management, and Approximation in a Data Stream Management System	2003	CIDR	0.00029208207
1,016	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00012645699
1,082	A Transducer-Based XML Query Processor	2002	VLDB	0.00012257574
1,252	Streaming Pattern Discovery in Multiple Time-Series	2005	VLDB	0.00011483752
1,397	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010906135
2,513	Tuple Routing Strategies for Distributed Eddies	2003	VLDB	8.48462e-05
3,255	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB	7.591663e-05
3,532	Scalable Distributed Stream Join Processing	2015	SIGMOD	7.3369085e-05
3,659	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS	7.2176232e-05
4,517	Window-Aware Load Shedding for Aggregation Queries over Data Streams	2006	VLDB	6.6481605e-05
4,576	Efficient Evaluation of XQuery over Streaming Data	2005	VLDB	6.6216442e-05
4,596	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.6133976e-05
5,247	Buffering in Query Evaluation over XML Streams	2005	PODS	6.3009176e-05
5,272	Adaptive, Hands-Off Stream Mining	2003	VLDB	6.2899363e-05
7,027	Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance	2005	VLDB	5.7231968e-05
7,321	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD	5.6454313e-05
8,763	Monitoring Business Processes with Queries	2007	VLDB	5.3766157e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
25	NiagaraCQ: A Scalable Continuous Query System for Internet Databases	2000	SIGMOD	0.00054667018
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
328	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00021081317
368	Continuous Queries over Append-Only Databases	1992	SIGMOD	0.00019968151
419	Cost-based Query Scrambling for Initial Delays	1998	SIGMOD	0.0001879684
551	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00016635191
576	Alert: An Architecture for Transforming a Passive DBMS into an Active DBMS	1991	VLDB	0.00016238156
1,853	Monitoring XML Data on the Web	2001	SIGMOD	9.6123436e-05
2,080	View Maintenance Issues for the Chronicle Data Model (Extended Abstract)	1995	PODS	9.2052704e-05
3,377	Expiring Data in a Warehouse	1998	VLDB	7.4598611e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
2	5,383	Compressed Representations of Conjunctive Query Results	2018	PODS
3	7,321	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD
4	4,596	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD
5	9,612	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR
6	4,393	Bounded Conjunctive Queries	2014	VLDB
7	3,197	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD
8	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
9	1,027	Chain: Operator Scheduling for Memory Minimization in Data Stream Systems	2003	SIGMOD
10	3,657	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB