RPJ: Producing Fast Join Results on Streams through Rate-based Optimization

Summary: RPJ is a rate-based progressive join for streaming relations over unreliable networks, to start output quickly and maintain high throughput. A theoretical framework guides optimization by adapting to data distribution and arrival patterns, yielding faster results than prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h1f79be9d661661b5
Venue: SIGMOD
Year: 2005
Pagerank: 5.8882414e-05
Overall Rank: 6,045 | 59.49%
DOI: 10.1145/1066157.1066200

Incoming Non-self Citations Over Time

Authors

1. Yufei Tao (City University of Hong Kong)
2. Man Lung Yiu (University of Hong Kong)
3. Dimitris Papadias (Hong Kong University of Science and Technology)
4. Marios Hadjieleftheriou (University of California Riverside)
5. Nikos Mamoulis (University of Hong Kong)

BibTeX Citation

@inproceedings{tao_sigmod05,
        title = {{RPJ: Producing Fast Join Results on Streams through Rate-based Optimization}},
        author = {Tao, Yufei and Yiu, Man Lung and Papadias, Dimitris and Hadjieleftheriou, Marios and Mamoulis, Nikos},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066200},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066200},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,972	Scalable and Adaptive Online Joins	2014	VLDB	7.7844791e-05
4,661	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	6.4656621e-05
6,880	SquirrelJoin: Network-Aware Distributed Join Processing with Lazy Partitioning	2017	VLDB	5.6423904e-05
7,985	Parallelizing Intra-Window Join on Multicores: An Experimental Study	2021	SIGMOD	5.3960833e-05
8,154	Thrifty Query Execution via Incrementability	2020	SIGMOD	5.3732833e-05
9,218	PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees	2010	SIGMOD	5.1918495e-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
26	Models and Issues in Data Stream Systems	2002	PODS	0.00051942573
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029532435
680	Load Shedding in a Data Stream Manager	2003	VLDB	0.00014799878
1,035	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00012361763
1,109	Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources	2003	VLDB	0.00011949421
1,439	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010641857
2,762	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB	8.025285e-05
2,853	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB	7.9179824e-05
3,735	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB	7.0431286e-05
5,620	On Producing Join Results Early	2003	PODS	6.0466546e-05
5,636	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	6.0385837e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,514	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD
2	5,254	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD
3	3,072	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
4	2,853	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB
5	2,762	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB
6	1,603	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
7	2,972	Scalable and Adaptive Online Joins	2014	VLDB
8	1,439	Approximate Join Processing Over Data Streams	2003	SIGMOD
9	1,109	Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources	2003	VLDB
10	9,218	PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees	2010	SIGMOD