US 2003/0149679 A1 · Optimal high-speed multi-resolution retrieval method on large capacity database

Abstract

Disclosed is an optimal high-speed multi-resolution retrieval method on a large capacity database capable of providing a retrieval speed sufficiently rapid to obtain a perfect retrieval accuracy, i.e., accuracy of 100%. The method provides an optimal high-speed retrieval algorithm for inducing an inequality capable of accurately determining effective clusters and ineffective clusters, and implementing an optimal high-speed information retrieval using the induced inequality, and an optimal high-speed retrieval algorithm for inducing an inequality based on a multi-resolution data structure for a high-speed processing, and implementing an optimal high-speed multi-resolution retrieval using the induced inequality. The method involves the steps of sorting all data contained in a database into a desired number of clusters each composed of data having similar features, deriving the lower bound of the distance between each cluster and a query, removing clusters having no possibility to be determined as best matches, searching, for best matches, data of clusters having the possibility to be determined as best matches, and inducing an inequality property based on a multi-resolution data structure for reducing unnecessary feature matching computation involved in a search procedure to reduce a large quantity of calculation.

Claims11

Dependent claims

An optimal high-speed multi-resolution retrieval method on a large capacity database comprising the steps of:

deriving the multi-resolution structure of a query “Q”;
setting an initial minimum distance “dmin” to have the infinite value.
setting respective values of “i” and “l” to be “1”.
deriving “dl(Xi, Q)”;
deriving “dL(Xl, Q)”;
and
selecting data having a final value of “dmin” as the best match.

4 more elements

An optimal high-speed multi-resolution retrieval method using a cluster-based multi-resolution search algorithm adapted to output a plurality of more-significant best matches, comprising the steps of:

performing a high-speed multi-resolution exhaustive search algorithm, thereby searching for a cluster “kmin” having a minimum distance “d′min”;
if n(Φkmin)≧M, searching for M more-significant best matches in accordance with an algorithm modified from the high-speed multi-resolution exhaustive search algorithm to search for the M more-significant best matches, and storing respective distance values of the searched more-significant best matches “dmin[.]”;
setting “k” to “1”, and if k=kmin, updating “k” with “k+1”;
if dlk(Ck, Q)−δk>dmin[0], removing the cluster “k”, and updating “k” with “k+1”;
updating “dmin[.]” while applying the modified high-speed multi-resolution exhaustive search algorithm to “Φk”, and updating “k” with “k+1”;
setting “k” to “1”, and if it is determined that the cluster “k” has been searched for, updating “k” with “k+1”;
if dlk(Ck, Q)−δk>dmin[M−1], removing the cluster “k”, and updating “k” with “k+1”;
updating “dmin[.]” while applying the modified high-speed multi-resolution exhaustive search algorithm to “Φk”, and updating “k” with “k+1”;
and
selecting M data corresponding to a final “dmin[.]” as best matches, respectively.

7 more elements

Dependencies are inferred from the claim text.

Optimal high-speed multi-resolution retrieval method on large capacity database

Life of this patent

Optimal high-speed multi-resolution retrieval method on large capacity database

Life of this patent

Abstract

Claims11