Method and apparatus for categorizing and presenting documents of a distributed database

• US 7,231,395 B2
• Filed: 05/24/2002
• Issued: 06/12/2007
• Est. Priority Date: 05/24/2002
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Overture Services Incorporated (Apollo Global Management, Inc.)
• Inventors: Savich, Peter, Ryan, Paul T., Fain, Daniel C.
• Primary Examiner(s): WOO, ISAAC M
• Application Number:
  US10/155,290
• Publication Number:
  US 20030220912A1
• Time in Patent Office: 1,845 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 715513-516
• US Class Current: 1/1
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9558 Details of hyperlinks; Management of linked annotations
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

Described herein are methods for creating categorized documents, categorizing documents in a distributed database and categorizing Resulting Pages. Also described herein is an apparatus for searching a distributed database. The method for creating categorized documents generally comprises: initially assuming all documents are of type 1; filtering out all type 2 documents and placing them in a first category; filtering out all type 3 documents and placing them in a second category; and defining all remaining documents as type 4 documents and placing all type 4 documents in a third category. The apparatus for searching a distributed database generally comprises at least one memory device; a computing apparatus; an indexer; a transactional score generator; and a category assignor; a search server; and a user interface in communication with the search server.

Claims

1. A computer-implemented method for categorizing Resulting Pages into categories, comprising:

designating a first category as commercial pages and a second category as informational pages;

determining a quality score q(wi) for each Resulting Page;

determining a transactional rating τ

(w_i)for each Resulting Page,

deriving a propagation matrix P;

determining a commercial score κ

for each Resulting Page;

filtering out all Resulting Pages that meet or exceed a commercial score threshold value;

wherein the Resulting Pages that meet or exceed the commercial page threshold value are placed in the first category and all remaining Resulting Pages are placed in the second category,

wherein the determining the transactional rating τ

(w_i) comprises

determining whether each Resulting Page meets select criteria,

determining how strongly each Resulting Page meets the select criteria,

determining a transactional score for each page, and

determining the transactional rating for each page from the transactional score, and

wherein determining a transactional score for each page comprises creating a vector for each Resulting Page α

k(w_i), wherein each vector contains a plurality of elements α

k_n(w_i), wherein each of the plurality of elements α

k_n(w_i) is a Boolean value that reflects how strongly each of the Resulting Pages meets each of the select criteria.

2. A computer-implemented method for categorizing Resulting Pages into categories, comprising:

designating a first category as commercial pages and a second category as informational pages;

determining a quality score q(wi) for each Resulting Page;

determining a transactional rating τ

(w_i) for each Resulting Page,

deriving a propagation matrix P;

determining a commercial score κ

for each Resulting Page;

filtering out all Resulting Pages that meet or exceed a commercial score threshold value;

wherein the Resulting Pages that meet or exceed the commercial page threshold value are placed in the first category and all remaining Resulting Pages are placed in the second category,

wherein the determining the transactional rating τ

(w_i) comprises

determining whether each Resulting Page meets select criteria,

determining how strongly each Resulting Page meets the select criteria,

determining a transactional score for each page, and

determining the transactional rating for each page from the transactional score, and

wherein determining a transactional score for each page comprises creating a vector for each Resulting Page β

k(w_i), wherein each vector contains a plurality of elements β

k_n(w_i), wherein each of the plurality of elements β

k_n(w_i) is a weighted value that reflects how strongly each of the Resulting Pages meets each of the select criteria.

3. A computer-implemented method for categorizing Resulting Pages into categories, comprising:

designating a first category as commercial pages and a second category as informational pages;

determining a quality score q(wi) for each Resulting Page;

determining a transactional rating τ

(w_i) for each Resulting Page,

deriving a propagation matrix P;

determining a commercial score κ

for each Resulting Page;

filtering out all Resulting Pages that meet or exceed a commercial score threshold value;

wherein the Resulting Pages that meet or exceed the commercial page threshold value are placed in the first category and all remaining Resulting Pages are placed in the second category,

wherein the determining the transactional rating τ

(w_i) comprises

determining whether each Resulting Page meets select criteria,

determining how strongly each Resulting Page meets the select criteria,

determining a transactional score for each page, and

determining the transactional rating for each page from the transactional score, and

wherein determining the transactional rating τ

(w_i) for each page from the transactional score comprises evaluating a relationship between the transactional rating τ

(w_i), and a p-norm of a vector for each Resulting Page α

k(w_i) wherein the relationship is defined by

4. A computer-implemented method for categorizing Resulting Pages into categories, as claimed in claim 3 wherein ρ

=2.

5. A computer-implemented method for categorizing Resulting Pages into categories, comprising:

designating a first category as commercial pages and a second category as informational pages;

determining a quality score q(wi) for each Resulting Page;

determining a transactional rating τ

(w_i) for each Resulting Page,

deriving a propagation matrix P;

determining a commercial score κ

for each Resulting Page;

filtering out all Resulting Pages that meet or exceed a commercial score threshold value;

wherein the Resulting Pages that meet or exceed the commercial page threshold value are placed in the first category and all remaining Resulting Pages are placed in the second category,

wherein the determining the transactional rating τ

(w_i) comprises

determining whether each Resulting Page meets select criteria,

determining how strongly each Resulting Page meets the select criteria,

determining a transactional score for each page, and

determining the transactional rating for each page from the transactional score, and

wherein determining the transactional rating τ

(w_i) for each page from the transactional score comprises evaluating a relationship between the transactional rating τ

(w_i) and a p-norm of a vector for each Resulting Page β

k(w_i) wherein the relationship is defined by

6. A computer-implemented method for categorizing Resulting Pages into categories, as claimed in claim 5 wherein ρ

=2.

7. A computer-implemented method for categorizing Resulting Pages into categories, comprising:

designating a first category as commercial pages and a second category as informational pages;

determining a quality score q(wi) for each Resulting Page;

determining a transactional rating for each Resulting Page τ

(w_i);

deriving a propagation matrix;

P

determining a commercial score κ

for each Resulting Page;

filtering out all Resulting Pages that meet or exceed a commercial score threshold value;

wherein the Resulting Pages that meet or exceed the commercial page threshold value are placed in the first category and all remaining Resulting Pages are placed in the second category

wherein deriving a propagation matrix, comprises;

creating a hyperlink connectivity matrix C containing elements Ci,j;

calculating a plurality of authority scores ai and a plurality of hub scores hi;

calculating a plurality of transition counts Ti,j and a plurality of pageviews vi for each Resulting Page; and

creating the propagation matrix P containing propagation matix elements Pi,j.

8. A computer-implemented method for categorizing Resulting Pages into categories, as claimed in claim 7, wherein creating a hyperlink connectivity matrix C comprises:

representing a link structure of the Internet in a matrix.

9. A computer-implemented method for categorizing Resulting Pages into categories, as claimed in claim 8, wherein the link structure if the Internet is represented by examining a number of links from each Resulting Page to each Resulting Page.

10. A computer-implemented method for categorizing Resulting Pages into categories, as claimed in claim 7, wherein the plurality of hub scores hi and the plurality of authority scores are related to the hyperlink connectivity matrix C and wherein the plurality of authority scores ai are defined as:

11. A computer-implemented method for categorizing Resulting Pages into categories, as claimed in claim 7, wherein the plurality of pageviews vi are related to the plurality of transition counts Ti,j and are defined by:

12. A computer-implemented method for categorizing Resulting Pages into categories, as claimed in claim 11, wherein the propagation matrix is a function of the hyperlink connectivity matrix, the plurality of hub scores, the plurality of authority scores, the plurality of transition counts and the plurality pageviews.

13. A computer-implemented method for categorizing Resulting Pages into categories, as claimed in claim 11, wherein calculating the propagation matrix further comprises weighting the plurality of hub scores, the plurality of authority scores, and the plurality pageviews.

14. A computer-implemented method for categorizing Resulting Pages into categories, as claimed in claim 11, wherein the propagation matrix P is a further function of weighing functions F(hi), G(ai) and H(vi), and wherein the propagation matrix P is defined as:

15. A computer-implemented method for categorizing Resulting Pages into categories, as claimed in claim 14, wherein each of the weighting functions comprises a step function.

16. A computer-implemented method for categorizing Resulting Pages into categories, as claimed in claim 15, wherein the commercial score κ

for each Resulting Page wi is determined recursively.

17. A computer-implemented method for categorizing Resulting Pages into categories, as claimed in claim 16, wherein the commercial score κ

is recursively determined over t iterations from a transverse of the propagation matrix P^T, a propagation matrix weight η

, and a commercial score initial value κ

′

(0), wherein κ

′

(0) is weighted by select quantities A and B and defined as;

18. A computer-implemented method for categorizing Resulting Pages into categories, comprising:

designating a first category as commercial pages and a second category as informational pages;

determining a quality score q(wi) for each Resulting Page;

determining a transactional rating for each Resulting Page τ

(w_i);

deriving a propagation matrix;

P

determining a commercial score κ

for each Resulting Page;

filtering out all Resulting Pages that meet or exceed a commercial score threshold value;

wherein the Resulting Pages that meet or exceed the commercial page threshold value are placed in the first category and all remaining Resulting Pages are placed in the second category, and

designating a third category as spam pages; and

determining a spam score σ

(wi) for each Resulting Page;

wherein determining the commercial score κ

for each Resulting Page is recursively determined over t iterations from a transverse of the propagation matrix P^T, propagation matrix weight η and

commercial score initial value κ

′

(0), wherein κ

′

(0) is weighted by select quantities A and B and defined as;