Method and apparatus for information access employing overlapping clusters

• US 5,999,927 A
• Filed: 04/24/1998
• Issued: 12/07/1999
• Est. Priority Date: 01/11/1996
• Status: Expired due to Term

• Current Assignee: Genaville LLC (IP Edge LLC)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Tukey, John W., Pedersen, Jan O.
• Primary Examiner(s): Lintz, Paul R.
• Application Number:
  US09/065,828
• Time in Patent Office: 592 Days
• Field of Search: 707/5, 707/2, 707/3, 707/6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

The present invention is a method and apparatus for document clustering-based browsing of a corpus of documents, and more particularly to the use of overlapping clusters to improve recall. The present invention is directed to improving the performance of information access methods and apparatus through the use of non-disjoint (overlapped) clustering operations. The present invention is further described in terms of two possible methods for expanding document clusters so as to achieve the overlap, and a method for increasing precision through the use of the overlapped clusters.

Claims

1. A method, operating in a digital computer, for searching a corpus of unclustered documents, comprising the steps of:

preparing, in response to a query, an initial structuring of the unclustered corpus into a plurality of primary overlapping clusters, wherein at least two of the plurality of primary overlapping clusters contain a document in common; and

determining a summary of the plurality of primary overlapping clusters prepared by said initial structuring of the corpus.

2. The method of claim 1, further including the step of defining an inner cluster associated with at least one of the plurality of primary overlapping clusters, said inner cluster consisting of documents found only in the at least one of the plurality of primary overlapping clusters.

3. The method of claim 2, further including the step of defining an intermediate cluster, associated with at least one of the plurality of primary overlapping clusters, said intermediate cluster corresponding to a primary overlapping cluster and consisting of all documents, in the primary overlapping cluster, for which a corresponding attractor is the closest attractor.

4. The method of claim 1, further comprising the steps of:

displaying the summary of the plurality of overlapping clusters;

allowing a user to select one of said primary overlapping clusters from the displayed summary; and

in response to a user selection, preparing a further structuring of a corpus defined by the documents associated with the selected one of said primary overlapping clusters, said further structuring including a plurality of secondary clusters.

5. The method of claim 4, further comprising the step of iteratively repeating the steps of:

displaying the summary of the plurality of clusters;

allowing user selection of one of said plurality of clusters from the displayed summary; and

preparing a further structuring of a corpus defined by the documents associated with the selected one of said clusters in response to the user selection, said further structuring including a new plurality of clusters.

6. The method of claim 4, further comprising the steps of:

determining a summary for each of the plurality of secondary clusters prepared by said further structuring of the corpus defined by the documents associated with the selected one of said primary overlapping clusters;

displaying the summaries for the plurality of secondary clusters.

7. The method of claim 4, further comprising the step of displaying, in response to the user selection of one of said secondary clusters, a list of the documents contained within the selected one of said secondary clusters.

8. A document browsing system for use with a corpus of unclustered documents stored in a computer system, the document browsing system comprising:

program memory for storing executable program code therein;

a processor, operating in response to the executable program stored in said program memory, for automatically preparing, in response to a query, an initial structuring of the corpus of unclustered documents into a plurality of document clusters, wherein at least two of the plurality of document clusters overlap and contain at least one common document therebetween;

data memory for storing data identifying the documents associated with each of the plurality of document clusters;

memory access means for accessing the data memory and said processor summarizing the plurality of document clusters and generating summary data for said document clusters; and

a user interface for displaying the summary data.

9. The document browsing system of claim 8, wherein said user interface is responsive to a user selection of one of said document clusters having data displayed thereon, and wherein said processor further provides a second structuring of a subset of the corpus corresponding to the documents associated with the selected one of said document clusters.

10. A document search and retrieval method, operating in a digital computer, for searching a corpus of unclustered documents, comprising the steps of:

identifying, in response to at least one user specified search term, a sub-corpus of unclustered documents containing the at least one user specified search term;

preparing an initial structuring of the sub-corpus of unclustered documents into a plurality of primary overlapping clusters, wherein at least two of the plurality of primary overlapping clusters contain a document in common; and

determining a summary of the plurality of primary overlapping clusters prepared by said initial structuring of the sub-corpus.

11. The method of claim 10, further including the step of defining an inner cluster associated with at least one of the plurality of primary overlapping clusters, said inner cluster consisting of documents found only in the one of the plurality of primary overlapping clusters.

12. The method of claim 10, further including the step of defining an intermediate cluster, associated with at least one of the plurality of primary overlapping clusters, said intermediate cluster corresponding to a primary overlapping cluster and consisting of all documents, in the primary overlapping cluster, for which a corresponding attractor is the closest attractor.

13. The method of claim 10, further comprising the steps of:

displaying the summary of the plurality of primary overlapping clusters;

allowing a user to select one of said primary overlapping clusters from the displayed summary; and

in response to a selection, preparing a further structuring of a sub-corpus defined by the documents associated with the selected one of said primary overlapping clusters, said further structuring including a plurality of secondary overlapping clusters.

14. The method of claim 13, further comprising the steps of:

determining a summary of the plurality of secondary overlapping clusters prepared by said further structuring of the corpus defined by the documents associated with the selected one of said primary overlapping clusters;

displaying the summary of the plurality of secondary overlapping clusters.

15. The method of claim 13, further comprising the step of displaying, in response to a user selection of a secondary overlapping cluster, a list of the documents contained within the selected one of said secondary overlapping clusters.

16. A method, operating in a digital computer, for searching a corpus of unclustered documents, comprising the steps of:

subdividing the unclustered corpus of documents into a hierarchical structure containing a plurality of levels of clusters, wherein at least two of the clusters on a particular level are overlapping clusters containing at least a document in common;

selecting, from the hierarchical structure, a plurality of clusters to form a subcorpus, wherein the subcorpus contains fewer document than the corpus; and

identifying, in response to a search query, those documents in the subcorpus providing a positive response to the search query.