SR-Tree (Sphere/Rectangle-Tree)

[ Japanese / English ]


お詫び
         2003年から2009年までの間、 SR-tree ライブラリをメンテナンスできない状態が続きました。 GCC 4 への対応などを約束しておきながら、 約束を反故にしてしまう非礼も少なからずありました。 この時期は、私の研究者キャリアにおける暗黒時代であり、 研究に割ける時間がほとんどありませんでした。
ご迷惑をおかけした皆様に、心よりお詫び申し上げます。


概要

  1. SR-Tree とは?

    SR-Tree は高次元点データに対する最近接検索を高速化するためのインデッ クス構造です。

  2. 用途は?

    特徴ベクトルに対する類似検索が代表例です。画像データに対する内容検索の 実現法として、特徴ベクトルを類似検索する方法が広く使われていますが [FSN+95,WKS+96]、そ の際に必要となる高次元空間での最近接検索を高速化できます。

  3. 特徴は?

    最近接検索の高速化法としては、R*-tree [BKS+90] を用いる方法や SS-tree [WJ96] を用いる方法が提案 されていますが、SR-tree はこれらよりも更に高速です。 SR-tree の特徴は、包囲球(bounding sphere)と包囲長方形(bounding rectangle)を併用する点にあります。これまで、包囲球は SS-tree で、包囲 長方形は R*-tree で使われていました。しかし、次元が高くなった場合、い ずれの方法にも問題点があり、包囲長方形を用いる方法では領域の径が長くな るという問題点が、包囲球を用いる方法では領域の体積が大きくなるという問 題点があります。そこで、SR-tree ではこれらを同時に使用することによって、 探索空間を径も体積も小さな領域に分割することを可能にしました。

  4. SR-Tree の``SR''とは?

    Sphere/Rectangle-tree を略したものです。論文発表の前には知らなかったの ですが、残念ながらこの略称はすでに使われた例がありました。1982年の Single Rotation Tree [HW82] や 1991年の Segment R-Tree [KS91] で使われています。


発表文献

  1. 片山紀生, 佐藤真一, 「SR-Tree: 高次元点データに対する最近接検索のためのインデックス構造の提案」, 電子情報通信学会論文誌 D-I, vol. J80-D-I, no. 8 (Aug. 1997) pp. 703-717.

  2. Norio Katayama and Shin'ichi Satoh, ``The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries,'' Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data (May 1997) pp. 369-380.
    (gzipped PostScript 100K bytes)

  3. 片山紀生,佐藤真一, 「マルチメディア情報の大規模処理に向けた多次元インデクシング手法の応用」, 第4回知能情報メディアシンポジウム論文集 (Dec. 1998) pp. 133-140.
    (gzipped PostScript 336K bytes)
    (PDF 189K bytes)

ライブラリ

C++ 言語で作成したライブラリを、フリーソフトウェアとして公開しています。 SR-Tree を実装したものと R*-Tree を実装したものがあります。いずれのラ イブラリも C 言語からでも呼び出せるよう C 言語用のインターフェイスも持っ ています。詳しくは、それぞれの README ファイルをご覧下さい。

ビデオ


参考文献

[HW82]
S.-H. S. Huang and C. K. Wong, ``Binary Search Trees with Local Rotation,'' Proc. 20th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, USA (1982) pp. 481-489.

[BKS+90]
N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger, ``The R*-tree: an Efficient and Robust Access Method for Points and Rectangles,'' Proc. ACM SIGMOD, Atlantic City, USA (May 1990) pp.322-331.

[KS91]
C. P. Kolovson and M. Stonebraker, ``Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data,'' Proc. ACM SIGMOD, Denver, Colorado, USA (May 1991) pp.138-147.

[FSN+95]
M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker, ``Query by image and video content: the QBIC system,'' IEEE Computer, vol.28, no.9 (Sep. 1995) pp. 23-32.

[WJ96]
D. A. White and R. Jain, ``Similarity Indexing with the SS-tree,'' Proc. of the 12th Int. Conf. on Data Engineering, New Orleans, USA (Feb. 1996) pp.516-523.

[WKS+96]
H. D. Wactlar, T. Kanade, M. A. Smith, and S. M. Stevens, ``Intelligent Access to Digital Video: Informedia Project,'' IEEE Computer, vol.29, no.5 (May 1996) pp. 46-52.

関連研究


研究活動のページへ戻る

Saturday, 22-Jan-2011 10:20:30 JST
katayama@nii.ac.jp