SR-tree: An index structure for nearest-neighbor searching of high-dimensional point data
✍ Scribed by Norio Katayama; Shin'ichi Satoh
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 273 KB
- Volume
- 29
- Category
- Article
- ISSN
- 0882-1666
No coin nor oath required. For personal study only.
✦ Synopsis
Similarity search methods using feature vectors are employed widely for implementation of content-based retrieval of visual data, and appropriate index structures were explored to accelerate the search. Methods proposed hitherto have used the R * -tree and the SS-tree. This study offers a faster index structure namely, the SR-tree (sphere/rectangle-tree). The main feature of the proposed method is that both bounding spheres and bounding rectangles are used in combination. Bounding spheres and rectangles have been already employed in the SS-tree and the R * -tree, respectively. Experiments carried out as a part of the present study show, however, that as dimensionality grows high, both methods become problematic. Thus, when using bounding rectangles, the difference between the length of the edge of the rectangle and the diagonal becomes too large; with bounding spheres, the volume increases considerably as compared to rectangles. On the other hand, the SR-tree method uses both spheres and triangles, which ensures more efficient partitioning as compared to the SS-tree or R * -tree. Evaluation experiments proved that the proposed method outperforms both SS-tree and R * -tree in terms of CPU time and number of disk accesses.