Content-based similarity search over peer-to-peer systemsにある多次元空間から1次元空間へのマッピング

元ネタは
Ozgur D. Sahin, Fatih Emekc ̧i, Divyakant Agrawal, and Amr El Abbadi. Content-based similarity search over peer-to-peer systems. In DBISP2P, 2004.

定義1

ある $n$ 次元の点 $p_1$ と $p_2$ が存在したとする．このとき，この2点間の距離は
$d(p_1, p_2)$
と表される．

定義2

全てのノードは，集合
$R = \{r_0, r_1, \dots, r_{m-1}\}$
を知っている．

ただし，
$(r_i | 0 \le i < m) \in \mathbb{R}^n$
である．

1次元空間への写像

ある点 $v \in \mathbb{R}^n$ があったとき，
$R$ に含まれる全ての点と $v$ との距離を計算し，
$L = \{r_{k_0}, r_{k_1}, \dots, r_{k_{m-1}} \}$
となる， $L$ を求める．

ただし，
$d(v, r_{k_i}) \le d(v, r_{k_j}) | i < j, 0 \le i < m, 0 \le j < m$
である．

$v$ に近い上位j個の $k_0, k_1, \dots, k_{j-1}$ のビット連結を1次元の値とする．
すなわち，ビット連結を||で表すと， $j = 2$ のとき，
$k_0 || k_1$
が $v$ の1次元空間上への写像先となる．

例

ある点 $v$ があり，
$R = \{r_0, r_1, r_2, r_3, r_4, r_5, r_6, r_7 \}$
$L = \{r_6, r_4, r_0, r_5, r_2, r_1, r_3, r_7 \}$
となったとする．

ここでは，定義どおり，
$d(v, r_6) \le d(v, r_4) \le d(v, r_0) \le d(v, r_5) \le \dots \le d(v, r_7)$
となっている．

いま， $j = 2$ とすると，
$6 || 4$
が写像先となる．
ただし，10ビット空間に写像する場合は，
$6 || 4 || 0 = 110\; 100\; 0000$
となる．

つまり，6や4のインデクスは3ビットずつで表されるので，
3ビット || 3ビット || 0000
が写像先の値となる．

$v$ と近い位置にある $v'$ はやはり， $r_6, r_4$ と近いと考えられるため，写像先が同じになる可能性が高い．
しかし，
$d(v', r_6) \le d(v', r_0) \le d(v', r_4)$
や
$d(v', r_4) \le d(v', r_0) \le d(v', r_6)$
などとなる場合も考えられ，これらについても検出したい場合は，実用的に，
$(r_6, r_4) \rightarrow 110\; 100\; 0000$
$(r_6, r_0) \rightarrow 110\; 000\; 0000$
$(r_4, r_0) \rightarrow 100\; 000\; 0000$
が $v$ の写像先として選ばれる．