Technical, Research Report
@TechReport
Technischer-, Forschungsbericht


Show entries of:

this year (2017) | last year (2016) | two years ago (2015) | Notes URL

Action:

login to update

Options:









Author, Editor

Author(s):

Bast, Holger
Majumdar, Debapriyo
Schenkel, Ralf
Theobald, Martin
Weikum, Gerhard

dblp
dblp
dblp
dblp
dblp



Editor(s):





BibTeX Citekey*:

TechReportGDF2006

Language:

English

Title, Institution

Title*:

IO-Top-k: Index-access Optimized Top-k Query Processing

Institution*:

University of Paderborn, Heinz Nixdorf Institute

Publishers or Institutions Address*:

Paderborn, Germany

Type:

Research Report

No, Year, pp.,

Number*:

DELIS-TR-0323

Pages*:

43

Month:


VG Wort
Pages*:


Year*:

2006

ISBN/ISSN:






DOI:




Note, Abstract, ©

Note:


(LaTeX) Abstract:

Top-k query processing is an important building block for ranked retrieval,with applications ranging from text and data integration to distributed aggregation of network logs and sensor data. Top-k queries operate on index lists for a query's elementary conditions and aggregate scores for result candidates. One of the best implementation methods in this setting is the family of threshold algorithms, which aim
to terminate the index scans as early as possible based on lower and upper bounds for the final scores of result candidates. This procedure performs sequential disk accesses for sorted index scans, but also has the option of performing random accesses to resolve score uncertainty. This entails
scheduling for the two kinds of accesses: 1) the prioritization of different index lists in the sequential accesses, and 2) the decision on when to perform random accesses and for which candidates.

The prior literature has studied some of these scheduling issues, but only for each of the two access types in isolation.
The current paper takes an integrated view of the scheduling issues and develops novel strategies that outperform prior proposals by a large margin. Our main contributions are new, principled, scheduling methods based on a Knapsack-related
optimization for sequential accesses and a cost model for random accesses. The methods can be further boosted by harnessing probabilistic estimators for scores, selectivities, and index list correlations. We also discuss efficient implementation techniques for the underlying data structures.
In performance experiments with three different datasets (TREC Terabyte, HTTP server logs, and IMDB), our methods achieved significant performance gains compared to the best previously known methods: a factor of up to 3 in terms of execution costs, and a factor of 5 in terms of absolute run-times of our implementation. Our best techniques are close to a lower bound for the execution cost of the considered class of threshold algorithms.

Categories / Keywords:


Copyright Message:


HyperLinks / References / URLs:

http://delis.upb.de/docs/tr-abst-0324.html

Personal Comments:


File Upload:


Download
Access Level:

MPG

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Databases and Information Systems Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:
@TECHREPORT{TechReportGDF2006,
AUTHOR = {Bast, Holger and Majumdar, Debapriyo and Schenkel, Ralf and Theobald, Martin and Weikum, Gerhard},
TITLE = {{IO-Top-k}: Index-access Optimized Top-k Query Processing},
YEAR = {2006},
TYPE = {Research Report},
INSTITUTION = {University of Paderborn, Heinz Nixdorf Institute},
NUMBER = {DELIS-TR-0323},
PAGES = {43},
ADDRESS = {Paderborn, Germany},
}


Entry last modified by Uwe Brahm, 04/27/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Matthias Bender
Created
02/12/2007 10:57:58 AM
Revisions
12.
11.
10.
9.
8.
Editor(s)
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
2007-04-27 14:39:15
2007-04-27 14:37:39
12.02.2007 14:06:26
12.02.2007 11:09:56
2007-01-19 11:26:56