Granted Patent B2

US 10,162,878 · App. 14/718,804 · Granted Dec 25, 2018

Inventors: Stephen Nuchia (Tulsa, OK); Daniel Scott (Broken Arrow, OK)

Assignee: TIBCO Software Inc.

G06F17/30598

Abstract

Claims (117)

1. A computer implemented method for improving, using multi-dimensional indexing data structures, a process of finding nearest neighbors for points, in multi-dimensional spaces, associated with a manufacturing process, the computer comprising a processor and memory, the method comprising:

powering the computer;

in response to powering the computer, executing an initialization procedure for the computer, the initialization procedure comprising configuring the memory and initializing one or more device drivers for communicating with one or more devices;

providing a multi-dimensional indexing data structure in the memory, the multi-dimensional indexing data structure comprising at least one of an R-tree data structure or a KD-tree data structure;

projecting, using at least one processor associated with the multi-dimensional indexing data structure, an n-dimension space Θ, with a dissimilarity measure μ into an m-dimensional space P with a dissimilarity measure μ′ by a projection function p, wherein:

1<m<n; and

μ′( p ( v 1), p ( v 2))≤μ( v 1, v 2) for all points v 1 and v 2 in Θ;

selecting, using the at least one processor associated with the multi-dimensional indexing data structure, a point v in Θ;

performing, using the at least one processor associated with the multi-dimensional indexing data structure, a search in P for a set S′ of k nearest neighbors of the point p(v) in P;

finding, using the at least one processor associated with the multi-dimensional indexing data structure, a set S of all points in Θ that project to the set S′; and

determining, using the at least one processor associated with the multi-dimensional indexing data structure, whether a point of the set S is a nearest neighbor of the point v,

wherein determining whether the point of the set S is the nearest neighbor of the point v enables determination of a problem or an issue associated with the manufacturing process.

2. The computer implemented method of claim 1 , wherein 3≤m≤5, and wherein n≥1000.

3. The computer implemented method of claim 1 , wherein the projecting comprises:

selecting a principal component u of Θ using principal component analysis; and

projecting points v of Θ onto u.

4. The computer implemented method of claim 1 , wherein the projecting comprises:

selecting a set PC of principal components of Θ using principal component analysis, wherein the set PC contains principal components for 0≤s<n;

projecting Θ onto the principal components of the set PC;

determining an additional principal component u of Θ that captures the most remaining variance after removing the variance captured by projecting Θ onto the principal components of the set PC;

if u captures at least 1/m-s of the remaining variance, projecting points v of Θ onto u; and

otherwise:

selecting a j-dimensional space J contained in Θ, where j>1; and

projecting the points v onto their norm in the space J.

5. The computer implemented method of claim 1 , wherein:

the method further comprises indexing the space P using a spatial indexing technique suitable for finding the k-nearest neighbors of a point or cluster and suitable for performing a bounding-box search, both in spaces of a small fixed dimension; and

the performing comprises using the indexing to find the set S′.

6. The computer implemented method of claim 1 , further comprising:

selecting a cluster C in Θ;

performing a search in P for a set T′ of k nearest neighbors of a cluster p(C) in P;

finding a set T of all clusters in Θ that project to the set T′;

determining whether a cluster C′ of the set T is a nearest neighbor of the cluster C; and

if C′ is a nearest neighbor of the cluster C, merging C and C′ to form a cluster.

7. The computer implemented method of claim 6 , further comprising:

initially setting k to an integer within 1 of the square root of n;

for each cluster D of a plurality of clusters in Θ, searching for the nearest neighbor of D by:

finding the k-nearest neighbors of the cluster p(D) in P;

finding a set of clusters S″ in Θ based upon the k-nearest neighbors; and

searching for a nearest neighbor of D′ in S″; and

adjusting k based upon how often S″ contains a nearest neighbor of C′.

8. The computer implemented method of claim 6 , wherein:

determining whether the cluster C′ in S is a nearest neighbor of the cluster C comprises:

determining that no other cluster in T is closer to C than C′;

determining whether all clusters D in P for which μ′ (D, p(C))≤backed-out (μ(C′,C) are members of T′;

if so, returning C′ as a closest neighbor of C; and

if not, increasing the value of k to k′ and performing a search in P for a set T″ of k′ nearest neighbors of the cluster p(C) in P.

9. The computer implemented method of claim 6 , wherein:

determining whether the cluster C′ in S is a nearest neighbor of the cluster C comprises:

determining that no other cluster in T is closer to C than C′;

determining whether all clusters D in P for which μ′(D, p(C))≤backed-out (μ(C′,C) are members of T′;

if so, returning C′ as a closest neighbor of C; and if not:

performing a bounding-box search in P for a set U′ of all clusters D for which μ′(D, p(C))≤backed-out (μ(C′,C); and

finding a set U of clusters in Θ that project to the set U′; and

searching the set U for a nearest neighbor of the cluster C.

10. The computer implemented method of claim 6 , further comprising searching for mutual nearest neighbors by generating a chain of nearest neighbor clusters, wherein:

a first cluster of the chain is the cluster C;

each successor cluster in the chain is a nearest neighbor of an immediately previous cluster in the chain; and

a last cluster in the chain and a second-last cluster in the chain are mutual nearest neighbors.

11. The computer implemented method of claim 10 , further comprising:

merging the last cluster and the second-last cluster in the chain of nearest neighbors;

selecting a cluster of the chain other than the last cluster and the second-last cluster; and

generating another chain of nearest neighbor clusters, wherein the first cluster of the other chain is the selected cluster of the chain.

12. The computer implemented method of claim 10 , further comprising generating a plurality of chains of nearest neighbor clusters in parallel.

13. A computer implemented method for improving, using multi-dimensional indexing data structures, a process of finding nearest neighbors for points, in multi-dimensional spaces, associated with a manufacturing process, the computer comprising a processor and memory, the method comprising:

powering the computer;

in response to powering the computer, executing an initialization procedure for the computer, the initialization procedure comprising configuring the memory and initializing one or more device drivers for communicating with one or more devices;

providing a multi-dimensional indexing data structure in the memory;

projecting, using at least one processor associated with the multi-dimensional indexing data structure, an n-dimension space Θ with a dissimilarity measure μ into an m-dimensional space P with a dissimilarity measure μ′ by a projection function p, wherein:

1≤m<n;

(μ′( p ( v 1), p ( v 2))≤μ( v 1, v 2) for all points v 1 and v 2 in Θ; and

the projecting comprises:

selecting, using at least one processor associated with the multi-dimensional indexing data structure, a j-dimensional space J of Θ, where j>1; and

projecting, using at least one processor associated with the multi-dimensional indexing data structure, points v onto their norm in the space J; and

selecting, using at least one processor associated with the multi-dimensional indexing data structure, a point v in Θ;

performing, using at least one processor associated with the multi-dimensional indexing data structure, a search in P for a set ‘S’ of k nearest neighbors of the point p(v) in P;

finding, using at least one processor associated with the multi-dimensional indexing data structure, a set S of points in Θ that project to the set S′; and

determining, using at least one processor associated with the multi-dimensional indexing data structure, whether a point of the set S is a nearest neighbor of the point v,

wherein determining whether the point of the set S is the nearest neighbor of the point v enables determination of an issue associated with the manufacturing process.

14. The computer implemented method of claim 13 , wherein the projecting further comprises:

selecting a principal component u of Θ using principal component analysis; and

projecting points v of Θ onto u.

15. The computer implemented method of claim 13 , wherein the projecting further comprises:

selecting a set PC of principal components of Θ using principal component analysis, wherein the set PC contains principal components for 0≤s<n;

projecting Θ onto the principal components of the set PC;

determining a principal component u of Θ that captures the most remaining variance;

if u captures at least 1/m-s of the remaining variance, projecting points v of Θ onto u; and

otherwise projecting points v onto their norm in the space J.

16. A computer program product embodied in a non-transitory computer readable medium and comprising computer instructions for:

powering a computer;

in response to powering the computer, executing an initialization procedure for the computer, the initialization procedure comprising configuring a memory and initializing one or more device drivers for communicating with one or more devices;

providing a multi-dimensional indexing data structure in the memory, the multi-dimensional indexing data structure comprising at least one of an R-tree data structure or a KD-tree data structure;

projecting, using at least one processor associated with the multi-dimensional indexing data structure, an n-dimension space Θ, with a dissimilarity measure μ into an m-dimensional space P with a dissimilarity measure μ′ by a projection function p, wherein:

1<m<n; and

μ′( p ( v 1), p ( v 2))≤μ( v 1, v 2) for all points v 1 and v 2 in Θ;

selecting, using the at least one processor associated with the multi-dimensional indexing data structure, a point v in Θ;

performing, using the at least one processor associated with the multi-dimensional indexing data structure, a search in P for a set S′ of k nearest neighbors of the point p(v) in P;

finding, using the at least one processor associated with the multi-dimensional indexing data structure, a set S of all points in Θ that project to the set S′; and

determining, using the at least one processor associated with the multi-dimensional indexing data structure, whether a point of the set S is a nearest neighbor of the point v,

wherein determining whether the point of the set S is the nearest neighbor of the point v enables determination of a problem or an issue associated with the manufacturing process.

17. The computer program product of claim 16 , wherein the projecting comprises:

selecting a principal component u of Θ using principal component analysis; and

projecting points v of Θ onto u.

18. The computer program product of claim 16 , wherein the projecting comprises:

selecting a set PC of principal components of Θ using principal component analysis, wherein the set PC contains principal components for 0≤s<n;

projecting Θ onto the principal components of the set PC;

determining an additional principal component u of Θ that captures the most remaining variance after removing the variance captured by projecting Θ onto the principal components of the set PC;

if u captures at least 1/m-s of the remaining variance, projecting points v of Θ onto u; and

otherwise:

selecting a j-dimensional space J contained in Θ, where j>1; and

projecting the points v onto their norm in the space J.

19. The computer program product of claim 16 , further comprising computer instructions for indexing the space P using a spatial indexing technique suitable for finding the k-nearest neighbors of a point or cluster and suitable for performing a bounding-box search, both in spaces of a small fixed dimension; and the performing comprises using the indexing to find the set S′.

20. The computer program product of claim 16 , further comprising computer instructions for:

selecting a cluster C in Θ;

performing a search in P for a set T′ of k nearest neighbors of a cluster p(C) in P;

finding a set T of all clusters in Θ that project to the set T′;

determining whether a cluster C′ of the set T is a nearest neighbor of the cluster C; and

if C′ is a nearest neighbor of the cluster C, merging C and C′ to form a cluster.

Assignments (34)

Continuity (1)

Cited By (1)

US 12,436,981