Локально-чутливе хешування та сфери його застосування

Abstract

На сьогодні існує безліч технологій для роботи з даними невеликих розмірів, вони виконують поставлені їм завдання швидко та якісно. Проте вони є неефективними для великих масивів даних, особливо якщо мова йде про знаходження подібностей. Для порівняння мільярдів чи навіть трильйонів множин потрібен метод чи технологія, яка б робила акцент на тих парах множин, що можуть бути дуже схожими між собою, при цьому ігноруючи переважну більшість інших пар. У статті описано особливості використання локально-чутливого хешування, яке здатне вказувати на подібні пари, не пробираючись через безліч усіх інших пар.

To date, there are many technologies for working with data of small sizes; they perform their tasks quickly and qualitatively. However, they are ineffective for large amounts of data, especially when it comes to finding similarities. To compare billions or even trillions of sets requires a method or technology that would focus on those pairs of sets that can be very similar to each other, while ignoring the vast majority of other pairs. To do this, a locality-sensitive hashing was invented, which is capable of pointing to such pairs without getting through the swamp of all other pairs. The method does not examine the whole set of elements; rather, it considers the elements that are likely to be similar. That is, locality-sensitive hashing focuses its attention on similar pairs of elements (candidate pairs) without exploring each pair. However, if the goal is to study the similarity of each pair, then localitysensitive hashing does not work for this.