SR-Tree (Sphere/Rectangle-Tree)

• 概要
• 発表文献
• ライブラリ <2010/03/09>
• ビデオ <1998/11/18>
• オンラインデモ
• 関連研究

概要

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)

ライブラリ

• SR-Tree ライブラリ version 2.0 beta 6 (README, User's Guide) <2010/03/09>

  HnSRTree-2.0beta6.tar.gz (314K bytes) for Solaris and Linux.

  HnSRTree-2.0beta6.zip (458K bytes) for Windows XP.

  バージョン 1.3.1 との最も大きな相違点はソースコードを改良したことです。 冗長な部分や非効率な部分を改めることにより、実行時の CPU 時間が減少し ています。さらにいくつか機能を追加する計画ですが、バージョン 2.0 beta 6 の時点ではまだ準備段階となっています。

• SR-Tree ライブラリ version 1.3.1 (README)

  HnSRTree-1.3.1.tar.gz (168K bytes)

• R*-Tree ライブラリ (README)

  HnRStar-1.0.tar.gz (256K bytes)

ビデオ

• SR-Tree 紹介ビデオ <1998/11/18>

  	QuickTime Movie (3.5M bytes ) Java Applet (Emblaze Video) 低速回線用 (1.0M bytes) 高速回線用 (1.8M bytes)
  (上映時間 3分)

参考文献

[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.

関連研究

• The GiST Indexing Project. The GiST (Generalized Search Tree) is designed to provide software developers with a general foundation of indexing structures. An implementation of the SR-tree is contained in the GiST library version 2.0.

• Colossi, N.G. and Nascimento, M.A., Benchmarking Access Structures for High-Dimensional Multimedia Data. Proc. of the IEEE Intl. Conf. on Multimedia and Expo (ICME'2000), p. 1215-1218, New York, USA, Jul/2000. A technical report version of this paper is available at the author's site.

• The DBLP entry of the SR-tree paper. You can see a list of such papers that references the SR-tree paper.

研究活動のページへ戻る