Timezone: »
Hashing has emerged as a popular technique for fast nearest neighbor search in gigantic databases. In particular, learning based hashing has received considerable attention due to its appealing storage and search efficiency. However, the performance of most unsupervised learning based hashing methods deteriorates rapidly as the hash code length increases. We argue that the degraded performance is due to inferior optimization procedures used to achieve discrete binary codes. This paper presents a graph-based unsupervised hashing model to preserve the neighborhood structure of massive data in a discrete code space. We cast the graph hashing problem into a discrete optimization framework which directly learns the binary codes. A tractable alternating maximization algorithm is then proposed to explicitly deal with the discrete constraints, yielding high-quality codes to well capture the local neighborhoods. Extensive experiments performed on four large datasets with up to one million samples show that our discrete optimization based graph hashing method obtains superior search accuracy over state-of-the-art unsupervised hashing methods, especially for longer codes.
Author Information
Wei Liu (Tencent)
Cun Mu (Columbia University)
Sanjiv Kumar (Google Research)
Shih-Fu Chang (Columbia University)
Related Events (a corresponding poster, oral, or spotlight)
-
2014 Spotlight: Discrete Graph Hashing »
Tue. Dec 9th 04:40 -- 05:00 PM Room Level 2, room 210
More from the Same Authors
-
2021 Poster: Batch Active Learning at Scale »
Gui Citovsky · Giulia DeSalvo · Claudio Gentile · Lazaros Karydas · Anand Rajagopalan · Afshin Rostamizadeh · Sanjiv Kumar -
2021 Poster: Efficient Training of Retrieval Models using Negative Cache »
Erik Lindgren · Sashank Reddi · Ruiqi Guo · Sanjiv Kumar -
2021 Poster: Neural Routing by Memory »
Kaipeng Zhang · Zhenqiang Li · Zhifeng Li · Wei Liu · Yoichi Sato -
2021 Poster: Generalized and Discriminative Few-Shot Object Detection via SVD-Dictionary Enhancement »
Aming WU · Suqi Zhao · Cheng Deng · Wei Liu -
2020 Poster: Why are Adaptive Methods Good for Attention Models? »
Jingzhao Zhang · Sai Praneeth Karimireddy · Andreas Veit · Seungyeon Kim · Sashank Reddi · Sanjiv Kumar · Suvrit Sra -
2020 Poster: Towards Playing Full MOBA Games with Deep Reinforcement Learning »
Deheng Ye · Guibin Chen · Wen Zhang · Sheng Chen · Bo Yuan · Bo Liu · Jia Chen · Zhao Liu · Fuhao Qiu · Hongsheng Yu · Yinyuting Yin · Bei Shi · Liang Wang · Tengfei Shi · Qiang Fu · Wei Yang · Lanxiao Huang · Wei Liu -
2020 Poster: Fewer is More: A Deep Graph Metric Learning Perspective Using Fewer Proxies »
Yuehua Zhu · Muli Yang · Cheng Deng · Wei Liu -
2020 Poster: Multi-Stage Influence Function »
Hongge Chen · Si Si · Yang Li · Ciprian Chelba · Sanjiv Kumar · Duane Boning · Cho-Jui Hsieh -
2020 Poster: O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformers »
Chulhee Yun · Yin-Wen Chang · Srinadh Bhojanapalli · Ankit Singh Rawat · Sashank Reddi · Sanjiv Kumar -
2020 Poster: Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization »
Yan Yan · Yi Xu · Qihang Lin · Wei Liu · Tianbao Yang -
2020 Spotlight: Fewer is More: A Deep Graph Metric Learning Perspective Using Fewer Proxies »
Yuehua Zhu · Muli Yang · Cheng Deng · Wei Liu -
2020 Poster: Robust large-margin learning in hyperbolic space »
Melanie Weber · Manzil Zaheer · Ankit Singh Rawat · Aditya Menon · Sanjiv Kumar -
2020 Poster: Learning discrete distributions: user vs item-level privacy »
Yuhan Liu · Ananda Theertha Suresh · Felix Xinnan Yu · Sanjiv Kumar · Michael D Riley -
2020 Poster: Adversarial Learning for Robust Deep Clustering »
Xu Yang · Cheng Deng · Kun Wei · Junchi Yan · Wei Liu -
2019 Poster: Semantic Conditioned Dynamic Modulation for Temporal Sentence Grounding in Videos »
Yitian Yuan · Lin Ma · Jingwen Wang · Wei Liu · Wenwu Zhu -
2019 Poster: Breaking the Glass Ceiling for Embedding-Based Classifiers for Large Output Spaces »
Chuan Guo · Ali Mousavi · Xiang Wu · Daniel Holtmann-Rice · Satyen Kale · Sashank Reddi · Sanjiv Kumar -
2019 Poster: Cross-Modal Learning with Adversarial Samples »
CHAO LI · Shangqian Gao · Cheng Deng · De Xie · Wei Liu -
2019 Poster: Multilabel reductions: what is my loss optimising? »
Aditya Menon · Ankit Singh Rawat · Sashank Reddi · Sanjiv Kumar -
2019 Spotlight: Multilabel reductions: what is my loss optimising? »
Aditya Menon · Ankit Singh Rawat · Sashank Reddi · Sanjiv Kumar -
2019 Poster: Category Anchor-Guided Unsupervised Domain Adaptation for Semantic Segmentation »
Qiming ZHANG · Jing Zhang · Wei Liu · Dacheng Tao -
2019 Poster: Sampled Softmax with Random Fourier Features »
Ankit Singh Rawat · Jiecao Chen · Felix Xinnan Yu · Ananda Theertha Suresh · Sanjiv Kumar -
2018 Poster: Nonlocal Neural Networks, Nonlocal Diffusion and Nonlocal Modeling »
Yunzhe Tao · Qi Sun · Qiang Du · Wei Liu -
2018 Poster: Generalizing Graph Matching beyond Quadratic Assignment Model »
Tianshu Yu · Junchi Yan · Yilin Wang · Wei Liu · baoxin Li -
2018 Poster: Adaptive Methods for Nonconvex Optimization »
Manzil Zaheer · Sashank Reddi · Devendra S Sachan · Satyen Kale · Sanjiv Kumar -
2018 Poster: Deep Non-Blind Deconvolution via Generalized Low-Rank Approximation »
Wenqi Ren · Jiawei Zhang · Lin Ma · Jinshan Pan · Xiaochun Cao · Wangmeng Zuo · Wei Liu · Ming-Hsuan Yang -
2018 Poster: Distilled Wasserstein Learning for Word Embedding and Topic Modeling »
Hongteng Xu · Wenlin Wang · Wei Liu · Lawrence Carin -
2018 Poster: cpSGD: Communication-efficient and differentially-private distributed SGD »
Naman Agarwal · Ananda Theertha Suresh · Felix Xinnan Yu · Sanjiv Kumar · Brendan McMahan -
2018 Spotlight: cpSGD: Communication-efficient and differentially-private distributed SGD »
Naman Agarwal · Ananda Theertha Suresh · Felix Xinnan Yu · Sanjiv Kumar · Brendan McMahan -
2018 Poster: Parsimonious Quantile Regression of Financial Asset Tail Dynamics via Sequential Learning »
Xing Yan · Weizhong Zhang · Lin Ma · Wei Liu · Qi Wu -
2017 : Now Playing: Continuous low-power music recognition »
Marvin Ritter · Ruiqi Guo · Sanjiv Kumar · Julian J Odell · Mihajlo Velimirović · Dominik Roblek · James Lyon -
2017 Poster: Geometric Descent Method for Convex Composite Minimization »
Shixiang Chen · Shiqian Ma · Wei Liu -
2017 Poster: Multiscale Quantization for Fast Similarity Search »
Xiang Wu · Ruiqi Guo · Ananda Theertha Suresh · Sanjiv Kumar · Daniel Holtmann-Rice · David Simcha · Felix Yu -
2017 Poster: Mixture-Rank Matrix Approximation for Collaborative Filtering »
Dongsheng Li · Chao Chen · Wei Liu · Tun Lu · Ning Gu · Stephen Chu -
2016 Poster: Orthogonal Random Features »
Felix Xinnan Yu · Ananda Theertha Suresh · Krzysztof M Choromanski · Daniel Holtmann-Rice · Sanjiv Kumar -
2016 Oral: Orthogonal Random Features »
Felix Xinnan Yu · Ananda Theertha Suresh · Krzysztof M Choromanski · Daniel Holtmann-Rice · Sanjiv Kumar -
2015 Workshop: The 1st International Workshop "Feature Extraction: Modern Questions and Challenges" »
Dmitry Storcheus · Sanjiv Kumar · Afshin Rostamizadeh -
2015 Poster: Spherical Random Features for Polynomial Kernels »
Jeffrey Pennington · Felix Yu · Sanjiv Kumar -
2015 Spotlight: Spherical Random Features for Polynomial Kernels »
Jeffrey Pennington · Felix Yu · Sanjiv Kumar -
2015 Poster: Structured Transforms for Small-Footprint Deep Learning »
Vikas Sindhwani · Tara Sainath · Sanjiv Kumar -
2015 Spotlight: Structured Transforms for Small-Footprint Deep Learning »
Vikas Sindhwani · Tara Sainath · Sanjiv Kumar -
2014 Session: Oral Session 8 »
Sanjiv Kumar -
2014 Poster: Zeta Hull Pursuits: Learning Nonconvex Data Hulls »
Yuanjun Xiong · Wei Liu · Deli Zhao · Xiaoou Tang -
2013 Poster: Analyzing the Harmonic Structure in Graph-Based Learning »
Xiao-Ming Wu · Zhenguo Li · Shih-Fu Chang -
2012 Poster: Learning with Partially Absorbing Random Walks »
Xiao-Ming Wu · Zhenguo Li · Shih-Fu Chang · John Wright · Anthony Man-Cho So -
2012 Poster: Angular Quantization based Binary Codes for Fast Similarity Search »
Yunchao Gong · Sanjiv Kumar · Vishal Verma · Svetlana Lazebnik -
2009 Poster: Ensemble Nystrom Method »
Sanjiv Kumar · Mehryar Mohri · Ameet S Talwalkar