MLSH: Mixed Hash Function Family for Approximate Nearest Neighbor Search in Multiple Fractional Metrics

In recent years, the approximate nearest neighbor search in multiple l(p) metrics (MMS) has gained much attention owing to its wide applications. Currently, LazyLSH, the state-of-the-art method only supports limited values of p and cannot always achieve high accuracy. In this paper, we design a mixed hash function family consisting of two types of functions generated in different metric spaces to solve MMS problem in the external memory. In order to make the mixed hash function family work properly, we also design a novel searching strategy to ensure the theoretical guarantee on the query accuracy. Based on the given scenario, MLSH constructs the corresponding mixed hash function family automatically by determining the proportion of two types of hash functions. Experimental results show that MLSH can meet the different user-specified recall rates and outperforms other state-of-the-art methods on various datasets.