Top-k query processing using partitioning-merging techniques

Abstract

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 sk...