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

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

doi:10.1145/1066157.1066200

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 publication › Conference article › Academic research › peer-review

58 Citations (Scopus)

Abstract

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 language	English
Pages (from-to)	371-382
Number of pages	12
Journal	Proceedings of the ACM SIGMOD International Conference on Management of Data
DOIs	https://doi.org/10.1145/1066157.1066200
Publication status	Published - 1 Dec 2005
Externally published	Yes
Event	SIGMOD 2005: ACM SIGMOD International Conference on Management of Data - Baltimore, MD, United States Duration: 14 Jun 2005 → 16 Jun 2005

ASJC Scopus subject areas

Software
Information Systems

More information

10.1145/1066157.1066200

Cite this

@article{891176b5e39241e59ec43971bab4a987,

title = "RPJ: Producing fast join results on streams through rate-based optimization",

abstract = "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.",

author = "Yufei Tao and Yiu, {Man Lung} and Dimitris Papadias and Marios Hadjieleftheriou and Nikos Mamoulis",

year = "2005",

month = dec,

day = "1",

doi = "10.1145/1066157.1066200",

language = "English",

pages = "371--382",

journal = "Proceedings of the ACM SIGMOD International Conference on Management of Data",

issn = "0730-8078",

note = "SIGMOD 2005: ACM SIGMOD International Conference on Management of Data ; Conference date: 14-06-2005 Through 16-06-2005",

}

TY - JOUR

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

AU - Tao, Yufei

AU - Yiu, Man Lung

AU - Papadias, Dimitris

AU - Hadjieleftheriou, Marios

AU - Mamoulis, Nikos

PY - 2005/12/1

Y1 - 2005/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=29844439309&partnerID=8YFLogxK

U2 - 10.1145/1066157.1066200

DO - 10.1145/1066157.1066200

M3 - Conference article

SN - 0730-8078

SP - 371

EP - 382

JO - Proceedings of the ACM SIGMOD International Conference on Management of Data

JF - Proceedings of the ACM SIGMOD International Conference on Management of Data

T2 - SIGMOD 2005: ACM SIGMOD International Conference on Management of Data

Y2 - 14 June 2005 through 16 June 2005

ER -

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

Abstract

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this