University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Improved Hamming Distance Search using Variable Length Substrings

Ong, E and Bober, M (2016) Improved Hamming Distance Search using Variable Length Substrings In: The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016,, 2016-07-26 - 2016-07-01, Las Vegas.

Ong_Bober_CVPR16_ImprovedHammingDistance.pdf - Accepted version Manuscript
Available under License : See the attached licence file.

Download (757kB) | Preview
Text (licence)
Available under License : See the attached licence file.

Download (33kB) | Preview


This paper addresses the problem of ultra-large-scale search in Hamming spaces. There has been considerable research on generating compact binary codes in vision, for example for visual search tasks. However the issue of efficient searching through huge sets of binary codes remains largely unsolved. To this end, we propose a novel, unsupervised approach to thresholded search in Hamming space, supporting long codes (e.g. 512-bits) with a wide-range of Hamming distance radii. Our method is capable of working efficiently with billions of codes delivering between one to three orders of magnitude acceleration, as compared to prior art. This is achieved by relaxing the equal-size constraint in the Multi-Index Hashing approach, leading to multiple hash-tables with variable length hash-keys. Based on the theoretical analysis of the retrieval probabilities of multiple hash-tables we propose a novel search algorithm for obtaining a suitable set of hash-key lengths. The resulting retrieval mechanism is shown empirically to improve the efficiency over the state-of-the-art, across a range of datasets, bit-depths and retrieval thresholds.

Item Type: Conference or Workshop Item (Conference Paper)
Subjects : Electronic Engineering
Divisions : Faculty of Engineering and Physical Sciences > Electronic Engineering
Authors :
Ong, E
Bober, M
Date : July 2016
DOI : 10.1109/CVPR.2016.220
Copyright Disclaimer : © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Depositing User : Symplectic Elements
Date Deposited : 21 Jul 2016 08:22
Last Modified : 31 Oct 2017 18:28

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800