Method and Apparatus for Efficient Indexed Storage for Unstructured Content

• US 20100076981A1
• Filed: 11/30/2009
• Published: 03/25/2010
• Est. Priority Date: 02/24/2005
• Status: Abandoned Application

• Current Assignee: Nahava, Inc.
• Original Assignee: Nahava, Inc.
• Inventors: Nakano, Russell T.
• Application Number:
  US12/628,007
• Publication Number:
  US 20100076981A1
• Time in Patent Office: Days
• US Class Current: 707/741
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures

Abstract

A method and apparatus for efficient indexed storage for unstructured content have been disclosed.

Claims

1. A computer implemented method comprising:

(a) inputting a node N;

(b) inputting a query vector q;

(c) if said node N is a leaf node then;

(c1) computing a distance e.i=∥

q−

x.i∥

for each vector x.i (i=1, . . . , n) contained in said node N;

(c2) returning an element with a smallest distance e.i; and

(c3) outputting said element to a user;

(d) else;

(d1) obtaining a splitter S from said node N;

(d2) computing d=<

q−

S.avg, S.avg>

;

(e) if said d>

S.split then;

(e1) returning (N.upper, q);

(g) else;

(g1) returning (N.lower, q).

2. The method of claim 1 wherein said (e) is replaced by:

if said d>

=S.split then.

3. A computer readable storage medium having stored thereon instructions, which when executed performs the method of claim 1.

4. A system comprising a processor coupled to a memory, which when executing a set of instructions performs the method of claim 1.

5. A computer implemented method for efficient indexed storage for unstructured content comprising:

(a) inputting a node N;

(b) inputting a query vector q;

(c) inputting a distance h;

(d) if said N is a leaf node then;

(d1) computing a distance e.i=∥

q−

x.i∥

for each vector x.i (i=1, . . . , n) contained in node N;

(d2) returning all elements with a distance e.i<

h; and

(d3) outputting said elements to a user;

(e) else;

(e1) obtaining a splitter S from said node N;

(e2) computing d=<

q−

S.avg, S.avg>

;

(e3) computing distance from q to hyperplane=sqrt(|S.split−

d|);

(f) if said distance h>

sqrt(|S.split−

d|) then;

(f1) computing SearchFiniteNeighborhood (N.upper, q, h) by completing steps (a)-(g1) wherein N at (a) is N.upper;

(f2) computing SearchFiniteNeighborhood (N.lower, q, h) by completing steps (a)-(h1) wherein N at (a) is N.lower;

(f3) computing a union of results (e1) and (e2) and returning said union of results (e1) and (e2);

(g) else if said d>

S.split then;

(g1) returning results from SearchFiniteNeighborhood(N.upper, q, h);

(h) else;

(h1) returning results from SearchFiniteNeighborhood(N. lower, q, h).

6. A computer readable storage medium having stored thereon instructions, which when executed performs the method of claim 5.

7. A system comprising a processor coupled to a memory, which when executing a set of instructions performs the method of claim 5.

8. An apparatus for efficient indexed storage for unstructured content comprising:

means for using a plurality of inner products to build an indexed structure; and

means for finding a most similar item to one in said indexed structure.

9. The apparatus of claim 8 further comprising means for representing unstructured content data elements by vectors in said plurality of inner products.

10. The apparatus of claim 8 further comprising means for insertion and means for query wherein said means for insertion and said means for query are timing related proportionally to log(N) wherein N is a collection of N items in said indexed structure.

11. The apparatus of claim 8 further comprising means for determining a split value.

12. The apparatus of claim 11 further comprising means for using said split value in means for splitting said plurality of inner products into two groups.