English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Top-k Query Evaluation with Probabilistic Guarantees

Theobald, M., Weikum, G., & Schenkel, R. (2004). Top-k Query Evaluation with Probabilistic Guarantees. In Proceedings 2004 VLDB Conference: The 30th International Conference on Very Large Databases (VLDB) (pp. 648-659). St. Louis, USA: Morgan Kaufmann.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-29E8-B Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-29E9-9
Genre: Conference Paper

Files

show Files
hide Files
:
vldb04-RS17P3.pdf (Any fulltext), 388KB
 
File Permalink:
-
Name:
vldb04-RS17P3.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Theobald, Martin1, Author           
Weikum, Gerhard1, Author           
Schenkel, Ralf1, Author           
Nascimento, Mario A., Editor
Özsu, M. Tamer, Editor
Kossmann, Donald, Editor
Miller, Renée J., Editor
Blakeley, José A., Editor
Schiefer, K. Bernhard, Editor
Affiliations:
1Databases and Information Systems, MPI for Informatics, Max Planck Society, ou_24018              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2005-06-152004
 Publication Status: Issued
 Pages: -
 Publishing info: St. Louis, USA : Morgan Kaufmann
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 231405
Other: Local-ID: C1256DBF005F876D-D56A76BD22C08825C1256E9700284CB5-TheobaldWS04
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Toronto, Canada
Start-/End Date: 2004-08-30

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings 2004 VLDB Conference : The 30th International Conference on Very Large Databases (VLDB)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: St. Louis, USA : Morgan Kaufmann
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 648 - 659 Identifier: ISBN: 0-12-088469-0