An Efficient Approximate Knn Graph Method For Diffusion On Image Retrieval

Abstract

The application of the diffusion in many computer vision and artificial intelligence projects has been shown to give excellent improvements in performance. One of the main bottlenecks of this technique is the quadratic growth of the kNN graph size due to the high-quantity of new connections between nodes in the graph, resulting in long computation times. Several strategies have been proposed to address this, but none are effective and efficient. Our novel technique, based on LSH projections, obtains the same performance as the exact kNN graph after diffusion, but in less time (approximately 18 times faster on a dataset of a hundred thousand images). The proposed method was validated and compared with other state-of-the-art on several public image datasets, including Oxford5k, Paris6k, and Oxford105k.

Stats

• citations6
• S2 citations—
• github stars0
• HF likes0
• heat score6.34
• arxiv keymagliani2019an

Related papers

• Efficient Image Retrieval Via Decoupling Diffusion Into Online And Offline Processing (2018)12.25
• Genetic Algorithms For The Optimization Of Diffusion Parameters In Content-based Image Retrieval (2019)9.23
• Accurate And Fast Pixel Retrieval With Spatial And Uncertainty Aware Hypergraph Diffusion (2024)0.00
• Efficient Diffusion On Region Manifolds: Recovering Small Objects With Compact CNN Representations (2016)15.83
• Learning Global And Local Consistent Representations For Unsupervised Image Retrieval Via Deep Graph Diffusion Networks (2020)0.00
• Approximate K-nn Graph Construction: A Generic Online Approach (2018)11.08
• EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based On Knn Graph (2016)0.00
• Hd-index: Pushing The Scalability-accuracy Boundary For Approximate Knn Search In High-dimensional Spaces (2018)14.02