Top-k query processing using partitioning-merging techniques = 분할-합병 기법을 이용한 Top-k 질의 처리

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 314
  • Download : 0
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...
Advisors
Whang, Kyu-Youngresearcher황규영researcher
Description
한국과학기술원 : 전산학전공,
Publisher
한국과학기술원
Issue Date
2009
Identifier
327793/325007  / 020035314
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 전산학전공, 2009. 8., [ x, 100 p. ]

Keywords

top-k queries; skyline; convex hull; partitioning; merging; top-k 질의; skyline; convex hull; 분할; 합병; top-k queries; skyline; convex hull; partitioning; merging; top-k 질의; skyline; convex hull; 분할; 합병

URI
http://hdl.handle.net/10203/33278
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=327793&flag=dissertation
Appears in Collection
CS-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0