Document retrieval apparatus

• US 6,078,913 A
• Filed: 02/11/1998
• Issued: 06/20/2000
• Est. Priority Date: 02/12/1997
• Status: Expired due to Fees

• Current Assignee: KDDI Corporation
• Original Assignee: Kokusai Denshi Denwa Company Limited (KDDI Corporation)
• Inventors: Aoki, Keiko, Matsumoto, Kazunori, Hashimoto, Kazuo
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/022,280
• Time in Patent Office: 860 Days
• Field of Search: 707/2, 707/5, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A document retrieval apparatus is connected to a network, and includes a cluster database storing a cluster of node information elements linked for clustering the documents to a hierarchical tree structure based on degree of similarity in all of the documents. The apparatus can post to an end address in the node information element encountered on the way to follow links of the cluster by whenever one of the documents is updated. Also, the apparatus selects a specific number of documents, clusters those, assigns the remaining non-selected documents respectively to a leaf node to be similar to the documents in the cluster, and repeats recursively the above operations toward a direction of the leaf node of cluster.

Claims

1. A document retrieval apparatus connected through a network to a plurality of computers having documents, said apparatus comprising:

a contents database for storing index information of the respective documents;

a cluster database for storing a plurality of node information elements which are linked as nodes of a cluster with a hierarchical tree structure of the documents arranged based on similarity of the documents, each said node information element including end addresses where an update of the cluster generated by a modification or an addition of an individual document located at a lower side of the node is to be posted; and

a control means for posting the modification or addition of the individual document to the end address in the node information element which encounters while following the link of the cluster when the cluster is updated.

2. The document retrieval apparatus of claim 1, wherein:

the node information element has a frequency table with weightings listing desired keywords which appear in the plurality of documents located at the lower side of the node,

the individual document has a frequency table with weightings listing the keywords which appear in the individual document,

the link of the cluster is followed by comparing the frequency table in the node information element with the frequency table of the individual document.

3. The document retrieval apparatus of claim 1, the network is the internet and the end address in the node information element is a mail address.

4. The document retrieval apparatus of claim 1, further comprising a user information database which includes a list of locations of the documents in which the user has an interest, and a list of domains indicating retrieving limits, for every end address.

5. The document retrieval apparatus of claim 1, further comprising a resource discovering engine collecting the documents automatically though the network.

6. A document retrieval apparatus including a database storing a plurality of documents, and a control means for constituting the documents in a cluster and retrieving the document, the control means comprising;

a leaf node selection means for random selecting a specific number of the plurality of documents as the documents assigned to leaf nodes, and clustering the selected documents;

a partial clustering means for assigning the remaining non-selected documents of the plurality respectively to the leaf node assigning one selected document to which each of the non-selected documents is similar; and

a recursively clustering means for recursively repeating the operations of the leaf node selection means and the clustering means toward a direction of the leaf node of the cluster.

7. The document retrieval apparatus of claim 6, wherein

the node selection means comprises means for random selecting the specific number of documents from the plurality documents, means for clustering the selected documents, means for assigning the remaining non-selected documents respectively to a leaf node assigning one document to which each of the non-selected documents is similar, and means for calculating the code length of the cluster,

the leaf node selection means repeating at a specific frequency the operation of each of said means in order to select the specific number of documents so that the code length of a cluster is minimized.

8. The document retrieval apparatus of claim 7, wherein the code length of the cluster is the sum of

an informational quantity L1=2k-1 necessary for clustering the documents where k is the number of the leaf nodes, and

a code length L2=Σ

n_i log p_i necessary for classifying the documents assigned to each leaf node where n_i is the number of the documents assigned to the leaf node i and pi=n_i /Σ

_j n_j is a probability of selecting the documents of the leaf node i from the plurality of documents.

9. The document retrieval apparatus of claim 6, wherein the recursively clustering means instructs the recursively repeating of the operations of the leaf node selection means and the partial clustering means toward a direction of the leaf node of the cluster if the number of document assigned to the leaf node of the cluster is more than the specific number.

10. A clustering method for constituting a plurality of documents as a cluster, and retrieving a particular document, the method comprising:

randomly selecting a specific number of documents as the documents assigned to leaf nodes from the plurality of documents, and clustering the selected documents;

partially clustering and assigning the remaining non-selected documents of the plurality respectively to the leaf node assigning one selected document to which each non-selected document is similar; and

recursively repeating the leaf node selection and the clustering toward a direction of the leaf node of the cluster.

11. The method of claim 10, further comprising calculating a code length of the cluster of selected documents, and

repeating at a specific frequency the method in order to select the specific number of documents so that the code length of a cluster is minimized.

12. The method of claim 11, wherein the code length of the cluster is calculated by summing

an informational quantity L1=2k-1 necessary for clustering the documents where k is the number of the leaf nodes, and

a code length L2=Σ

n_i log p_i necessary for classifying the documents assigned to each leaf node where n_i is the number of the documents assigned to the leaf node i and p_i =n_i /Σ

_j n_j is a probability of selecting the documents of the leaf node i from the plurality of documents.

13. The method of claim 10, wherein recursively repeating of the leaf node selection and the partial clustering toward a direction of the leaf node of the cluster is continued if the number of document assigned to the leaf node of the cluster is more than the specific number.