Top-k queries return k tuples with the highest (or the lowest) scores in a relation. The score is computed by combining the values of one or more attributes. The weight of each attribute varies according to the user`s preference. Top-k queries are a useful operation for efficient decision making. Users want to see the information in the order of the importance from the users` perspectives because, in a decision making process, users cannot afford to see the entire information whose volume is huge.
In this dissertation, we propose an approach to efficient processing of top-k queries using partitioning-merging techniques. We first partition the database into a number of components and construct an index for each component; we then retrieve top-k tuples by merging as many of these indices as are needed. The partitioning and merging techniques allow us to significantly reduce the number of tuples to be accessed for processing top-k queries.
In the first part of this dissertation, we propose a method that is useful for processing top-k queries in the full space. That is, the queries are expressed based on all the attributes in the database. Layer-based methods are well-known techniques for this kind of top-k query processing. These methods construct a database as a single list of layers. Here, the $i^{th}$ layer has the tuples that can be the top-i tuple. Thus, these methods answer top-k queries by reading at most k layers. Query performance, however, is poor when the number of tuples in each layer (simply, the layer size) is large. In this dissertation, we propose a new layer-ordering method, called the Partitioned-Layer Index (simply, the PL-index), that significantly improves query performance by reducing the layer size. The PL-index uses the notion of partitioning, which constructs a database as multiple sublayer lists instead of a single layer list subsequently reducing the layer size. The PL-index also uses the convex skyline, which is a subset of the skyline, to construct a sublayer to further reduce the layer size. The PL-index has the following desired properties. The query performance of the PL-index is quite insensitive to the weights of attributes (called the preference vector) of the scoring function and is approximately linear in the value of k. The PL-index is capable of tuning query performance for the most frequently used value of k by controlling the number of sublayer lists. Experimental results using synthetic and real datasets show that the query performance of the PL-index significantly outperforms existing methods except for small values of k (say, k ≤ 9).
In the second part of this dissertation, we propose a method that is useful for processing top-k queries in arbitrary subspaces. That is, the queries are expressed based on any arbitrary subset of attributes in the database. To answer these top-k queries efficiently, we propose the Hybrid-Layer Index (simply, the HL-index). Compared to existing approaches, our proposed HL-index significantly reduces the number of tuples accessed during query processing by pruning out tuples based on two criteria: It filters out tuples both (1) globally based on the combination of all attribute values of the tuples (like in Chang et al.[9]) and (2) based on individual attribute values specifically used for the ranking of the tuples (like in Fagin et al.[18]). Through an in-depth analysis of the complicated interaction of the two pruning criteria, we derive a tight bound that reduces the number of tuples retrieved during query processing while guaranteeing the correct query results. We propose the HL-index construction and retrieval algorithms and prove their correctness. Finally, we present our experimental results on synthetic and real dataset comparing the performance of the HL-index to other state-of-the-art indexes. Our experiments demonstrate that the HL-index shows the best (or close to best) performance in most scenarios regardless of the size of the dataset, the number of attributes in the tuples, and the number of attributes used in the queries.
We summarize the contributions of this dissertation as follows. First, we have proposed a new layer-based method that significantly improves top-k query processing in the full space by using the notions of partitioning and the convex skyline, which help reduce the layer size. Second, we have proposed a new hybrid method that significantly improves top-k query processing in arbitrary subspaces by filtering out a tuple both by the global combination of all of its attribute values and by the individual consideration of the particular attribute values. Finally, through extensive experiments, we have shown the effectiveness of the proposed methods.
Top-k 질의는 relation에서 score가 가장 높은 (또는 가장 낮은) k개의 tuple들을 구하는 질의이다. 이때, score는 한 개 또는 여러 개의 attribute들의 값들을 결합함으로써 계산되며, 각 attribute의 중요도 (간단히, attribute weight)는 사용자에 의해 결정된다. 이러한 top-k 질의는 효율적인 의사 결정을 위해 매우 유용하다. 왜냐하면 사용자는 의사 결정 과정에서 방대한 정보를 모두 볼 수 없으며, 따라서 일부의 정보를 자신에게 중요한 순서대로 보기 원하기 때문이다.
본 학위논문에서는 top-k 질의의 효율적인 처리를 위해 분할-합병 기법을 사용하는 접근방법을 제안한다. 먼저, 데이터베이스를 여러 개의 component들로 분할(partitioning)하고 각 component에 대해 index를 구성한다. 그리고, 그 index들을 top-k 결과를 보장할 수 있는 만큼 합병(merging)함으로써 top-k tuple들을 찾는다. 이러한 분할 기법과 합병 기법을 통해 top-k 질의 처리시 읽어 들이는 tuple들의 개수를 크게 줄이는 것이 가능하다.
본 학위논문의 첫 번째 파트에서는 데이터베이스의 모든 attribute들을 고려하는 top-k 질의 처리에 유용한 방법을 제안한다. Top-k 질의를 처리하는 대표적인 방법으로 layer 기반의 방법이 있다. Layer 기반의 방법은 데이터베이스의 tuple들을 layer들의 단일 list (간단히, layer list)로 구성한다. 이때, top-i가 될 수 있는 tuple들을 가지고 i번째 layer를 구성한다. 그리고, 최대 k개까지의 layer들을 읽음으로써 top-k 질의 결과를 구한다. 그러나, 이러한 방법은 각 layer에 속한 tuple들의 개수 (간단히, layer size)가 많을 경우에는 질의 처리 성능이 좋지 않다는 단점을 가진다. 이에 본 학위논문에서는 layer size를 줄임으로써 질의 처리 성능을 향상시킨 Partitioned Layer Index (간단히, PL-index)라는 새로운 layer 기반의 방법을 제안한다. PL-index에서는 “partitioning” 개념을 사용하여 데이터베이스를 단일 layer list로 partition하는 대신 여러 개의 sublayer list들로 partition함으로써 layer size를 줄인다. 그리고, sublayer를 구성하기 위해 skyline의 subset인 convex skyline이라는 새로운 layer 개념을 이용함으로써 layer size를 더욱 줄인다. PL-index는 다음과 같은 바람직한 특성을 가진다. PL-index는 attribute weight들에 대해 질의 처리 성능이 거의 영향을 받지 않으며, k 값이 증가함에 따라 질의 처리 시간이 거의 linear하게 증가한다. 또한, 질의에서 주로 사용되는 k값에 따라 layer list들의 개수를 다르게 조정함으로써 질의 처리 성능을 조율할 수 있다. 합성 데이터와 실제 데이터에 대한 실험을 통하여 제안한 PL-index가 기존의 방법들에 비해 질의 처리 성능이 더 우수함을 보인다. 단, k의 값이 작을 때는 예외이다(예를들어, k ≤ 9).
본 학위논문의 두 번째 파트에서는 데이터베이스의 임의의 일부 attribute들만을 고려하는 top-k 질의 처리에 유용한 방법인 Hybrid-Layer Index (간단히, HL-index)를 제안한다. 기존 방법들과 비교했을 때, HL-index는 불필요한 tuple들을 제거하기 위해 다음 두 가지 제거 기준을 동시에 사용함으로써 질의 처리시 읽어 들이는 tuple들의 개수를 줄인다. (1) “모든” attribute 값들의 조합에 기반하여 top-k 결과가 될 수 없는 tuple들을 제거한다(Chang et al.[9]의 방법을 이용). (2) 질의에서 고려한 “개별” attribute의 값들에 기반하여 top-k 결과가 될 수 없는 tuple들을 제거한다 (Fagin et al.[18]의 방법을 이용). 또한, 이러한 두 가지 제거 기준들 간의 복잡한 상호작용을 심도있게 분석함으로써, 정확한 질의 결과를 보장할 뿐만 아니라 질의 처리 동안 읽어 들이는 tuple의 개수를 줄이는 방법을 유도한다. 그리고, HL-index를 구성하는 알고리즘 및 이를 이용한 질의 처리 알고리즘을 제안하고 알고리즘들이 정확함을 증명한다. 합성 데이터와 실제 데이터에 대한 실험을 통하여 제안한 HL-index가 데이터베이스의 크기, 전체 attribute의 개수, 질의에서 고려한 attribute의 개수와 상관없이 대부분의 경우 기존의 방법들에 비해 질의 처리 성능이 더 우수함을 보인다.
본 학위논문의 공헌을 요약하면 다음과 같다. 첫째, “모든 attribute들(즉, full space)을 고려하는 top-k 질의”를 효과적으로 처리하는 새로운 layer 기반의 방법을 제안하였다. 이 방법은 제안한 partitioning 개념과 convex skyline을 개념을 사용함으로써 layer size를 크게 줄였다. 둘째, “임의의 일부 attribute들만을 (즉, arbitrary subspace) 고려하는 top-k 질의”를 효과적으로 처리하는 새로운 hybrid 방법을 제안하였다. 이 방법은 모든 attribute들에 대해 그 모든 attribute들의 값들을 조합함으로써 불필요한 tuple들을 제거하였고, 동시에 질의에서 고려한 attribute들의 값만을 고려함으로써 불필요한 tuple들을 제거하였다. 마지막으로, 다양한 실험을 통하여 제안한 방법들의 유효성을 입증하였다.
