論文はこちら．
- Skip Graphs
Skip Graphs
Skip graph は，skip list にもとづく分散データ構造である．
Chord などの DHT とは異なり，範囲探索などの複雑なクエリをサポートする．
形式的な定義
文字の有限集合をアルファベットといい，$\Sigma$ で記す．$w_0, w_1, w_2, \ldots \in \Sigma$ とすると，$\Sigma$ 上の語は $w = w_0 w_1 w_2 \ldots$ と書ける．語 $w$ の長さを $|w|$ と表記する．特に，$|w| = 0$ となる語 $w$ を $\varepsilon$ と書く．$|w| < \infty$ となる $w$ 全体からなる集合を $\Sigma^*$ とし，$|w| = \infty$ となる $w$ 全体からなる集合を $\Sigma^\omega$ とする．
要素 $x$ はいくつかの双方向連結リスト $S_w$ に属する．どの要素がどのリストに属するかはメンバシップベクタ $m(x) \in \Sigma^\omega$ によって決まる．双方向連結リスト $S_w$ は，$w$ が $m(x)$ の接頭語となるような要素 $x$ が昇順で並んだリストである．$S_\varepsilon$ はすべての要素 $x$ が昇順で並んだリストとなる．Skip graph は，双方向連結リストの族 $\mathfrak{S} = \left\{ S_w \right\}$ である．