局所感度ハッシュのためのインテリジェントプロービング

過去十年は、多様なデータコンテンツの（引き続きの）爆発と、インテリジェントデータ分析技術の急速な発展によって特徴づけられています。2000年代中頃に私たちが特定した問題の一つは、特徴を豊富に持つデータの類似検索でした。ここでの課題は、高次元空間において高い精度と高い効率を両立させることでした。近似最近傍を見つけるために特定のランダムな空間パーティションとハッシュテーブルルックアップを使用する局所感度ハッシュ（LSH）は、理論的保証を持つ有望なアプローチでした。しかし、良好な検索品質を達成するには多くのハッシュテーブルが必要であり、LSH単体では不十分でした。Panigrahyのアイデアに基づいて、私たちのマルチプローブLSHメソッドはインテリジェントプロービングの概念を導入しました。クエリオブジェクトが与えられると、統計的確率を計算することによって、その隣接ハッシュバケットを戦略的にプローブします。このようなインテリジェントプロービングは、高品質を維持しつつハッシュテーブルの数を大幅に削減することができます。本論文では、問題の動機付け、課題、マルチプローブLSHの重要な設計考慮事項を再検討し、この分野の最近の進展と今後の研究のためのいくつかの質問について議論します。