research-article

A General and Efficient Querying Method for Learning to Hash

Authors:

Kelvin K. W. Ng,

Ti-chung ChengAuthors Info & Claims

SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data

Pages 1333 - 1347

https://doi.org/10.1145/3183713.3183750

Published: 27 May 2018 Publication History

Abstract

As an effective solution to the approximate nearest neighbors (ANN) search problem, learning to hash (L2H) is able to learn similarity-preserving hash functions tailored for a given dataset. However, existing L2H research mainly focuses on improving query performance by learning good hash functions, while Hamming ranking (HR) is used as the default querying method. We show by analysis and experiments that Hamming distance, the similarity indicator used in HR, is too coarse-grained and thus limits the performance of query processing. We propose a new fine-grained similarity indicator, quantization distance (QD), which provides more information about the similarity between a query and the items in a bucket. We then develop two efficient querying methods based on QD, which achieve significantly better query performance than HR. Our methods are general and can work with various L2H algorithms. Our experiments demonstrate that a simple and elegant querying method can produce performance gain equivalent to advanced and complicated learning algorithms.

References

[1]

Artem Babenko and Victor S. Lempitsky . 2012. The Inverted Multi-Index. In CVPR. 3069--3076.

Digital Library

[2]

Jon Louis Bentley . 1975. Multidimensional Binary Search Trees Used for Associative Searching CACM, Vol. Vol. 18. 509--517.

Digital Library

[3]

Konstantin Berlin, Sergey Koren, Chen-Shan Chin, James P Drake, Jane M Landolin, and Adam M Phillippy . 2015. Assembling Large Genomes With Single-Molecule Sequencing and Locality-Sensitive Hashing. In Nature biotechnology, Vol. Vol. 33. 623--630.

[4]

Deng Cai . 2016. A Revisit of Hashing Algorithms for Approximate Nearest Neighbor Search CoRR, Vol. Vol. abs/1612.07545.

[5]

Abhinandan Das, Mayur Datar, Ashutosh Garg, and Shyamsundar Rajaram . 2007. Google News Personalization: Scalable Online Collaborative Filtering WWW. 271--280.

Digital Library

[6]

Junhao Gan, Jianlin Feng, Qiong Fang, and Wilfred Ng . 2012. Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting SIGMOD. 541--552.

Digital Library

[7]

Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun . 2013. Optimized Product Quantization for Approximate Nearest Neighbor Search CVPR. 2946--2953.

Digital Library

[8]

Yunchao Gong and Svetlana Lazebnik . 2011. Iterative Quantization: A Procrustean Approach to Learning Binary Codes CVPR. 817--824.

Digital Library

[9]

Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin . 2013. Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-Scale Image Retrieval. In TPAMI, Vol. Vol. 35. 2916--2929.

Digital Library

[10]

Antonin Guttman . 1984. R-Trees: A Dynamic Index Structure for Spatial Searching SIGMOD. 47--57.

Digital Library

[11]

Kaiming He, Fang Wen, and Jian Sun . 2013. K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes. In CVPR. 2938--2945.

Digital Library

[12]

Pinjia He, Jieming Zhu, Shilin He, Jian Li, and Michael R. Lyu . 2017. Towards Automated Log Parsing for Large-Scale Log Data Analysis TDSC.

[13]

Johannes Hoffart, Stephan Seufert, Dat Ba Nguyen, Martin Theobald, and Gerhard Weikum . 2012. KORE: Keyphrase Overlap Relatedness for Entity Disambiguation CIKM. 545--554.

Digital Library

[14]

Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng . 2015. Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search PVLDB, Vol. Vol. 9. 1--12.

Digital Library

[15]

Yuzhen Huang, Tatiana Jin, Yidi Wu, Zhenkun Cai, Xiao Yan, Fan Yang, Jinfeng Li, Yuying Guo, and James Cheng . 2018. FlexPS: Flexible Parallelism Control in Parameter Server Architecture PVLDB.

Digital Library

[16]

Piotr Indyk and Rajeev Motwani . 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality STOC. 604--613.

Digital Library

[17]

Wang-Cheng Kang, Wu-Jun Li, and Zhi-Hua Zhou . 2016. Column Sampling Based Discrete Supervised Hashing. In AAAI. 1230--1236.

Digital Library

[18]

Brian Kulis and Kristen Grauman . 2009. Kernelized Locality-Sensitive Hashing for Scalable Image Search ICCV. 2130--2137.

[19]

Learning to Hash . 2017. http://cs.nju.edu.cn/lwj/L2H.html.

[20]

Cong Leng, Jiaxiang Wu, Jian Cheng, Xi Zhang, and Hanqing Lu . 2015. Hashing for Distributed Data. In ICML. 1642--1650.

Digital Library

[21]

Jinfeng Li, James Cheng, Fan Yang, Yuzhen Huang, Yunjian Zhao, Xiao Yan, and Ruihao Zhao . 2017 a. LoSHa: A General Framework for Scalable Locality Sensitive Hashing SIGIR. 635--644.

Digital Library

[22]

Jinfeng Li, James Cheng, Yunjian Zhao, Fan Yang, Yuzhen Huang, Haipeng Chen, and Ruihao Zhao . 2016 a. A Comparison of General-Purpose Distributed Systems for Data Processing IEEE BigData. 378--383.

[23]

Wu-Jun Li, Sheng Wang, and Wang-Cheng Kang . 2016 b. Feature Learning Based Deep Supervised Hashing with Pairwise Labels IJCAI. 1711--1717.

Digital Library

[24]

Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Wenjie Zhang, and Xuemin Lin . 2016 c. Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement. In CoRR, Vol. Vol. abs/1610.02455.

[25]

Xuelong Li, Di Hu, and Feiping Nie . 2017 b. Large Graph Hashing with Spectral Rotation. In AAAI. 2203--2209.

[26]

Wei Liu, Cun Mu, Sanjiv Kumar, and Shih-Fu Chang . 2014 b. Discrete Graph Hashing. In NIPS. 3419--3427.

Digital Library

[27]

Yingfan Liu, Jiangtao Cui, Zi Huang, Hui Li, and Heng Tao Shen . 2014 a. SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search PVLDB, Vol. Vol. 7. 745--756.

Digital Library

[28]

Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li . 2007. Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search VLDB. 950--961.

Digital Library

[29]

Marius Muja and David G. Lowe . 2009. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration VISAPP. 331--340.

[30]

Marius Muja and David G. Lowe . 2014. Scalable Nearest Neighbor Algorithms for High Dimensional Data TPAMI, Vol. Vol. 36. 2227--2240.

[31]

Ankur Narang and Souvik Bhattacherjee . 2011. Real-time Approximate Range Motif Discovery & Data Redundancy Removal Algorithm EDBT. 485--496.

Digital Library

[32]

NNS Benchmark . 2017. https://github.com/DBWangGroupUNSW/nns_benchmark.

[33]

Mohammad Norouzi, Ali Punjani, and David J. Fleet . 2012. Fast Search in Hamming Space with Multi-Index Hashing CVPR. 3108--3115.

Digital Library

[34]

Mohammad Norouzi, Ali Punjani, and David J. Fleet . 2014. Fast Exact Search in Hamming Space With Multi-Index Hashing TPAMI, Vol. Vol. 36. 1107--1119.

Digital Library

[35]

OpenCV . 2017. http://opencv.org/.

[36]

Rina Panigrahy . 2006. Entropy Based Nearest Neighbor Search in High Dimensions SODA. 1186--1195.

Digital Library

[37]

Lo"ıc Paulevé, Hervé Jégou, and Laurent Amsaleg . 2010. Locality Sensitive Hashing: A Comparison of Hash Function Types and Querying Mechanisms. In PRL, Vol. Vol. 31. 1348--1358.

Digital Library

[38]

Yuxin Su, Irwin King, and Michael R. Lyu . 2017. Learning to Rank Using Localized Geometric Mean Metrics SIGIR. 45--54.

Digital Library

[39]

Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis . 2009. Quality and Efficiency in High Dimensional Nearest Neighbor Search SIGMOD. 563--576.

Digital Library

[40]

Jun Wang, Ondrej Kumar, and Shih-Fu Chang . 2010. Semi-Supervised Hashing for Scalable Image Retrieval CVPR. 3424--3431.

[41]

Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji . 2014. Hashing for Similarity Search: A Survey. In CoRR, Vol. Vol. abs/1408.2927.

[42]

Jingdong Wang, Ting Zhang, Jingkuan Song, Nicu Sebe, and Heng Tao Shen . 2017. A Survey on Learning to Hash. In TPAMI.

[43]

Xin-Jing Wang, Lei Zhang, Feng Jing, and Wei-Ying Ma . 2006. AnnoSearch: Image Auto-Annotation by Search. In CVPR. 1483--1490.

Digital Library

[44]

Yair Weiss, Antonio Torralba, and Robert Fergus . 2008. Spectral Hashing. In NIPS. 1753--1760.

Digital Library

[45]

Fan Yang, Yuzhen Huang, Yunjian Zhao, Jinfeng Li, Guanxian Jiang, and James Cheng . 2017 a. The Best of Both Worlds: Big Data Programming with Both Productivity and Performance SIGMOD. 1619--1622.

Digital Library

[46]

Fan Yang, Jinfeng Li, and James Cheng . 2016. Husky: Towards a More Efficient and Expressive Distributed Computing Framework PVLDB, Vol. Vol. 9. 420--431.

Digital Library

[47]

Fan Yang, Fanhua Shang, Yuzhen Huang, James Cheng, Jinfeng Li, Yunjian Zhao, and Ruihao Zhao . 2017 b. LFTF: A Framework for Efficient Tensor Analytics at Scale PVLDB, Vol. Vol. 10. 745--756.

Digital Library

[48]

Cui Yu . 2002. High-Dimensional Indexing: Transformational Approaches to High-Dimensional Range and Similarity Searches (Lecture Notes in Computer Science), Vol. Vol. 2341. Springer.

Digital Library

[49]

Fuzhen Zhang . 2011. Matrix Theory: Basic Results and Techniques. Springer Science & Business Media.

[50]

Ting Zhang, Chao Du, and Jingdong Wang . 2014. Composite Quantization for Approximate Nearest Neighbor Search ICML. 838--846.

Digital Library

[51]

Yuxin Zheng, Qi Guo, Anthony K. H. Tung, and Sai Wu . 2016. LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index. In SIGMOD. 2023--2037.

Digital Library

Cited By

Yin ZGao JBalsebre PCong GLong C(2025)DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation GraphProceedings of the ACM on Management of Data10.1145/37096793:1(1-28)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709679
Gao JLong C(2024)RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor SearchProceedings of the ACM on Management of Data10.1145/36549702:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654970
Zhang PHu Z(2024)NetDS: Distributed Search Framework with Hybrid Acceleration Methods2024 IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA)10.1109/ISPA63168.2024.00301(2203-2210)Online publication date: 30-Oct-2024
https://doi.org/10.1109/ISPA63168.2024.00301
Show More Cited By

Recommendations

When is ontology-mediated querying efficient?
LICS '19: Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science

In ontology-mediated querying, description logic (DL) ontologies are used to enrich incomplete data with domain knowledge which results in more complete answers to queries. However, the evaluation of ontology-mediated queries (OMQs) over relational ...
Querying data provenance
SIGMOD '10: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data

Many advanced data management operations (e.g., incremental maintenance, trust assessment, debugging schema mappings, keyword search over databases, or query answering in probabilistic databases), involve computations that look at how a tuple was ...
Learning Label Preserving Binary Codes for Multimedia Retrieval: A General Approach

Learning-based hashing has been researched extensively in the past few years due to its great potential in fast and accurate similarity search among huge volumes of multimedia data. In this article, we present a novel multimedia hashing framework, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data

May 2018

1874 pages

ISBN:9781450347037

DOI:10.1145/3183713

General Chairs:
Gautam Das
University of Texas at Arlington, USA
,
Christopher Jermaine
Rice University, USA
,
Philip Bernstein
Microsoft Research, USA

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication Notes

Badge change: Article originally badged under Version 1.0 guidelines https://www.acm.org/publications/policies/artifact-review-badging

Publication History

Published: 27 May 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Results Reproduced / v1.1

Author Tags

Qualifiers

Research-article

Funding Sources

Hong Kong RGC

Conference

SIGMOD/PODS '18

Sponsor:

SIGMOD

SIGMOD/PODS '18: International Conference on Management of Data

June 10 - 15, 2018

TX, Houston, USA

Acceptance Rates

SIGMOD '18 Paper Acceptance Rate 90 of 461 submissions, 20%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
525
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)3

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yin ZGao JBalsebre PCong GLong C(2025)DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation GraphProceedings of the ACM on Management of Data10.1145/37096793:1(1-28)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709679
Gao JLong C(2024)RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor SearchProceedings of the ACM on Management of Data10.1145/36549702:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654970
Zhang PHu Z(2024)NetDS: Distributed Search Framework with Hybrid Acceleration Methods2024 IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA)10.1109/ISPA63168.2024.00301(2203-2210)Online publication date: 30-Oct-2024
https://doi.org/10.1109/ISPA63168.2024.00301
Gao JLong C(2023)High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison OperationsProceedings of the ACM on Management of Data10.1145/35892821:2(1-27)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3589282
Xu ABai Y(2023)Distributed Adaptive Optimization with Divisible CommunicationMachine Learning and Knowledge Discovery in Databases: Research Track10.1007/978-3-031-43418-1_39(654-670)Online publication date: 17-Sep-2023
https://doi.org/10.1007/978-3-031-43418-1_39
Xu ABai Y(2023)Cross Model Parallelism for Faster Bidirectional Training of Large Convolutional Neural NetworksMachine Learning and Knowledge Discovery in Databases: Research Track10.1007/978-3-031-43418-1_38(637-653)Online publication date: 17-Sep-2023
https://doi.org/10.1007/978-3-031-43418-1_38
Zhang PPan HLi ZCui PJia RHe PZhang ZTyson GXie G(2022)NetSHa: In-Network Acceleration of LSH-Based Distributed SearchIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.313584233:9(2213-2229)Online publication date: 1-Sep-2022
https://doi.org/10.1109/TPDS.2021.3135842
Zhang PPan HLi ZXie GCui P(2021)NetANNS: A High-Performance Distributed Search Framework Based On In-Network Computing2021 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom)10.1109/ISPA-BDCloud-SocialCom-SustainCom52081.2021.00047(271-278)Online publication date: Sep-2021
https://doi.org/10.1109/ISPA-BDCloud-SocialCom-SustainCom52081.2021.00047
Zhang PPan HLi ZHe PZhang ZTyson GXie G(2021)Accelerating LSH-based Distributed Search with In-network ComputationIEEE INFOCOM 2021 - IEEE Conference on Computer Communications10.1109/INFOCOM42981.2021.9488722(1-10)Online publication date: 10-May-2021
https://dl.acm.org/doi/10.1109/INFOCOM42981.2021.9488722
Song YGu YZhang RYu G(2021)ProMIPS: Efficient High-Dimensional c-Approximate Maximum Inner Product Search with a Lightweight Index2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00143(1619-1630)Online publication date: Apr-2021
https://doi.org/10.1109/ICDE51399.2021.00143
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten