LSH-Bibliotheken in Java

Question

Ich bin auf der Suche nach einer leichten Java-Bibliothek, die Nearest Neighbor Searches nach Locality Sensitive Hashing für nahezu gleichverteilte Daten in einem hochdimensionalen (in meinem Fall 32) Dataset mit einigen hunderttausend Datenpunkten unterstützt.

Es ist völlig gut genug, um alle Einträge in einem Bucket für eine Abfrage zu erhalten. Was ich wirklich brauche, könnte dann unter Berücksichtigung einiger Filterparameter auf andere Weise verarbeitet werden.

Ich habe bereits likelike gefunden, hoffe aber, dass es etwas kleiner und ohne andere Werkzeuge (wie Apache Hadoop im Fall von likelike) gibt.

Answer 1

Es ist diese: http://code.google.com/p/lsh-clustering/

Ich habe Zeit gehabt zu testen, aber zumindest kompiliert.

Answer 2

hier ein anderer: https://github.com/allenlsy/knn

Es verwendet LSH für KNN. Ich untersuche derzeit, es ist Usability =)

Answer 3

Vielleicht dieses:

„TarsosLSH ist eine Java-Bibliothek, die Örtlichkeit empfindlichen Hashing (LSH), ein praktischer nächste Nachbar Suchalgorithmus für mehrdimensionale Vektoren, die in sublinear Zeit arbeitet Es unterstützt mehrere Locality Sensitive Hashing (LSH) -Familien: die euklidische Hash-Familie (L2), die City-Block-Hash-Familie (L1) und die Cosinus-Hash-Familie.Die Bibliothek versucht, den "Sweet Spot" zu erreichen. und kompakt genug, um als Demonstration dafür zu dienen, wie LSH funktioniert. "

-Code kann here

Answer 4

Der ELKI Data-Mining-Framework kommt mit einem LSH-Index zu finden. Es kann mit den meisten enthaltenen Algorithmen verwendet werden (alles, das Bereichs- oder nn-Suchen verwendet) und funktioniert manchmal sehr gut.

In anderen Fällen scheint LSH kein guter Ansatz zu sein. Es kann ziemlich schwierig sein, die LSH-Parameter richtig zu machen: Wenn Sie einige Parameter zu hoch wählen, wächst die Laufzeit sehr (bis hin zu einem linearen Scan). Wenn Sie sie zu niedrig wählen, wird der Index zu approximativ und verliert an viele Nachbarn.

Es ist wahrscheinlich die größte Herausforderung mit LSH: Suche nach guten Parameter, die die gewünschte Beschleunigung ergeben und aus dem Index gut genug Genauigkeit immer ...