In this talk we will present some of our recent results on answering approximate queries efficiently. One problem related to optimizing such queries is to estimate the selectivity of a fuzzy string predicate, i.e., estimating how many strings in the database satisfy the predicate. We develop a novel technique, called SEPIA, to solve the problem. We will present the details of this technique using the edit distance function. We study challenges in adopting this technique, including how to construct its histogram structures, how to use them to do selectivity estimation, and how to alleviate the effect of non-uniform errors in the estimation. We discuss how to extend the techniques to other similarity functions. We show the results of our extensive experiments.

Time permitting, we will also briefly report our other related results. One is on supporting fuzzy queries with both predicates on numeric attributes (e.g., salary > 50K) and predicates on string attributes (e.g., telephone numbers similar to 412-0964). Another one is on how to relax conditions in an SQL query that returns an empty answer. These results are based on three recent papers in VLDB'2005 and VLDB'2006.

Lomet, D. and Tuttle, M. A Theory of Redo Recovery. SIGMOD Conference, San Diego, CA (June 2003) 397-406
Lomet, D. and Tuttle, M. Logical Logging to Extend Recovery to New Domains. ACM SIGMOD Conference Philadelphia, PA (June, 1999)
Lomet, D. and Tuttle, M. Redo Recovery after System Crashes. VLDB Conference, Zurich, Switzerland (Sept. 1995) 457-468.

Wasserman, Ted J. et. al. "Developing a Characterization of Business Intelligence Workloads for Sizing New Database Systems", DBOLAP 2004, Washington, DC (November, 2004)

In this talk we will present some of our recent results on answering approximate queries efficiently. One problem related to optimizing such queries is to estimate the selectivity of a fuzzy string predicate, i.e., estimating how many strings in the database satisfy the predicate. We develop a novel technique, called SEPIA, to solve the problem. We will present the details of this technique using the edit distance function. We study challenges in adopting this technique, including how to construct its histogram structures, how to use them to do selectivity estimation, and how to alleviate the effect of non-uniform errors in the estimation. We discuss how to extend the techniques to other similarity functions. We show the results of our extensive experiments.

Time permitting, we will also briefly report our other related results. One is on supporting fuzzy queries with both predicates on numeric attributes (e.g., salary > 50K) and predicates on string attributes (e.g., telephone numbers similar to 412-0964). Another one is on how to relax conditions in an SQL query that returns an empty answer. These results are based on three recent papers in VLDB'2005 and VLDB'2006.

Second Talk
In this talk, we will present an efficient process for named entity annotation, an important IE problem, using inverse index operations. Named entity annotation involves attaching a label such as `name' or `organization' to a sequence of tokens in a document. The current rule-based and machine learning-based approaches for this task operate at the document level. We present a new and generic approach to entity annotation which uses the inverse index typically created for rapid key-word based searching of a document collection. We define a set of operations on the inverse index that allows us to create annotations defined by cascading regular expressions. The entity annotations for an entire document corpus can be created purely of the index with no need to access the original documents. Experiments on two publicly available data sets show very significant performance improvements over the document-based annotators.

"Data anonymization techniques based on the k-anonymity model have been the focus of intense research in the last few years. Although the k-anonymity model and the related techniques provide valuable solutions to data privacy, current solutions are limited only to static data release (i.e., the entire dataset is assumed to be available at the time of release). While this may be acceptable in some applications, today we see databases continuously growing everyday and even every hour. In such dynamic environments, the current techniques may suffer from poor data quality and/or vulnerability to inference. In this paper, we analyze various inference channels that may exist in multiple anonymized datasets and discuss how to avoid such inferences. We then present an approach to securely anonymizing a continuously growing dataset in an efficient manner while assuring high data quality."

To access the full paper, visit http://www.springerlink.com/content/p80r126487u63w31/fulltext.pdf

David McWherter, Bianca Schroeder, Natassa Ailamaki, and Mor Harchol-Balter "Priority Mechanisms for OLTP and Transactional Web Applications." ICDE 2004.

David McWherter, Bianca Schroeder, Natassa Ailamaki, and Mor Harchol-Balter "Improving Preemptive Prioritization via Statistical Characterization of OLTP Locking." ICDE 2005.