Toward Scalable Indexing for Top-k Queries
SCIE
SCOPUS
- Title
- Toward Scalable Indexing for Top-k Queries
- Authors
- Lee, J; Cho, H; Lee, S; Hwang, SW
- Date Issued
- 2014-12
- Publisher
- IEEE COMPUTER SOC
- Abstract
- A top-k query retrieves the best k tuples by assigning scores for each tuple in a target relation with respect to a user-specific scoring function. This paper studies the problem of constructing an indexing structure for supporting top-k queries over varying scoring functions and retrieval sizes. The existing research efforts can be categorized into three approaches: list-, layer-, and view-based approaches. In this paper, we mainly focus on the layer-based approach that pre-materializes tuples into consecutive multiple layers. We first propose a dual-resolution layer that consists of coarse-level and fine-level layers. Specifically, we build coarse-level layers using skylines, and divide each coarse-level layer into fine-level sublayers using convex skylines. To make our proposed dual-resolution layer scalable, we then address the following optimization directions: 1) index construction; 2) disk-based storage scheme; 3) the design of the virtual layer; and 4) index maintenance for tuple updates. Our evaluation results show that our proposed method is more scalable than the state-of-the-art methods.
- Keywords
- skyline; convex skyline; for all-dominance; there exists-dominance; dual-resolution layer; SKYLINE; DATABASES
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/13879
- DOI
- 10.1109/TKDE.2013.149
- ISSN
- 1041-4347
- Article Type
- Article
- Citation
- IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, vol. 26, no. 12, page. 3103 - 3116, 2014-12
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.