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: hac9748cc22642ba3
Venue: SIGMOD
Year: 2005
Pagerank: 5.5988347e-05
Overall Rank: 7,138 | 52.03%
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,729	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB	7.0664086e-05
4,644	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	6.4869417e-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
57	On Random Sampling over Joins	1999	SIGMOD	0.00040095727
152	Query Processing, Resource Management, and Approximation in a Data Stream Management System	2003	CIDR	0.00028657752
677	Load Shedding in a Data Stream Manager	2003	VLDB	0.0001484703
1,431	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010676907
2,210	Multi-Dimensional Regression Analysis of Time-Series Data Streams	2002	VLDB	8.8340718e-05
2,261	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.7313225e-05
3,729	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB	7.0664086e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
2	2,738	Sketching Probabilistic Data Streams	2007	SIGMOD
3	7,471	Reservoir Sampling over Joins	2024	SIGMOD
4	11,531	Low-Latency Adaptive Distributed Stream Join System Based on a Flexible Join Model	2024	SIGMOD
5	843	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
6	8,462	Stochastic Consistency, and Scalable Pull-Based Caching for Erratic Data Stream Sources	2004	VLDB
7	2,754	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB
8	13,020	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS
9	1,431	Approximate Join Processing Over Data Streams	2003	SIGMOD
10	3,729	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB