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: hdc0a251df6b2b261
Venue: PODS
Year: 2002
Pagerank: 9.9008287e-05
Overall Rank: 1,674 | 88.79%
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.00051942573
152	Query Processing, Resource Management, and Approximation in a Data Stream Management System	2003	CIDR	0.00028566618
1,035	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00012361763
1,115	A Transducer-Based XML Query Processor	2002	VLDB	0.00011939087
1,285	Streaming Pattern Discovery in Multiple Time-Series	2005	VLDB	0.00011189681
1,439	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010641857
2,563	Tuple Routing Strategies for Distributed Eddies	2003	VLDB	8.2699925e-05
2,762	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB	8.025285e-05
3,610	Scalable Distributed Stream Join Processing	2015	SIGMOD	7.1463915e-05
3,755	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS	7.0291407e-05
4,607	Window-Aware Load Shedding for Aggregation Queries over Data Streams	2006	VLDB	6.4894359e-05
4,694	Efficient Evaluation of XQuery over Streaming Data	2005	VLDB	6.4490159e-05
4,708	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.4419838e-05
5,391	Buffering in Query Evaluation over XML Streams	2005	PODS	6.1364667e-05
5,414	Adaptive, Hands-Off Stream Mining	2003	VLDB	6.1275934e-05
7,192	Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance	2005	VLDB	5.5736733e-05
7,485	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD	5.5003667e-05
8,953	Monitoring Business Processes with Queries	2007	VLDB	5.2361195e-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.00053734242
26	Models and Issues in Data Stream Systems	2002	PODS	0.00051942573
316	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021238056
336	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00020619345
370	Continuous Queries over Append-Only Databases	1992	SIGMOD	0.00019781831
426	Cost-based Query Scrambling for Initial Delays	1998	SIGMOD	0.00018432573
566	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00016236872
584	Alert: An Architecture for Transforming a Passive DBMS into an Active DBMS	1991	VLDB	0.00015927926
1,913	Monitoring XML Data on the Web	2001	SIGMOD	9.3689751e-05
2,133	View Maintenance Issues for the Chronicle Data Model (Extended Abstract)	1995	PODS	8.9830012e-05
3,451	Expiring Data in a Warehouse	1998	VLDB	7.2722725e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,122	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
2	5,512	Compressed Representations of Conjunctive Query Results	2018	PODS
3	7,485	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD
4	4,708	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD
5	4,473	Bounded Conjunctive Queries	2014	VLDB
6	9,822	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR
7	844	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
8	3,284	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD
9	1,052	Chain: Operator Scheduling for Memory Minimization in Data Stream Systems	2003	SIGMOD
10	3,735	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB