問題：
私は N (~100m) 文字列をそれぞれ D (例: 100) 文字の長さで、低いアルファベット (例: 4 文字) 持っています。これらの N ポイント ( k ~ 0.1D) ごとに k 最近傍点を見つけたいと思います。隣接する文字列は、ハミング距離によって定義されます。解決策は可能な限り最善である必要はありませんが、近いほど良いです。
問題についての考え
これは些細な問題ではないと感じています。私は多くの論文とアルゴリズムを読みましたが、それらのほとんどは高次元では結果が悪く、次元が 5 未満の場合に機能します。たとえば、この論文は効率的なアルゴリズムを提案していますが、その定数は次元に指数関数的に関連しています。
現在、ハミング距離を維持または計算できるように次元を削減する方法を調査しています。
別のオプションは、局所性に敏感なハッシングです。選択したメトリックの下で互いに近いポイントは、高い確率で同じバケットにマップされます。ヘルプはありますか？あなたはどのオプションを好みますか？