13
Approximate Similarity Search Query Probabilistic Data Structures
13.1 Introduction
Large datasets generated from a system may contain duplicates or near duplicates. Applying brute force technique to probe all possible combination can give exact nearest neighbor match, but this way is no scalable. Over and above, the traditional cluster analysis techniques (e.g., k-nearest neighbor) take quadratic or cubic time which seems unpractical for large datasets. Moreover, tree structure methods, such as- kd-trees, BDD trees etc. demands enough space and time as these methods compare given query with each record while searching to identify similar records [83], [106]. Hence, there is a demand for efficient similarity search method that can solve ...
