Similarity Query Processing Algorithms: Use of Enumeration and Divide and Conquer Techniques


Dr. Wei Wang, Univ. of New South Wales



Raum A520 (Augusteum)



A similarity query finds all the objects in the database that are similar to the query object according to a given similarity/distance function and a threshold. It plays a fundamental role in many areas such as data integration, pattern recognition, and biological or chemical informatics. A key algorithmic challenge is how to execute similarity queries efficiently, and decades of research has contributed many elegant solutions. The objectives of this talk are to provide an introduction and categorization to the similarity query algorithms based on the enumeration and divide and conquer ideas, with an emphasis on Hamming and edit distance functions.


Dr. Wei Wang is an Associate Professor (Reader) in the School of Computer Science and Engineering, The University of New South Wales, Australia. His current research interests include keyword search on (semi-)structured data, similarity query processing, high dimensional indexing, and spatial databases. He has published over ninety research papers in these areas, with many in premier database journals (TODS, VLDB J, and TKDE) and conferences (SIGMOD, VLDB, ICDE, and WWW). He is the PC Area Chair of ICDE 2014 for the track of “Strings, Texts and Keyword Search”.