Method of indexing and searching feature vector space

• US 6,745,205 B2
• Filed: 02/28/2001
• Issued: 06/01/2004
• Est. Priority Date: 11/15/2000
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd., Regents of the University of California (University of California)
• Original Assignee: Samsung Electronics Co. Ltd., Regents of the University of California (University of California)
• Inventors: Manjunath, B. S., Chandrasekaran, Shiv, Choi, Yang-lim, Huh, Youngsik
• Primary Examiner(s): Mizrahi, Diane D.
• Assistant Examiner(s): Wu, Yicun
• Application Number:
  US09/794,401
• Publication Number:
  US 20020085011A1
• Time in Patent Office: 1,189 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/100, 707/104.1, 707/200
• US Class Current: 1/1
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A method of indexing a high-dimensional vector space, along with a method of quickly retrieving a feature vector having features similar to a query vector from the vector space indexed by the indexing method, are provided. The method of indexing a feature vector space includes the steps of (a) partitioning the feature vector space into a plurality of approximation regions; (b) selecting an arbitrary approximation region to determine whether the selected approximation region is heavily or sparsely distributed; and (c) if the approximation region is determined to be sparsely distributed, indexing the corresponding approximation region as one special node belonging to a child node of the tree data structure, together with any other sparsely distributed approximation region spaced apart by a distance less than a predetermined distance.

Claims

1. A method of indexing a feature vector space using a tree data structure, the method comprising:

determining a distribution of feature vector elements in a first approximation region of the feature vector space; and

if the distribution of feature vector elements in the first approximation region is determined to be sparse, indexing the first approximation region, together with a second approximation region of the feature vector space, the second approximation region having a sparse distribution of feature vector elements, as one special node in the tree data structure,

wherein the first approximation region and the second approximation region are spaced apart by a distance less than a predetermined distance, and

wherein the special node is a child node in the tree data structure.

2. A method of retrieving a feature vector having features similar to a query vector from a vector space indexed by an indexing method using a tree structure including the step of indexing an approximation region in which feature vector elements are sparsely distributed, together with another sparsely distributed approximation region spaced apart by a distance less than a predetermined distance, as one special node belonging to a child node of the tree data structure, the retrieval method comprising the steps of:

(a) determining a special node to which the query vector belongs;

(b) setting the distance between an element of the query vector and an element in an approximation region corresponding to the determined special node, which is the closest to the element of the query vector, as a first threshold value; and

(c) excluding all child nodes of the corresponding node if the distance between the query vector and the approximation region indexed as an ordinary node is greater than or equal to the first threshold value.

3. The method of claim 2, prior to the step (c) further comprising the step of:

(c′

) selecting an arbitrary node among child nodes of a root node and determining whether the selected node is a special or ordinary node.

4. The method of claim 3, wherein the step (c) comprises the steps of:

(c-1) if the selected node is determined to be an ordinary node in the step (c′

), calculating the distance the distance d_or between the query vector q and the approximation region nor indexed as the ordinary node according to the following equation;

$d_{\mathrm{or}}=d<br><br>\left(q,n_{\mathrm{or}}\right)=\underset{i}{\sum <br><br>}<br><br>\{\begin{array}{c}|q_i-a_i<br><br>{|}^2<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{when}<br><br>\text{\hspace{1em}<br><br>}<br><br>q_i><br><br>a_i\\ 0<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{when}<br><br>\text{\hspace{1em}<br><br>}<br><br>a_i><br><br>q_i><br><br>b_i\\ |q_i-a_i<br><br>{|}^2<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{when}<br><br>\text{\hspace{1em}<br><br>}<br><br>b_i><br><br>q_i\end{array}$

(c-2) determining whether the distance d_or between the query vector q and the approximation region nor indexed as the ordinary node is less than the first threshold value;

(c-3) if the distance do, between the query vector q and the approximation region no, indexed as the ordinary node is less than the first threshold value, selecting child nodes of the corresponding node; and

(c-4) if the distance d_or between the query vector q and the approximation region no, indexed as the ordinary node is greater than or equal to than the first threshold value, excluding all child nodes of the corresponding node.

5. The method of claim 4, after the step (c-2), further comprising the step of updating the first threshold value with the distance d_or if the distance do, is less than the first threshold value.

6. The method of claim 3, after the step (c′

), further comprising the step of if the selected node is determined to be a special node in the step (c′

), converting a space of approximation region corresponding to the special node into a low-dimensional space.

7. The method of claim 4, after the step (c′

), further comprising the steps of;

(c-5) if the node selected in the step (c′

) is determined to be a special node, converting a space of approximation region corresponding to the node into a low-dimensional space;

(c-6) calculating the distance d_sp between the query vector q and each element v in the approximation region n_sp indexed as the special node according to the following equation;

$d_{\mathrm{sp}}=d<br><br>\left(q,n_{\mathrm{sp}}\right)=\underset{v\in <br><br>n_{\mathrm{sp}}}{\min }<br><br>\text{\hspace{1em}<br><br>}<br><br>d<br><br>\left(q,v\right);<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}$

(c-7) determining elements that satisfy the requirement of the distance d_sp being less than the first threshold value to be candidate elements.

8. The method of claim 7, after the step (c-7), further comprising the step of updating the first threshold value with the distance d_sp if an element satisfying the requirement of the distance d_sp being less than the first threshold value exists.

9. The method of claim 4, after the step (c-4), further comprising the steps of:

determining whether all special nodes have been searched;

selecting the next node to perform the steps after (c-1) repeatedly if all special nodes have not been searched;

determining a predetermined number of elements as finally found elements if all special nodes have been searched.