A Low Memory Cost Fast Retrieval Method Based on Bucket Map Chain

Abstract:

To reduce the high memory cost of fast retireval method, we present a fast retrieval method based on bucket map chain on the basis of Exact Euclidean Locality Sensitive Hashing (E2LSH). The bucket map chain contains all the points projected from feature space in multiple buckets, which store the nearby points. When conducting query, it searches the chain by the bucket index of query point and locates the position of related buckets, then reads the related points in related buckets and measurs the similarity of these points with query point. The experiments show that this method can efficiently decrease the memory cost of retrieval. It is very important for increasing the feasibility of large scale information retrieval especially image retrieval.

• Periodical: Applied Mechanics and Materials (Volumes 321-324)
• Pages: 969-973
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.321-324.969
• Online since: June 2013
• Authors: Tian Qiang Peng, Xiao Feng Sun
• Keywords: Bucket Map Chain, Image Retrieval, Locality Sensitive Hashing, Memory Cost

References

[1] Gionis A, Indyk P, Motwani R. Similarity search in high dimensions via hashing. In: Proceedings of the 25th International Conference on Very Large Data Bases. Edinburgh, Scotland: Morgan Kaufmann, 1999. 518-529

[2] Indyk P, Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the Symposium on Theory of Computing. Dallas, Texas, USA:ACM, 1998. 604-613

DOI: 10.1145/276698.276876

[3] Alexandr Andoni, Piotr Indyk, E2LSH 0.1 User Manual, 2005,1.

[4] Datar M, Immorlica N, Indyk P, Mirrokni V. Locality sensitive hashing scheme based on p-stable distributions. In: Proceedings of the ACM Symposium on Computational Geometry. New York, USA:ACM, 2004. 253-262

DOI: 10.1145/997817.997857

[5] Kristen Gruman Efficiently Searching for Similar Images. Communications of the ACM, 2010(53) 6:85-94

[6] MuYadong, Yan Shuicheng. Non-metric Locality-Sensitive Hashing. Proceedings of the 24th AAAI Conference on Artificial Intelligence. 2010:

DOI: 10.1609/aaai.v24i1.7683

[7] Zhu Liu, Tao Liu, David Gibbon, Behzad Shaharar Effective and scalable video copy detection[C]. MIR'10, 2010,3.

[8] Cao Yiqun, Jiang Tao, Girke Thomas. Accelerated similarity searching and clustering of large compound sets by geometric embedding and locality sensitive hashing. Bioinfomatics.2010(26)7:953-959.

DOI: 10.1093/bioinformatics/btq067

[9] He Jun-Feng, Radhakrishnan R, Chang S F. Compact Hashing with Joint Optimization of Search Accuracy and Time. In: Proceeding of IEEE Conference on Computer Vision and Pattern Recognition. Colorado Springs, USA: IEEE, 2011. 753-759.

DOI: 10.1109/cvpr.2011.5995518

[10] Liu Wei, Wang Jun, Kumar S, Chang S F. Hashing with Graphs. In: Proceedings of the 28th International Conference on Machine Learning. Bellevue, WA, USA: ACM, 2011.

[11] Jegou H, Douze M, Schmid C. Improving bag-of-Features for Large Image Search. Int J Comput Vis 2010, 87:316-336.

DOI: 10.1007/s11263-009-0285-2

[12] Andoni A, Indyk P. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Communications of the ACM, 2008, 51(1):117-122

DOI: 10.1145/1327452.1327494

[13] Panigrahy R. Entropy-based nearest neighbor algorithm high dimensions. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. Miami, Florida, USA:ACM, 2006. 1185-1195

DOI: 10.1145/1109557.1109688