ローカリティセンシティブハッシュ - バケットが空の場合はどうなりますか？

Question

いくつかのハッシュのセットに基づいてLSHデータベースを構築したと仮定し、近似近似を見つけるためにデータベースにクエリを開始します。

クエリポイントのハッシュを計算し、対応するバケットが空の場合に何が起こるかに関するガイドラインはありますか？同様に、私は5つの近似近点を見つけたいと思い、バケットには他の4つのデータ点しかありませんか？

Answer 1

私は検索のためのポイントが少なすぎると思うので、あなたのトレーニングデータにはバケツが多すぎます。それはもちろんアプリケーションに依存します。 LSH toolbox by Greg Shakhnarovichの実装と彼のREADME fileを見てください。この実装では、より少ないハッシュ関数（より小さいk）はいっそう豊富なバケットを意味し、それは遅いLSHを意味する。