In order to accelerate the similarity search in highdimensional
database, we propose a new hierarchical indexing
method. It is composed of offline and online phases. Our contribution
concerns both phases. In the offline phase, after gathering the whole
of the data in clusters and constructing a hierarchical index, the main
originality of our contribution consists to develop a method to
construct bounding forms of clusters to avoid overlapping. For the
online phase, our idea improves considerably performances of
similarity search. However, for this second phase, we have also
developed an adapted search algorithm.
Our method baptized NOHIS (Non-Overlapping Hierarchical
Index Structure) use the Principal Direction Divisive Partitioning
(PDDP) as algorithm of clustering. The principle of the PDDP is to
divide data recursively into two sub-clusters; division is done by
using the hyper-plane orthogonal to the principal direction derived
from the covariance matrix and passing through the centroid of the
cluster to divide. Data of each two sub-clusters obtained are including
by a minimum bounding rectangle (MBR). The two MBRs are
directed according to the principal direction. Consequently, the nonoverlapping
between the two forms is assured.
Experiments use databases containing image descriptors. Results
show that the proposed method outperforms sequential scan and SRtree
in processing k-nearest neighbors.