Efficient set similarity join on multi-attribute data using lightweight filters

Abstract

We consider the problem of efficiently answering set similarity joins on multi-attribute data. Traditionalset similarity join algorithms assume string data represented by a single set and, thus, miss the opportunity to exploitpredicates over multiple attributes to reduce the number of similarity computations. In this article, we present a frame-work to enhance existing algorithms with additional filters for dealing with multi-attribute data. We then instantiatethis framework with a lightweight filtering technique based on a simple, yet effective data structure, for which exact andprobabilistic implementations are evaluated. In this context, we devise a cost model to identify the best attribute order-ing to reduce processing time. Moreover, alternative approaches are also investigated and a new algorithm combiningkey ideas from previous work is introduced. Finally, we present a thorough experimental evaluation, which demonstratesthat our main proposal is efficient and significantly outperforms competing algorithms.