Similarity is a vague concept which can be treated in a quantitative manner only using appropriate mathematical representation of the objects to compare and a metric on the space representation. In biology the mathematical representation of structure relies on strings taken from an alphabet of m symbols. Very often binary strings, m = 2, are used. The size of the binary string depends on the complexity of the structure to represent, so the string can be quite long. The Hamming distance is the most used metric with binary strings. The computational effort required to compute the Hamming distance linearly depends on the size of the string. However even a linear effort case may be computational heavy if many computations are required. One of the fastest computational approach to evaluate Hamming distances relies on look-up tables. The computational performance, however, rapidly deteriorates with the size of binary string length, due to cache misses. We present a computational strategy and implementation which can handle huge number of Hamming distance evaluation between binary strings of arbitrary length keeping computational performance competitive.

HAMFAST: Fast hamming distance computation

PAPPALARDO, FRANCESCO;PENNISI, MARZIO ALFIO;MOTTA, Santo
2009-01-01

Abstract

Similarity is a vague concept which can be treated in a quantitative manner only using appropriate mathematical representation of the objects to compare and a metric on the space representation. In biology the mathematical representation of structure relies on strings taken from an alphabet of m symbols. Very often binary strings, m = 2, are used. The size of the binary string depends on the complexity of the structure to represent, so the string can be quite long. The Hamming distance is the most used metric with binary strings. The computational effort required to compute the Hamming distance linearly depends on the size of the string. However even a linear effort case may be computational heavy if many computations are required. One of the fastest computational approach to evaluate Hamming distances relies on look-up tables. The computational performance, however, rapidly deteriorates with the size of binary string length, due to cache misses. We present a computational strategy and implementation which can handle huge number of Hamming distance evaluation between binary strings of arbitrary length keeping computational performance competitive.
2009
9780769535074
Mathematical representations; Hamming distance; Computational performance
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/76143
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact