System for categorizing documents in a linked collection of documents

• US 5,895,470 A
• Filed: 04/09/1997
• Issued: 04/20/1999
• Est. Priority Date: 04/09/1997
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Pirolli, Peter L., Pitkow, James E., Rao, Ramana B.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US08/842,926
• Time in Patent Office: 741 Days
• Field of Search: 707/4, 707/101, 707/103, 707/5, 707/6, 707/102, 707/104
• US Class Current: 707/727
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• 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/99945 Object-oriented database structure processing

Abstract

A system for extracting and analyzing information from a collection of linked documents at a locality to enable categorization of documents and prediction of documents relevant to a focus document. The system obtains and analyzes topology, usage and path information from for a collection at a locality, e.g. a web locality on the world wide web. For categorization, document meta information is represented as document vectors. Predefined criteria is applied to the document vectors to create lists of "similar" types of documents. For relevance prediction, networks representing topology, usage path and text similarity amongst the documents in the collection are created. A spreading activation technique is applied to the networks starting at a focus document to predict the documents relevant to the focus document. Using category and relevance prediction information, tools can be built to enable a user to more efficiently traverse through the collection of linked documents.

Claims

1. A system for categorizing documents contained in a linked collection of documents comprising:

means for obtaining raw data from said linked collection of documents, said raw data including meta information for documents in said linked collection of documents;

means for creating a feature vector for documents in said linked collection of documents from said raw data, said feature vector comprising a plurality of elements;

means for defining classification criteria indicating particular categories of document types, said classification criteria comprising user defined weightings of the elements for said feature vector and a corresponding class threshold value;

processing means for applying said classification criteria to feature vectors to determine if a document is in a corresponding category.

2. The system as recited in claim 1 wherein said means for obtaining raw data for said linked collection of documents is further comprised of a first agent for traversing said linked collection of documents to obtain topology information and document meta information.

3. The system as recited in claim 2 wherein the plurality of elements of a feature vector for a document in said linked collection of documents include:

size information for said document;

inlink information for said document, said inlink information indicating the number of links in said linked collection of documents that point to said document;

outlink information for said document, said outlink information indicating the number of links the document contains to other documents said linked collection of documents;

frequency information for said document, said frequency information indicating the number of times said document was requested during a sample period;

source information for said document, said source information indicating the number of times said document was identified as the start of a path traversal;

text similarity information for said document, said text similarity information indicating the similarity of the text of the document to documents in said linked collection of document to which they are linked; and

depth information for said document, said depth information indicating the average depth in said linked collection of documents of documents to which said document links.

4. The system as recited in claim 3 wherein said processing is comprised of means for determining that a document is a class if after applying said classification criteria the result exceeds said corresponding class threshold value.

5. The system as recited in claim 1 wherein said linked collection of documents is a Web locality.

6. A method for generating a list of web pages in a web locality that are contained in a user defined class comprising the steps of:

a) obtaining raw data for said web locality, said raw data including topology information and web locality usage information;

b) generating page meta data for each web page in said web locality from said raw data;

c) generating feature vectors for each web page in said web locality using said page meta data and said topology information, said feature vector comprised of a plurality of elements;

d) obtaining a classification criteria for determining if a web page is a member of a category of web pages, said classification criteria comprising user defined weightings of the plurality of elements for said feature vector and a corresponding class threshold value; and

e) applying said classification criteria to said feature vectors to obtain a list of pages in said category.

7. The method as recited in claim 6 wherein said step of obtaining topology information for said web locality is comprised of the steps of:

a1) retrieving a web page;

a2) storing location information for said web page;

a3) parsing said web page to identify links to other web pages; and

a4) repeating steps a1)-a3) for each of said other web pages.

8. The method as recited in claim 6 wherein said step of obtaining page meta data for each web page in said web locality is further comprised of the step of collecting page meta data for a page as the page is retrieved.

9. The method as recited in claim 6 wherein said step of generating feature vectors for each web page in said web locality using said page meta data and said topology information is further comprised of the step of for each associated web page in said web locality performing the steps of:

extracting size information for said associated web page and storing as a size element in said corresponding feature vector;

extracting inlink information for said associated web page, said inlink information indicating the number of links in said web locality that point to said associated web page as storing as an inlink element in said corresponding feature vector;

extracting outlink information for said associated web page, said outlink information indicating the number of links the web page contains to other web pages in said web locality and storing as an outlink element in said corresponding feature vector;

extracting frequency information for said associated web page, said frequency information indicating the number of times said associated web page was requested during a sample period and storing as a frequency element in said corresponding feature vector;

extracting source information for said associated web page, said source information indicating the number of times said associated web page was identified as the start of a path traversal and storing as a source element in said corresponding feature vector;

extracting text similarity information for said associated web page, said itext similarity information indicating the similarity of the text of the associated web page to other web pages in said web locality to which they are linked and storing as a text similarity element in said corresponding feature vector; and

extracting depth information for said associated web page, said depth information indicating the average depth in said web locality of other web pages to which said associated web page links and storing as a depth element in said corresponding feature vector.

10. The method as recited in claim 9 wherein said step of applying said classification criteria to said feature vectors to obtain a list of pages in said category is further comprised of the steps of:

for each element of a feature vector applying a corresponding weighting value to obtain a feature value;

summing the resulting values feature values; and

comparing said sum to said class threshold value to determine if said corresponding page is in said class.

11. A system for generating characteristic data for a linked collection of documents comprising:

means for obtaining raw data for said linked collection of documents, said raw data including usage data, topology data and content data;

means for creating a feature vector for each document in said linked collection of documents from said raw data; and

means for categorizing each of said documents in said linked collection of documents according to predetermined classification criteria, said predetermined classification criteria comprising user defined weightings of the elements for said feature vector and a corresponding class threshold value.

12. The system as recited in claim 11 further comprising:

means for creating usage, topology and text similarity maps for said linked collection of documents from said raw data;

means for predicting a relevant set of documents for a subset of said linked collection of documents using one or more of said usage, topology and text similarity maps.

13. A system for categorizing documents contained in a linked collection of documents comprising:

means for obtaining raw data from said linked collection of documents, said raw data including meta information for documents in said linked collection of documents;

means for creating a feature vector for documents in said linked collection of documents from said raw data, said feature vector having at least one element indicating a frequency of request for an associated document;

means for defining classification criteria indicating particular categories of document types;

processing means for applying said classification criteria to feature vectors to determine if a document is in a corresponding category.

14. A method for generating a list of web pages in a web locality that are contained in a user defined class comprising the steps of:

a) obtaining raw data for said web locality, said raw data including topology information and web locality usage information;

b) generating page meta data for each web page in said web locality from said raw data, said meta data including data indicating a frequency of request for an associated document;

c) generating feature vectors for each web page in said web locality using said page meta data and said topology information;

d) obtaining a classification criteria for determining if a web page is a member of a category of web pages; and

e) applying said classification criteria to said feature vectors to obtain a list of pages in said category.