SNU Professor Hyun Oh Song’s Team Designs a Data Search Algorithm with 478 times Speedup

- Deep Binary Representation Learning Algorithm which Provides Fast and Accurate Search

The research team (MS/PhD Student Yeonwoo Jeong) led by Professor Hyun Oh Song of the Department of Computer Science and Engineering has designed an optimization algorithm for binary representation, providing fast and accurate data search using deep learning network.
 
Conventional data search engines resort to the post-processing procedure such as vector quantization of the representation from deep learning network in order to elevate the search speedup while trading off the accuracy.
 
The research team tackles this issue by developing an optimization algorithm that learns sparse binary hash code which respect the pairwise relationships between data. (Note Figure 1.) This algorithm is optimized via alternating minimization through iterating over solving for the optimal sparse binary hash code and training deep learning network with metric learning losses.
 
In addition, the team has demonstrated that the combinatorial optimization problem, which finds the optimal sparse binary code, is equivalent to the minimum-cost flow problem, and the corresponding problem can be solved within polynomial time. (Note Figure 2.)
 
The team constructed a hash table with this optimal sparse binary hash code. It showed a 98-times and 478-times search speedup in Cifar-100 and ImageNet, respectively, both which are machine learning benchmark datasets.
 
This research (titled “Efficient End-to-End Learning for Quantizable Representation”) was published and selected as a long oral presentation in ICML18, one of the top conference in machine learning community, in July.
 

▲ Figure 1. Optimization Problem that Displays Image Similarity and Learns Sparse Hash Code


▲ Figure 2. Flow Graph that Demonstrates the Minimum Cost Issue which is in Equivalence Relation with Optimization Problem of Finding Sparse Binary Hash Code

[Reference Links]
Link to Research Paper: https://arxiv.org/abs/1805.05809
Link to GitHub Source Code: https://github.com/maestrojeong/Deep-Hash-Table-ICML18