2

数ヶ月前にBK-trees （Burkhard-Keller-Trees）について読みましたが、距離計量でもう一度読みたいものを保存するのに良い方法だと言われています。したがって、類似性によって何かを取得したい場合はそれぞれ。

しかし、これらのBKツリーは私にはそれほど速くは見えません。実装を試し、いくつかの出力を行ったとき、長距離を許可するとすぐにツリー内を頻繁に移動する必要がありました（レーベンシュタインでそれを実現し、最大6回の編集を許可しました）。

もちろん、最速の実装（速度だけの場合）は、テーブル内の各エントリから各エントリまでの距離を保存し、それらを直接検索することですが、これはオーバーヘッドが大きすぎます。

したがって、タイトルにリアルを追加しました。もう少しメモリが必要なのは問題ありませんが、実装は現実的で使用可能である必要があります（このような手法については、現実的とは何かを言うのに十分な知識はありませんが、ある程度の境界があると思います）。

利用可能なBKツリーよりも速いものはありますか、それともBKは本当に山の頂上にありますか（まだ）？

シナリオ

私には実際のユースケースはありませんが、シナリオは次のとおりです。私は何かの1 mioエントリがあり、それらは互いにある程度の距離を持っています（距離関数によって定義されます）。今、私は1つのエントリを取得し、次のいずれかを知りたいと思います。

  • 指定されたエントリに最もよく一致する5つのエントリ
  • 他のどのエントリ（数に依存しない）が、指定されたしきい値まで同じかそれ以下であるか

データベースは関係ありません。

結局、最良のアルゴリズムは両方に一致すると思いますか？

4

1 に答える 1

1

別のツリーベースの最近傍メトリックはhttp://en.wikipedia.org/wiki/Cover_treeです。それは実用的であると主張しており、http：//www.cs.waikato.ac.nz/ml/weka/がそれを取り上げているので、私は確かにそうです。しかし、最も近い隣人は、木やその他のものを使って正確に行うのは難しいようです。なぜなら、おおよその最も近い隣人のためにたくさんの提案が浮かんでいるからです。それが難しくなければ、かなりばかげていると思います。http://people.csail.mit.edu/indyk/edit.psで編集距離の1つを見ることができます。

最近傍検索を行う別の方法は、最近傍がクエリ文字列に正確に出現する文字の連続したセクションを持つことを期待することです。次に、データベース内のすべての文字列について、それらをすべての連続するk-longサブ文字列に切り刻み、完全に一致して使用できるテーブルを作成します。次に、クエリ文字列について、すべてのk-long連続サブ文字列を検討し、これらを完全に一致させ、このk-longサブ文字列の正確な検索で見つかったデータベースからのすべての文字列までの編集距離を計算します。

于 2012-07-02T03:54:54.627 に答える