Es gibt eine Datenbank mit N Zeichenfolgen mit fester Länge. Es gibt eine Abfragezeichenfolge mit derselben Länge. Das Problem besteht darin, zuerst k Zeichenfolgen aus der Datenbank abzurufen, die die kleinste Hamming-Distanz zu q haben.

N ist klein (ca. 400), Zeichenfolgen sind lang und haben eine feste Länge. Die Datenbank ändert sich nicht, sodass wir Indizes vorberechnen können. Abfragen variieren stark, Caching und / oder Vorberechnung sind keine Option. Es gibt viele von ihnen pro Sekunde. Wir brauchen immer k Ergebnisse, auch wenn k-1 Ergebnisse mit 0 übereinstimmen (nach Hamming-Distanz sortieren und zuerst k nehmen, damit ortsabhängiges Hashing und ähnliche Ansätze nicht funktionieren). kd-tree und eine ähnliche Raumpartitionierung führen wahrscheinlich zu einer schlechteren Suche als die lineare Suche (Zeichenfolgen können sehr lang sein). BK-Tree ist derzeit die beste Wahl, aber es ist immer noch langsam und kompliziert, als es sein muss.

Es fühlt sich an, als gäbe es einen Algorithmus, der einen Index erstellt, der die meisten Einträge in wenigen Schritten verwirft und k <= t << N Einträge zur Berechnung der tatsächlichen Hamming-Distanz zurücklässt.

People schlägt Fuzzy-String-Matching basierend auf der Entfernung von Levenstein vor - danke, aber das Problem ist viel einfacher. Verallgemeinerte distanzmetrikbasierte Ansätze (wie BK-Bäume) sind gut, aber vielleicht gibt es etwas, das die oben beschriebenen Fakten nutzt (kleine DB / lange Zeichenfolgen mit fester Größe, einfache Hamming-Distanz

Links, Keywords, Papiere, Ideen? =)