数学

HST(Hierarchically well Separated Tree)とは

少しググった感じ日本語の情報がなくて困ったので。

tree metric space とは

まず木\(T\)を考えます。普通の木です。それに対してある関数\(w\)を考えます。

$$ w : T  → R_{\geq 0} $$

ただし\(w\)には次の2つの条件があります。

  1. 全ての葉\(v\)について、\(w(v) = 0 \)
  2. 根を除く全ての頂点\(v\)について、\(w(v) < w(p(v)) \)

ここで\(p(v)\)は\(v\)の親頂点のことです。

ここで葉集合\(L\)に対して、距離関数 \(d(x, y) = w(lca(x, y)) \)とすると、\( (L, d) \)は距離空間をなっていることがわかります。ただし\(lca\)とはleast common ancestor、すなわち最も近い共通の祖先です。

この距離空間のことを tree metric space と言います。

a-HST(Hierarchically well Separated Tree with parameter a)とは

上で説明したtree metric treeにおける関数\(w\)の条件2番目が次のように変わったものをa-HSTと呼びます。ただし\( a > 1 \)です。

  • 根を除く全ての頂点\(v\)について、\( a * w(v) \leq w(p(v)) \)

つまりtree metric treeの条件をきつくしたものがa-HSTということです。

参考