Distributed Graph Hashing

Recently, hashing-based approximate nearest neighbors search has attracted considerable attention, especially in big data applications, due to its low computation cost and fast retrieval speed. In the literature, most of the existing hashing algorithms are centralized. However, in many large-scale applications, the data are often stored or collected in a distributed manner. In this situation, the centralized hashing methods are not suitable for learning hash functions. In this paper, we consider the distributed learning to hash problem. We propose a novel distributed graph hashing model for learning efficient hash functions based on the data distributed across multiple agents over network. The graph hashing model involves a graph matrix, which contains the similarity information in the original space. We show that the graph matrix in the proposed distributed hashing model can be decomposed into multiple local graph matrices, and each local graph matrix can be constructed by a specific agent independently, with moderate communication and computation cost. Then, the whole objective function of the distributed hashing model can be represented by the sum of local objective functions of multiple agents, and the hashing problem can be formulated as a nonconvex constrained distributed optimization problem. For tractability, we transform the nonconvex constrained distributed optimization problem into an equivalent bi-convex distributed optimization problem. Then we propose two algorithms based on the idea of alternating direction method of multipliers to solve this problem in a distributed manner. We show that the proposed two algorithms have moderate communication and computational complexities, and both of them are scalable. Experiments on benchmark datasets are given to demonstrate the effectiveness of the proposed methods.