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

• US 20030225750A1
• Filed: 09/03/2002
• Published: 12/04/2003
• 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.
• Granted Patent: US 7,188,117 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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;

determining one or more of a textual authoritativeness value or 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; and

rearranging the set of relevant documents in an order selected using at least the determined textual authoritativeness value or the textual authority class for the documents to re-rank the set of relevant documents.

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 determining 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 determining 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 one or more of a textual authoritativeness value or a textual authority class of each top-ordered document; and

determining a weighted social authority rank for each top-ordered document based on the one or more of a textual authoritativeness value or a textual authority class of each top-ordered document.

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 another document. The innovation is the weighting not the adjacency matrix.

10. The method of claim 7, wherein estimating the textual authoritativeness value or a textual authority class 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

determining a textual authoritativeness value or 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 authoritativeness value or textual authority class 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;

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. Same comment as before, it'"'"'s the weight and not the structure that sets us apart.

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;

determining 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 determined 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; and

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

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 determining 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

determining at least one of textual authoritativeness value or 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 least two sets of rank orderings, the method comprising:

determining a first set rank ordering of relevant documents;

determining a textual authoritativeness 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 determined 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.

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

determining a textual authoritativeness value or 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.

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;

determining 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 determined 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.

25. The method of claim 24, wherein estimating 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

determining 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.