Please use this identifier to cite or link to this item:
Title: Efficient join processing over uncertain data
Authors: Singh, S
Cheng, R
Xia, Y
Prabhakar, S
Shah, R
Vitter, JS
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
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.
Keywords: Imprecise data
Uncertainty management
ISBN: 1-59593-433-2
DOI: 10.1145/1183614.1183719
Appears in Collections:Conference Paper

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


Last Week
Last month
Citations as of Aug 21, 2020

Page view(s)

Last Week
Last month
Citations as of Sep 14, 2020

Google ScholarTM



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