Full Citation

Title: Toward Scalable Indexing for Top-k Queries

Citation Type: Journal Article

Publication Year: 2014

ISBN:

ISSN:

DOI:

NSFID:

PMCID:

PMID:

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 with varying scoring functions and retrieval sizes. The existing research efforts can be categorized into three approaches: list-, layer-, and view-based approaches. This paper focuses 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.

Url: https://ieeexplore.ieee.org/document/6587712/

User Submitted?: No

Authors: Lee, Sunyou; Cho, Hyunsouk; Hwang, Seung-won; Lee, Jongwuk

Periodical (Full): IEEE Transactions in Knowledge & Data Engineering

Issue: 12

Volume: 26

Pages: 3103-3116

Data Collections: IPUMS USA

Topics: Methodology and Data Collection

Countries: