# US 8,255,397 B2 · Method and apparatus for document clustering and document sketching

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,255,397 B2
- Document ID: US8255397B2
- Status: Granted
- Kind: B2
- Application number: 12/198,841
- Filed: 2008-08-26
- Published: 2008-12-25
- Granted: 2012-08-28
- Earliest claimed: 2005-07-01
- Assignees: Ebrary
- Inventors: Sreenivas Gollapudi
- Web page: https://patentgrep.com/patent/US8255397B2

## CPC

- G06F 16/313: {Selection or weighting of terms for indexing}
- G06F 16/355: Creation or modification of classes or clusters
- Y10S 707/99933: Query processing, i.e. searching
- Y10S 707/99935: Query augmenting and refining, e.g. inexact access
- Y10S 707/99942: Manipulating data structure, e.g. compression, compaction, compilation
- Y10S 707/99943: Generating database or data structure, e.g. via user interface
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

A first embodiment of the invention provides a system that automatically classifies documents in a collection into clusters based on the similarities between documents, that automatically classifies new documents into the right clusters, and that may change the number or parameters of clusters under various circumstances. A second embodiment of the invention provides a technique for comparing two documents, in which a fingerprint or sketch of each document is computed. In particular, this embodiment of the invention uses a specific algorithm to compute the document's fingerprint. One embodiment uses a sentence in the document as a logical delimiter or window from which significant words are extracted and, thereafter, a hash is computed of all pair-wise permutations. Words are extracted based on their weight in the document, which can be computed using measures such as term frequency and the inverse document frequency.

## Claims

### Claim 1

An automatic document classification apparatus, comprising:
a system comprising a processor configured for automatically generating document sketches by using a sentence in a document as a logical delimiter from which significant words are extracted and, thereafter, for each sentence computing a hash of all pair-wise permutations of said significant words which are extracted from said sentence, wherein said significant words are extracted based on a word's weight in the document, which is computed using measures comprising either of term frequency and inverse document frequency;
said processor configured for using said document sketches for automatically classifying a collection of documents into clusters based on a distance metric, wherein distance between any two documents in a cluster is smaller than the distance between documents across clusters; and
said processor configured for automatically classifying a new document into an appropriate document cluster based upon said distance metric;
said processor applying said automatic classification of said new document into an appropriate document cluster based upon said distance metric to effect at least one of:
user selection of a section of a document to identify documents containing similar information;
automatic taxonomy generation and clustering of documents;
inter-repository distribution, communication, and retrieval of information across networks, wherein said document sketch is substituted for a document; and
constructing a traversal order of a document set from nearest neighbors of a query document in a metric space.

### Claim 2 (depends on 1)

The apparatus of claim 1, further comprising:
said processor configured for organizing said clusters hierarchically by approximating said distance metric by a tree metric.

### Claim 3 (depends on 2)

The apparatus of claim 2, further comprising:
said processor configured for generating a taxonomy by using a parameter that sets a threshold on cohesiveness of a cluster, wherein cohesiveness of a cluster comprises a largest distance between any two documents in said cluster.

### Claim 4 (depends on 3)

The apparatus of claim 3 wherein, based on said cohesiveness, nodes in the taxonomy comprise clusters that can be merged to form bigger clusters having larger diameters, as long as said cohesiveness threshold is not violated.
