21

Petar Maymounkov と David Mazières による Kademlia の論文では、XOR 距離は有効な非ユークリッド メトリックであり、有効なメトリックの各プロパティが必要または興味深い理由についての説明が限られていると言われています。

  • d(x,x) = 0
  • d(x,y) > 0、x != y の場合
  • forall x,y : d(x,y) = d(y,x) -- 対称性
  • d(x,z) <= d(x,y) + d(y,z) -- 三角形の不等式

一般に、メトリクスがこれらのプロパティを持つことが重要なのはなぜですか? Kademlia Distributed Hash Table 実装でクエリをルーティングするコンテキストで、これらの各プロパティが必要なのはなぜですか?

さらに、この論文では、一方向性 (特定の x と距離 l に対して、d(x,y) = l となる単一の y のみが存在する) により、すべてのクエリが同じパスに沿って収束することが保証されると述べられています。どうしてこんなことに？

4

3 に答える 3

7

私はこれについてかなり長い間頭を悩ませてきました.XOR-異なるビットの数、適切なハミング距離のように-はどのようにして全順序の基礎になるのでしょうか?

それはできません。そのようなメトリックだけでは、比較可能な関係には不十分です。できることは、ポイントの周りの円にノードをダンプすることだけです。

その後、私はその論文をより詳しく読んで、「整数値としての XOR」と書かれていることに気付きました。重要なのは「XOR メトリック」ではなく、ID の共通プレフィックスの長さです (そのうちの XOR派生メカニズムです。)

「self」からのハミング距離が同じで、「self」に共通するプレフィックスの長さを持つ 2 つのノードを取得します。最短の共通プレフィックスを持つノードが最も遠いノードです。

この論文では「XOR距離メトリック」を使用していますが、実際には「IDプレフィックス長の合計順序」を読む必要があります

于 2015-05-25T07:18:23.680 に答える
6

私はこれがそれを少し説明するかもしれないと思います、私に知らせてください

基本的に、完全に実装されたネットワーク (極端な) で一度に 1 ビットのみである場合、各ホップは前のホップの 2 倍の知識を持ちます。収束するにつれて、知識がネットワーク内で究極である最も近いノードに到達するまで、知識はより大きくなります。

于 2014-09-10T02:24:08.047 に答える