Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/39810
Title: Efficient join processing over uncertain data
Authors: Singh, S
Cheng, R
Xia, Y
Prabhakar, S
Shah, R
Vitter, JS
Keywords: Imprecise data
Joins
Uncertainty management
Issue Date: 2006
Source: CIKM '06 Proceedings of the 15th ACM International Conference on Information and Knowledge Management, Arlington, USA, November 2006, p. 738-747 How to cite?
Abstract: In many applications data values are inherently uncertain. This includes moving-objects, sensors and biological databases. There has been recent interest in the development of database management systems that can handle uncertain data. Some proposals for such systems include attribute values that are uncertain. In particular, an attribute value can be modeled as a range of possible values, associated with a probability density function. Previous efforts for this type of data have only addressed simple queries such as range and nearest-neighbor queries. Queries that join multiple relations have not been addressed in earlier work despite the significance of joins in databases. In this paper we address join queries over uncertain data. We propose a semantics for the join operation, define probabilistic operators over uncertain data, and propose join algorithms that provide efficient execution of probabilistic joins. The paper focuses on an important class of joins termed probabilistic threshold joins that avoid some of the semantic complexities of dealing with uncertain data. For this class of joins we develop three sets of optimization techniques: item-level, page-level, and index-level pruning. These techniques facilitate pruning with little space and time overhead, and are easily adapted to most join algorithms. We verify the performance of these techniques experimentally.
URI: http://hdl.handle.net/10397/39810
ISBN: 1-59593-433-2
DOI: 10.1145/1183614.1183719
Appears in Collections:Conference Paper

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

29
Citations as of Feb 26, 2017

Page view(s)

28
Last Week
1
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.