선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 블로그 서비스 시스템에서는 문서가 생성되는 시점에 중복 여부 판정이 가능하고, 문서의 생성 시각을 이용해 중복된 문서들 중에서 원본문서를 판정할 수 있다. 따라서 본 논문에서는 이와 같은 블로그 서비스 시스템의 특성에 착안하여 문서 생성시점에서 중복 여부를 판정하고, 중복문서로 판정될 경우 해당 문서를 검색 인덱스에 삽입하지 않음으로써 원천적으로 검색 결과에 중복문서를 반영하지 않는 효과적인 중복문서 처리 프레임워크를 제안하였다.
제안 방법
- 3. 효과적인 검출을 위해 인덱싱 기법 제안.
- 4. 검출된 중복문서를 블로그 검색엔진에 반영하지 않는 처리 과정 제안.
- 중복 판정 인덱스를 구축하였다. 그런 다음, 각각의 중복 판정 인덱스를 사용하여 1, 000개의 질의 문서에 대한 질의 처리 시간을 측정한 후, 1000으로 나누어 한 개의 문서에 대해 평균 질의 처리 시간을 계산하였다’ 또한, 세 가지 인덱싱 및 질의처리 방법에 대해 페이지 접근 횟수를 측정하였다. 질의 처리 성능 실험을 위하여본 논문에서는 2G의 메모리 크기와 3 GHz 펜티엄 4 CPU를 가진 윈도우즈 XP 미디어 센터를 이용하여 수행하였다.
- 임의의 두 문서가 중복문서로 판정되기 위해서는 2개 이상의 문서 특징이 동일해야 하므로, 6개의 B-트리를 검색된 결과로 반환된 문서 ID들 중 검색 결과 내 두 개 이상 존재하는 문서 ID를 찾아내는 후처리 과정이 필요하다. 따라서 i 번째 B-트리(L, M5)와, 번째 B-트리(2MJM6, 扑勺)에서 검색된 문서 ID들의 모든 쌍을 비교하여, 일치하는 문서 ID가 적어도 하나 이상 존재하면, 이후의 인덱스 검색을 중단하고 질의 처리에 사용된 문서를 중복문서로 판정한다.
- 문서 집합으로 구성하였다. 또한, 수집된 전체 문서 집합으로부터 1, 000개 문서를 무작위로 선정하고, 해당 문서에서 임의의 위치에 있는 1〜5개의 단어를 다른 단어로 변경하여 질의 문서들을 생성하였다.
- 중복문서가 아닌 것으로 판정된 경우에는 검색 인덱스에 반영하고 데이터베이스에 저장한다. 또한, 이후의 중복문서 검출을 위하여 해당 문서의 15개의 인덱스 키들을 각각 대웅되는 2차원 R*- 트리에 반영시킨다. 반면, 중복문서로 판정된 경우에는 중복문서를 데이터베이스에는 저장하되, 검색인덱스에 반영하지 않는다.
- 구성되며, 모든 조합의 순서대로 2차원 R*- 트리 15개에 차례로 저장된다. 또한, 질의처리 시 질의 점과 동일한 점이 검색될 때까지 15개의 질의 점을 순서에 맞는 2차원 R*-트리를 이용해 검색한다.
- 검출을 위해 인덱싱 기법을 제안한다. 마지막으로 검출된 중복문서를 블로그 검색엔진에 반영하지 않는 처리 과정을 제안한다. 본 논문의 공헌은 다음과 같다.
- 이러한 인덱스 구조를 기반으로 하는 질의 처리 과정은 다음과 같다. 먼저, 질의 처리에 사용될 문서로부터 추출된 6개 의를 2개씩 조합하여 조합의 순서와 함께 15개 질의 엔트리를 생성한다. 각 질의 엔트리에 대하여 3차원 R*- 트리를 검색한다.
- 본 논문에서는 문서의 생성시점을 알 수 있다는 블로그 서비스 시스템의 특징을 이용하여 중복문서를 검출하는 프레임워크를 제안한다’ 제안하는 프레임워크는 기존 Min-hashing 기법을 기반하고 있으며, 효과적인 중복문서 검출을 위해 인덱싱 기법을 제안한다. 마지막으로 검출된 중복문서를 블로그 검색엔진에 반영하지 않는 처리 과정을 제안한다.
- 본 논문에서는 제안하는 기법의 확장성(scalability)을 검증하기 위해 약1, 500, 000개의 실제 블로그 데이터를 사용하여 문서의 증가에 따른 질의 처리 성능 변화를 측정하였다. 또한, 인덱싱 및 질의처리 기법의 변형들을 제안하고 질의 처리 성능을 비교함으로써 제안하는 인덱싱 및 질의처리 기법의 우수성을 입증하였다.
- 본 실험에서는 제안된 세 가지 인덱싱 및 질의처리 방법에 대해서, 5개의 실험 데이터 집합을 사용하여 5개의 중복 판정 인덱스를 구축하였다. 그런 다음, 각각의 중복 판정 인덱스를 사용하여 1, 000개의 질의 문서에 대한 질의 처리 시간을 측정한 후, 1000으로 나누어 한 개의 문서에 대해 평균 질의 처리 시간을 계산하였다’ 또한, 세 가지 인덱싱 및 질의처리 방법에 대해 페이지 접근 횟수를 측정하였다.
- 그런 다음, 각각의 중복 판정 인덱스를 사용하여 1, 000개의 질의 문서에 대한 질의 처리 시간을 측정한 후, 1000으로 나누어 한 개의 문서에 대해 평균 질의 처리 시간을 계산하였다’ 또한, 세 가지 인덱싱 및 질의처리 방법에 대해 페이지 접근 횟수를 측정하였다. 질의 처리 성능 실험을 위하여본 논문에서는 2G의 메모리 크기와 3 GHz 펜티엄 4 CPU를 가진 윈도우즈 XP 미디어 센터를 이용하여 수행하였다.
- 이때, /; 는 i 번째 B-트리에 저장한다. 질의할 문서의 6개의 无가 주어지면, 각각의 无로부터 생성된 질의 엔트리 3>를 사용하여 6개의 B-트리를 검색한다. 임의의 두 문서가 중복문서로 판정되기 위해서는 2개 이상의 문서 특징이 동일해야 하므로, 6개의 B-트리를 검색된 결과로 반환된 문서 ID들 중 검색 결과 내 두 개 이상 존재하는 문서 ID를 찾아내는 후처리 과정이 필요하다.
대상 데이터
- 000/1 60。, 000개, 900, 0007]], 1, 200, 000개, 1, 500, 000개의 총 5 개의 문서 집합으로 구성하였다. 또한, 수집된 전체 문서 집합으로부터 1, 000개 문서를 무작위로 선정하고, 해당 문서에서 임의의 위치에 있는 1〜5개의 단어를 다른 단어로 변경하여 질의 문서들을 생성하였다.
- 본 논문에서는 제안하는 기법의 질의 처리 성능을 평가하기 위하여 블로그 사이트 중 하나인 이글루스 (Egloos)[4]로부터 1, 525, 465개 문서를 수집하였다’ 그리고 데이터 셋의 크기 증가에 따른 질의 처리 성능 변화를 측정하기 위해, 수집한 문서들로부터 각각 300, 000/1 60。, 000개, 900, 0007]], 1, 200, 000개, 1, 500, 000개의 총 5 개의 문서 집합으로 구성하였다. 또한, 수집된 전체 문서 집합으로부터 1, 000개 문서를 무작위로 선정하고, 해당 문서에서 임의의 위치에 있는 1〜5개의 단어를 다른 단어로 변경하여 질의 문서들을 생성하였다.
이론/모형
- 먼저, HTML 문서 형태로 되어 있는 문서로부터 HTML 태그를 분석하여 블로그 프레임을 제외한 코어 텍스트를 추출한다. 이렇게 추출된 코어 텍스트로부터 기존 Min-hashing 기법을 이용하여 순서를 가진 6개의 고정 크기 정수 값으로 변환한다. 따라서 기존 Min-hashing과 제안하는 프레임워크의 정확도는 동일하다.
성능/효과
- 5. 실험을 통해 제안한 3가지 인덱스 성능을 비교하여가장 우수한 인덱스 기법을 보임.
- 예를 들어, B6D1 기법에서 첫 번째 B-트리와 두 번째 B-트리만을 검색하여 중복인 문서를 찾았다면, 남은 3-6번째 B-트리는 검색하지 않는다. R1D3 기법은 실험 데이터 1, 500, 000개에서 평균 38.9회의 페이지 접근이 발생되었으며, R15D2 기법과 B6D1 기법은 각각 평균 29.9회와 평균 23.3회의 페이지 접근이 발생되었다. B6D1 기법이 R15D2 기법에 비해 적은 페이지 접근이 발생되는 반면, 그림 2의 질의 처리 시간은 B6D1 기법이 R15D2 기법에 비해 많이 소요되는 것은 B6D1 에서 발생되는 후처리 연산의 오버헤드가 크다는 것을 설명해준다.
- 또한, 인덱싱 및 질의처리 기법의 변형들을 제안하고 질의 처리 성능을 비교함으로써 제안하는 인덱싱 및 질의처리 기법의 우수성을 입증하였다. 그 결과 제안하는 프레임워크에서 사용되는 2차원 R*- 트리 15개를 사용한 인덱싱 기법이 다른 인덱싱 기법에 비해 약 0.5배에서 2배 정도 우수한 성능을 나타내는 것을 알 수 있었다.
- 또한, B6D1 기법은 질의 결과로 나온 후보들 중에서 동일한 후보들을 찾는 추가적인 연산 시간을 포함하였다. 그 결과, 실험 데이터가 1, 500, 000개 문서일 때, 3차원 R*- 트리 1개를 사용한 경우 하나의 문서에 대한 평균 질의 처리 시간이 0.417초, B-트리 6 개를 사용한 경우 0.244초 2차원 R*- 트리 15개를 사용한 경우 0.214초가 소요되어 2차원 R*- 트리 15개를 사용한 기법의 성능이 가장 우수하였음을 보였다. 그림 2 에서 실험 데이터가 1, 200, 000개 문서일 때, 2차원 R*- 트리 15개를 사용한 인덱싱 기법이 B-트리 6개를 사용한 인덱싱 기법보다 평균 질의 처리 시간이 빨라지는 것을 볼 수 있다.
- 또한, 인덱싱 및 질의처리 기법의 변형들을 제안하고 질의 처리 성능을 비교함으로써 제안하는 인덱싱 및 질의처리 기법의 우수성을 입증하였다. 그 결과 제안하는 프레임워크에서 사용되는 2차원 R*- 트리 15개를 사용한 인덱싱 기법이 다른 인덱싱 기법에 비해 약 0.
- 인덱스 구축에 사용되는 문서의 개수를 D 라고 할 때, 인덱스 검색 시 페이지 접근 횟수는 검색되는 인덱스 개수 乂 log虫쓰维으〃 이다. 문서의 개수 D가 1, 500, 000일 때, 제안된 세 가지 기법의 예상되는 페이지 접근 횟수는 3차원 R*- 트리 1개를 사용한 기법에서 약 55.0회가 발생되며, B-트리 6개를 사용한 기법에서는 약 14.9회, 그리고 R*- 트리 15개를 사용한 기법에서는 약 42.6회의 페이지 접근이 발생된다.
- B6D1 기법이 R15D2 기법에 비해 적은 페이지 접근이 발생되는 반면, 그림 2의 질의 처리 시간은 B6D1 기법이 R15D2 기법에 비해 많이 소요되는 것은 B6D1 에서 발생되는 후처리 연산의 오버헤드가 크다는 것을 설명해준다. 실험 결과를 통해 본 논문에서 제안한 세 가지 인덱싱 및 질의처리 기법들 중 R15D2 기법이 중복문서 검출에 가장 효과적인 인덱싱 및 질의처리 기법인 것으로 나타났다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.