Managing Uncertainty Using Probabilistic Databases

April 2, 2007
Nilesh Dalvi | University of Washington

Uncertainty is a fundamental problem underlying several modern database applications: exploratory queries in databases, data integration, querying information extracted from the Web, queries over sensor networks, scientific data management, reasoning about privacy breaches in data mining and many others.

In this talk, I will describe probabilistic databases as a unifying framework to manage the various kinds of uncertainties that arise in these wide range of applications. In a probabilistic database, each data item has a probability of belonging to the database and queries return answers that are ranked by probabilities. The main challenge here is query evaluation. Unlike in traditional databases, some queries have a #P-complete complexity. I will present the results of our study of the complexity of queries and present algorithms and techniques for efficient query evaluation over probabilistic databases.

Speaker Details

Nilesh Dalvi received his B.S. from Indian Institute of Technology, Mumbai in 2001. He is currently a Ph.D. candidate at the University of Washington, advised by Prof. Dan Suciu. His research interests lie in the area of Database management. His focus is on the management of uncertainty in databases, with applications to several domains: data integration, information retrieval, information extraction and data privacy.