Using a Core Data Structure to Calculate Document Ranks

• US 20080016061A1
• Filed: 08/01/2006
• Published: 01/17/2008
• Est. Priority Date: 07/14/2006
• Status: Abandoned Application

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: BEA Systems Incorporated (Oracle Corporation)
• Inventors: Frieden, Kurt, Rudominer, Mitch
• Application Number:
  US11/461,568
• Publication Number:
  US 20080016061A1
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Ranks for documents can comprise calculating coefficients indicating connections between users and documents. The coefficients cam be stored as a part of a core data structure on disk for a sparse matrix. The coefficients can be used to calculate rank values for the documents. The using step can include, (a) for each row of the core data structure, reading a row of the core data structure into local memory, inflating the row, converting the row into a row of a damped matrix and multiplying the row of a damped matrix by a current vector to get a value of the next vector; (b) comparing the next vector to the current vector; if the difference is greater than an error value, set the next vector as the current vector and repeat step (a) if the difference is less than an error value, determine rank values from the next vector.

Claims

1. A computer-implemented method for operating on matrix comprising:

(a) for each row of a core data structure;

reading a row of the core data structure into local memory,

inflating the row,

converting the row into a row of a damped matrix,

multiplying the row of a damped matrix by a current vector to get a value of the next vector.

(b) comparing the next vector to the current vector, wherein

if the difference is greater than an error value, set the next vector as the current vector and repeat step (a);

if the difference is less than an error value, determine a result from the next vector.

2. The computer-implemented method of claim 1, wherein the damped matrix is column stocastic.

3. The computer-implemented method of claim 1, wherein the damped matrix is positive.

4. The computer-implemented method of claim 1, wherein the core data structure includes skip counts.

5. The computer-implemented method of claim 4, wherein the first byte of a skip count encodes a number of next zero values in a row if the number is less than a threshold or an indication of additional bytes that encode the number if the number is greater that a threshold.

6. The computer-implemented method of claim 1, wherein the result is search independent object rank value.

7. The computer-implemented method of creating ranks for documents comprising:

calculating coefficients indicating connections between users and documents;

storing the coefficients as a part of a core data structure on disk for a sparse matrix; and

using the coefficients to calculate rank values for the documents, the using step including

(a) for each row of the core data structure;

reading a row of the core data structure into local memory,

inflating the row,

converting the row into a row of a damped matrix,

multiplying the row of a damped matrix by a current vector to get a value of the next vector;

(b) comparing the next vector to the current vector, wherein

if the difference is greater than an error value, set the next vector as the current vector and repeat step (a);

if the difference is less than an error value, determine rank values from the next vector.

8. The computer-implemented method of claim 7, wherein the damped matrix is column stochastic.

9. The computer-implemented method of claim 7, wherein the damped matrix is positive.

10. The computer-implemented method of claim 7, wherein the core data structure includes skipcounts

11. The computer-implemented method of claim 10, wherein the first byte of a skip count encodes a number of next zero values in a row if the number is less than a threshold or an indication of additional bytes that encode the number if the number is greater than a threshold.

12. The computer-implemented method of claim 7, wherein additional coefficients indicate connections between tags and users and documents.

13. The computer-implemented method of claim 7, wherein connections between users and documents include an authorizing relationship.

14. The computer-implemented method of claim 7, wherein connections between documents and users include an access relationship.

15. The computer-implemented method of creating ranks for documents comprising:

calculating coefficients indicating connections between users, tags and documents; and

using the coefficients to calculate rank values for the documents, the using step including

(a) for each row of the core data structure;

reading a row of the core data structure into local memory,

inflating the row,

converting the row into a row of a damped matrix,

multiplying the row of a damped matrix by a current vector to get a value of the next vector;

(b) comparing the next vector to the current vector, wherein

if the difference is greater than an error value, set the next vector as the current vector and repeat step (a);

if the difference is less than an error value, determine rank values from the next vector.

16. The computer-implemented method of claim 15, wherein the damped matrix is column stochastic.

17. The computer-implemented method of claim 15, wherein the damped matrix is positive.

18. The computer-implemented method of claim 15, wherein the core data structure includes skipcounts

19. The computer-implemented method of claim 18, wherein the first byte of a skip count encodes a number of next zero values in a row if the number is less than a threshold or an indication of additional bytes that encode the number if the number is greater than a threshold.

20. The computer-implemented method of claim 15, wherein connections between users and documents include an authoring relationship.

21. The computer-implemented method of claim 15, wherein connections between documents and users include an access relationship.

22. A computer-implemented system comprising:

using document rank values to calculate a relevance of a document to a search; and

using the calculated relevance to display search results, wherein the document rank values are obtained by calculating coefficients indicating connections between users, tags and documents; and

using the coefficients to calculate rank values for the documents, the using step including

(a) for each row of the core data structure;

reading a row of the core data structure into local memory,

inflating the row,

converting the row into a row of a damped matrix,

multiplying the row of a damped matrix by a current vector to get a value of the next vector;

(b) comparing the next vector to the current vector, wherein

if the difference is greater than an error value, set the next vector as the current vector and repeat step (a);

if the difference is less than an error value, determine rank values from the next vector.

23. The computer-implemented method of claim 22, wherein the damped matrix is column stochastic.

24. The computer-implemented method of claim 22, wherein the damped matrix is positive.

25. The computer-implemented method of claim 22, wherein the core data structure includes skipcounts

26. The computer-implemented method of claim 25, wherein the first byte of a skip count encodes a number of next zero values in a row if the number is less than a threshold or an indication of additional bytes that encode the number if the number is greater than a threshold

27. The computer-implemented system of claim 22, wherein connections between users and documents include an authoring relationship.

28. The computer-implemented system of claim 22, wherein connections between documents and users include an access relationship.