비트-벡터 해시 테이블을 이용한 효율적인 다중 스트림 조인 알고리즘 (An Efficient M-way Stream Join Algorithm Exploiting a Bit-vector Hash Table)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 데이타베이스 / 35권 / 4호 / 297 ~ 306페이지
· 저자명 : 권태형, 김현규, 이유원, 김명호

초록

MJoin은 변화가 잦은 데이타 스트림의 조인을 효율적으로 수행하기 위한 방법으로 소개되었다. MJoin은 다중 스트림의 처리가 가능하도록 대칭적 해시 알고리즘을 확장한 것으로, 각 입력 튜플마다 모든 해시 테이블에 동일한 키를 지닌 튜플이 존재하는지 반복적으로 체크한다. 그러나, 조인 선택율이 낮고 조인되는 데이타 스트림의 수가 많을 경우, 이러한 체크 과정의 성능은 조인되는 데이타 스트림의 조인순서에 많은 영향을 받게 된다. 본 논문에서는 MJoin처럼 대칭적 해시 알고리즘을 기본으로 하지만, 이러한 체크 과정을 조인순서에 상관 없이 상수 시간에 처리하는 BiHT-Join 알고리즘을 제안한다. BiHT-Join은 스트림에 있는 튜플의 존재 유무를 비트-벡터로 유지하며, 이를 비교하는 것으로 조인의 성공/실패를 판단한다. 따라서, BiHT-Join은 이 판단을 기준으로 조인이 성공하는 튜플만 해시 조인을 수행함으로 조인 효율을 높일 수 있다. 우리는 실험을 통해 BiHT-Join이 다중 데이타 스트림 조인에서 MJoin에 비해 더 나은 성능을 제공한다는 것을 보인다.

영어초록

MJoin is proposed as an algorithm to join multiple data streams efficiently, whose characteristics are unpredictably changed. It extends a symmetric hash join to handle multiple data streams. Whenever a tuple arrives from a remote stream source, MJoin checks whether all of hash tables have matching tuples. However, when a join involves many data streams with low join selectivity, the performance of this checking process is significantly influenced by the checking order of hash tables. In this paper, we propose a BiHT-Join algorithm which extends MJoin to conduct this checking in a constant time regardless of a join order. BiHT-Join maintains a bit-vector which represents the existence of tuples in streams and decides a successful/unsuccessful join through comparing a bit-vector. Based on the bit-vector comparison, BiHT-Join can conduct a hash join only for successful joining tuples based on this decision. Our experimental results show that the proposed BiHT-Join provides better performance than MJoin in the processing of multiple streams.

참고자료

· 없음