Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Quick Search
My eDoc
Session History
Support Wiki
Direct access to
document ID:

          Institute: MPI für Informatik     Collection: Databases and Information Systems Group     Display Documents

ID: 231405.0, MPI für Informatik / Databases and Information Systems Group
Top-k Query Evaluation with Probabilistic Guarantees
Authors:Theobald, Martin; Weikum, Gerhard; Schenkel, Ralf
Editors:Nascimento, Mario A.; Özsu, M. Tamer; Kossmann, Donald; Miller, Renée J.; Blakeley, José A.; Schiefer, K. Bernhard
Publisher:Morgan Kaufmann
Place of Publication:St. Louis, USA
Date of Publication (YYYY-MM-DD):2004
Title of Proceedings:Proceedings 2004 VLDB Conference : The 30th International Conference on Very Large Databases (VLDB)
Start Page:648
End Page:659
Place of Conference/Meeting:Toronto, Canada
(Start) Date of Conference/Meeting
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2005-06-15
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Gerhard Weikum
Affiliations:MPI für Informatik/Databases and Information Systems Group
Full Text:
You have privileges to view the following file(s):
vldb04-RS17P3.pdf  [387,00 Kb] [Comment:file from upload service]  
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.