# US 7,433,869 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 7,433,869 B2
- Document ID: US7433869B2
- Status: Granted
- Kind: B2
- Application number: 11/427,781
- Filed: 2006-06-29
- Published: 2007-01-04
- Granted: 2008-10-07
- Earliest claimed: 2006-06-29
- Assignees: Ebrary
- Inventors: Sreenivas Gollapudi
- Web page: https://patentgrep.com/patent/US7433869B2

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

A method for computing the sketch for a document, comprising the steps of:
using a sentence in a document as a logical delimiter or window from which significant words are extracted based upon semantics of each word in the sentence and each word's relationship to other words in the sentence;
computing a weight for said extracted words;
extracting the top-k of said words based on their weight in the document, wherein k represents a numerical value;
lexicographically sorting words in a phrase to capture content of the sentence before computing a sketch;
computing a hash of all pair-wise permutations for said significant words;
sorting said computed hashes; and
choosing the top-m hashes to represent the document, wherein m represents a numerical value.

### Claim 2 (depends on 1)

The method of claim 1, wherein values of m are 256 to 512 for large documents (>1M).

### Claim 3 (depends on 1)

The method of claim 1, wherein weight is computed using measures comprising any of term frequency and inverse document frequency.

### Claim 4 (depends on 1)

The method of claim 1, further comprising the step of:
transporting sketches using Bloom filters.

### Claim 5 (depends on 1)

The method of claim 1, further comprising the step of:
computing a sketch of a hierarchy or a taxonomy given the sketches of the documents in the taxonomy.

### Claim 6 (depends on 1)

The method of claim 1, further comprising the step of:
performing a selection based associative search of documents by allowing an end user to select a portion of a document and then identifying documents containing similar information.

### Claim 7 (depends on 1)

The method of claim 1, further comprising the step of:
performing automatic taxonomy generation and clustering of documents using a tree metric approach to maintain original distances between documents while at the same time organizing said documents in a hierarchy.

### Claim 8 (depends on 7)

The method of claim 7, further comprising the step of:
performing efficient extraction of taxonomies from said tree metric.

### Claim 9 (depends on 1)

The method of claim 1, further comprising the step of:
performing on-line classification, wherein documents arrive at different times and are indexed in an existing taxonomy.

### Claim 10 (depends on 1)

The method of claim 1, further comprising the steps of:
providing a compact representation of a sketch; and
computing similarities for associative search.

### Claim 11 (depends on 1)

The method of claim 1, further comprising the step of:
in a distributed environment for collaboratively shared documents, using a sketch for efficient inter-repository distribution, communication, and retrieval of information across networks, wherein a whole document or a collection need not be transported or queried against, wherein said sketch substitutes for a document in all supported computations.

### Claim 12 (depends on 11)

The method of claim 11, wherein an efficient associative search offers similar documents when a requested document is not available.
