US5930784A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of locating related items in a geometric space for data mining
Assignee: National Technology and Engineering Solutions of Sandia LLC
•
Filing: 1997-08-21
•
Granted: 1999-07-27
•
Expires: 2017-08-21
Abstract
Abstract A method for locating related items in a geometric space transforms relationships among items to geometric locations. The method locates items in the geometric space so that the distance between items corresponds to the degree of relatedness. The method facilitates communication of the structure of the relationships among the items. The method is especially beneficial for communicating databases with many items, and with non-regular relationship patterns. Examples of such databases include databases containing items such as scientific papers or patents, related by citations or keywords. A computer system adapted for practice of the present invention can include a processor, a storage subsystem, a display device, and computer software to direct the location and display of the entities. The method comprises assigning numeric values as a measure of similarity between each pairing of items. A matrix is constructed, based on the numeric values. The eigenvectors and eigenvalues of the matrix are determined. Each item is located in the geometric space at coordinates determined from the eigenvectors and eigenvalues. Proper construction of the matrix and proper determination of coordinates from eigenvectors can ensure that distance between items in the geometric space is representative of the numeric value measure of the items' similarity.
Inventors
- 👤 Bruce A. Hendrickson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 14:39
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/34; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
172 words
A method for locating a plurality of related items V(i) in a database, indexed from 1 to n, in a geometric space of dimension d, where the relationship between items is represented by a value S(i,j) for the relationship between item V(i) and item V(j), comprising: a) constructing a matrix A(i,j), where: i) A(i,j), for i≠j, is a first function of S(i,j); and ii) A(i,i) is chosen from the group consisting of: 0, and a second function of S(i,j, for j=1 to n); b) determining m eigenvectors of A, denoted by u 1 through u m , with corresponding eigenvalues, denoted by λ 1 through λ m ; c) selecting d of the eigenvectors, denoted by t 1 through t d , with corresponding eigenvalues denoted by λt 1 through λt d ; and d) locating each item at coordinates in the geometric space, where the coordinate along dimension i assigned to item with index k is given by t i (k) multiplied by a third function applied to λt 1 .
Claim 2
Independent Claim
172 words
A method for locating a plurality of related items V(i) in a database, indexed from 1 to n, in a geometric space of dimension d, where the relationship between items is represented by a value S(i,j) for the relationship between item V(i) and item V(j), comprising: a) constructing a matrix A(i,j), where: i) A(i,j), for i≠j, is a first function of S(i,j); and ii) A(i,i) is chosen from the group consisting of: 0, and a second function of S(i,j, for j=1 to n); b) determining m eigenvectors of A, denoted by u 1 through u m , with corresponding eigenvalues, denoted by λ 1 through λ m ; c) selecting d of the eigenvectors, denoted by t 1 through t d , with corresponding eigenvalues denoted by λt 1 through λt d ; and d) locating each item at coordinates in the geometric space, where the coordinate along dimension i assigned to item with index k is given by t i (k) multiplied by a third function applied to λt 1 .
Claim 3
Dependent Claim
28 words
The method of claim 1, wherein the first function of S(i,j) is -S(i,j), and wherein the second function of S(i,j) is the sum, for all j, of S(i,j).
Claim 4
Dependent Claim
20 words
The method of claim 1, wherein the third function is chosen from the group consisting of: f(x)=1, f(x)=x, f(x)=x.sup.1/2, f(x)=x.sup.2.
Claim 5
Dependent Claim
31 words
The method of claim 2, wherein the eigenvectors are selected by discarding the eigenvector corresponding to the least eigenvalue, and selecting the d eigenvectors corresponding to the d next least eigenvalues.
Claim 6
Dependent Claim
20 words
The method of claim 4, wherein the third function is chosen from the group consisting of: f(x)=1, f(x)=x, f(x)=x.sup.1/2, f(x)=x.sup.2.
Claim 7
Dependent Claim
28 words
The method of claim 1, wherein the first function of S(i,j) is S(i,j), and wherein the second function of S(i,j) is the sum, for all j, of -S(i,j).
Claim 8
Dependent Claim
190 words
A computer system adapted to locate a plurality of related items in a geometric space of dimension d, wherein the relationship between item i and item j is denoted S(i,j), comprising: a) a processor; b) a storage subsystem accessible from said processor; c) software means for accessing S(i,j) from said storage subsystem and for locating the items in the geometric space, comprising means for: i) constructing a matrix A, where: a) A(i,j), for i≠j, is a first function of S(i,j); and b) A(i,i) is chosen from the group consisting of: 0, and a second function of S(i,j, for j=1 to n); ii) determining m eigenvectors of A, denoted by u 1 through u m , with corresponding eigenvalues, denoted by λ 1 through λ m ; iii) selecting d of the eigenvectors, denoted by t 1 through t d , with corresponding eigenvalues denoted by λt 1 through λt d ; and iv) assigning to each item coordinates in the geometric space, where the coordinate along dimension i assigned to item with index k is given by t i (k) multiplied by a third function applied to λt i .
Claim 9
Dependent Claim
190 words
A computer system adapted to locate a plurality of related items in a geometric space of dimension d, wherein the relationship between item i and item j is denoted S(i,j), comprising: a) a processor; b) a storage subsystem accessible from said processor; c) software means for accessing S(i,j) from said storage subsystem and for locating the items in the geometric space, comprising means for: i) constructing a matrix A, where: a) A(i,j), for i≠j, is a first function of S(i,j); and b) A(i,i) is chosen from the group consisting of: 0, and a second function of S(i,j, for j=1 to n); ii) determining m eigenvectors of A, denoted by u 1 through u m , with corresponding eigenvalues, denoted by λ 1 through λ m ; iii) selecting d of the eigenvectors, denoted by t 1 through t d , with corresponding eigenvalues denoted by λt 1 through λt d ; and iv) assigning to each item coordinates in the geometric space, where the coordinate along dimension i assigned to item with index k is given by t i (k) multiplied by a third function applied to λt i .
Claim 10
Dependent Claim
28 words
The method of claim 7, wherein the first function of S(i,j) is -S(i,j), and wherein the second function of S(i,j) is the sum, for all j, of S(i,j).
Claim 11
Dependent Claim
20 words
The method of claim 7, wherein the third function is chosen from the group consisting of: f(x)=1, f(x)=x, f(x)=x.sup.1/2, f(x)=x.sup.2.
Claim 12
Dependent Claim
31 words
The method of claim 8, wherein the eigenvectors are selected by discarding the eigenvector corresponding to the least eigenvalue, and selecting the d eigenvectors corresponding to the d next least eigenvalues.
Claim 13
Dependent Claim
24 words
The method of claim 10, wherein the third function is chosen from the group consisting of: f(x)=1, f(x)=x, f(x)=x 1/2 , f(x)=x 2 .
Claim 14
Dependent Claim
28 words
The method of claim 7, wherein the first function of S(i,j) is S(i,j), and wherein the second function of S(i,j) is the sum, for all j, of -S(i,j).
Claim 15
Independent Claim
184 words
A method of using a computer to locate a plurality of related items V(i) in a database, indexed from 1 to n, in a geometric space of dimension d, where the relationship between items is represented by a value S(i,j) for the relationship between item V(i) and item V(j), comprising: a) constructing a matrix A(i,j), where: i) A(i,j), for i≠j, is a first function of S(i,j); and ii) A(i,i) is chosen from the group consisting of: 0, and a second function of S(i,j, for j=1 to n); b) using the computer to determine m eigenvectors of A, denoted by u 1 through u m , with corresponding eigenvalues, denoted by λ 1 through λ m ; c) using the computer to select d of the eigenvectors, denoted by t 1 through t d , with corresponding eigenvalues denoted by λt 1 through λt d ; and d) locating each item at coordinates in the geometric space, where the coordinate along dimension i assigned to item with index k is given by t i (k) multiplied by a third function applied to λt i .
Claim 16
Independent Claim
184 words
A method of using a computer to locate a plurality of related items V(i) in a database, indexed from 1 to n, in a geometric space of dimension d, where the relationship between items is represented by a value S(i,j) for the relationship between item V(i) and item V(j), comprising: a) constructing a matrix A(i,j), where: i) A(i,j), for i≠j, is a first function of S(i,j); and ii) A(i,i) is chosen from the group consisting of: 0, and a second function of S(i,j, for j=1 to n); b) using the computer to determine m eigenvectors of A, denoted by u 1 through u m , with corresponding eigenvalues, denoted by λ 1 through λ m ; c) using the computer to select d of the eigenvectors, denoted by t 1 through t d , with corresponding eigenvalues denoted by λt 1 through λt d ; and d) locating each item at coordinates in the geometric space, where the coordinate along dimension i assigned to item with index k is given by t i (k) multiplied by a third function applied to λt i .
Claim 17
Dependent Claim
37 words
The method of claim 13, wherein said items are chosen from the group consisting of: scientific articles, books, publications, patents, student records, customer records, Web pages, financial records, court decisions, company records, protein structures, and combinations thereof.
Claim 18
Independent Claim
181 words
A method of data mining, comprising locating a plurality of related items V(i) in a database, indexed from 1 to n, in a geometric space of dimension d, where the relationship between items is represented by a value S(i,j) for the relationship between item V(i) and item V(j), wherein locating the plurality of items comprises: a) constructing a matrix A(i,j), where: i) A(i,j), for i≠j, is a first function of S(i,j); and ii) A(i,i) is chosen from the group consisting of: 0, and a second function of S(i,j, for j=1 to n); b) determining m eigenvectors of A, denoted by u 1 through u m , with corresponding eigenvalues, denoted by λ 1 through λ m ; c) selecting d of the eigenvectors, denoted by t 1 through t d , with corresponding eigenvalues denoted by λt 1 through λt d ; and d) locating each item at coordinates in the geometric space, where the coordinate along dimension i assigned to item with index k is given by t i (k) multiplied by a third function applied to λt i .
Claim 19
Independent Claim
181 words
A method of data mining, comprising locating a plurality of related items V(i) in a database, indexed from 1 to n, in a geometric space of dimension d, where the relationship between items is represented by a value S(i,j) for the relationship between item V(i) and item V(j), wherein locating the plurality of items comprises: a) constructing a matrix A(i,j), where: i) A(i,j), for i≠j, is a first function of S(i,j); and ii) A(i,i) is chosen from the group consisting of: 0, and a second function of S(i,j, for j=1 to n); b) determining m eigenvectors of A, denoted by u 1 through u m , with corresponding eigenvalues, denoted by λ 1 through λ m ; c) selecting d of the eigenvectors, denoted by t 1 through t d , with corresponding eigenvalues denoted by λt 1 through λt d ; and d) locating each item at coordinates in the geometric space, where the coordinate along dimension i assigned to item with index k is given by t i (k) multiplied by a third function applied to λt i .
Claim 20
Dependent Claim
37 words
The method of claim 15, wherein said items are chosen from the group consisting of: scientific articles, books, publications, patents, student records, customer records, Web pages, financial records, court decisions, company records, protein structures, and combinations thereof.
Claim 21
Independent Claim
208 words
A method of enhancing human comprehension of a database, comprising locating a plurality of related items V(i) in a database, indexed from 1 to n, in a geometric space of dimension d, where the relationship between items is represented by a value S(i,j) for the relationship between item V(i) and item V(j), and presenting the items to a user according to the locations in the geometric space, wherein locating the plurality of items comprises: a) constructing a matrix A(i,j), where: i) A(i,j), for i≠j, is a first function of S(i,j); and ii) A(i,i) is chosen from the group consisting of: 0, and a second function of S(i,j, for j=1 to n); b) using the computer to determine m eigenvectors of A, denoted by u 1 through u m , with corresponding eigenvalues, denoted by λ 1 through λ m ; c) using the computer to select d of the eigenvectors, denoted by t 1 through t d , with corresponding eigenvalues denoted by λt 1 through λt d ; and d) locating each item at coordinates in the geometric space, where the coordinate along dimension i assigned to item with index k is given by t i (k) multiplied by a third function applied to λt i .
Claim 22
Independent Claim
208 words
A method of enhancing human comprehension of a database, comprising locating a plurality of related items V(i) in a database, indexed from 1 to n, in a geometric space of dimension d, where the relationship between items is represented by a value S(i,j) for the relationship between item V(i) and item V(j), and presenting the items to a user according to the locations in the geometric space, wherein locating the plurality of items comprises: a) constructing a matrix A(i,j), where: i) A(i,j), for i≠j, is a first function of S(i,j); and ii) A(i,i) is chosen from the group consisting of: 0, and a second function of S(i,j, for j=1 to n); b) using the computer to determine m eigenvectors of A, denoted by u 1 through u m , with corresponding eigenvalues, denoted by λ 1 through λ m ; c) using the computer to select d of the eigenvectors, denoted by t 1 through t d , with corresponding eigenvalues denoted by λt 1 through λt d ; and d) locating each item at coordinates in the geometric space, where the coordinate along dimension i assigned to item with index k is given by t i (k) multiplied by a third function applied to λt i .
Claim 23
Dependent Claim
37 words
The method of claim 17, wherein said items are chosen from the group consisting of: scientific articles, books, publications, patents, student records, customer records, Web pages, financial records, court decisions, company records, protein structures, and combinations thereof.
Claim 24
Independent Claim
212 words
A method of communicating relationships among items in a database to a user, comprising locating a plurality of related items V(i) in a database, indexed from 1 to n, in a geometric space of dimension d, where the relationship between items is represented by a value S(i,j) for the relationship between item V(i) and item V(j), and communicating the items to the user according to the locations in the geometric space, wherein locating the plurality of items comprises: a) constructing a matrix A(i,j), where: i) A(i,j), for i≠j, is a first function of S(i,j); and ii) A(i,i) is chosen from the group consisting of: 0, and a second function of S(i,j, for j=1 to n); b) using the computer to determine m eigenvectors of A, denoted by u 1 through u m , with corresponding eigenvalues, denoted by λ 1 through λ m ; c) using the computer to select d of the eigenvectors, denoted by t 1 through t d , with corresponding eigenvalues denoted by λt 1 through λt d ; and d) locating each item at coordinates in the geometric space, where the coordinate along dimension i assigned to item with index k is given by t i (k) multiplied by a third function applied to λt i .
Claim 25
Independent Claim
212 words
A method of communicating relationships among items in a database to a user, comprising locating a plurality of related items V(i) in a database, indexed from 1 to n, in a geometric space of dimension d, where the relationship between items is represented by a value S(i,j) for the relationship between item V(i) and item V(j), and communicating the items to the user according to the locations in the geometric space, wherein locating the plurality of items comprises: a) constructing a matrix A(i,j), where: i) A(i,j), for i≠j, is a first function of S(i,j); and ii) A(i,i) is chosen from the group consisting of: 0, and a second function of S(i,j, for j=1 to n); b) using the computer to determine m eigenvectors of A, denoted by u 1 through u m , with corresponding eigenvalues, denoted by λ 1 through λ m ; c) using the computer to select d of the eigenvectors, denoted by t 1 through t d , with corresponding eigenvalues denoted by λt 1 through λt d ; and d) locating each item at coordinates in the geometric space, where the coordinate along dimension i assigned to item with index k is given by t i (k) multiplied by a third function applied to λt i .
Claim 26
Dependent Claim
37 words
The method of claim 19, wherein said items are chosen from the group consisting of: scientific articles, books, publications, patents, student records, customer records, Web pages, financial records, court decisions, company records, protein structures, and combinations thereof.
References Cited (Backward Citations)
EP0202686A2
Cited
US5047842A
Cited
US5446681A
Cited
US5121337A
Cited
US5546472A
Cited
US5619709A
Cited
US5623679A
Cited
US5623681A
Cited
US5751612A
Cited
US5819258A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-07-26 | 2003-01-25 | 2003-07-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-07-26 | 2007-01-25 | 2007-07-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-07-26 | 2011-01-25 | 2011-07-27 | $7700.00 | Window Closed / Lapsed |