Fast and Compact Hamming Distance Index

Simon Gog

Rossano Venturini

0 0 Department of Computer Science, University of Pisa and Istella Srl 1 Institute of Theoretical Informatics, Karlsruhe Institute of Technology

This paper proposes new solutions for the approximate dictionary queries problem. These solutions combine the use of succinct data structures with an e cient representation of the keys to signi cantly reduce the space usage of the state-of-the-art solutions without introducing any time penalty. Finally, by exploiting triangle inequality, we can also signi cantly speed up the query time of the existing solutions.

Charikar . Similarity estimation techniques from rounding algorithms . In Proc. STOC , pages 380 { 388 , 2002 .

Cole ,

L.-A.

Gottlieb , and

Lewenstein . Dictionary matching and indexing with errors and don't cares . In Proc. STOC , pages 91 { 100 , 2004 .

Gog and

Venturini . Fast and compact Hamming distance index . In SIGIR , 2016 .

D. H.

Greene ,

Parnas , and

F. F.

Yao . Multi-index hashing for information retrieval . In Proc. FOCS , pages 722 { 731 , 1994 .

A. X.

Liu ,

Shen ,

and E.

Torng . Large scale hamming distance query processing . In Proc. ICDE , pages 553 { 564 , 2011 .

G. S.

Manku ,

Jain , and

A. D.

Sarma . Detecting near-duplicates for web crawling . In Proc. WWW , pages 141 { 150 , 2007 .