The SR-Tree (Sphere/Rectangle-Tree)

• Description
• Publications
• Softwares <09-Mar-2010>
• Online Demonstration
• Related Works

Description

1. What is the SR-tree?

   The SR-tree is an index structure for high-dimensional nearest neighbor queries.

2. What is the typical use of the SR-tree?

   One of the typical applications of the SR-tree is the similarity queries on feature vectors which is widely used for performing content-based retrieval of images [FSN+95, WKS+96].

   

3. What is the advantange of the SR-tree?

   The SR-tree is an extension of the R*-tree [BKS+90] and the SS-tree [WJ96]. The distinctive feature of the SR-tree is the combined utilization of bounding spheres and bounding rectangles. This improves the performance on nearest neighbor queries by reducing both the volume and the diameter of regions compared with the R*-tree and the SS-tree. According to our performance tests, the SR-tree outperforms the R*-tree and the SS-tree especially for high-dimensional and non-uniform data which are likely to appear in the actual image / video applications.

   

4. What does ``SR'' stands for?

   The ``SR-tree'' stands for the ``Sphere/Rectangle-tree''. Regrettably, after the publication of the SR-tree, we found that this name is already used in the database literature, e.g., ``Single Rotation tree'' [HW82] and ``Segment R-tree'' [KS91]. Please, do not confuse our ``Sphere/Rectangle-tree'' with these predecessors.

Publications

• 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)

• Norio Katayama and Shin'ichi Satoh, ``Application of Multidimensional Indexing Methods toward Massive Processing of Multimedia Information,'' The Transactions of the Institute of Electronics, Information and Communication Engineers D-II, vol. J82-D-II, no. 10 (Oct. 1999) pp. 1606-1616.
  (The original manuscript is written in Japanese. An English translation of the paper is available in ``Systems and Computers in Japan'' (John Wiley & Sons, Inc.), vol. 31, no. 13 (Nov. 2000) pp.31-41.)

Softwares

• SR-Tree Library version 2.0 beta 6 (README, User's Guide) <09-Mar-2010>

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

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

  The most significant difference between version 1.3.1 and 2.0 is the source code refinement reducing CPU time. The source code is reviewed and optimized in order to eliminate redundant or inefficient implementation. In addition, some features are planned to be added in version 2.0; however they are in preparation as of version 2.0 beta 6.

• SR-Tree Library version 1.3.1 (README)

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

• R*-Tree Library (README)

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

References

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

Related Works

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

Back to the Research Activities