iDistanceを用いた多次元空間におけるK近傍法 - NO!と言えるようになりたい

元ネタは
H. V. Jagadish, Beng Chin Ooi, Kian-Lee Tan, Cui Yu, and Rui Zhang. iDistance: An adaptive B+-tree based indexing method for nearest neighbor search. ACM Trans. Database Syst., Vol. 30, No. 2, pp. 364–397, 2005.

iDistanceは多次元のデータを1次元空間に写像してK近傍探索を行う方法である．K近傍探索は，写像後の1次元データに対して範囲検索を行うことで可能となる．1次元データの範囲検索ということで，写像後の1次元データはB+木に格納される．また，1次元空間に写像するという特徴から，構造化P2Pなどにも応用されている．

iDistanceではまず，データ空間を $n$ 個のクラスタ $C_i | 0 \le i < n$ に分割し，各クラスタから代表点 $p_i$ を選出する． $d$ 次元のデータはクラスタの代表点からの距離に基づいて，1次元の値に写像される．いま，定数 $c$ が与えられたとすると，オブジェクト $x \in C_i$ のiDistance値は
$iDist(x) = d(p_i, x) + i \cdot c$
となる．ただし， $d(a, b)$ は $a$ と $b$ 間の距離とする．ここで， $c$ が十分に大きい場合は，クラスタ $C_i$ は区間 $[i \cdot c,\: (i + 1) \cdot c)$ へと写像される．iDistance値を鍵としてB+木にデータが追加される．

いま，クエリポイント $q$ から半径 $r$ 以内にあるすべてのデータを得たいとする．これは，
$d(q, p_i) - r \le r^{\mathrm{max}}_{i}$
を満たす代表点 $p_i$ について，
$[d(q, p_i) + i \cdot c - r,\: d(q, p_i) + i \cdot c + r]$
となるiDistance値の範囲にあるデータを検索することによって行うことが可能である．ただし， $r^{\mathrm{max}}_{i}$ は， $p_i$ から同一クラスタ内にある最も遠い距離にある点と $p_i$ との距離を示している．K近傍探索は，この範囲検索を繰り返し行うことで達成出来る．