Более-менее повторена работа "Sim. search in high dimensions..." in ("Proc. of 25th VLDB conf", 1999)
Написан питонячий прототип для расстояния Хамминга и для l1-метрики.
Для растояния хамминга есть c++ библиотека и реализация. Работа над l-1 метрикой в C++ в процессе (TODO добавить инфу как будет готово)
В нулевом порядке повторяет питонячью реализацию, но имеет одну приятную особенность, она умеет работать с разной реализацией двоичных строк, лишь бы для них были определены SetBit и GetBit (см. lsh.h)
В частности, она умеет работать с разреженными строками к которым применено хеширование признаков
Простые вещи в духе того, что биты выставляются верно и хэши считаются адекватно проверены тестами. Кроме того проверяется, что метод всегда найдет элемент если он есть в выборке. Более сложные утверждения проверять кажется сложно, т. к. они случаются с некоторой вероятностью.
Есть обозримый пример того как метод работает в тетрадке нельзя сказать что не возникает сомнений относительно того, на сколько такие результаты адекватны, но кажется более-менее приемлимо. В частности
- совсем больших расстояний не получилось
- при уменьшении
r_1т.е. расстояния в котором мы ищем соседей, уменьшается число найденных примеров (поиск ближайшего соседа становится точнее) - при увеличении числа бит, число найденных примеров падает (по аналигичным причинам)
- при увеличении числа минихэшей распределение расстояний сдвигается в сторону истинного распределения расстояний
Как обычно
mkdir ./build
cd ./build
cmake ..
makeПонадобятся библиотеки boost версии 1.63 (или другой которую надо указать в CMakeLists)
Я нагенерировал случайных данных, достаточно разреженных, с вероятностью взведения каждого из 4096 бит p=0.01, 100000 примеров для тренировки и 10000 для теста, просил найти 32 соседа. Памяти это не занимает почти нисколько (сравни с питоном и плотными матрицами для KNN: около 3ГБ). После очень продолжительной предобработки запрос занял около шести минут. Питонячей версии честного KNN из sklearn на поиск соселей понадобилось около 50-ти минут. Подробности в тетрадке
Мне как-то не очень понравился метод, на то есь несколько причин
Метод параметризован параметрами r_1, r_2, p_1, p_2 из свосйтв хеширующего семейства (напомню, примеры в шаре r_1 с вероятностью более p_1 будут иметь одинаковый набор минихэшей, а за пределами шара r_2 - с вероятностью менее p_2). Такой набор параметров понятен с точки зренее математики, но пользователю не говорит ровным счетом ничего. Кроме того не получается требовать какие-то гарантии от метода на занимаемую память и количество копий объектов (даже если и не копий, за счет указателей, то просмотров одного объекта в разных корзинках) т. к. размер корзины, их количество и количество минихэшей сложно связаны между собой и нельзя задать их все отдельно друг от друга.
И вроде бы метод будет сублинейным по этим параметрам, но заказать их не получается.
Метод ищет ближайший пример в шаре r_1 а "заодно" находит еще какие-то близкие примеры, иногда их хавататает чтобы ответить на запрос пользователя, а иногда - нет. Управлять этим напрямую нельзя, только через параметры радиуса и отступа.