The SS+ tree: An improved index structure for similarity searches in a high-dimensional feature spaces
Ruth Kurniawati,
Jesse Jin,
John Shepherd
SPIE Conference on Storage and Retrieval for Image and Video Databases V,
San Jose, California, February 1997.
(Compressed Postscript ... 401KB)
In this paper, we describe the SS+-tree, a tree structure for
supporting similarity searches in a high-dimensional Euclidean space.
Compared to the SS-tree, the tree uses a tighter bounding sphere for
each node which is an approximation to the smallest enclosing sphere
and it also makes a better use of the clustering property of the available
data by using a variant of the $k$-means clustering algorithm as the split
heuristic for its nodes. A local reorganization rule is also introduced
during the tree building to reduce the overlapping between the nodes'
bounding spheres.
Keys:
High-dimensional indexing and retrieval,
Similarity search,
Multimedia databases,
Enclosing spheres,
Enclosing boxes (MBR)
Recent Publications ...
John Shepherd ...
CSE ...
UNSW