Managing and Mining Uncertain Data

Preface

Contents

List of Figures

List of Tables

Chapter 1 AN INTRODUCTION TO UNCERTAIN DATA ALGORITHMS AND APPLICATIONS

1. Introduction

2. Algorithms for Uncertain Data

3. Conclusions

Acknowledgements

References

Chapter 2 MODELS FOR INCOMPLETE AND PROBABILISTIC INFORMATION

1. Introduction

2. Incomplete Information and Representation Systems

3. RA-Completeness and Finite Completeness

4. Closure Under Relational Operations

5. Algebraic Completion

6. Probabilistic Databases and Representation Systems

7. Probabilistic ?-Tables and Probabilistic Or-Set Tables

8. Probabilistic c-tables

9. Queries on Annotated Relations

10. K-Relations

11. Polynomials for Provenance

12. Query Containment

13. RelatedWork

14. Conclusion and Further Work

Acknowledgments

References

15. Appendix

Chapter 3 RELATIONAL MODELS AND ALGEBRA FOR UNCERTAIN DATA

1. Introduction

2. Different Probabilistic Data Models

2.1 Point-Valued Probability Measures Assigned to Each Tuple

2.2 Point-Valued Probability Measures Assigned to Attributes and Attribute Sets

2.3 Interval-Valued Probability Measures Assigned to Attribute-Values

2.4 Interval-valued Probability Measures Assigned to Tuples

3. Probabilistic Relational Algebra

3.1 Basic Definitions

3.2 Primary and Foreign Keys

3.3 Relational Operations

3.4 Relational Algebra

3.5 Incomplete Distribution and Null Values

4. Algebraic Implications of the Different Representations and Associated Assumptions

4.1 Models Assigning Point-Valued Probability Measures at the Tuple Level

4.2 Models Assigning Point-Valued Probability Measures at the Attribute Level

4.3 Models Assigning Interval-Valued Probability Measures at the Attribute Level

4.4 Models Assigning Interval-Valued Probability Measures to Tuples

4.5 Some Observations on the Independence Assumption Across Tuples

5. Concluding Remarks

References

Chapter 4 GRAPHICAL MODELS FOR UNCERTAIN DATA

1. Introduction

2. Graphical Models: Overview

2.1 Directed Graphical Models: Bayesian Networks

2.2 Undirected Graphical Models: Markov Networks

2.3 Inference Queries

3. Representing Uncertainty using Graphical Models

3.1 PossibleWorld Semantics

3.2 Shared Factors

3.3 Representing Probabilistic Relations

4. Query Evaluation over Uncertain Data

4.1 Example

4.2 Generating Factors during Query Evaluation

4.3 Query Evaluation as Inference

4.4 Optimizations

5. RelatedWork and Discussion

5.1 Safe Plans

5.2 Representing Uncertainty using Lineage

5.3 Probabilistic Relational Models

5.4 Lifted Inference

5.5 Scalable Inference using a Relational Database

6. Conclusions

Acknowledgments

References

Chapter 5 TRIO:ASYSTEMFORDATA,UNCERTAINTY,AND LINEAGE

Introduction

1. ULDBs: Uncertainty-Lineage Databases

1.1 Alternatives

1.2 ‘?’ (Maybe) Annotations

1.3 Confidences

1.4 Lineage

1.5 Relational Queries

2. TriQL: The Trio Query Language

2.1 Operational Semantics

2.2 Querying Confidences

2.3 Querying Lineage

2.4 Duplicate Elimination

2.5 Aggregation

2.6 Reorganizing Alternatives

2.7 Horizontal Subqueries

2.8 Query-Defined Result Confidences

2.9 Other TriQL Query Constructs

3. Data Modifications in Trio

3.1 Inserts

3.2 Deletes

3.3 Updates

3.4 Data Modifications and Versioning

4. Confidence Computation

5. Additional Trio Features

6. The Trio System

6.1 Encoding ULDB Data

6.2 Basic Query Translation Scheme

6.3 Duplicate Elimination

6.4 Aggregation

6.5 Reorganizing Alternatives

6.6 Horizontal Subqueries

6.7 Built-In Predicates and Functions

6.8 Query-Defined Result Confidences

6.9 Remaining Constructs

References

Chapter 6 MAYBMS: A SYSTEM FOR MANAGING LARGE UNCERTAIN AND PROBABILISTIC DATABASES

1. Introduction

2. Probabilistic Databases

3. Query Language Desiderata

4. The Algebra

5. Representing Probabilistic Data

6. Conceptual Query Evaluation, Rewritings, and Asymptotic Efficiency

7. The MayBMS Query and Update Language

8. The MayBMS System

9. Conclusions and Outlook

References

Chapter 7 UNCERTAINTY IN DATA INTEGRATION

1. Introduction

2. Overview of the System

2.1 Uncertainty in data integration

2.2 System architecture

2.3 Source of probabilities

2.4 Outline of the chapter

3. Uncertainty in Mappings

3.1 Motivating probabilistic mappings

3.2 Definition and Semantics

3.3 Query Answering

3.4 Creating P-mappings

3.5 Broader Classes of Mappings

3.6 Other Types of Approximate Schema Mappings

4. Uncertainty in Mediated Schema

4.1 P-Med-Schema Motivating Example

4.2 Probabilistic Mediated Schema

4.3 P-med-schema Creation

4.4 Consolidation

4.5 Other approaches

5. Future Directions

References

Chapter 8 SKETCHING AGGREGATES OVER PROBABILISTIC STREAMS

1. Introduction

1.1 Aggregates over probabilistic streams

1.2 Organization

2. The Probabilistic Stream Model

2.1 Problem definitions

2.2 Frequency Moments and Quantiles

3. Overview of techniques and summary of results

4. Universal Sampling

5. Frequency moments: DISTINCT and REPEAT-RATE

5.1 DISTINCT

5.2 REPEAT-RATE

6. Heavy-Hitters, Quantiles, and MEDIAN

7. A Binning Technique for MIN and MAX

8. Estimating AVG using generating functions

8.1 Generating functions

8.2 Estimating AVG

8.3 Approximating AVG by SUM/COUNT

9. Discussion

References

Chapter 9 PROBABILISTIC JOIN QUERIES IN UNCERTAIN DATABASES

1. Introduction

2. Traditional Join Approaches

2.1 Simple Nested-Loop Join

2.2 Nested-Block-Loop Join

2.3 Sort-Merge-Loop Join

2.4 Other Join Methods

2.5 Spatial Join Algorithms

2.6 Spatial Join using a spatial index structure for both relations

2.7 Spatial Join using a spatial index structure on one relation

2.8 Spatial Join using no Spatial-Index Structure

3. Uncertainty Models and Join Predicates

3.1 The Continuous Uncertainty Model

3.2 The Discrete Uncertainty Model

3.3 Join Predicates and Score

3.4 Probabilistic Join Query Types

3.5 Example

3.6 Overview of UncertaintyModels and Probabilistic Join Queries

4. Approaches for Efficient Join Processing on Uncertain Data

4.1 Confidence-Based Join Methods

4.2 Probabilistic Similarity Joins

4.3 Probabilistic Spatial Join

5. Summary

References

Chapter 10 INDEXING UNCERTAIN DATA

1. Introduction

2. Data Models and Query Semantics

2.1 Uncertain Attribute types

3. Uncertainty Index for Continuous Domains

3.1 Probability Threshold Indexing

3.2 Special Case: Uniform PDFS

3.3 2D mapping of intervals

3.4 Join Queries

3.5 Multi-dimensional Indexing

4. Uncertainty Index for discrete domains

4.1 Data Model and Problem Definition

4.2 Probabilistic Inverted Index

4.3 Probabilistic Distribution R-tree

5. Indexing for Nearest Neighbor Queries

References

Chapter 11 RANGEANDNEARESTNEIGHBORQUERIESON UNCERTAIN SPATIOTEMPORAL DATA

1. Introduction

2. Range Search

2.1 Query Definitions

2.2 Filter and Refinement

2.3 Nonfuzzy Range Search

2.4 Fuzzy Range Search

2.5 Indexing

3. Nearest Neighbor Retrieval

3.1 Query Definition

3.2 Query Processing

3.3 Variations of Nearest Neighbor Retrieval

4. Summary

References

Chapter 12 PROBABILISTIC XML

1. Introduction

2. Sources of Uncertainty in XML Data

3. Modeling Uncertainty using Tags

4. Modeling Uncertainty using Semi-structured Data

5. Modeling Uncertainty in XML with Independent or Mutually Exclusive Distribution in Point Probability

6. Formal Model of Probabilistic Semi-structured Data with Arbitrary Probabilistic Distributions

6.1 Motivating Examples

6.2 Probabilistic Semi-structured Data Model

6.3 Semantics

6.4 PXML Algebra and Comparison with PreviousWork

6.5 Probabilistic Aggregate Operations

6.6 Modeling Interval Uncertainty in Semi-structured Data

7. Summary

Acknowledgements

References

Chapter 13 ON CLUSTERING ALGORITHMS FOR UNCERTAIN DATA

1. Introduction

2. Density Based Clustering Algorithms

3. The UK-means and CK-means Algorithms

4. UMicro: Streaming Algorithms for Clustering Uncertain Data

4.1 The UMicro Algorithm: Overview

4.2 Computing Expected Similarity

4.3 Computing the Uncertain Boundary

4.4 Further Enhancements

5. Approximation Algorithms for Clustering UncertainData

6. Conclusions and Summary

Acknowledgements

References

Chapter 14 ON APPLICATIONS OF DENSITY TRANS FORMSFOR UNCERTAIN DATA MINING

1. Introduction

2. Kernel Density Estimation with Errors

2.1 Scalability for Large Data Sets

3. Leveraging Density Estimation for Classification

4. Application of Density Based Approach to Outlier Detection

4.1 Outlier Detection Approach

4.2 Subspace Exploration for Outlier Detection

5. Conclusions

Acknowledgements

References

Chapter 15 FREQUENT PATTERN MINING ALGORITHMS WITH UNCERTAIN DATA

1. Introduction

2. Frequent Pattern Mining of Uncertain Data Sets

3. Apriori-style Algorithms

3.1 Pruning Methods for Apriori-Style Algorithms

4. Set-Enumeration Methods

5. Pattern Growth based Mining Algorithms

5.1 Extending the H-mine algorithm

5.2 Extending the FP-growth Algorithm

5.3 Another Variation of the FP-growth Algorithm

6. A Comparative Study on Challenging Cases

6.1 Performance Comparison

6.2 Scalability Comparison

7. Generalization to the PossibleWorlds Model

8. Discussion and Conclusions

Acknowledgements

References

Chapter 16 PROBABILISTIC QUERYING AND MINING OF BIOLOGICAL IMAGES

1. Introduction

1.1 An Illustrative Example

2. RelatedWork

3. Probabilistic Image Analyses

3.1 Probabilistic Segmentation

3.2 Measuring Neurite Thickness

3.3 Ganglion Cell Features

4. Querying Probabilistic Image Data

4.1 Range Queries on Uncertain Data

4.2 k-NN Queries on Uncertain Data

4.3 Adaptive, Piecewise-Linear Approximations

4.4 Indexing the APLA

4.5 Experimental Results

5. Mining Probabilistic Image Data

5.1 Defining Probabilistic Spatial Join (PSJ)

5.2 Threshold PSJ Query

5.3 Top-k PSJ Query

5.4 Experimental Results

6. Conclusion

Acknowledgements

References

Index