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보다 좋다는 것을 보였다. 또한 실험을 통해 이를 확인하였다.
