A top-k spatial keyword query returns the k best spatio-textual objects ranked based on their proximity to the query location and relevance to the query keywords. It allows users to find the objects in the order of importance according to the users` preference on spatial proximity and textual relevancy. In this dissertation, we propose a generic approach for indexing top-k spatial keyword queries. The goal of the dissertation is to exhaustively investigate possible indexing methods for top-k spatial keyword queries and to identify the most appropriate method for a certain usage pattern (i.e., a set of query loads and frequencies). To achieve this, we model an indexing method for top-k spatial keyword queries as a combination of various clustering techniques. First, we propose a new method for top-k spatial keyword queries employing a novel clustering technique. Second, we propose an index generation model for top-k spatial keyword queries by combining multiple clustering techniques.
In the first part of this dissertation, we propose a new method for the separate index approach called Rank-Aware Separate Index Method(RASIM) for top-k spatial keyword queries. Possible indexing approaches for top-k spatial keyword queries can be classified into two categories: the separate index approach and the hybrid index approach. The separate index approach maintains the spatial index and the text index independently and can accommodate new data types. However, it has been considered difficult to support top-k pruning in the separate index approach since it requires clustering/ordering the objects by two different criteria---one for top-k pruning and the other for efficient merging.
Naturally, all the existing methods have been based on the hybrid index approach. Thus, we need to develop a new method supporting top-k pruning based on the separate index approach by devising a technique that clusters the objects by multiple criteria. RASIM supports both top-k pruning and efficient merging at the same time by clustering each separate index in two different orders through the partitioning technique. Specifically, RASIM partitions the set of objects in each index into rank-aware (RA) groups that contain the objects with similar scores and applies the first order to these groups according to their scores and the second order to the objects within each group according to their object IDs. Based on the RA groups, we propose two query processing algorithms: 1)
External Threshold Algorithm (External TA) that supports top-k pruning in the unit of RA groups and 2) Generalized External TA that enhances the performance of External TA by exploiting special properties of the RA groups. RASIM is the first research work that supports top-k pruning based on the separate index approach. Naturally, it keeps the advantages of the separate index approach. In addition, in terms of storage and query processing time, RASIM is more efficient than the IR-tree method, which is the prevailing method to support top-k pruning to date and is based on the hybrid index approach. Experimental results show that, compared with the IR-tree method, the index size of RASIM is reduced by up to 1.85 times, and the query performance is improved by up to 3.22 times.
In the second part of this dissertation, we propose an index generation model for top-k spatial keyword queries. Many indexing methods have been proposed for spatial keyword queries, but only a few of them support top-k spatial keyword queries. Even among these,
each method fits certain query loads only. Moreover, there are query loads that none of
the existing methods can handle effectively. In this dissertation, we present a generic index generation model for top-k spatial keyword queries. For this, we define a set of basic clustering operators and show that we can generate various indexing methods for top-k spatial keyword queries by combining these operators. The result shows that all the existing methods map to our generated methods. This sheds new light on understanding existing methods under a unified framework. Using this model, we also discover three new
methods that have not been reported before. We also propose a cost model for all the generated methods. We then use the cost model to evaluate indexing methods and to identify the most appropriate one for a specific query load. Consequently, our model allows us to do physical database design to find an optimal indexing method for a given usage pattern. Our experiments show that the best indexing method identified by the cost model for a specific query load is consistent with that identified by the experimental results.
We summarize the contributions of this dissertation as follows. First, we have proposed a novel efficient method for top-k spatial keyword queries. It is the first research effort to support top-k pruning based on the separate index approach. Second, we have proposed an index generation model for top-k spatial keyword queries. The salient points of our model are that 1) we have enumerated all the possible methods from the viewpoint of clustering of objects, 2) we have shown that the model encompasses all the existing methods, and 3) we have discovered a few new methods that have not been reported in the literature. Finally, through cost analysis and extensive experiments, we have shown the effectiveness of the proposed methods.
Top-k 공간-키워드 질의는 질의점에 대한 공간 인접성과 질의 키워드에 대한 문서 관련성을 기반으로 랭킹을 메겨 상위 k개의 공간-텍스트 객체들을 찾는다. 이 질의는 사용자가 공간 인접성과 문서 관련성에 대한 사용자 선호도에 따라 중요한 순서대로 객체들을 찾을 수 있도록 해준다.
본 학위 논문에서는 top-k 공간-키워드 질의를 위한 포괄적 색인 접근법을 제안한다. 본 학위 논문의 목표는 top-k 공간-키워드 질의를 위한 가능한 색인 방법들을 철저하게 조사하고, 특정 사용 패턴 (즉, 질의 로드와 사용빈도의 집합)을 위한 가장 적합한 방법을 찾는 것이다. 이를 위하여, top-k 공간-키워드 질의를 위한 색인 방법을 다양한 클러스터링 기법들의 조합으로 모델한다. 첫째, 한 가지 기발한 클러스터링 기법을 적용함으로써 top-k 공간-키워드 질의를 위한 새로운 방법을 제안한다. 둘째, 다수의 클러스터링 기법들을 조합함으로써 top-k 공간-키워드 질의를 위한 색인 생성 모델을 제안한다.
본 학위 논문의 첫 번째 파트에서는 top-k 공간-키워드 질의를 위한 분리 색인 접근법 기반의 새로운 방법인 랭크를 알고 있는 분리 색인 방법 (간단히, RASIM)을 제안한다. Top-k 공간-키워드 질의를 위한 가능한 색인 접근법은 1) 분리 색인 접근법과 2) 혼합 색인 접근법으로 분류된다.
분리 색인 접근법은 공간 색인과 텍스트 색인을 독립적으로 유지할 수 있으며, 새로운 데이터 타입에 대한 확장성이 좋다. 그러나, 분리 색인 접근법은 top-k 가지치기(pruning)와 효율적인 합병(merging)을 위한 서로 다른 두 가지 순서에 의한 객체들의 클러스터링을 요구하기 때문에
분리 색인 접근법을 기반으로 top-k 가지치기를 지원하는 것은 어렵다고 고려되어져 왔다. 자연스럽게, 기존의 모든 방법들은 혼합 색인 접근법을 기반으로 하고 있다. 따라서, 다수의 기준에 의하여 객체들을 클러스터하는 기술을 고안함으로써 분리 색인 접근법을 기반으로 top-k 가지치기를 지원하는 새로운 방법을 개발할 필요가 있다. RASIM은 각 색인을 분할 기법을 사용하여 두 가지 서로 다른 순서로 클러스터링함으로써 top-k 가지치기와 효율적인 합병을 모두 지원한다. 구체적으로, RASIM은 각 색인의 전체 객체들을 점수가 유사한 객체들의 집합인 랭크를 알고 있는 그룹들(간단히, rank-aware(RA) 그룹들)로 분할한다. 그룹들 간에는 점수에 따른 첫 번째 순서를 적용하고 각 그룹 내의 객체들에는 객체 식별자에 따른 두 번째 순서를 적용한다. RA 그룹을 기반으로, 본 논문에서는 두 가지 질의 처리 알고리즘을 제안한다. 첫째, RA 그룹 단위로 top-k 가지치기를 지원하는 External Threshold Algorithm (External TA)이다. 둘째, RA 그룹의 특성을 이용함으로써 External TA의 성능을 향상시킨 Generalized External TA이다. RASIM은 분리 색인 접근법을 기반으로 top-k 가지치기를 지원하는 첫 번째 연구이다. 자연스럽게, RASIM은 분리 색인 접근법의 장점을 유지한다. 또한, RASIM은 top-k 가지치기를 지원하는 가장 저명한 방법이면서 혼합 색인 접근법을 기반으로 하는 IR-tree 방법에 비하여 저장 공간과 질의 처리 시간 측면에서 효율적이다. 실험 결과, RASIM이 IR-tree 방법의 색인 크기를 최대 1.85배 줄이면서, 질의 처리 성능은 최대 3.22배 향상됨을 보였다.
본 학위 논문의 두 번째 파트에서는 top-k 공간-키워드 질의를 위한 색인 생성 모델을 제안한다.
공간-키워드 질의를 지원하기 위한 많은 색인 방법들이 제안되어져 왔지만, 그들 중 일부만이 top-k 공간-키워드 질의를 지원한다. 심지어, 이들 중 각 방법은 특정 질의 로드에만 적합하다.
또한, 기존의 어떠한 방법으로도 효과적으로 처리할 수 없는 질의 로드가 존재한다. 본 학위 논문에서는 top-k 공간-키워드 질의를 위한 포괄적인 색인 생성 모델을 제시한다. 이를 위하여 기본적인 클러스터링 연산자들의 집합을 정의하고 이들 연산자들을 조합함으로써, top-k 공간-키워드 질의를 위한 다양한 색인 방법들을 생성할 수 있음을 보인다. 이 결과는 기존의 모든 방법들이 모델에 의하여 생성된 방법들로 맵핑됨을 보인다. 이것은 기존의 방법들을 하나의 통합된 프레임워크로 이해하도록 재조명한 것이다. 또한, 이 모델은 기존에 발표되지 않은 새로운 세 가지 방법들을 발견한다. 다음으로, 생성된 모든 색인 방법들을 위한 비용 모델을 제안한다. 비용 모델은 색인 방법들을 평가하고 특정 질의 로드에 대하여 가장 적합한 색인 방법을 찾아내기 위하여 사용된다. 결과적으로, 제안한 모델은 특정 사용 패턴에 대해 최적의 색인 방법을 찾기 위한 물리적 데이터베이스 디자인에 사용될 수 있다. 실험을 통하여, 특정 질의 로드에 대해 비용 모델에 의한 최선의 색인 방법이 실험 결과에 의한 최선의 색인 방법과 일치함을 보인다.
본 학위 논문의 공헌을 요약하면 다음과 같다. 첫째, top-k 공간-키워드 질의를 위한 참신하고 효율적인 방법을 제안하였다. 제안한 방법은 분리 색인 접근법을 기반으로 top-k 가지치기를 지원하는 최초의 연구이다. 둘째, top-k 공간-키워드 질의를 위한 색인 생성 모델을 제안하였다. 제안한 모델의 핵심은 1) 객체들에 대한 클러스터링 관점에서 가능한 모든 방법들을 나열하였고, 2) 모델이 기존의 모든 방법들을 포함함을 보였으며, 3) 이전에 발표되지 않은 새로운 방법들을 발견한 것이다. 마지막으로, 비용 분석과 광범위한 실험을 통하여 제안한 방법들의 효과를 보였다.
