Patent AU-2021105152-A4 (AU)
Title: Discrete Hash Algorithm Based on Two-bit Quantization Strategy
Inventor: YUE ZHENYA
IPC: H04L9/06
Filed: 2021-08-09
Granted: 2021-11-11
Abstract: : 
Discrete hashing algorithm based on double-bit quantization strategy. Hashing encodes high 
dimensional data points into binary codes. Most hashing methods use the single-bit quantization (SBQ) 
strategy for coding the data. However, this strategy often encodes neighboring points into totally different 
bits. Recently, a double-bit quantization (DBQ) strategy was proposed, which can better preserve the 
similarity of the data. The hashing problems are generally NP-hard, due to the discrete constraints. For 
tractability, some relaxation methods were proposed by discarding the discrete constraints. However, 
such a manner makes the hash codes less effective, due to the large quantization error. To obtain high
quality hash codes, some discrete hashing methods were proposed, which directly solve the hashing 
problem without any relaxations. However, the existing discrete hashing methods can only deal with 
single-bit hashing. In this patent, we propose a discrete hashing method to solve double-bit hashing 
problems. To address the difficulty brought by the discrete constraints, we propose a method to transform 
the discrete hashing problem into an equivalent continuous optimization problem. Then, we devise 
algorithms based on DC (difference of convex functions) programming to solve the problem. Numerical 
experiments are provided to show the superiority of the proposed methods.  
1
Table.1 
Methods MAP Precision @ 500 Trai 48bits I 64its |96bits 128bits 48bits MR 6 I| 96bits I 128~bits | bits 64it i | 6its I 128bits 
KSH 0.2732 | 0.3031 | 0.3065 0.3146 0.3821 | 0.4165 0.4234 | 0.4328 | 1.0440e+03 1.3415e+03| 2.4658e+03 | 3.4430e+03 
SDH 0.6448 | 0.6679 | 0.6772 0.6861 0.5731 | 0.5744 0.5862 | 0.5958 | 52.2322 63.3745 | 102.2348 | 138.4779 
CCA-rQ -f.359- |.-3976-- .4T .47 4-854|46 h 0977 0.5032 - -6.265- -7.980- | .873- | 13.628
(D)CCA-ITQ 0.4108 | 0.4293 | 0.4366 0.4373 0.5024 | 0.5096 0.5187 | 0.5264 | 5.4424 5.9688 | 7.2472 | 10.5403 
COSDISH 0.6324 | 0.6371 | 0.6427 0.6512 0.5545 | 0.5520 0.5692 | 0.5696 | 42.2243 78.3157 176.0228 - 338.4248
SDBQ 0.6645 | 0.6813 | 0.6886 0.6968 (16011 | 0.6047 0.6153 | 0.6176 | 15.5960 19.8074 23.4522 | 28.1509 
CDBQ-S 0.6773 | 0.6988 0 ,.7024 0.7112 0.6146 | 0.6234 0.6342 0.6374 16.2332 21.2458 26.4709 | 31.4643 
AGH 0.1457 0.1432 0.1415 0.1394 0.2588 | 0.2632 0.2677 0.2583 21.2244 21.2427 22.1082 | 22.1256 
(D)AGH 0.1552 0.1545 01512 0.1497 02594 - 0.2677 0.2708 0.2684 18.7156 18.8848 19.0712 19.2544 
SGH 0.1574 | 0.1647| 0.1633 0.1727 0.2389 | 0.2437 0.2548 | 0.2622 | 46.5229 63.5632 | 88.4528 | 122.3302 
(D)SGH 0.1605 0.1686 0.1692 0.1745 0.2544 - 0.2596 0.2626 0.2639 28.4007 36.1224 52.5547 | 84.4346 
PCA-TCQ | 0.1614 | 0.1683 | 0.1684 0.1702 0.2460 | 0.2584 0.2650 | 0.2724| 2.7743 3.5474 | 4.6547 | 5.7742 
(D)PCA-ITQ 0.1625 0.1688 0.1693 0.1714 0.2499 | 0.2597 0.2717 0.2749 1.8824 2.5478 3.2056 | 4.6698 
UDBQ | 0.1751 | 0.1796 | 0.1831 0.1862 0.2450 | 0.2682 0.2724- 0.2740| 46542 5.7585 | 7.1632 | 8.7965 
CDBQ-U 0.1762 0.1814 0.1868 0.1906 0.2526| 0.2723 0.2811 0.2846 4.8668 6.6584 9.2212 11.3437 
Table.2 
Methods |1MAP 2 | Precision @ 500 | Training time (s) 
|48bitM 64its I 96bits |128bits | 48bits |64its |96bits | 128bit |4ts sSMS 64its | 96bit-s 128bits 
KSH 0.4890 0.4893 0.4903 0.4915 0.4960 0.4970 0.5021 0.5094 817.9798 1.1621e+03 1.5132e+03 2.0097+03 
SDH 0.6426 0.6452 0.6446 0.6520 0.6359 0.6380 0.6308 0.6457 9.9351 16.2369 32.6964 58.3285 
CCA-ITQ 0.5544 0.5580 0.5592 0.5589 0.6107 0.6152 0.6169 0.6153 1.8941 2.8821 3.5243 4.4191 
(D)CCA-ITQ 0.5591 0.5601 0.5627 0.5630 0.6172 0.6197 0.6202 0.6223 1.6641 1.8129 2.8201 3.9318 
COSDISH 0.6427 0.6433 0.6576 0.6548 0.6234 0.6298 0.6243 0.6124 21.5985 38.7445 91.7205 208.707 
SDBQ 0.6772 0.6740 0.6741 0.6766 0.6436 0.6470 0.6498 0.6567 3.0987 3.7739 4.7762 5.7946 
CDBQ-S 0.6769 0.6746 0.6816 0.6862 0.6467 0.6488 0.6563 0.6551 2.3793 3.6676 4.6202 5.7005 
AGH 0.5075 0.5063 0.5049 0.5036 0.5483 0.5492 0.5493 0.5496 3.8590 3.8070 3.9793 3.9943 
(D)AGH 0.5082 0.5075 0.5077 0.5076 0.5407 0.5408 0.5381 0.5379 3.1289 3.8023 4.0200 4.1185 
SGH 0.5096 0.5106 0.5121 (.5127 0.5456 0.5468 0.5481 0.5504 17.6921 27.6947 39.2978 53.9579 
(D)SGH 0.5112 0.5107 0.5118 D.5107 0.5443 0.5434 0.5430 0.5414 9.1540 12.3466 18.3360 25.1673 
PCA-ITQ 0.5098 0.5099 0.5109 0.5107 0.5369 0.5376 0.5381 0.5389 0.2511 0.2263 0.3223 0.4066 
(D)PCA-ITQ 0.5112 0.5113 0.5112 0.5117 0.5444 0.5417 0.5411 0.5429 0.2285 0.1961 0.2326 0.2361 
QOCH 0.5117 0.5126 0.5163 0.515 - 0.5540 0.5163 0.515 0.518 912.672 2.631 2.615 3.3537 
UDBQ 0.5117 0.5176 .5163 0 .5155 0,5547 0.5616 0.5532 0.5605 1.6451 1.9437 2.5471 3.3853 
CDBQ-U 0.5169 0.5253 0.5227 0.5235 0.5559 0.5761 0.5600 0.5640 1.5617 1.8957 2.5297 3.2776 
1