효율적인 Top-k 공간-키워드 다각형 질의 처리 (Efficient Top-k Spatial-Keyword Polygonal Query Processing)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 데이타베이스연구 / 29권 / 2호 / 27 ~ 42페이지
· 저자명 : 권혁윤

초록

본 논문에서는 top-k 공간-키워드 다각형 질의 (top-k spatial-keyword polygonal queries)를 정의하고 이질의를 효율적으로 처리하는 방법을 제안한다. Top-k 공간-키워드 다각형 질의는 다각형 객체들(polygonal objects) (예를 들어, polygons, line segments, polygonal chains)에 대한 질의와의 공간 인접성과 문서 관련성에 따라 관련 정도가 높은 순서로 상위 k개의 객체를 반환한다. 포인트 객체에 대한 질의와의 공간 인접성과문서 관련성에 따라 관련 정도가 높은 순서로 상위 k개의 결과를 반환하는 질의는 top-k 공간-키워드 질의(top-k spatial keyword queries)라고 부르며, 이 질의에 대해서는 기존에 많은 연구가 수행되어 왔다. 그러나 top-k 공간-키워드 다각형 질의는 연구된 적이 없으며, 이 질의는 데이터 파일내의 객체에 대한 접근을 요구하는 특성으로 인하여 top-k 공간-키워드 질의와는 다른 질의 처리 방법을 요구한다. 본 논문에서는 top-k 공간-키워드 다각형질의를 효율적으로 처리하기 위한 방법인 Polygon-RASIM을 제안한다. Polygon-RASIM은 색인으로부터 질의와관련 있는 객체들의 근사적인 스코어를 계산하고, 이들을 데이터 파일에서 접근하여 정확한 스코어를 계산하여 상위 k개의 결과를 찾는다. Polygon-RASIM의 핵심적인 특성은 1) 색인의 각 디스크 페이지에 저장되는 객체들의순서와 데이터 파일에 저장되는 객체들의 순서를 동일한 기준으로 클러스터링하고, 2) space-filling curve에 따른객체들의 순서를 클러스터링 기준으로 이용함으로써 공간적으로 인접한 객체들을 데이터 파일에서도 인접하게 저장하는 것이다. 이에 따라, Polygon-RASIM은 다음의 장점을 가진다. 1) 색인으로부터 반환되는 각 디스크 페이지 내의 객체들의 순서와 데이터 파일에 저장된 객체들의 순서가 동일하기 때문에 색인으로부터 검색된 객체들을데이터 파일로부터 순차적으로 접근할 수 있다. 2)　공간적으로 인접한 객체들을 데이터 파일에서 같은 디스크 페이지에 저장함으로써 데이터 파일 접근의 오버헤드를 줄일 수 있다. 본 논문에서는 성능 비교를 위하여 top-k 공간-키워드 질의에 대한 대표적인 연구들인 IR-tree와 S2I를 top-k 공간-키워드 다각형 질의를 처리하도록 확장한Polygon-IRtree와 Polygon-S2I를 제시한다. 실험을 통하여 Polygon-RASIM이 Polygon-IRtree와Polygon-S2I의 질의 처리 성능을 각각 최대 9.44배, 18.36배까지 향상시킴을 보인다.

영어초록

In this paper, we define top-k spatial-keyword polygonal queries and propose an efficient method for processing those queries. Top-k spatial-keyword polygonal queries find the top-k objects in the order of the relevancy between the query and the object based on spatial proximity and textual relevancy on polygonal objects such as polygons, line segments, or polygonal chains. The queries that find the top-k objects in the order of the relevancy between the query and the object based on spatial proximity and textual relevancy on point objects are called as top-k spatial keyword queries. There have been a lot of research efforts for top-k spatial keyword queries. However, there has been no research efforts for top-k spatial keyword polygonal queries, and those queries require different query processing methods from the top-k spatial keyword queries due to accessing data files. In this paper, we propose an efficient method for top-k spatial keyword polygonal queries, which we call Polygon-RASIM. Polygon-RASIM calculates approximate scores of the objects relevant to the query from the index, calculates their exact scores by accessing them in the data files, and finds the top-k results among them. The novel characteristics of Polygon-RASIM are as follows. 1) We cluster the objects in a disk page of the index and those in data files by the same clustering criterion. 2) We use the order of the objects according to space-filling curve as the clustering criterion. As a result, Polygon-RASIM has the following advantages. 1) We can access the objects in data files sequentially since the order of objects searched from the index is the same as the order of objects stored in data files. 2) We reduce the overhead for accessing data files by storing the objects that are close in the space in the same disk page. For the comparison of the query performance, we extend IR-tree and S2I, which are representative existing methods for top-k spatial keyword queries, for processing top-k spatial-keyword polygonal queries. Though experiments, we show that the query performance of Polygon-RASIM improves those of Polygon-IRtree and Polygon-S2I by up to 9.44 times and 18.36 times, respectively.

참고자료

· 없음