US6678690B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Retrieving and ranking of documents from database description
Assignee: Google LLC
•
Filing: 2001-06-12
•
Granted: 2004-01-13
•
Expires: 2021-06-12
Abstract
Abstract A method, a computer system, and a program product for retrieving and/or ranking documents in a database. The method comprising steps of, providing a document matrix derived from the documents, the matrix including numerical elements derived from the attributes; providing a covariance matrix derived from the document matrix; executing singular value decomposition of the covariance matrix so as to obtain the following formula: K=V·Σ·V T , wherein K represents the covariance matrix, V represents the matrix consisting of eigenvectors, Σ represents a diagonal matrix, and V T represents a transpose of the matrix V; reducing a dimension of the matrix V using a predetermined number of eigenvectors included in the matrix V, the eigenvectors including an eigenvector corresponding to the largest singular value; reducing a dimension of the document matrix using the dimension reduced matrix V; and retrieving and/or ranking the documents in the database by computing the scalar product between the dimension reduced document matrix and a query vector.
Inventors
- 👤 Mei Kobayashi
- 👤 Loic Malassis
- 👤 Hikaru Samukawa
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:07
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/33; G06F16/3331; G06F16/334; G06F16/3347; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
200 words
A method for retrieving and/or ranking documents in a database, the documents including attribute data, said method comprising steps of: providing a document matrix from said documents, said matrix including numerical elements derived from said attribute data; providing a covariance matrix from said document matrix; executing singular value decomposition of said covariance matrix so as to obtain the following formula: K=V·Σ·V T , wherein K represents said covariance matrix, V represents the matrix consisting of eigenvectors, Σ represents a diagonal matrix, and V T represents a transpose of the matrix V; reducing a dimension of said matrix V using predetermined numbers of eigenvectors included in said matrix V, said eigenvectors including an eigenvector corresponding to the largest singular value; reducing a dimension of said document matrix using said dimension reduced matrix V; and retrieving and/or ranking said documents in said database by computing a scalar product between said dimension reduced document matrix and a query vector, wherein said covariance matrix is computed by the following formula: K=B−X bar ·X bar T , wherein K represents said covariance matrix, B represents a momentum matrix, X bar represents a mean vector and X bar T represents a transpose of said mean vector.
Claim 2
Independent Claim
200 words
A method for retrieving and/or ranking documents in a database, the documents including attribute data, said method comprising steps of: providing a document matrix from said documents, said matrix including numerical elements derived from said attribute data; providing a covariance matrix from said document matrix; executing singular value decomposition of said covariance matrix so as to obtain the following formula: K=V·Σ·V T , wherein K represents said covariance matrix, V represents the matrix consisting of eigenvectors, Σ represents a diagonal matrix, and V T represents a transpose of the matrix V; reducing a dimension of said matrix V using predetermined numbers of eigenvectors included in said matrix V, said eigenvectors including an eigenvector corresponding to the largest singular value; reducing a dimension of said document matrix using said dimension reduced matrix V; and retrieving and/or ranking said documents in said database by computing a scalar product between said dimension reduced document matrix and a query vector, wherein said covariance matrix is computed by the following formula: K=B−X bar ·X bar T , wherein K represents said covariance matrix, B represents a momentum matrix, X bar represents a mean vector and X bar T represents a transpose of said mean vector.
Claim 3
Dependent Claim
19 words
The method according to claim 1 , wherein said attributes include at least one keyword and/or a time stamp.
Claim 4
Dependent Claim
23 words
The method according to claim 1 , wherein said predetermined numbers are 15-25% of a total or the eigenvectors of said covariance matrix.
Claim 5
Dependent Claim
66 words
The method according to claim 1 , further comprising switching from dimension reduction using said document matrix directly to dimension reduction using said covariance matrix depending on a predetermined computation time, so that said dimension reduction, using said covariance matrix, is executed when said dimension reduction of said document matrix using eigenvectors thereof computed from said document matrix is not completed within said predetermined computation time.
Claim 6
Dependent Claim
14 words
The method according to claim 1 , further comprising adding documents to said database.
Claim 7
Dependent Claim
205 words
A computer system for executing a method for retrieving and/or ranking documents in a database, the documents including attribute data, said computer system having apparatus for: providing a document matrix from said documents, said matrix including numerical elements derived from said attribute data; providing a covariance matrix from said document matrix; executing singular value decomposition of said covariance matrix so as to obtain the following formula: K=V·Σ·V T , wherein K represents said covariance matrix, V represents the matrix consisting of eigenvectors, Σ represents a diagonal matrix, and V T represents a transpose of the matrix V; reducing a dimension of said matrix V using predetermined numbers of eigenvectors included in said matrix V, said eigenvectors including an eigenvector corresponding to the largest singular value; reducing a dimension of said document matrix using said dimension reduced matrix V; and retrieving and/or ranking said documents in said database by computing a scalar product between said dimension reduced document matrix and a query vector, wherein said covariance matrix is computed by the following formula: K=B−X bar ·X bar T wherein K represents said covariance matrix, B represents a momentum matrix, X bar represents a mean vector and X bar T represents a transpose of said mean vector.
Claim 8
Dependent Claim
205 words
A computer system for executing a method for retrieving and/or ranking documents in a database, the documents including attribute data, said computer system having apparatus for: providing a document matrix from said documents, said matrix including numerical elements derived from said attribute data; providing a covariance matrix from said document matrix; executing singular value decomposition of said covariance matrix so as to obtain the following formula: K=V·Σ·V T , wherein K represents said covariance matrix, V represents the matrix consisting of eigenvectors, Σ represents a diagonal matrix, and V T represents a transpose of the matrix V; reducing a dimension of said matrix V using predetermined numbers of eigenvectors included in said matrix V, said eigenvectors including an eigenvector corresponding to the largest singular value; reducing a dimension of said document matrix using said dimension reduced matrix V; and retrieving and/or ranking said documents in said database by computing a scalar product between said dimension reduced document matrix and a query vector, wherein said covariance matrix is computed by the following formula: K=B−X bar ·X bar T wherein K represents said covariance matrix, B represents a momentum matrix, X bar represents a mean vector and X bar T represents a transpose of said mean vector.
Claim 9
Dependent Claim
21 words
The computer system according to the claim 6 , wherein said attributes include at least one keyword and/or a time stamp.
Claim 10
Dependent Claim
24 words
The computer system according to claim 6 , wherein said predetermined numbers are 15-25% of a total of the eigenvectors of said covariance matrix.
Claim 11
Dependent Claim
69 words
The computer system according to claim 6 , further comprising apparatus for switching from dimension reduction using said document matrix directly to dimension reduction using said covariance matrix, depending on a predetermined computation time, so that saw dimension reduction, using said covariance matrix, is executed when said dimension reduction of said document matrix, using eigenvectors thereof computed from said document matrix, is not completed within said predetermined computation time.
Claim 12
Dependent Claim
16 words
The computer according to claim 6 , further comprising apparatus for adding documents to said database.
Claim 13
Dependent Claim
221 words
A program product including a computer readable computer program for executing a method for retrieving and/or ranking documents in a database, the documents including attribute data, said computer program including computer readable code for causing said apparatus to execute the steps of: providing a document matrix from said documents, said matrix including numerical elements derived from said attribute data; providing a covariance matrix from said document matrix; executing singular value decomposition of said covariance matrix so as to obtain the following formula: K=V·Σ·V T , wherein K represents said covariance matrix, V represents the matrix consisting of eigenvectors, Σ represents a diagonal matrix, and V T represents a transpose of the matrix V; reducing a dimension of said matrix V using predetermined numbers of eigenvectors included in said matrix V, said eigenvectors including an eigenvector corresponding to the largest singular value; reducing a dimension of said document matrix using said dimension reduced matrix V; and retrieving and/or ranking said documents in said database by computing a scalar product between said dimension reduced document matrix and a query vector, wherein said covariance matrix is computed by the following formula: K=B−X bar ·X bar T wherein K represents said covariance matrix, B represents a momentum matrix, X bar represents a mean vector and X bar T represents a transpose of said mean vector.
Claim 14
Dependent Claim
221 words
A program product including a computer readable computer program for executing a method for retrieving and/or ranking documents in a database, the documents including attribute data, said computer program including computer readable code for causing said apparatus to execute the steps of: providing a document matrix from said documents, said matrix including numerical elements derived from said attribute data; providing a covariance matrix from said document matrix; executing singular value decomposition of said covariance matrix so as to obtain the following formula: K=V·Σ·V T , wherein K represents said covariance matrix, V represents the matrix consisting of eigenvectors, Σ represents a diagonal matrix, and V T represents a transpose of the matrix V; reducing a dimension of said matrix V using predetermined numbers of eigenvectors included in said matrix V, said eigenvectors including an eigenvector corresponding to the largest singular value; reducing a dimension of said document matrix using said dimension reduced matrix V; and retrieving and/or ranking said documents in said database by computing a scalar product between said dimension reduced document matrix and a query vector, wherein said covariance matrix is computed by the following formula: K=B−X bar ·X bar T wherein K represents said covariance matrix, B represents a momentum matrix, X bar represents a mean vector and X bar T represents a transpose of said mean vector.
Claim 15
Dependent Claim
21 words
The program product according to the claim 11 , wherein said attributes include at least one keyword and/or a time stamp.
Claim 16
Dependent Claim
24 words
The program product according to claim 11 , wherein said predetermined numbers are 15-25% of a total of the eigenvectors of said covariance matrix.
Claim 17
Dependent Claim
94 words
The program product according to claim 11 , wherein said steps further comprise a switching step from dimension reduction using said document matrix directly to dimension reduction using said covariance matrix depending on a predetermined computation time, so that said dimension reduction, using said covariance matrix, is executed when said dimension reduction of said document matrix using eigenvectors thereof, computed from said document matrix, is not completed within said predetermined computation time. 15 .The program product according to claim 11 , further comprising computer code for accepting additional documents for addition to said database.
References Cited (Backward Citations)
US4839853A
Cited
US5583951A
Cited
US5794178A
Cited
US5842194A
Cited
US5805742A
Cited
US6345109B1
Cited
US6233495B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-01-12 | 2007-07-14 | 2008-01-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-01-12 | 2011-07-14 | 2012-01-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-01-12 | 2015-07-14 | 2016-01-13 | $7700.00 | Window Closed / Lapsed |