Open AccessHierarchical soft clustering tree for fast approximate search of binary codes
Author(s) -
Choi S.,
Lee S.,
Yang H.S.
Publication year - 2015
Publication title -
electronics letters
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.375
H-Index - 146
ISSN - 1350-911X
DOI - 10.1049/el.2015.2806
Subject(s) - cluster analysis , computer science , hierarchical clustering , bottleneck , optimal binary search tree , binary search tree , hamming distance , tree (set theory) , k d tree , algorithm , hamming code , ternary search tree , binary tree , theoretical computer science , tree traversal , interval tree , mathematics , tree structure , artificial intelligence , decoding methods , block code , mathematical analysis , embedded system
Binary codes play an important role in many computer vision applications. They require less storage space while allowing efficient computations. However, a linear search to find the best matches among binary data creates a bottleneck for large‐scale datasets. Among the approximation methods used to solve this problem, the hierarchical clustering tree (HCT) method is a state‐of the‐art method. However, the HCT performs a hard assignment of each data point to only one cluster, which leads to a quantisation error and degrades the search performance. As a solution to this problem, an algorithm to create hierarchical soft clustering tree (HSCT) by assigning a data point to multiple nearby clusters in the Hamming space is proposed. Through experiments, the HSCT is shown to outperform other existing methods.