Laboratory of Mathematical Logic at PDMI

Пятница, 8 февраля, комната 106. Начало в 18:00.

Докладчик: В. Б. Балакирский (EIDMA, Eindhoven University of Technology).

HASHING OF DATABASES WITH THE USE OF METRIC PROPERTIES OF THE HAMMING SPACE
We describe hashing of databases as a problem of information and coding theory. It is shown that the triangle inequality for the Hamming distances between binary vectors can essentially decrease the computational efforts of searching for a pattern in databases. Introduction of the Lee distance in the space, which consists of the Hamming distances, leads to a new metric space where the triangle inequality is effectively used.