RPJ: Producing fast join results on streams through rate-based optimization

Yufei Tao, Man Lung Yiu, Dimitris Papadias, Marios Hadjieleftheriou, Nikos Mamoulis

Research output: Journal article publicationConference articleAcademic researchpeer-review

57 Citations (Scopus)


We consider the problem of "progressively" joining relations whose records are continuously retrieved from remote sources through an unstable network that may incur temporary failures. The objectives are to (i) start reporting the first output tuples as soon as possible (before the participating relations are completely received), and (ii) produce the remaining results at a fast rate. We develop a new algorithm RPJ (Rate-based Progressive Join) based on solid theoretical analysis. RPJ maximizes the output rate by optimizing its execution according to the characteristics of the join relations (e.g., data distribution, tuple arrival pattern, etc.). Extensive experiments prove that our technique delivers results significantly faster than the previous methods.
Original languageEnglish
Pages (from-to)371-382
Number of pages12
JournalProceedings of the ACM SIGMOD International Conference on Management of Data
Publication statusPublished - 1 Dec 2005
Externally publishedYes
EventSIGMOD 2005: ACM SIGMOD International Conference on Management of Data - Baltimore, MD, United States
Duration: 14 Jun 200516 Jun 2005

ASJC Scopus subject areas

  • Software
  • Information Systems

Cite this