Method and apparatus for efficient indexed storage for unstructured content

• US 8,032,476 B2
• Filed: 04/24/2011
• Issued: 10/04/2011
• Est. Priority Date: 02/24/2005
• Status: Active Grant

• Current Assignee: Nahava, Inc.
• Original Assignee: Nahava, Inc.
• Inventors: Nakano, Russell Toshio
• Primary Examiner(s): Gaffin; Jeffrey A
• Assistant Examiner(s): Wong; Lut
• Application Number:
  US13/092,965
• Publication Number:
  US 20110202540A1
• Time in Patent Office: 163 Days
• Field of Search: 706/48, 707/603, 707/999.1
• US Class Current: 706/48
• 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 for transforming unstructured content and determining a split value for indexed storage, the method 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, said each vector x.i (i=1, . . . , n) contained in said node N representing said unstructured content;

(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 a deviation 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).

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

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