블로그 환경에서 중복 포스트의 효과적인 검출 방안

Abstract

본 논문에서는 블로그 환경에서 중복포스트 검출을 효과적으로 처리하 는 방안에 관하여 논의한다. 본 논문에서는 먼저, 기존의 중복문서 검출 기 법에서 발생하는 성능상의 문제점들을 지적하고, 이들을 해결할 수 있는 방법을 제시한다. 제안된 기법은 포스트간의 중복된 정도를 측정하는 것을 시퀀스 간의 중복된 정도를 측정하는 문제로 새롭게 해석하는 것에서 출발 한다. 제안된 기법에서는 효과적인 중복포스트 검출을 위하여 블로그 환경 에서 발생되는 중복포스트의 특성에 착안한 중복률 측정 함수를 제안하고 이를 이용하여 시퀀스의 중심으로부터 일정 크기의 서브시퀀스를 추출하여 비교하므로 써 중복 여부를 빠르게 판정한다. 또한 R^(*)-트리를 사용한 인덱 스 구축과 질의 처리를 기반으로 대용량의 포스트들로부터 중복포스트를 효과적으로 검출한다. 본 논문에서는 실제 블로그 데이터를 이용한 여러 가지 실험을 통하여 제안된 기법이 기존의 중복문서 검출 기법인 Min-hashing보다 빠른 중복포스트 검출이 가능함을 보여 블로그 환경에서 중복포스트 검출을 위한 최적의 기법임을 증명한다. 실험 결과에 의하면, 제안된 방법은 기존 방법과 비교하여 중복포스트 검출의 성능을 최대 6.9 배 개선할 수 있는 것으로 나타났다.; This paper discusses an effective method for detecting duplicate posts in blog environment. We first point out the problems of Min-hashing, a previous method for duplicate document detection, in blog environment and then propose an effective method that overcomes them. The proposed method starts with a new attempt that measures the duplication ratio between two posts. For effective processing of duplicate document detection, we suggest a new notion of duplication ratio that reflects the characteristics of duplicate posts in blog environment. The proposed method rapidly determine whether two blog posts are duplicated by comparing the centers of their feature sequences. In this paper, we call this method CentralMatch. For efficient processing of CentralMatch with large blog post data, we build one or more R*-trees for indexing. Our query processing first converts a query post into a R*-tree search key and searches the R*-tree for the entries matched with the search key. We verify the superiority of our proposed method through extensive experiments with a large volume of real-world blog posts. The experimental results reveal that our method achieves significant speedup up to 6.9 times, compared with Min-hashing.