Systems and methods for authoritativeness grading, estimation and sorting of documents in large heterogeneous document collections

• US 7,188,117 B2
• Filed: 09/03/2002
• Issued: 03/06/2007
• Est. Priority Date: 05/17/2002
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Farahat, Ayman O., Chen, Francine R., Mathis, Charles R., Nunberg, Geoffrey D.
• Primary Examiner(s): Pardo, Thuy N.
• Application Number:
  US10/232,709
• Publication Number:
  US 20030225750A1
• Time in Patent Office: 1,645 Days
• Field of Search: 707 1- 5, 707/104.1, 707/6, 707/10, 707/101, 707/102, 707/103.Y, 412/19
• US Class Current: 707/688
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• 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
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Systems and methods for determining the authoritativeness of a document based on textual, non-topical cues. The authoritativeness of a document is determined by evaluating a set of document content features contained within each document to determine a set of document content feature values, processing the set of document content feature values through a trained document textual authority model, and determining a textual authoritativeness value and/or textual authority class for each document evaluated using the predictive models included in the trained document textual authority model. Estimates of a document'"'"'s textual authoritativeness value and/or textual authority class can be used to re-rank documents previously retrieved by a search, to expand and improve document query searches, to provide a more complete and robust determination of a document'"'"'s authoritativeness, and to improve the aggregation of rank-ordered lists with numerically-ordered lists.

Claims

1. A method for re-ranking a set of relevant documents identified following a search, the method comprising:

determining a set of document content feature values for each relevant document identified;

generating a textual authoritativeness value and determining a textual authority class for each relevant document using a trained document textual authority model based on the determined set of document content feature values, the trained document textual authority model reclassifying the documents by assigning the document content feature values to a textual authority rank;

rearranging the set of relevant documents in an order selected based on the textual authority rank by using the generated textual authoritativeness value and the determined textual authority class for the documents to rearrange the set of relevant; and

displaying the rearranged set of relevant documents;

wherein the textual authoritativeness value is generated for each document using a document textual authority framework model that considers at least one of an author'"'"'s background, a targeted audience, an author'"'"'s institutional affiliation, or whether the document has been reviewed by others.

2. The method of claim 1, further comprising selecting a subset of relevant documents from the set of identified relevant documents prior to determining a set of document content feature values for each relevant document.

3. The method of claim 2, wherein selecting the subset of relevant documents comprises selecting a predetermined number of top-ordered documents as identified during the search.

4. The method of claim 1, wherein determining the set of document content feature values comprises determining the set of document content feature values using one or more parsing techniques or methods.

5. The method of claim 1, wherein generating the textual authoritativeness value for each relevant document comprises:

providing the set of document content feature values to the trained document textual authority model; and

processing the set of document content feature values using one or more metric-regression algorithms or methods.

6. The method of claim 1, wherein generating the textual authoritativeness value for each relevant document comprises:

providing the set of document content feature values to the trained document textual authority model; and

processing the set of document content feature values using one or more AdaBoost algorithm model or method.

7. A method for determining the authoritativeness of a document having a plurality of document content features, the method comprising:

selecting a predetermined number of top-ordered documents identified following a topic search of a large document collection;

evaluating a link structure of each top-ordered document;

determining a textual authority from a textual authoritativeness value and a textual authority class of each top-ordered document;

determining a weighted social authority rank for each top-ordered document based on the textual authority of each top-ordered document by associating a set of hyper-linked pages with a set of corresponding nodes using an adjacency matrix; and

displaying the weighted social authority ranked documents,

wherein the textual authoritativeness value is generated for each document using a document textual authority framework model that considers at least one of an author'"'"'s background, a targeted audience, an author'"'"'s institutional affiliation, and whether the document has been reviewed by others.

8. The method of claim 7, wherein evaluating the link structure of each top-ordered document comprises evaluating whether the document links or points to other documents in the document collection or whether the document is pointed to or linked to by other documents in the document collection.

9. The method of claim 7, wherein evaluating the link structure of each top-ordered document comprises:

determining whether the document in the set of top-ordered documents points to other documents in the set; and

setting the corresponding entry in the adjacency matrix to “

1”

if the document points to another document or to “

0”

if the document does not point to the another document.

10. The method of claim 7, wherein determining the textual authority of each top-ordered document comprises:

extracting a plurality of document content features from each top-ordered document;

determining a set of document content feature values for each top-ordered document; and

generating a textual authoritativeness value or determining a textual authority class for the document using a trained document textual authority model based on the determined set of document content feature values.

11. The method of claim 10, wherein determining the set of document content feature values comprises determining the set of document content features values using one or more parsing techniques or methods.

12. The method of claim 7, wherein determining the textual authority comprises using one or more of metric regression or boosted decision tree algorithms or methods.

13. The method of claim 7, wherein estimating a weighted social authority rank for each top-ordered document is performed by determining entries of eigenvectors of a matrix P, where:

P=α

U+ (1−

α

) M

where;

M is the adjacency matrix in which each row is normalized to a sum of “

1”

;

U is a transition matrix of uniform transition probability and represents a random transition to any page; and

α

[i][j] is set to the textual authority of a page i if the page i points to a page j, and is set to zero otherwise.

28. The method of claim 7, wherein determining a weighted social authority rank further includes:

defining an authority weight for a page of the each top-ordered document as a sum of hub weights of a plurality of adjacent pages;

defining a hub weight for the page as a sum of authority weights of the plurality of adjacent pages, the hub weight representing relative measuring of a hub, the hub being a specific page that points to high-authority pages;

combining the textual authority and the weighted social authority rank for the each top-ordered document by setting elements of the adjacency matrix to a normalized textual authority if a page i points to an adjacent page j and to “

0”

otherwise.

14. A method for expanding a search query based on a textual authoritativeness of a document, the method comprising:

identifying a first set of relevant documents using an initial set of query terms;

generating a textual authoritativeness value for each document of the first set of relevant documents;

identifying a second set of relevant documents from the first set of relevant documents based on the textual authoritativeness values generated for at least some of the first set of documents;

defining a candidate set of query expansion terms from the second set of relevant documents by evaluating and extracting at least one term most frequently present in the second set of relevant documents;

selecting at least one query expansion term from the candidate set of query expansion terms; and

displaying the at least one ciuerv expansion term;

wherein the textual authoritativeness value is generated for each document using a document textual authority framework model that considers at least one of an author'"'"'s background, a targeted audience, an author'"'"'s institutional affiliation, and whether the document has been reviewed by others.

15. The method of claim 14, wherein identifying a second set of relevant documents comprises selecting documents having textual authoritativeness values based on a user-determined textual authoritativeness value.

16. The method of claim 14, wherein selecting at least one query expansion term comprises extracting the at least one query expansion term from the candidate set of query expansion terms using at least one statistical test.

17. The method of claim 16, wherein the at least one statistical test comprises at least one of log likelihood ratio test, Fisher'"'"'s exact test and mutual information test.

18. The method of claim 14, wherein selecting at least one query expansion term from the candidate set of query expansion terms comprises:

estimating a first distribution for each query expansion term in the first set of relevant documents;

estimating a second distribution for each query expansion term in the second set of relevant documents;

applying a statistical test to each query expansion term in the candidate set of query expansion terms to compare the first and second distributions estimated for each query expansion term; and

selecting at least one query expansion term from the candidate set of query expansion terms based on values obtained from first and second distribution comparisons performed on the candidate set of query expansion terms.

19. The method of claim 14, wherein generating a textual authoritativeness value for each document identified in the first set of relevant documents comprises:

extracting a plurality of document content features from each document identified in the first set of relevant documents;

determining a set of document content feature values for each document identified in the first set of relevant documents; and

generating a textual authoritativeness value and a textual authority class for the document using a trained document textual authority model based on the determined set of document content feature values.

20. A method of combining at least two sets of rank orderings to produce an aggregate set ordering that is closest in some distance to each of the at least two sets of rank orderings, the method comprising:

determining first set rank ordering of relevant documents;

generating a textual authoritativeness value for each document in the first set rank ordering of relevant documents;

determining a second set rank ordering of relevant documents from the first set rank ordering based on the textual authoritativeness value generated for at least some of the first set of documents; and

combining the first set rank ordering of relevant documents and the second set rank ordering of relevant documents using a rank aggregation algorithm model or method based on a Markov chain, further including;

assigning a current state to a first page from the first set rank ordering,

selecting at least one second page uniformly chosen in an ordered list from at least one of the first set rank of ordering and the second set rank of ordering,

determining a first rank for the first page,

determining at least one second rank for the at least one second page in the ordered list,

reassigning the current state to the second page if the second page is ranked higher than the first page by the majority of the ordered lists, and

displaying the combined set of relevant documents,

wherein the textual authoritativeness value is generated for each document using a document textual authority framework model that considers at least one of an author'"'"'s background, a targeted audience, an author'"'"'s institutional affiliation, and whether the document has been reviewed by others.

21. The method of claim 20, wherein determining a textual authoritativeness for each document determined in the first set rank ordering of relevant documents comprises:

extracting a plurality of document content features from each document identified in the first set rank ordering of relevant documents;

determining a set of document content feature values for each document identified in the first set rank ordering of relevant documents; and

generating a textual authoritativeness value or determining a textual authority class for the document using a trained document textual authority model based on the determined set of document content feature values.

22. The method of claim 21, wherein determining a textual authoritativeness value or a textual authority class for each document determined in the first set rank ordering of relevant documents comprises processing the determined set of document content feature values using one or more of metric regression or boosted decision tree algorithms or methods.

23. The method of claim 21, wherein the plurality of document content features includes at least some of question marks, semicolons, numerals, words with learned prefixes, words with learned suffixes, words in certain grammatical locations, HTML features, abbreviations and classes of abbreviations, text characteristics features, speech tagging features and readability indices features.

29. The method of claim 20, wherein combining the first set rank ordering and the second set rank ordering further includes computing a state transition matrix that includes eigenvalues λ

_a>

λ

_b>

. . . λ

_k for a desired order of pages a, b, . . . , k.

24. A method for simultaneously estimating an aggregate rank and aggregate weights to be assigned to two or more ranked document lists or document rank orderings, the method comprising:

determining a first set rank ordering of relevant documents;

generating a textual authoritativeness value for each document in the first set rank ordering of relevant documents;

determining a second set rank ordering of relevant documents from the first set rank ordering based on the textual authoritativeness values generated for at least some of the first set of documents; and

combining the first set rank ordering of relevant documents and the second set rank ordering of relevant documents using a rank aggregation algorithm model or method based on a Markov chain, further including;

assigning a current state to a first page from the first set rank ordering,

selecting at least one second page uniformly chosen in an ordered list from at least one of the first set rank of ordering and the second set rank of ordering,

determining a first rank for the first page,

determining at least one second rank for the at least one second page in the ordered list, and

reassigning the current state to the second page if the second page is ranked higher than the first page by the majority of the ordered lists, and

displaying the combined set of relevant documents,

wherein the textual authoritativeness value is generated for each document using a document textual authority framework model that considers at least one of an author'"'"'s background, a targeted audience, an author'"'"'s institutional affiliation, and whether the document has been reviewed by others.

25. The method of claim 24, wherein generating a textual authoritativeness value for each document determined in the first set rank ordering of relevant documents comprises:

extracting a plurality of document content features from each document identified in the first set rank ordering of relevant documents;

determining a set of document content feature values for each document using one or more parsing processes or methods; and

generating a textual authoritativeness value by processing the determined set of document content feature values using one or more of metric regression or boosted decision tree algorithms.

26. The method of claim 24, wherein the plurality of document content features includes at least some of question marks, semicolons, numerals, words with learned prefixes, words with learned suffixes, words in certain grammatical locations, HTML features, abbreviations and classes of abbreviations, text characteristics features, speech tagging features and readability indices features.

27. The method of claim 24 further comprising determining a textual authority class for the document prior to determining a second set rank ordering of relevant documents.

30. The method of claim 24, wherein combining the first set rank ordering and the second set rank ordering further includes computing a state transition matrix that includes eigenvalues λ

_a>

λ

_b>

. . . λ

_k for a desired order of pages a, b, . . . , k.