Method and Apparatus for Efficient Indexed Storage for Unstructured Content

Abstract

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

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.