Lokalempfindliches Hashing

Im Informatik, lokalempfindliches Hashing (LSH) ist eine algorithmische Technik, die ähnliche Eingabeelemente in dieselbe "Eimer" mit hoher Wahrscheinlichkeit hasht.[1] (Die Anzahl der Eimer ist viel kleiner als das Universum möglicher Eingabeelemente.)[1] Da ähnliche Elemente in denselben Eimern enden, kann diese Technik verwendet werden Datenclustering und Suche nach Nachbarn. Es unterscheidet sich von Konventionelle Hashing -Techniken darin Hash -Kollisionen werden maximiert, nicht minimiert. Alternativ kann die Technik als Weg gesehen werden Reduzieren Sie die Dimensionalität von hochdimensionalen Daten; Hochdimensionale Eingangselemente können auf niedrigdimensionale Versionen reduziert werden, während die relativen Abstände zwischen den Elementen erhalten bleiben.

Hashing-basierte ungefähre Suche nach Nachbarn Algorithmen verwenden im Allgemeinen eine von zwei Hauptkategorien von Hashing-Methoden: entweder datenunabhängige Methoden, wie z. B. lokalempfindliches Hashing (LSH); oder datenabhängige Methoden wie z. Lokalitätsvorverwaler Hashing (Lph).[2][3]

Definitionen

Ein LSH -Familie[1][4][5] ist definiert für

  • a metrischer Raum ,
  • eine Schwelle ,
  • ein Annäherungsfaktor ,
  • und Wahrscheinlichkeiten und .

Diese Familie ist eine Reihe von Funktionen Diese Kartenelemente des metrischen Raums zu Eimern . Eine LSH -Familie muss die folgenden Bedingungen für zwei Punkte erfüllen und jede Hash -Funktion gleichmäßig zufällig ausgewählt von :

  • wenn , dann (d. h., p und q kollidieren) zumindest mit Wahrscheinlichkeit ,
  • wenn , dann mit Wahrscheinlichkeit höchstens .

Eine Familie ist interessant, wenn . Eine solche Familie wird genannt -empfindlich.

Alternative[6] Es wird in Bezug auf ein Universum von Gegenständen definiert U das hat a Ähnlichkeit Funktion . Ein LSH -Schema ist eine Familie von Hash Funktionen H gekoppelt mit a Wahrscheinlichkeitsverteilung D über die Funktionen so, dass eine Funktion nach D erfüllt das Eigentum, das für jeden .

Lokalitätsvorverwaler Hashing

A örtlich ertragende Hash ist ein Hash-Funktion f das karten Punkte in a metrischer Raum zu einem skalaren Wert so, dass

für drei Punkte .

Mit anderen Worten, dies sind Hash -Funktionen, bei denen der relative Abstand zwischen den Eingangswerten im relativen Abstand zwischen den Ausgangshash -Werten erhalten bleibt. Eingangswerte, die näher beieinander liegen, erzeugen Ausgabe -Hash -Werte, die näher beieinander liegen.

Dies steht im Gegensatz zu kryptografisch Hash Funktionen und Überprüfungen, die so konzipiert sind, dass sie haben sollen zufällige Ausgangsdifferenz zwischen benachbarten Eingängen.

Die erste Familie der lokalerbewussten Hash-Funktionen wurde als eine Möglichkeit zur Erleichterung entwickelt Datenpipelination in Implementierungen von Parallele Random-Access-Maschine (Kinderwagen) Verwenden von Algorithmen Universal Hashing Speicher reduzieren Streit und Netzüberlastung.[7][8]

Lokalitätserhaltungshashes beziehen sich auf Raumfüllungskurven.[wie?]

Verstärkung

Angenommen -empfindliche Familie Wir können neue Familien bauen entweder durch die und bestehende oder or oder konstruktiv von .[1]

Um ein und einzubauen, definieren wir eine neue Familie von Hash -Funktionen g, wo jede Funktion g ist gebaut von k zufällige Funktionen aus . Wir sagen dann das für eine Hash -Funktion , wenn und nur wenn alles zum . Seit den Mitgliedern von werden unabhängig für jeden ausgewählt , ist ein -empfindliche Familie.

Um eine Ortskonstruktion zu schaffen, definieren wir eine neue Familie von Hash -Funktionen g, wo jede Funktion g ist gebaut von k zufällige Funktionen aus . Wir sagen dann das für eine Hash -Funktion , dann und nur dann, wenn für einen oder mehrere Werte von i. Seit den Mitgliedern von werden unabhängig für jeden ausgewählt , ist ein -empfindliche Familie.

Anwendungen

LSH wurde auf mehrere Problembereiche angewendet, darunter:

  • Computersicherheit[17]

Methoden

Bit -Probenahme für Hamming -Distanz

Eine der einfachsten Möglichkeiten, eine LSH -Familie zu konstruieren, ist die Probenahme.[5] Dieser Ansatz funktioniert für die Hamming -Entfernung Über d-Dimensionale Vektoren . Hier die Familie von Hash -Funktionen ist einfach die Familie aller Projektionen von Punkten auf einem der Koordinaten, d. H., , wo ist der Die Koordinate von . Eine zufällige Funktion aus Wählt einfach ein zufälliges Bit aus dem Eingangspunkt. Diese Familie hat die folgenden Parameter: , .[Klarstellung erforderlich]

Min-wise unabhängige Permutationen

Vermuten U besteht aus Teilmengen mit einem Boden von aufzählbaren Elementen zusammen S und die Ähnlichkeitsfunktion von Interesse ist die Jaccard Index J. Wenn π ist eine Permutation auf den Indizes von S, zum Lassen . Jede mögliche Wahl von π definiert eine einzelne Hash -Funktion h Mapping -Eingangssätze auf Elemente von S.

Definieren Sie die Funktionsfamilie H die Menge all dieser Funktionen sein und lassen D sei der einheitliche Verteilung. Zwei Sätze Der Fall, dass entspricht genau dem Ereignis, den der Minimierer von π Über liegt im Inneren . Wie h wurde gleichmäßig zufällig ausgewählt, und Definieren Sie ein LSH -Schema für den Jaccard -Index.

Weil die Symmetrische Gruppe an n Elemente haben Größe n!, Wählen Sie eine wirklich zufällige Permutation Aus der vollständigen symmetrischen Gruppe ist es für noch mäßig dimensionierbar n. Aus diesem Tatsache gab es erhebliche Arbeiten daran, eine Familie von Permutationen zu finden, die "wise unabhängig" sind-eine Permutationsfamilie, für die jedes Element der Domäne die gleiche Wahrscheinlichkeit hat, dass sie unter einem zufällig ausgewählten Minimum sein π. Es wurde festgestellt, dass eine min-weise unabhängige Familie von Permutationen mindestens Größe hat ,[18] und dass diese Grenze eng ist.[19]

Da die unabhängigen Familien in Bezug auf praktische Anwendungen zu groß sind, werden zwei variante Vorstellungen von Minise Unabhängigkeit eingeführt: eingeschränkte min-wise-unabhängige Permutationen Familien und ungefähre miniede unabhängige Familien. Die eingeschränkte Minise-Unabhängigkeit ist die minise Unabhängigkeitseigenschaft, die auf bestimmte Kardinalitätsgruppen beschränkt ist k.[20] Die ungefähre miniege Unabhängigkeit unterscheidet sich von der Immobilie um höchstens ein fester ε.[21]

Open Source -Methoden

Nilsimsa Hash

Nilsimsa ist ein lokalempfindlicher Hashing-Algorithmus, der in verwendet wird Anti-Spam Bemühungen.[22] Das Ziel von Nilsimsa ist es, eine Hash -Verdauung einer E -Mail -Nachricht so zu generieren, dass die Verdauung von zwei ähnlichen Nachrichten zueinander ähneln. Das Papier legt nahe, dass der Nilsimsa drei Anforderungen erfüllt:

  1. Die Digest, die jede Nachricht identifiziert, sollte nicht wesentlich für Änderungen variieren, die automatisch erzeugt werden können.
  2. Die Codierung muss gegen absichtliche Angriffe robust sein.
  3. Die Codierung sollte ein extrem geringes Risiko für falsch -positive Ergebnisse unterstützen.

Tlsh

Tlsh ist ortsempfindlicher Hashing-Algorithmus für eine Reihe von Sicherheits- und digitalen forensischen Anwendungen.[17] Das Ziel von TLSH ist es, Hash -Verdauungen für Nachrichten zu generieren, so dass niedrige Entfernungen zwischen Digests darauf hinweisen, dass ihre entsprechenden Nachrichten wahrscheinlich ähnlich sind.

Die in der Arbeit auf einer Reihe von Dateitypen durchgeführten Tests identifizierten den NilSIMSA -Hash als eine signifikant höhere falsch positive Rate im Vergleich zu anderen Ähnlichkeitsdau -Digest -Schemata wie TLSH, SSDEEP und SDHASH.

Eine Implementierung von TLSH ist als verfügbar als Quelloffene Software.[23]

Zufällige Projektion

Sketch of 1-theta vs. cos(theta)
Für kleine Winkel (nicht zu nahe an orthogonal), ist eine ziemlich gute Annäherung an .

Die zufällige Projektionsmethode von LSH durch Moses Charikar[6] genannt Simhash (Auch manchmal als Arccos bezeichnet[24]) ist so konzipiert, dass sie die annähern Kosinusentfernung zwischen Vektoren. Die Grundidee dieser Technik besteht darin, einen zufälligen Auswahl zu wählen Hyperebene (definiert durch einen normalen Einheitsvektor r) Zu Beginn und verwenden Sie die Hyperebene zu Hash -Eingangsvektoren.

Bei einem Eingangsvektor v und eine Hyperebene definiert von r, wir lassen . Das ist, Je nachdem welche Seite der Hyperebene v Lügen.

Jede mögliche Wahl von r definiert eine einzelne Funktion. Lassen H Sei der Satz all dieser Funktionen und lassen D Sei wieder die einheitliche Verteilung. Es ist nicht schwer zu beweisen, dass für zwei Vektoren , , wo ist der Winkel zwischen u und v. ist eng verwandt mit .

In diesem Fall produziert Hashing nur ein einziges Stück. Zwei Vektoren stimmen mit der Wahrscheinlichkeit überein, proportional zum Cosinus des Winkels zwischen ihnen.

Stabile Verteilungen

Die Hash -Funktion[25] Karten a d-Dimensionaler Vektor auf den Satz von Ganzzahlen. Jede Hash -Funktion in der Familie wird durch eine Auswahl von zufälligen indiziert und wo ist ein d-Dimensionaler Vektor mit Einträgen, die unabhängig von a ausgewählt wurden stabile Verteilung und ist eine reelle Zahl, die gleichmäßig aus dem Bereich ausgewählt wird [0, R]. Für ein festes die Hash -Funktion wird gegeben von .

Andere Baumethoden für Hash -Funktionen wurden vorgeschlagen, um den Daten besser zu passen.[26] Insbesondere K-Means-Hash-Funktionen sind in der Praxis besser als projektionsbasierte Hash-Funktionen, jedoch ohne theoretische Garantie.

Semantisches Hashing

Semantisches Hashing ist eine Technik, die versucht, Eingabelemente an Adressen zu kartieren, so dass engere Eingaben höher sind Semantische Ähnlichkeit.[27] Die Hashcodes werden durch Training von einem gefunden künstliche neuronale Netz oder Grafisches Modell.

LSH -Algorithmus für die nächste Suche nach Nachbarn

Eine der Hauptanwendungen von LSH ist die Bereitstellung einer Methode für eine effiziente ungefähre Annäherung Suche nach Nachbarn Algorithmen. Betrachten Sie eine LSH -Familie . Der Algorithmus hat zwei Hauptparameter: den Breitenparameter k und die Anzahl der Hash -Tabellen L.

Im ersten Schritt definieren wir eine neue Familie von Hash -Funktionen g, wo jede Funktion g wird durch Verkettung erhalten k Funktionen aus , d.h. . Mit anderen Worten, eine zufällige Hash -Funktion g wird durch Verkettung erhalten k zufällig ausgewählte Hash -Funktionen von . Der Algorithmus konstruiert dann L Hash -Tabellen, die jeweils einer anderen zufällig ausgewählten Hash -Funktion entsprechen g.

Im Vorverarbeitungsschritt haben wir alle n d-Dimensionale Punkte aus dem Datensatz S in jeden der der L Hash -Tische. Da die resultierenden Hash -Tabellen nur haben n ungleich Null-Einträge können die Menge an Speicher, die pro Hash-Tabelle verwendet wird Verwenden von Standard Hash Funktionen.

Einen Abfragepunkt gegeben qDer Algorithmus iteriert über die L Hash Funktionen g. Für jeden g Betrachtet wird die Datenpunkte abgerufen, die in denselben Eimer wie q. Der Prozess wird so schnell wie ein Punkt in der Entfernung gestoppt aus q gefunden.

Angesichts der Parameter k und LDer Algorithmus hat die folgenden Leistungsgarantien:

  • Vorverarbeitungszeit: , wo t ist die Zeit, eine Funktion zu bewerten an einem Eingangspunkt p;
  • Platz: , plus den Raum zum Speichern von Datenpunkten;
  • Abfragezeit: ;
  • Der Algorithmus gelingt es, einen Punkt in Abstand zu finden aus q (Wenn es einen Punkt in Abstand gibt R) mit Wahrscheinlichkeit zumindest ;

Für ein festes Annäherungsverhältnis und Wahrscheinlichkeiten und , man kann setzen und , wo . Dann erhält man die folgenden Leistungsgarantien:

  • Vorverarbeitungszeit: ;
  • Platz: , plus den Raum zum Speichern von Datenpunkten;
  • Abfragezeit: ;

Verbesserungen

Wann t ist groß, es ist möglich, die Hashing -Zeit von von . Dies wurde durch gezeigt[28] und[29] was gab

  • Abfragezeit: ;
  • Platz: ;

Es ist manchmal auch der Fall, dass der Faktor kann sehr groß sein. Dies geschieht zum Beispiel mit Jaccard -Ähnlichkeit Daten, bei denen selbst der ähnlichste Nachbarn oft eine ziemlich niedrige Jaccard -Ähnlichkeit mit der Abfrage hat. Im[30] Es wurde gezeigt, wie die Abfragezeit verkürzt werden kann (ohne Hashing -Kosten) und ähnlich der Raumnutzung.

Siehe auch

Verweise

  1. ^ a b c d Rajaraman, A.; Ullman, J. (2010). "Mining von massiven Datensätzen, Kap. 3".
  2. ^ Zhao, Kang; Lu, Hongtao; Mei, Jincheng (2014). Lokalitätserhaltungshashing. AAAI -Konferenz über künstliche Intelligenz. Vol. 28. S. 2874–2880.
  3. ^ Tsai, Yi-Hsuan; Yang, Ming-Hsuan (Oktober 2014). "Lokalität aufbewahrt Hashing". 2014 IEEE International Conference on Image Processing (ICIP). S. 2988–2992. doi:10.1109/icip.2014.7025604. ISBN 978-1-4799-5751-4. ISSN 1522-4880. S2CID 8024458.
  4. ^ Gionis, a.; Indyk, P.; Motwani, R. (1999). "Ähnlichkeitssuche in hohen Dimensionen über Hashing". Proceedings der 25. sehr großen Datenbankkonferenz (VLDB).
  5. ^ a b Indyk, Piotr.; Motwani, Rajeev. (1998). "Ungefähr am nächsten Nachbarn: Um den Fluch der Dimensionalität zu beseitigen.". Proceedings of 30. Symposium über die Computertheorie.
  6. ^ a b Charikar, Moses S. (2002). "Ähnlichkeitsschätzungstechniken aus Rundalgorithmen". Verfahren des 34. jährlichen ACM -Symposiums über die Theorie des Computers. S. 380–388. Citeseerx 10.1.1.147.4064. doi:10.1145/509907.509965.
  7. ^ Chin, Andrew (1991). Komplexitätsprobleme im Allgemeinen Parallele Computing (DPHIL). Universität von Oxford. S. 87–95.
  8. ^ Chin, Andrew (1994). "Lokalitätsverschreibende Hash-Funktionen für allgemeine Zwecke parallele Berechnung" (PDF). Algorithmus. 12 (2–3): 170–181. doi:10.1007/bf01185209.
  9. ^ Das, Abhinandan S.; et al. (2007), "Google News Personalisierung: Skalierbares Online -Kollaborationsfiltering", Proceedings der 16. Internationalen Konferenz über World Wide Web: 271, doi:10.1145/1242572.1242610, ISBN 9781595936547, S2CID 207163129.
  10. ^ Koga, Hisashi; Tetsuo ishibashi; Toshinori Watanabe (2007), "Schneller agglomerativer hierarchischer Clustering-Algorithmus unter Verwendung von lokalempfindlichem Hashing", Wissens- und Informationssysteme, 12 (1): 25–53, doi:10.1007/s10115-006-0027-5, S2CID 4613827.
  11. ^ Cochez, Michael; Mou, Hao (2015), "Twister Versuche: Ungefähre hierarchische agglomerative Clustering für die durchschnittliche Entfernung der linearen Zeit" (PDF), Verfahren Sie Sigmod '15 Proceedings der ACM Sigmod International Conference 2015 über das Management von Daten: 505–517, doi:10.1145/2723372.2751521, ISBN 9781450327589, S2CID 14414777.
  12. ^ Brinza, Dumitru; et al. (2010), "Schneller Nachweis von Gen-Gene-Wechselwirkungen in genomweiten Assoziationsstudien", Bioinformatik, 26 (22): 2856–2862, doi:10.1093/bioinformatics/btq529, PMC 3493125, PMID 20871107
  13. ^ Dejavu - Audio -Fingerabdruck und Anerkennung in Python, 2018-12-19
  14. ^ Aluç, Güneş; Özsu, M. Tamer; Daudjee, Khuzaima (2018), "Aufbau selbstklusterender RDF-Datenbanken mithilfe von Tunable-LSH", Das VLDB -Journal, 28 (2): 173–195, doi:10.1007/s00778-018-0530-9, S2CID 53695535
  15. ^ Chen, Beidi; Medini, Tharun; Farwell, James; Gobriel, Sameh; Tai, Charlie; Shrivastava, Anshumali (2020-02-29). "Folie: Zur Verteidigung intelligenter Algorithmen über die Beschleunigung von Hardware für großflächige Deep-Learning-Systeme". Arxiv:1903.03129 [cs.dc].
  16. ^ Chen, Beidi; Liu, Zichang; Peng, Binghui; Xu, Zhaozhuo; Li, Jonathan Lingjie; Dao, Tri; Lied, Zhao; Shrivastava, Anshumali; Re, Christopher (2021), "Mongoose: Ein lernbarer LSH -Rahmen für ein effizientes Training des neuronalen Netzwerks", Internationale Konferenz über Lernrepräsentation
  17. ^ a b Oliver, Jonathan; Cheng, Chun; Chen, Yanggui (2013). TLSH - ein lokalempfindlicher Hash. 4. Cyberkriminalität und vertrauenswürdiger Computerworkshop. doi:10.1109/ctc.2013.9. ISBN 978-1-4799-3076-0.
  18. ^ Broder, A.Z.; Charikar, M.; Frieze, A.M.; Mitzenmacher, M. (1998). "Min-weise unabhängige Permutationen". Proceedings of the Thirtieth Annual ACM -Symposium über die Theorie des Computers. S. 327–336. Citeseerx 10.1.1.409.9220. doi:10.1145/276698.276781. Abgerufen 2007-11-14.
  19. ^ Takei, y.; Itoh, T.; Shinozaki, T. "Ein optimaler Konstruktion von genau min-weisen unabhängigen Permutationen". Technischer Bericht Comp98-62, IECE, 1998.
  20. ^ Matoušek, J.; Stojakovic, M. (2002). "Über eingeschränkte minise Unabhängigkeit der Permutationen". Vordruck. Abgerufen 2007-11-14.
  21. ^ Saks, M.; Srinivasan, a.; Zhou, S.; Zuckerman, D. (2000). "Niedrige Diskrepanz-Sets ergeben ungefähre min-wise unabhängige Permutationsfamilien". Informationsverarbeitungsbriefe. 73 (1–2): 29–32. Citeseerx 10.1.1.20.8264. doi:10.1016/s0020-0190 (99) 00163-5. Abgerufen 2007-11-14.
  22. ^ Damiani; et al. (2004). "Eine offene Digest-basierte Technik zur Spam-Erkennung" (PDF). Abgerufen 2013-09-01.
  23. ^ "TLSH". Abgerufen 2014-04-10.
  24. ^ Alexandr Andoni; Indyk, P. (2008). "Nahezu optimale Hashing-Algorithmen für den ungefähren Nachbarn in hohen Abmessungen". Kommunikation der ACM. 51 (1): 117–122. Citeseerx 10.1.1.226.6905. doi:10.1145/1327452.1327494. S2CID 6468963.
  25. ^ Datar, M.; Immorlica, N.; Indyk, P.; Mirrokni, V.S. (2004). "Lokalitätsempfindliches Hashing-Schema basierend auf p-stabilen Verteilungen". Verfahren des Symposiums zur Computergeometrie.
  26. ^ Pauleve, L.; Jegou, H.; Amsaleg, L. (2010). "Lokalität sensitives Hashing: Ein Vergleich von Hash -Funktionstypen und Abfragemechanismen". Mustererkennungsbuchstaben. 31 (11): 1348–1358. doi:10.1016/j.patrec.2010.04.004.
  27. ^ Salakhutdinov, Ruslan; Hinton, Geoffrey (2008). "Semantisches Hashing". Internationales Journal of Unen -Argumentation. 50 (7): 969–978. doi:10.1016/j.ijar.2008.11.006.
  28. ^ Dahlgaard, Søren, Mathias Bæk Tejs Knudsen und Mikkel Thorup. "Schnelle Ähnlichkeitskizzierung." 2017 IEEE 58. jährliches Symposium für Fundamente der Informatik (FOCS). IEEE, 2017.
  29. ^ Christiani, Tobias. "Schnelle ortssensitive Hashing-Frameworks für ungefähre Nachbarsuchung." Internationale Konferenz über Ähnlichkeitssuche und Anwendungen. Springer, Cham, 2019.
  30. ^ Ahale, Thomas Dybdahl. "Über das Problem von $$ p_1^{-1} $$ im ortssensitiven Hashing." Internationale Konferenz über Ähnlichkeitssuche und Anwendungen. Springer, Cham, 2020.
  31. ^ Gorman, James und James R. Curran. "Skalierung der Verteilung Ähnlichkeit mit großer Korpora." Proceedings der 21. Internationalen Konferenz über Computerlinguistik und die 44. Jahrestagung des Vereins für Computer -Linguistik. Association for Computational Linguistics, 2006.

Weitere Lektüre

  • Samet, H. (2006) Grundlagen mehrdimensionaler und metrischer Datenstrukturen. Morgan Kaufmann. ISBN0-12-369446-9

Externe Links