기본 정보
연구 분야
프로젝트
발행물
구성원
article|
인용수 7
·2013
Toward Scalable Indexing for Top-<inline-formula> <tex-math notation="TeX">\(k\) </tex-math></inline-formula> Queries
Jongwuk Lee, Hyunsouk Cho, Sunyou Lee, Seung-won Hwang
IF 10.4IEEE Transactions on Knowledge and Data Engineering
초록

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.

키워드
TupleComputer scienceSearch engine indexingScalabilityLayer (electronics)Dual layerFocus (optics)NotationInformation retrievalDatabase
타입
article
IF / 인용수
10.4 / 7
게재 연도
2013