Библиотеки LSH на Яве

Question

Я ищу облегченную библиотеку Java, которая поддерживает поиск ближайших соседей с помощью хеширования с учетом локальных особенностей для почти одинаково распределенных данных в многомерном (в моем случае 32) наборе данных с несколькими сотнями тысяч точек данных.

Это достаточно хорошо, чтобы получить все записи в корзине для запроса. Какие из них мне действительно нужны, могут быть обработаны другим способом с учетом некоторых параметров фильтра, к которым относится моя проблема.

Я уже нашел likelike , но надеюсь, что есть что-то немного меньше и без необходимости каких-либо других инструментов (например, Apache Hadoop в случае likelike).

Answer 1

Может быть, это:

"TarsosLSH - это библиотека Java, реализующая хеширование с учетом локальности (LSH), практичный алгоритм поиска ближайшего соседа для многомерных векторов, который работает в сублинейное время. Он поддерживает несколько семейств сэмплирования с учетом локальности (LSH): евклидово семейство хэшей (L2) ), семейство хеш-кодов городских кварталов (L1) и семейство хеш-кодов косинусов. Библиотека пытается найти хорошее место: она достаточно способна выполнять реальные задачи и достаточно компактна, чтобы служить демонстрацией того, как работает LSH ".

Код можно найти здесь

Answer 2

Apache Spark имеет реализацию LSH: https://spark.apache.org/docs/2.1.0/ml-features.html#locality-sensitive-hashing ( API ).

После игры с реализациями tdebatty и TarsosLSH я, скорее всего, буду использовать Spark, поскольку он поддерживает разреженные векторы в качестве входных данных. Для tdebatty требуется не разреженный массив логических значений или значений типа int, а реализация TarsosLSH Vector представляет собой не разреженный массив значений типа double. Это сильно ограничивает число измерений, которые можно разумно поддерживать.

Эта страница содержит ссылки на другие проекты, а также соответствующие документы и информацию: https://janzhou.org/lsh/.

Answer 3

Инфраструктура интеллектуального анализа данных ELKI поставляется с индексом LSH.Он может использоваться с большинством включенных алгоритмов (все, что использует поиск по диапазону или nn) и иногда работает очень хорошо.

В других случаях LSH не кажется хорошим подходом.Может быть довольно сложно получить правильные параметры LSH: если вы выбираете слишком высокие параметры, время выполнения сильно возрастает (вплоть до линейного сканирования).Если вы выбираете их слишком низко, индекс становится слишком приблизительным и проигрывает многим соседям.

Вероятно, это самая большая проблема с LSH: найти хорошие параметры, которые дают желаемое ускорение и , получаяДостаточно хорошая точность из индекса ...

Answer 4

Вот еще один: https://github.com/allenlsy/knn

Он использует LSH для KNN. Я сейчас изучаю его юзабилити =)

Answer 5

Вот этот: http://code.google.com/p/lsh-clustering/

У меня не было времени проверить его, но по крайней мере он компилируется.