비트맵 필터를 이용한 효율적인 역 리스트 탐색 기법
Efficient Inverted List Search Technique using Bitmap Filters
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
텍스트 데이터는 표현 방식의 차이, 타이핑 오류 등을 포함하고 있어 정확히 일치하는 검색으로는 유용한 정보를 얻기 어렵다. 따라서 유사도 기반 검색 방법이 많이 연구되고 있으며 효율적인 유사도 기반 검색을 위해 텍스트 데이터에 대한 역 리스트를 구성한다. 그리고 이를 병합하여 질의와 일정 기준 이상 유사한 데이터를 찾는다. 본 논문에서는 Suffix 필터링 과정에서 역 리스트의 탐색 비용을 줄이기 위해 역 리스트의 통계 정보인 비트맵 필터를 사용하는 기법을 제안한다. 제안하는 기법은 비트맵 필터를 사용하여 Suffix 필터링 과정에서 역 리스트의 탐색여부를 결정하여 불필요한 역 리스트 탐색을 회피함으로써 역 리스트 병합 비용을 줄인다. 실험을 통하여 제안된 기법이 기존의 연구에서 제안된 Suffix 필터링 알고리즘보다 더 효율적임을 보인다.
Abstract
Finding similar strings is an important operation because textual data can have errors, duplications, and inconsistencies by nature. Many algorithms have been developed for string approximate searches and most of them make use of inverted lists to find similar strings. These algorithms basically perform merge operations on inverted lists. In this paper, we develop a bitmap representation of an inverted list and propose an efficient search algorithm that can skip unnecessary inverted lists without searching using bitmap filters. Experimental results show that the proposed technique consistently improve the performance of the search.
참고문헌 (17)
- 권인택, "비트맵 필터를 이용한 효율적인 유사 문자열 검색 기법", 한국정보처리학회 춘계학술대회 논문집, 18(1), pp.1298~1301 (2011)
- S. Sarawagi, "Efficient set joins on similarity predicates", SIGMOD, pp.743~755 (2004)
- C. Xiao, "Ed-Join: an efficient algorithm for similarity joins with edit distance constraints", VLDB (2008)
- S. Chaudhuri, "A Primitive Opeartor for Similarity Joins in Data Cleaning", ICDE, pp.5~ (2006)
- C. Xiao, "Efficient Similarity Joins for Near Duplicate Detection", WWW (2008)
- Roberto J, "Scaling Up All Pairs Simialrity Search" (2007), WWW
- Leonardo Andrade Ribeiro, "Generalizing prefix filtering to improve set similarity joins", Information Systems (2010)
- C. Li, "Efficient Merging and Filtering Algorithms for Approximate String Searches", pp.257~266 (2008), ICDE
- A. Behm, "Space-Constrained Gram-Based Indexing for Efficient Approximate String Search", ICDE, pp.604~615 (2009)
- C. Li, "VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams", VLDB, pp.303~314 (2007)
- X. Yang, "Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently", SIGMOD (2008)
- A. Arasu, "Efficient Exact Set-Similarity Joins", VLDB, pp.918~929 (2006)
- K. Chakrabarti, "An Efficient Filter for Approximate Membership Checking", SIGMOD (2008)
- S. Chaudhuri, "Data cleaning in microsoft SQL server 2005", SIGMOD, pp.918~920 (2005)
- N. Okazaki, "Simple and Efficient Algorithm for Approximate Dictionary Matching", In proc. of the 23rd International Conference on Computational Linguistics, pp.851~859 (2010)
- J. Barbay, "Adaptive intersection and t-threshold problems", pp.390~399 (2002), SODA
- N. Koudas, "Record linkage: Similarity measures and algorithms" (2006), SIGMOD