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.9382031e-05
Overall Rank: 1,666 | 88.81%
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.00052121228
152	Query Processing, Resource Management, and Approximation in a Data Stream Management System	2003	CIDR	0.0002867034
1,030	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00012407749
1,111	A Transducer-Based XML Query Processor	2002	VLDB	0.00011984202
1,278	Streaming Pattern Discovery in Multiple Time-Series	2005	VLDB	0.00011231952
1,431	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010681774
2,558	Tuple Routing Strategies for Distributed Eddies	2003	VLDB	8.3007355e-05
2,753	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB	8.0549317e-05
3,603	Scalable Distributed Stream Join Processing	2015	SIGMOD	7.173496e-05
3,746	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS	7.0557724e-05
4,590	Window-Aware Load Shedding for Aggregation Queries over Data Streams	2006	VLDB	6.5139479e-05
4,677	Efficient Evaluation of XQuery over Streaming Data	2005	VLDB	6.4733736e-05
4,693	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.4662079e-05
5,368	Buffering in Query Evaluation over XML Streams	2005	PODS	6.1597369e-05
5,390	Adaptive, Hands-Off Stream Mining	2003	VLDB	6.1508226e-05
7,168	Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance	2005	VLDB	5.5947893e-05
7,462	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD	5.521211e-05
8,925	Monitoring Business Processes with Queries	2007	VLDB	5.2559789e-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.00053930011
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052121228
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021311793
334	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00020691326
369	Continuous Queries over Append-Only Databases	1992	SIGMOD	0.00019854467
424	Cost-based Query Scrambling for Initial Delays	1998	SIGMOD	0.0001848836
566	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00016295476
581	Alert: An Architecture for Transforming a Passive DBMS into an Active DBMS	1991	VLDB	0.00015984359
1,902	Monitoring XML Data on the Web	2001	SIGMOD	9.4042335e-05
2,115	View Maintenance Issues for the Chronicle Data Model (Extended Abstract)	1995	PODS	9.0155433e-05
3,438	Expiring Data in a Warehouse	1998	VLDB	7.2996039e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,106	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
2	5,489	Compressed Representations of Conjunctive Query Results	2018	PODS
3	7,462	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD
4	4,693	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD
5	4,452	Bounded Conjunctive Queries	2014	VLDB
6	9,784	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR
7	842	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
8	3,272	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD
9	1,047	Chain: Operator Scheduling for Memory Minimization in Data Stream Systems	2003	SIGMOD
10	3,727	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB