Stanford InfoLab Publication Server

Confidence-Aware Join Algorithms

Agrawal, Parag and Widom, Jennifer (2009) Confidence-Aware Join Algorithms. In: 25th International Conference on Data Engineering (ICDE 2009), March 29 - April 4, 2009, Shanghai, China.


PDF - Published Version


In uncertain and probabilistic databases, confidence values (or probabilities) are associated with each data item. Confidence values are assigned to query results based on combining confidences from the input data. Users may wish to apply a threshold on result confidence values, ask for the “top-k” results by confidence, or obtain results sorted by confidence. Efficient algorithms for these types of queries can be devised by exploiting properties of the input data and the combining functions for result confidences. Previous algorithms for these problems assumed sufficient memory was available for processing. In this paper, we address the problem of processing all three types of queries when sufficient memory is not available, minimizing retrieval cost. We present algorithms, theoretical guarantees, and experimental evaluation.

Item Type:Conference or Workshop Item (Paper)
Subjects:Computer Science > Query Processing
Related URLs:Project Homepage
ID Code:799
Deposited By:Parag Agrawal
Deposited On:20 Mar 2007 17:00
Last Modified:16 Apr 2009 12:32

Download statistics

Repository Staff Only: item control page