선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 역색인 파일을 이용한 불리 언 질의 최적화 문제는 결국 최적 키워드 처리 순서를 구하는 문제임을 비용 모델을 통해 알 수 있고 이 문제는 데이터베 이스 분야 의 질의 최적화 문제 중 최적 조인 순서를 구 하는 문제와 구조적으로 유사하다. 따라서 본 논문에서는 이 분야의 연구결과를 이용하여 문제를 해결하였다.
- 비용 기반 질의 최적화를 위해서는 질의 처리비용 모델이 필요하다. 본 논문에서는 역 색 인 파일을 사용하여 확장 불리 언 질의를 처리할 경우의 비용 모델을 수립하였다. 그리고 비용모델을 기반으로 하여 키워드에 대한 순차검색 역비용지수와 탐색 비용지수를 정 의하고 이들을 이용하여 질의 최적화 알고리즘을 도춤하였다.
- 본 논문에서는 역색인 파일을 이용한 확장 불리언 질의 최적화를 위해 비용에 기반한 체 계적인 질의 최적화를 시도하였다. 확장 불리 언 질의를 처리하는 방법은 질의를 구성하는 키워드의 처리 순서에 따라 여러 가지가 있을 수 있으므로 이 중에서 최소 비용을 가지는 질의 처리 방법을 구하는 질의 최적화가 필요하다.
- 따라서 새로운 포스텅을 추가할 때 항상 포스텅 리스트의 끝에 추가(append)하게 되면 포스팅 리스트는 문서식별자 순의 정렬을 유지하지 못하지만 포스팅의 추가가 간단해 져 역색인 파일의 변경 비용이 작게 든다. 본 논문에서는 이러한 역색인 파일에 대한 확장 불리언 실의 최적화를 다룬다. 먼저 확장 불 리언 질의에 대한 처리 방법이 여러 가지가 있을 수 있음을 보이고 그 중 비용이 최소가 되는 질의 처리 방법을 선정해 주는 질의 최 적화 알고리즘을 제안한다.
- 확장 불리 언 질의를 처리하는 방법은 질의를 구성하는 키워드의 처리 순서에 따라 여러 가지가 있을 수 있으므로 이 중에서 최소 비용을 가지는 질의 처리 방법을 구하는 질의 최적화가 필요하다. 본 논문에서는 이를 위해 질의 최적화 알고리즘을 제시하고 이의 최적성을 증명하였다. 그리고 실험을 통하여 질의 최적화를 수 행할 경우와 수행하지 않을 경우의 질의 처리 비용 비교를 통해 질의 최적화의 중요성을 입증하였다.
가설 설정
- 역색인 파일을 이용한 불리언 질의 최적화 연구로는 Liu(1976)가 주어진 불리 언 질의와 동등한 질의 형태 중 포스팅 리스트의 병합 을 가장 호율적으로 만드는 질의 형태를 구 하는 최적화 알고리즘을 제시하였다. 본 논문에서는 Liu(1976)가 제시한 알고리즘을 통해 결정된 질의 형태를 가정하고 그 질의 형태 에서의 최적 키워드 처리 순서를 다룬다. Moffat(1996)은 압축된 포스텅 리스트에 대한 불리언 칠의 처리 속도를 높이기 위해 포 스팅 리스트 내부에 색 인 정보를 심는 방안 을 제안하였고, Tomasic(1993)은 불리언 질 의의 분산 처리 속도를 높일 수 있는 역색인 파일 저장 구조를 연구하였다.
- 비용 파라미터들의 값을 구하기 위하여 역 색인 파일의 키워드 디렉토리를 와 같이 유지한다고 가정한다.
- 또한 질의 최적화를 수행하는 경우와 수행하지 않는 경우의 질의 처 리비용을 서로 비교해 봄으로써 질의 최적화 의 중요성을 입증한다. 질의 처리비용은 수식(1)의 비용모델에 의하며 질의 최적화를 수 행하지 않는 경우에는 질의에 명시된 키워드 순서대로 질의를 처리한다고 가정한다.
- 포스팅 리스트 탐색 비용은 별도의 탐색 구조를 사용하지 않으면 포스팅 리스트 순차 검색 비용과 같고, 사용하면 달라진다. 키워 드 W1과 W2는 별도의 탐색 구조를 사용하지 않고 키워드 W3은 별도의 탐색 구조를 사용 한다고 가정한다. 따라서 키워드 W1과 W2의 포스텅 리스트 탐색 비용은 포스팅 리스트 순차검색 비용과 같고, 키워드 W3의 포스팅 리스트 탐색 비용은 포스팅 리스트 순차검색 비용보다 작다.
- <표 2>에서 보는 바와 같이 키워드 W3의 포스팅 리스트 순차검색 비용은 키워드 W2의 포스팅 리스트 순차검색 비용보다 더 크지만 별도의 탐색 구조를 사용함으 로써 키워드 W3의 포스팅 리스트 탐색 비용 은 키워드 W2의 포스팅 리스트 탐색 비용보다 더 작다. 한편, 본 실험에서는 저장된 총 문서의 개수 nP를 1,000, 000으로 가정하였다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.