An algorithmic approach to Approximate Query
Dominic Tsang · The Sydney eScholarship Repository (The University of Sydney) · 2014
As data collection continues to grow rapidly the ability to efficiently carry out exploratory searches on the data is becoming more important. An exploratory search can be modelled as an approximate query in a database: retrieve all database elements which are similar to the query. Different forms of approximate queries are already popular in many applications such as data cleansing. Currently the most popular approach for approximate query processing consists of a two steps (phase) process. The first phase is called the filter phase and consists of enumerating a set of q-grams or substrings in a database. The q-grams form the inverted index and the query will use the inverted index to prune those records that are unlikely to match the query. In the second refinement phase, all database records which passed through the first phase are validated to produce the final answer. Despite showing improvement over a full table scan, the two phase approach for approximate querying is still not practical and is not part of any well known database management system. This is partially due to the fact that the index size can be very large - sometimes bigger than the size of the database. In this thesis we propose an algorithmic approach of selecting q-grams which will constitute the inverted index. We model the q-gram selection problem as an optimization problem and explore several models including vertex cover and feedback vertex. We also evaluate several algorithm design patterns including greedy and primal-dual to solve the optimization problems. Our particular focus is on evaluating techniques on how easily (or gracefully) they be implemented and integrated in a modern relational database management system. We will demonstrate that our approach results in an index size which is bounded above by the size of the database and provides no false dismissals and a low false positive rate.