Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:








Author, Editor

Author(s):

Theobald, Martin
Weikum, Gerhard
Schenkel, Ralf

dblp
dblp
dblp



Editor(s):

Nascimento, Mario A.
Özsu, M. Tamer
Kossmann, Donald
Miller, Renée J.
Blakeley, José A.
Schiefer, K. Bernhard

dblp
dblp
dblp
dblp
dblp
dblp

Not MPII Editor(s):

Nascimento, Mario A.
Özsu, M. Tamer
Kossmann, Donald
Miller, Renée J.
Blakeley, José A.
Schiefer, K. Bernhard

BibTeX cite key*:

TheobaldWS04

Title, Booktitle

Title*:

Top-k Query Evaluation with Probabilistic Guarantees


vldb04-RS17P3.pdf (387.48 KB)

Booktitle*:

Proceedings 2004 VLDB Conference : The 30th International Conference on Very Large Databases (VLDB)

Event, URLs

URL of the conference:

http://www.vldb04.org/

URL for downloading the paper:


Event Address*:

Toronto, Canada

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

30 August 2004

Event End Date:

3 September 2004

Publisher

Name*:

Morgan Kaufmann

URL:


Address*:

St. Louis, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

648-659

Year*:

2004

VG Wort Pages:

52

ISBN/ISSN:

0-12-088469-0

Sequence Number:


DOI:




Note, Abstract, ©

Note:

Acceptance ratio 1:6

(LaTeX) Abstract:

Top-k queries based on ranking elements of multidimensional datasets are a fundamental building block for many kinds of information discovery. The best known general-purpose algo-rithm for evaluating top-k queries is Fagin’s threshold algorithm (TA). Since the user’s goal behind top-k queries is to identify one or a few relevant and novel data items, it is intriguing to use approximative variants of TA to reduce run-time costs. This paper introduces a family of approximative top-k algorithms based on probabilistic arguments. When scanning index lists of the underlying multidimensional data space in descending order of local scores, various forms of convolution and derived bounds are employed to predict when it is safe, with high probability, to drop candidate items and to prune the index scans. The precision and the efficiency of the developed methods are experimentally evaluated based on a large Web corpus and a structured data collection.



Download
Access Level:

Public

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:

@INPROCEEDINGS{TheobaldWS04,
AUTHOR = {Theobald, Martin and Weikum, Gerhard and Schenkel, Ralf},
EDITOR = {Nascimento, Mario A. and {\"O}zsu, M. Tamer and Kossmann, Donald and Miller, Ren{\'e}e J. and Blakeley, Jos{\'e} A. and Schiefer, K. Bernhard},
TITLE = {Top-k Query Evaluation with Probabilistic Guarantees},
BOOKTITLE = {Proceedings 2004 VLDB Conference : The 30th International Conference on Very Large Databases (VLDB)},
PUBLISHER = {Morgan Kaufmann},
YEAR = {2004},
PAGES = {648--659},
ADDRESS = {Toronto, Canada},
ISBN = {0-12-088469-0},
NOTE = {Acceptance ratio 1:6},
}


Entry last modified by Christine Kiesel, 06/15/2005
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)
Ralf Schenkel
Created
05/17/2004 09:20:10 AM
Revisions
14.
13.
12.
11.
10.
Editor(s)
Christine Kiesel
Christine Kiesel
Ralf Schenkel
Ralf Schenkel
Ralf Schenkel
Edit Dates
15.06.2005 10:58:49
31.05.2005 14:55:21
20.04.2005 16:39:48
29.03.2005 16:08:32
09.02.2005 11:25:22
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
vldb04-RS17P3.pdf
View attachments here: