SUPPORTING GENERIC CLUSTERING AND SIMILARITY SEARCH FOR MASSIVE DATASETS

Abstract

Clustering and Similarity Search are two crucial challenges in big data analytics. The large cardinality, dimensionality, and diverse nature of big data require analytic methods to be both efficient and flexible for various distance functions. However, there is a lack of research focused on generic functionality that simultaneously supports multiple distance functions. In this thesis, we first propose a generic distributed clustering framework to process large-scale data with different distance functions by leveraging different Locality-Sensitive Hashing. We further investigate the clustering problem in sparse data and introduce a new method k-FreqItems with a novel sparse center representation called FreqItem. Additionally, we present a seeding technique that significantly improves the convergence speed of k-FreqItems. Finally, with the support of our clustering methods, we incorporate a generic similarity search framework GENIE with a two-level distributed indexing structure and develop a scalable framework dGENIE for billion-scale data.