A Study on the Efficiency of Join Operation On Stream Data Using Sliding Windows (스트림 데이터에서 슬라이딩 윈도우를 사용한 조인 연산의 효율에 관한 연구)

양영휴

A Study on the Efficiency of Join Operation On Stream Data Using Sliding Windows

Journal of The Korea Society of Computer and Information
Abbr : JKSCI
2012, 17(2), pp.149-157
Publisher : The Korean Society Of Computer And Information
Research Area : Engineering > Computer Science

양영휴 ¹

¹한양여자대학교

Accredited

ABSTRACT

In this thesis, the problem of computing approximate answers to continuous sliding-window joins over data streams when the available memory may be insufficient to keep the entire join state. One approximation scenario is to provide a maximum subset of the result, with the objective of losing as few result tuples as possible. An alternative scenario is to provide a random sample of the join result, e.g., if the output of the join is being aggregated. It is shown formally that neither approximation can be addressed effectively for a sliding-window join of arbitrary input streams. Previous work has addressed only the maximum-subset problem, and has implicitly used a frequency based model of stream arrival. There exists a sampling problem for this model. More importantly, it is shown that a broad class of applications for which an age-based model of stream arrival is more appropriate, and both approximation scenarios under this new model are addressed. Finally, for the case of multiple joins being executed with an overall memory constraint, an algorithm for memory allocation across the join that optimizes a combined measure of approximation in all scenarios considered is provided.

KEYWORDS

sliding-window, join, maximum subset, arbitrary result, frequency-based model, age-based model, multiple join operation

Citation status

* References for papers published after 2023 are currently being built.

[confproc] A. Das / 2003 / Approximate join processing over data streams / In Proc. of the 2003 ACM SIGMOD Intl. Conf. on Management of Data

[confproc] J. Kang / 2003 / Evaluating window joins over unbounded streams / In Proc. of the 2003 Intl. Conf. on Data Engineering

[confproc] B. Babcock / 2002 / Models and issues in data stream systems / In Proc. of the 2002 ACM Symp. on Principles of Database Systems : 1~16

[confproc] A. Dobra / 2002 / Processing complex aggregate queries over datastreams / In Proc. of the 2002 ACM SIGMOD Intl.Conf. on Management of Data : 61~72

[journal] T. Urhan / 2000 / A reactively-sc heduled pipelined join operator / IEEE Data Engineering Bulletin 23(2) : 27~33

[confproc] N. Tatbul / 2003 / Load-shedding in a data stream manager / In Proc. of the 2003 Intl. Conf. on Very Large Data Bases

[confproc] B. Babcock / 2004 / Load-sheddi ng for aggregation queries over data streams / In Proc. of the 2004 Intl. Conf. on Data Engineering

[confproc] N. Alon / 1999 / Tracking join and self-join sizes in limited storage / In Proc. of the 1999 ACM Symp. on Principles ofDatabase Systems : 10~20

[confproc] B. Babcock / 2002 / Sampling from a moving window over streaming data / In Proc. of the 2002 Annual ACMSIAM Symp. on Discrete Algorithms : 633~634

[confproc] S. Chaudhuri / 1999 / ACM SIGMOD Intl. Conf. on Management ofData, pp / In Proc. of the1999 ACM SIGMOD Intl. Conf. on Management ofData : 263~274

[book] W. G. Cochran / 1977 / Sampling Techniques / John Wiley& Sons

[confproc] M. Datar / 2002 / Maintaining stream statistics over slidingwindows / In Proc. of the 2002 Annual ACMSIAMSymp. on Discrete Algorithms : 635~644

[confproc] A. Gilbert / 2002 / Fast, small-space algorithms for approximate histogram maintena nce / In Proc. of the 2002 Annual ACM Symp. on Theory of Computing

[journal] L. Golab / 2003 / Issues in data stream management / SIGMOD Record 32(2) : 5~14

[confproc] S. Guha / 2001 / Data-streams and histograms / In Proc. of the 2001 Annual ACM Symp. on Theory of Computing : 471~475

[journal] S. Krishnamurthy / 2003 / TelegraphCQ: An Archi tectural Status Report / IEEE Data Engineering Bulletin 26(1) : 11~18

[book] R. Motwani / 1995 / Randomized Algor ithms / Cambridge University Press

[journal] The STREAM Group / 2003 / STREAM: The Stanford Stream Data Manager / IEEE Data Engineering Bulletin 26(1) : 19~26

[journal] Hong Shen / 2008 / Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows / Journal of computer science and technology 23(6) : 973~987

[journal] 양영휴 / 2008 / An Efficient Query Processing in Stream DBMS using Query Preprocessor / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 13(1) : 65~74

[journal] 이동언 / 2009 / A Multi-dimensional Query Processing Scheme for Stream Data using Range Query Indexing / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 14(2) : 69~77

KJCKorea
Journal Central

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65