2

私は、接頭辞ツリーを使用して O(1) で単一の最近傍を見つけることができたと彼らが言及している論文を読んでいます。一般的な問題を説明し、次に古典的な解決策を説明し、最後に提案された解決策を論文で説明します。

問題: ビット ベクトル L (すべてのベクトルは同じ長さ) とクエリ ビット ベクトル q のリストが与えられた場合、q の最近傍を見つけたいとします。距離メトリックは、ハミング距離 (異なるビット数) です。単純なアプローチは、リストを調べて、リスト内の各ベクトルと q の間のハミング距離を計算することです。これには O(N) が必要です。ただし、非常に高価な数百万のビット ベクトルがあることを考えると、それを削減したいと考えています。

古典的な解決策: この問題に対する古典的な解決策は、近似を使用して最近傍を見つけ、O(logN) を達成することです。これを行う方法は、最初に L を辞書順に並べ替えて、同様のビット ベクトルが互いに近くなるようにすることです。次に、q が与えられると、ソートされたリストにバイナリ検索を適用して、ソートされたリスト内で q が存在する可能性のある位置を取得し、リスト内でその上と下にあるベクトルを取得して (それらはソートの点で類似しているため)、それらの間の距離を調べ、ハミング距離が最も小さいものを選択します。ただし、単純に 1 つの並べ替えを行うだけでは、多くの同様のベクトルを見逃す可能性があるため、できるだけ多くの同様のベクトルをカバーするために、P 個のリストと P 個のジャンブリング関数を使用します。各ジャンブリング関数は、各リストに対応しています。次に、対応するジャンブリング関数でビットをジャンブリングした後、各ビット ベクトルを P の各リストに挿入します。したがって、それぞれがビット ベクトルを持ちますが、ビットの順序が異なる P 個のリストになります。P の各リストを辞書順に並べ替えます。q が与えられると、P の各リストに同じ二分探索を適用しますが、ここでは、アクセスしているリストに応じて q にジャンブリング関数を適用する前に適用します。このステップでは、q に最も類似した P 個のベクトルを取得するため、最終的に q に最も類似したベクトルを取得します。このようにして、できるだけ類似したベクトルをカバーします。ソートに必要な時間を無視すると、最近傍を見つけるのに必要な時間は O(log n) になります。これは、各リストでの二分探索の時間です。P の各リストを辞書順に並べ替えます。q が与えられると、P の各リストに同じ二分探索を適用しますが、ここでは、アクセスしているリストに応じて q にジャンブリング関数を適用する前に適用します。このステップでは、q に最も類似した P 個のベクトルを取得するため、最終的に q に最も類似したベクトルを取得します。このようにして、できるだけ類似したベクトルをカバーします。ソートに必要な時間を無視すると、最近傍を見つけるのに必要な時間は O(log n) になります。これは、各リストでの二分探索の時間です。P の各リストを辞書順に並べ替えます。q が与えられた場合、P の各リストに同じ二分探索を適用しますが、ここでは、アクセスしているリストに応じて q にジャンブリング関数を適用する前に適用します。このステップでは、q に最も類似した P 個のベクトルを取得するため、最終的に q に最も類似したベクトルを取得します。このようにして、できるだけ類似したベクトルをカバーします。ソートに必要な時間を無視すると、最近傍を見つけるのに必要な時間は O(log n) になります。これは、各リストでの二分探索の時間です。このようにして、できるだけ類似したベクトルをカバーします。ソートに必要な時間を無視すると、最近傍を見つけるのに必要な時間は O(log n) になります。これは、各リストでの二分探索の時間です。このようにして、できるだけ類似したベクトルをカバーします。ソートに必要な時間を無視すると、最近傍を見つけるのに必要な時間は O(log n) になります。これは、各リストでの二分探索の時間です。

提案された解決策: 論文で提案されているこのソリューション (ただし、説明はありません) は、プレフィックス ツリーを使用して O(1) 時間で最近傍を取得できることを示しています。論文では、P 個のプレフィックス ツリーと P 個のジャンブリング関数を使用すると述べています。ここで、各ジャンブリング関数は各ツリーに対応しています。次に、対応するジャンブリング関数で各ベクトルのビットをジャンブリングした後、ビット ベクトルを各ツリーに挿入します。q が与えられると、各ツリーに対応する q にジャンピング関数を適用し、各ツリーから q に最も類似したベクトルを取得します。これで、ツリーから取得された P ビットのベクトルが得られます。論文では、プレフィックスツリーから q に最も類似したベクトルを取得するだけで O(1) であると述べています。プレフィックスツリーの検索はO（M）であることがわかっているので、これはまったくわかりません.Mはビットベクトルの長さです。

これは私が参照している論文です (セクション 3.3.2): リアルタイム Web でのコンテンツベースの群集検索

http://students.cse.tamu.edu/kykamath/papers/cikm2012/fp105-kamath.pdf

また、これに関連する私の他の質問に答えていただければ幸いです: NN検索のプレフィックスツリーで最も類似したビットベクトルを検索する方法は?

4

3 に答える 3

1

これはO(1)、非常に大まかに定義された意味でのみです。実際、この場合、私はそれらの使用法に異議を唱えることまでします。

彼らの論文から、ユーザーに最も近い隣人を決定するには、u.

  1. 「最初にその署名を計算します」： 「署名」に依存するu可能性がありますO(1)
  2. "then for every prefix tree in " : うーん、Pあまり聞こえないの方が正しいでしょう。O(1)O(P)
  3. 2からの反復部分O(d)。d(これは、プレフィックス ツリーで最も近いポイントを見つけることがこれ以上になる可能性があるため、寛大です)
  4. 「これを行った後...|P|署名が得られます...その中で最小のハミング距離が選択されます」:別のP計算で単語の長さを計ります。 O(Pd).

より正確には、総実行時間はO(1) + O(P)+ O(Pd) + O(Pd) = O(Pd)

@mcdowella は、彼らがこれをどのように作成しようとしているのかについての彼の分析で正しいと信じていますが、O(1)私が読んだことから、彼らは私を納得させませんでした.

于 2013-06-24T19:58:51.767 に答える
1

この論文の議論は、それが O(f(x)) の場合、x は次元数ではなく、ツリーに格納されているアイテムの数でなければならないということだと思います。ご指摘のとおり、プレフィックス ツリーの場合、M はビット ベクトルの長さである O(M) のように時間がかかりますが、M が固定されていると考えると、関心のあるのはアイテムの数としての動作ですツリーが増加すると、O(1) になります。

ところで、Muja と Lowe による論文「自動アルゴリズム構成による高速近似最近傍」では、LSH に対するツリーベースの競合も考慮されています。ここでのアイデアは、ツリーの構築をランダム化し、複数のツリーを作成し、各ツリーをすばやく大雑把に検索して、任意のツリーで見つかった最良の答えを選択することです。

于 2013-06-24T18:40:07.230 に答える
0

ツリー内の P のノードへの参照があり、O(1) 償却時間で次または前のエントリに移動できると仮定します。つまり、秘訣は下層のノードにアクセスできるようにすることです。

于 2013-06-24T18:23:36.450 に答える