Journal of KIISE (정보과학회 논문지)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지
DOI QR코드

DOI QR Code

An Efficient String Similarity Search Technique based on Generating Inverted Lists of Variable-Length Grams

가변길이 그램의 역리스트 생성을 이용한 효율적인 유사 문자열 검색 기법

  • Received : 2016.07.08
  • Accepted : 2016.08.27
  • Published : 2016.11.15
⟨ Previous Next ⟩

Abstract

Existing techniques for string similarity search first generate a set of candidate strings and then verify the candidates. The efficiency of string similarity search is highly dependent on candidate generation methods. State of the art techniques select fixed length q-grams from a query string and generate candidates using inverted lists of the selected q-grams. In this paper, we propose a technique to generate candidates using variable length grams of a query string and develop a dynamic programming algorithm that selects an optimal combination of variable length grams from a query string. Experimental results show that the proposed technique improves the performance of string similarity search compared with the existing techniques.

유사 문자열 검색을 위해 기존의 기법들은 우선 후보 문자열 집합을 생성한 후에 후보 문자열을 검증하는 방법을 사용한다. 이때, 유사 문자열 검색의 성능을 결정짓는 가장 중요한 요소는 후보 생성 방법이다. 기존의 기법들은 질의 문자열로부터 고정길이 q-그램들을 선택하고, 선택된 q-그램에 해당하는 역리스트를 이용해 후보 문자열을 생성한다. 본 논문에서는 질의 문자열 내의 가변길이 그램들을 사용하여 후보 문자열을 생성할 수 있는 기법과 질의 문자열로부터 최적의 가변길이 그램들의 조합을 선택하는 동적 프로그래밍 알고리즘을 제안한다. 실험을 통해 제안하는 기법이 기존의 기법들 보다 유사 문자열 검색의 성능을 향상시킴을 보인다.

Keywords

Acknowledgement

Supported by : 정보통신기술진흥센터

References

  1. S. Sarawagi and A. Kirpal, "Efficient set joins on similarity predicates," Proc. of the ACM SIGMOD Conference, pp. 743-754, 2004.
  2. C. Li, J. Lu, and Y. Lu, "Efficient merging and filtering algorithms for approximate string searches," IEEE ICDE, pp. 257-266, 2008.
  3. C. Xiao, W. Wang, X. Lin, Ed-join: an efficient algorithm for similarity joins with edit distance constraints, PVLDB, 1, pp. 933-944, 2008.
  4. J. Kim and H. Lee, "Efficient exact similarity searches using multiple token orderings," IEEE ICDE, 2012.
  5. S. Chaudhuri, V. Ganti, and R. Kaushik, "A primitive operator for similarity joins in data cleaning," IEEE ICDE, p. 5, 2006.
  6. J. Kim, "An Effective Candidate Generation Method for Improving Performance of Edit Similarity Query Processing," Information Systems, Vol. 47, No. 1, pp. 116-128, 2015. https://doi.org/10.1016/j.is.2014.07.005
  7. G. Li, D. Deng, J. Wang, and J. Feng, "Pass-join: A partition based method for similarity joins," PVLDB, Vol. 5, pp. 253-264, 2011.
  8. J.Qin, W.Wang, Y.Lu, C.Xiao, and X.Lin, "Efficient exact edit similarity query processing with asymmetric signature schemes," Proc. of the ACM SIGMOD Conference, pp. 1033-1044, 2011.
  9. C. Li, B. Wang, and X. Yang, "VGRAM: Improving performance of approximate queries on string collections using variable-length grams," VLDB, pp. 303-314, 2007.
  10. J. Kim, C. Li, and X. Xie, "Improving read mapping using additional prefix grams," BMC Bioinformatics, 15(1):42, 2014. https://doi.org/10.1186/1471-2105-15-42