On Joining and Caching Stochastic Streams

Summary: A statistics-aware caching framework for joining stochastic streams with bounded memory aims to maximize the expected number of output tuples. It shows that full lookahead can be suboptimal, derives a dominance condition between candidate tuples, and provides a heuristic that matches optimal behavior under that condition, with empirical gains and a reduction of static paging to stream joins. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3711
Venue: SIGMOD
Year: 2005
Pagerank: 5.7282075e-05
Overall Rank: 7,001 | 51.97%
DOI: 10.1145/1066157.1066199

Incoming Non-self Citations Over Time

Authors

1. Junyi Xie (Duke University)
2. Jun Yang (Duke University)
3. Yuguo Chen (Duke University)

BibTeX Citation

@inproceedings{xie_sigmod05,
        title = {{On Joining and Caching Stochastic Streams}},
        author = {Xie, Junyi and Yang, Jun and Chen, Yuguo},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066199},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066199},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,657	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB	7.2217692e-05
4,630	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	6.5955933e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
150	Query Processing, Resource Management, and Approximation in a Data Stream Management System	2003	CIDR	0.00029208207
671	Load Shedding in a Data Stream Manager	2003	VLDB	0.00015154516
1,397	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010906135
2,171	Multi-Dimensional Regression Analysis of Time-Series Data Streams	2002	VLDB	9.0406168e-05
2,218	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.9331834e-05
3,657	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB	7.2217692e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
2	2,697	Sketching Probabilistic Data Streams	2007	SIGMOD
3	7,335	Reservoir Sampling over Joins	2024	SIGMOD
4	11,181	Low-Latency Adaptive Distributed Stream Join System Based on a Flexible Join Model	2024	SIGMOD
5	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
6	8,285	Stochastic Consistency, and Scalable Pull-Based Caching for Erratic Data Stream Sources	2004	VLDB
7	3,255	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB
8	12,724	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS
9	1,397	Approximate Join Processing Over Data Streams	2003	SIGMOD
10	3,657	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB