서지주요정보
연속적인 데이터 스트림에서 효율적인 술어 색인 방법 = An efficient predicate indexing method over continuous data streams
서명 / 저자 연속적인 데이터 스트림에서 효율적인 술어 색인 방법 = An efficient predicate indexing method over continuous data streams / 강우람.
저자명 강우람 ; Kang, Woo-Lam
발행사항 [대전 : 한국과학기술원, 2008].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8019602

소장위치/청구기호

학술문화관(문화관) 보존서고

MCS 08034

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

A large number of range queries can be issued against continuous data streams. To process the range queries efficiently over continuous streams, a predicate index is generally used. IBS-tree is one of the most adequate predicate indexing methods for stream processing. However, its search performance may be degraded from unnecessary equality test conducted in every intermediate node of the tree, especially when number of queries increases. To address this issue, we propose an indexing method called PRINS(PRedicate INdex over Streams), which improves search performance by separating equality test from the tree and using hash table for the test. The separation of equality test can make, the number of comparisons per node smaller and the tree depth also decreased. We analyze the search costs of both methods based on the expected number of comparisons per input tuple. Based on the cost measures, we derive that our method provides better search performance than IBS-tree. And we show it by conducting experiments.

경매, 주식 거래, 네트워크 통계 등의 응용에서는 많은 수의 범위 질의가 연속 데이터 스트림에 대해 이루어진다. 이 질의들을 연속 스트림 상에서 효율적으로 처리하기 위해서 일반적으로 술어 색인이 이용된다. 기존에 많은 술어방식이 제안되었지만 모두 스트림 환경에 적합하지는 않다. IBS-tree는 스트림 환경에 적합한 술어 색인 방법 중 하나이다. 하지만 IBS-tree는 트리의 각 노드마다 불필요한 등호 검사를 수행하기 때문에 질의의 수가 늘어남에 따라 검색 성능이 나빠질 수 있다. 이 문제점을 해결하기 위하여 본 논문에서는 등호 검사를 트리로부터 분리하고 이를 위해 해시 테이블을 사용하여 검색 성능을 향상시킨 PRINS(PRedicate INdex over Streams)라는 술어 색인 방법을 제안한다. 등호 검사의 분리는 트리의 각 노드에서의 비교 횟수를 줄이고 트리의 높이가 낮아지도록 한다. 본 논문에서는 한 입력값에 대한 비교 횟수의 기대값을 통해 두 방법의 검색 비용 식을 구하여 분석하였다. 이 비용 식을 통해 PRINS의 검색 성능이 IBS-tree보다 좋다는 것을 보였다. 또한 실험을 통해 이를 확인하였다.

서지기타정보

서지기타정보
청구기호 {MCS 08034
형태사항 iv, 42p. : 삽도 ; 26 cm
언어 한국어
일반주기 저자명의 영문표기 : Woo-Lam Kang
지도교수의 한글표기 : 이윤준
지도교수의 영문표기 : Yoon-Joon Lee
학위논문 학위논문(석사) - 한국과학기술원 : 전산학전공,
서지주기 참고문헌 : p. 41-42
주제 Predicate Index;Range Query;Event Matching;PRINS;IBS-tree
술어 색인;범위 질의;이벤트 매칭;;
QR CODE qr code