데이터 스트림에 대한 키워드 검색을 위한, 효율적인 갱신이 가능한 디스크 기반 역색인 구조 (An Update-Efficient, Disk-Based Inverted Index Structure for Keyword Search on Data Streams)

서지정보

· 발행기관 : 한국정보처리학회
· 수록지 정보 : 정보처리학회 논문지 / 5권 / 4호 / 171 ~ 180페이지
· 저자명 : 박은주, 이기용

초록

트위터와 같은 소셜 네트워킹 서비스(social networking service)의 확산으로 스트림 형태의 데이터가 크게 증가하고 있다. 스트림 형태로 들어와 누적되는 데이터를 효율적으로 검색하기 위해서는 색인이 반드시 필요하다. 본 논문에서는 스트림 형태로 들어와 계속 누적되는 데이터에대한 키워드 검색을 효율적으로 할 수 있게 해주는, 효율적인 갱신이 가능한 디스크 기반 역색인(inverted index) 구조를 제안한다. 데이터 스트림을 검색하기 위해서는 데이터의 유입에 따라 역색인을 계속해서 갱신해 주어야 한다. 전통적인 역색인을 사용하는 경우, 역색인을 갱신하기위해서는 매번 디스크에 저장된 모든 색인 데이터를 읽고 다시 써야 하므로 디스크 I/O 측면에서 매우 비효율적이다. 이러한 문제를 해결하기위해 본 논문에서는 역색인을 크기가 지수적으로 증가하는 여러 역색인들로 나누어 저장한다. 새로운 데이터가 들어오면 우선 가장 작은 크기의 역색인에 삽입하고, 작은 크기의 역색인들을 더 큰 크기를 가진 역색인들과 나중에 병합함으로써 평균적으로 역색인을 갱신하는 비용을 크게 낮춘다. 또한 디스크에 저장된 역색인들을 병합할 때 발생하는 디스크 I/O 비용을 최소화함으로써 역색인의 갱신 비용을 더욱 낮춘다. 다양한 실험을 통해 기존 방법과 제안 방법의 효율성을 비교하고, 제안 방법이 갱신 비용에 있어 기존 방법에 비해 훨씬 효율적임을 보인다.

영어초록

As social networking services such as twitter become increasingly popular, data streams are widely prevalent these days. In order to search data accumulated from data streams efficiently, the use of an index structure is essential. In this paper, we propose an update-efficient, disk-based inverted index structure for efficient keyword search on data streams. When new data arrive at the data stream, the index needs to be updated to incorporate the new data. The traditional inverted index is very inefficient to update in terms of disk I/O, because all index data stored in the disk need to be read and written to the disk each time the index is updated. To solve this problem, we divide the whole inverted index into a sequence of inverted indices with exponentially increasing size. When new data arrives, it is first inserted into the smallest index and, later, the small indices are merged with the larger indices, which leads to a small amortize update cost for each new data. Furthermore, when indices stored in the disk are merged with each other, we minimize the disk I/O cost incurred for the merge operation, resulting in an even smaller update cost. Through various experiments, we compare the update efficiency of the proposed index structure with the previous one, and show the performance advantage of the proposed structure in terms of the update cost.

참고자료

· 없음