Similarity Joins in Relational Database Systems

Nikolaus Augsten, Michael Bohlen (Autoren)

Buch | Softcover

XVII, 106 Seiten

2013
Springer International Publishing (Verlag)
978-3-031-00723-1 (ISBN)

Artikel merken

State-of-the-art database systems manage and process a variety of complex objects, including strings and trees. For such objects equality comparisons are often not meaningful and must be replaced by similarity comparisons. This book describes the concepts and techniques to incorporate similarity into database systems. We start out by discussing the properties of strings and trees, and identify the edit distance as the de facto standard for comparing complex objects. Since the edit distance is computationally expensive, token-based distances have been introduced to speed up edit distance computations. The basic idea is to decompose complex objects into sets of tokens that can be compared efficiently. Token-based distances are used to compute an approximation of the edit distance and prune expensive edit distance calculations. A key observation when computing similarity joins is that many of the object pairs, for which the similarity is computed, are very different from each other. Filters exploit this property to improve the performance of similarity joins. A filter preprocesses the input data sets and produces a set of candidate pairs. The distance function is evaluated on the candidate pairs only. We describe the essential query processing techniques for filters based on lower and upper bounds. For token equality joins we describe prefix, size, positional and partitioning filters, which can be used to avoid the computation of small intersections that are not needed since the similarity would be too low.

Nikolaus Augsten is a professor in the Department of Com puter Science at the University of Salzburg, Austria, where he heads the Database Group. He received his Ph.D. degree in computer science from Aalborg University, Denmark, in 2008, and holds a M.Sc. degree from Graz University of Technol ogy, Austria. Prior to joining the University of Salzburg in 2013, he was an assistant professor at the Free University of Bolzano, Italy. He was on leave at TU Munchen, Germany, in 2010/2011 and visited Washington State University for six months in 2005/2006. His main research interests include sim ilarity search queries over massive data collections, approximate matching techniques for complex data structures, efficient in dex structures for distance computations, and top-k queries. For his work on top-k approximate subtree matching he received the Best Paper Award at the IEEE International Conference on Data Engineering in 2010. Currently, he serves as an Associate Editor for the VLDB Journal. Michael H. Boehlen is a professor of computer science at the University of Zurich where he heads the Database Technology Group. His research interests include various aspects of data management, and have focused on time-varying information, data warehousing and data analysis, and similarity search. He received his M.Sc. and Ph.D. degrees from ETH Zurich in 1990 and 1994, respectively. Before joining the University of Zurich he visited the University of Arizona for one year, and was a faculty member at Aalborg University for eight years and the Free University of Bozen-Bolzano for six years. He was pro gram co-chair of the 39th International Conference on Very Large Data Bases and served as an Associate Editor for the VLDB Journal. He served as a PC member for SIGMOD, VLDB, ICDE, and EDBT. Cur rently, he serves as an Associate Editor for ACM TODS, and he is a member of the VLDB Endowment's Board of Trustees

Preface.- Acknowledgments.- Introduction.- Data Types.- Edit-Based Distances.- Token-Based Distances.- Query Processing Techniques.- Filters for Token Equality Joins.- Conclusion.- Bibliography.- Authors' Biographies.- Index.

Erscheinungsdatum	06.06.2022
Reihe/Serie	Synthesis Lectures on Data Management
Zusatzinfo	XVII, 106 p.
Verlagsort	Cham
Sprache	englisch
Maße	191 x 235 mm
Gewicht	255 g
Themenwelt	Mathematik / Informatik ► Informatik ► Netzwerke
Themenwelt	Informatik ► Theorie / Studium ► Algorithmen
ISBN-10	3-031-00723-9 / 3031007239
ISBN-13	978-3-031-00723-1 / 9783031007231
Zustand	Neuware