Method and apparatus for fast similarity-based query, self-join, and join for massive, high-dimension datasets

• US 7,644,090 B2
• Filed: 06/24/2007
• Issued: 01/05/2010
• Est. Priority Date: 06/27/2006
• Status: Active Grant

• Current Assignee: Nahava, Inc.
• Original Assignee: Nahava, Inc.
• Inventors: Cheng, Stanley, Nakano, Russell Toshio
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): Gortayo; Dangelino N
• Application Number:
  US11/767,521
• Publication Number:
  US 20070299865A1
• Time in Patent Office: 926 Days
• Field of Search: 707/1, 707/3, 707/100, 707/102, 707/200
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2264 Multidimensional index structures

Abstract

A method and apparatus for fast similarity-based query, self-join, and join for massive, high-dimension datasets have been disclosed.

Claims

1. A computer implemented method comprising:

(a) specifying a maximum of G items per leaf node;

(b) inputting n distinct input content items and denoting said n distinct input content items as a current collection;

(c) determining if n>

G; and

(d) if not then

(d1) building a leaf node;

(d2) filling said leaf node with said n distinct input content items; and

(d3) connecting a link from a parent to said leaf node capable of being stored in hardware on said computer and capable of being displayed to a user.

(e) if yes then

(e1) computing a vector sum over all items in said current collection, wherein said vector sum is denoted vsplit, and vsplit=sum(i;

x.i)/n, where i denotes an index (i=1, . . . , n) and x.i denotes a vector at index i;

(e2) computing a vector difference for each item in said current collection, wherein said vector difference is denoted as d.i, and d.i=x.i−

vsplit;

(e3) computing a scalar value for each item in said current collection, wherein said scalar value is denoted as p.i, and p.i=<

d.i, vsplit>

where <

.>

denotes inner product, and making a collection of said computed scalar value for each item;

(e4) determining if p.i<

3; and

(f) if not then

(f1) removing a largest p.i from said collection

(f2) removing a smallest p.i from said collection; and

(f3) resuming at (e3)

(g) if yes then

(g1) determining if 1 or 2 computed values remain in said collection; and

(h) if 1 then

(h1) letting p.split be said 1 computed remaining value; and

(h2) resuming at (j);

(i) if 2 then

(i1) letting p.split be an average of said 2 computed remaining values; and

(i2) resuming at (j);

(j) defining a splitter which consists of said vsplit and said p.split;

(k) denoting for each of said n distinct input content items in said current collection a designation of “

upper”

if p.i>

p.split, otherwise a designation of “

lower”

;

(l) building an interior node, consisting of said splitter, and defining links to said “

lower” and

said “

upper”

nodes;

(m) inputting said “

lower”

nodes as items into a new “

lower”

current collection, letting new “

lower”

n denote the number of items in said new “

lower”

current collection, replacing said current collection with said new “

lower”

current collection, replacing said n with said new “

lower”

n, and resuming at (c);

(n) inputting said “

upper”

nodes as items into a new “

upper”

current collection, letting new “

upper”

n denote the number of items in said new “

upper”

current collection replacing said current collection with said new “

upper”

current collection, replacing said n with said new “

upper”

n, and resuming at (c).

2. The computer implemented method of claim 1 further comprising:

(o) specifying a maximum cluster size of G;

(p) specifying a minimum cluster similarity of s;

(q) inputting n distinct content items;

(r) building a bulk similarity index for said n distinct content items, yielding a tree with leaf nodes of G or fewer content items per node;

(s) computing for each leaf node a pairwise similarity between items;

(t) determining if there is at least one pair of items with similarity exceeding s; and

(u) if no then

(u1) defining a “

oneoff”

cluster;

(u2) putting said items in said “

oneoff”

cluster; and

(u3) resuming at (w);

(v) if yes then

(v1) computing a highest pairwise similarity, and designating one item as a “

anchor”

of a cluster;

(v2) defining a “

good”

cluster;

(v3) placing into said “

good”

cluster each item in said current node if its similarity to said “

anchor”

exceeds s, otherwise designate any remaining items as “

residuals” and

collect them separately;

(w) determining if all leaf nodes have been processed; and

(x) if not then

(x1) resuming at (s);

(y) if so then

(z) determining if any “

residuals”

have been collected at this point; and

(aa) if not then

(aa1) storing in hardware on said computer any “

good”

cluster and any “

oneoff”

cluster, said stored any “

good”

cluster and said stored any “

oneoff”

cluster capable of being displayed to a user

(ab) if yes then

(ab1) gathering said “

residuals”

collected earlier; and

(ab2) resuming at (q).

3. The computer implemented method of claim 2 further comprising:

(ac) inputting datasets 1 and 2

(ad) inputting a similarity threshold of s*, where 0<

=s*<

=1;

(ae) inputting for each said datasets 1 and 2 a “

grouping”

size G.i, where =1 or 2;

(af) computing, based on datasets 1 and 2 size, an anticipated height of a tree denoted h, and h.i=ceiling(log 2(N.i/G.i)), where i=1 or 2, and N is number of items in dataset i;

(ag) building for datasets 1 and 2 a self-join tree using a similarity threshold, s.i=1−

[(1−

s*)/(2*h.i−

1], yielding a tree of good groups and oneoff groups;

(ah) designating a “

topmost”

set as an anchor of a root good group, together with members of said oneoff groups;

(ai) forming a dataset from said “

topmost”

set;

(aj) performing a self-join on said dataset, using said similarity threshold s*;

(ak) outputting from said self-join on said dataset “

good”

groups that have at least one member from dataset 1, and at least one member from dataset 2 denoting these a s*-join cluster, said s*-join cluster capable of being stored in hardware on said computer and capable of being displayed to a user.

4. The computer implemented method of claim 3 wherein said “

grouping”

size G.i is determined in advance.

5. The computer implemented method of claim 3 wherein said “

grouping”

size G.i minimizes overall computation time of building a similarity index.

6. A hardware based apparatus comprising:

(a) means for specifying a maximum of G items per leaf node;

(b) means for inputting n distinct input content items and denoting said n distinct input content items as a current collection;

(c) means for determining if n>

G; and

(d) if not then

(d1) means for building a leaf node;

(d2) means for filling said leaf node with said n distinct input content items; and

(d3) means for connecting a link from a parent to said leaf node capable of being stored in a memory and said memory capable of being displayed to a user.

(e) if yes then

(e1) means for computing a vector sum over all items in said current collection, wherein said vector sum is denoted vsplit, and vsplit=sum(i;

x.i)/n, where i denotes an index (i=1, . . . , n) and x.i denotes a vector at index i;

(e2) means for computing a vector difference for each item in said current collection, wherein said vector difference is denoted as d.i, and d.i=x.i−

vsplit;

(e3) means for computing a scalar value for each item in said current collection, wherein said scalar value is denoted as p.i, and p.i=<

d.i, vsplit>

where <

.>

denotes inner product, and making a collection of said computed scalar value for each item;

(e4) means for determining if p.i<

3; and

(f) if not then

(f1) means for removing a largest p.i from said collection

(f2) means for removing a smallest p.i from said collection; and

(f3) means for resuming at (e3)

(g) if yes then

(g1) means for determining if 1 or 2 computed values remain in said collection; and

(h) if 1 then

(h1) means for letting p.split be said 1 computed remaining value; and

(h2) means for resuming at (j);

(i) if 2 then

(i1) means for letting p.split be an average of said 2 computed remaining values; and

(i2) means for resuming at (j);

(j) means for defining a splitter which consists of said vsplit and said p.split;

(k) means for denoting for each of said n distinct input content items in said current collection a designation of “

upper”

if p.i>

p.split, otherwise a designation of “

lower”

;

(l) means for building an interior node, consisting of said splitter, and defining links to said “

lower” and

said “

upper”

nodes;

(m) means for inputting said “

lower”

nodes as items into a new “

lower”

current collection, letting new “

lower”

n denote the number of items in said new “

lower”

current collection, replacing said current collection with said new “

lower”

current collection, replacing said n with said new “

lower”

n, and resuming at (c);

(n) means for inputting said “

upper”

nodes as items into a new “

upper”

current collection, letting new “

upper”

n denote the number of items in said new “

upper”

current collection, replacing said current collection with said new “

upper”

current collection, replacing said n with said new “

upper”

n, and resuming at (c).

7. The hardware based apparatus of claim 6 further comprising:

(o) means for specifying a maximum cluster size of G;

(p) means for specifying a minimum cluster similarity of s;

(q) means for inputting n distinct content items;

(r) means for building a bulk similarity index for said n distinct content items, yielding a tree with leaf nodes of G or fewer content items per node;

(s) means for computing for each leaf node a pairwise similarity between items;

(t) means for determining if there is at least one pair of items with similarity exceeding s; and

(u) if no then

(u1) means for defining a “

oneoff”

cluster;

(u2) means for putting said items in said “

oneoff”

cluster; and

(u3) means for resuming at (w);

(v) if yes then

(v1) means for computing a highest pairwise similarity, and designating one item as a “

anchor”

of a cluster;

(v2) means for defining a “

good”

cluster;

(v3) means for placing into said “

good”

cluster each item in said current node if its similarity to said “

anchor”

exceeds s, otherwise designate any remaining items as “

residuals” and

collect them separately;

(w) means for determining if all leaf nodes have been processed; and

(x) if not then

(x1) means for resuming at (s);

(y) if so then

(z) means for determining if any “

residuals”

have been collected at this point; and

(aa) if not then

(aa1) means for storing in a memory any “

good”

cluster and any “

oneoff”

cluster, and said memory capable of being displayed to a user

(ab) if yes then

(ab1) means for gathering said “

residuals”

collected earlier; and

(ab2) means for resuming at (q).

8. The hardware based apparatus of claim 7 further comprising:

(ac) means for inputting datasets 1 and 2

(ad) means for inputting a similarity threshold of s*, where 0<

=s*<

=1;

(ae) means for inputting for each said datasets 1 and 2 a “

grouping”

size G.i, where i=1 or 2;

(af) means for computing, based on datasets 1 and 2 size, an anticipated height of a tree denoted h, and h.i=ceiling(log 2(N.i/G.i)), where i=1 or 2, and N is number of items in dataset i;

(ag) means for building for datasets 1 and 2 a self-join tree using a similarity threshold, s.i=1−

[(1−

s*)/(2*h.i−

1], yielding a tree of good groups and oneoff groups;

(ah) means for designating a “

topmost”

set as an anchor of a root good group, together with members of said oneoff groups;

(ai) means for forming a dataset from said “

topmost”

set;

(aj) means for performing a self-join on said dataset, using said similarity threshold s*;

(ak) means for outputting from said self-join on said dataset “

good”

groups that have at least one member from dataset 1, and at least one member from dataset 2 denoting these a s*-join cluster, said s*-join cluster capable of being stored in a memory, and said memory capable of being displayed to a user.

9. The hardware based apparatus of claim 8 wherein said “

grouping”

size G.i is determined in advance.

10. The hardware based apparatus of claim 8 wherein said “

grouping”

size G.i minimizes overall computation time of building a similarity index.