ZANELLA-THESIS-2023.pdf (1.34 MB)
Similarity Join Queries: Techniques and Optimizations
thesisposted on 2023-08-01, 00:00 authored by Simone Zanella
In this thesis we are going to propose efficient algorithms and data structures to handle similarity join queries over any number of constant relations in the dynamic setting with delay guarantees. We provide a lower bound complexity proof for the dynamic case, in which points are inserted and deleted after an initial preprocessing phase where all the needed data structures are created. We analyze special cases in which constraints allow us to efficiently answer a similarity join query exactly. Then, we design a grid-based approximation data structure for any dynamic similarity join query proving delay guarantees. A reduction to equi-joins is also provided. Finally an implementation of similarity join approximation algorithm with tests on different use cases is added at the end in appendices section.
Degree GrantorUniversity of Illinois at Chicago
Degree nameMS, Master of Science
Committee MemberSidiropoulos, Anastasios Cerquitelli, Tania
Submitted dateAugust 2023