Machine Learning - Detecting similar documents using entity extraction (Nhn) - Patent Application - PRIOR ART REQUEST

Question

AN OVERBROAD PATENT ON Methods of detecting similar documents - This application from Nhn seeks to patent the idea of...Extracting an entity from two or more web documents, calculating weights based on the two or more documents, and determining a similarity between the two or more documents! 10 minutes of your time can help narrow US patent applications before they become patents. Follow @askpatents on twitter to help.

QUESTION - Have you seen anything that was published before 5/4/2011 that discusses:

• Methods for detecting similar documents by matching and comparing extracted entities from the documents

If so, please submit evidence of prior art as an answer to this question. We welcome multiple answers from the same individual.

EXTRA CREDIT - A characteristic index for each of the web documents is calculated based on weight of the corresponding entity. A similarity between the web documents is determined based on the calculated characteristic indices

TITLE: Method and device to detect similar documents

Summary: [Translated from Legalese into English] Extracting an entity from two web documents, calculating weights for the entity based on importance contribution elements corresponding to both of the two web documents, and determining a similarity between the two web documents based on the calculated weights.

• Publication Number: US 20120284270 A1
• Application Number: US 13/462,592
• Assignee: Nhn
• Prior Art Date: Seeking prior Art predating 5/4/2011
• Open for Challenge at USPTO: Open through 5/7/2013
• Link to Google Prior Art Search - "Find Prior Art"

Claim 1 requires each and every step below:

A method that uses a processor for detecting similar documents, comprising:

1. Extracting an entity from each of a first web document and a second web document;

2. Determining an importance contribution element corresponding to each of the web documents;

3. Calculating, using the processor, weights for each entity based on the determined importance contribution elements; and

4. Determining whether the web documents are similar documents based on the calculated weights. Determining whether the web documents are similar documents based on the calculated weights.

In English this means:

A method for detecting similar documents, the method comprises the following steps:

1. Extracting an entity from two web documents;

2. Determining an importance contribution element corresponding to both the web documents;

3. Calculating weights for each entity based on the determined importance contribution elements; and

4. Determining whether the two web documents are similar documents based on the calculated weights.

Good prior art would be evidence of a system that did each and every one of these steps prior to 5/4/2011

"You're probably aware of ten pieces of art that meet this criteria already... separately, the applicant is claiming Each importance contribution element comprises at least one of a hash value of the corresponding entity, and a frequency of which the corresponding entity is duplicated within the corresponding web document. Further, the calculating the weights comprises using an inverted document frequency concept, the inverted document frequency concept increasing a weight of each entity in inverse proportion to decreasing frequency of duplication of the respective entity. "

---

"Method and device to detect similar documents" from the Applicant

---

What is good prior art? Please see our FAQ.

Want to help? Please vote or comment on submissions below. We welcome you to post your own request for prior art on other questionable US Patent Applications.

---

Answer 1

This sounds the same as Netscape Navigator's "What's Related" feature. This may overlap with their "What's Cool" functionality too. Both of which were present in their Navigator product circa ~1995. Their may be others, but this is at least one patent tied to those features:

"Shared document repository with coupled recommender system" US 6999962 B2

A web-based shared document repository includes recommender system functions to allow users of the repository to input reviews of documents contained in the repository and to read inputted reviews. The recommender system functions appear as a seamless integration in the document repository by loosely coupling the shared document repository to a web-based recommender system.

Publication number  US6999962 B2
Publication type    Grant
Application number  US 10/217,025
Publication date    Feb 14, 2006
Filing date Aug 13, 2002
Priority date   Aug 13, 2002
Fee status  Paid
Also published as   US20040034631
Inventors   Laurent Julliard, Jean-Luc Meunier, Scott D Weber, Manfred Dardenne
Original Assignee   Xerox Corporation
Export Citation BiBTeX, EndNote, RefMan

Answer 2

A Vector Space Model for Automatic Indexing (1975) by G. Salton, A. Wong, and C. S. Yang.

The first two paragraphs (after the abstract) describe how to compute a similarity coefficient between two documents. The documents are associated with one or more index terms; a weight for each term may be computed according to its importance in the given document; the similarity of the documents may be computed by comparing the resulting weights.

Instead of "entities," the paper refers to "index terms."

Answer 3

From Elin's comment of 1/14/2014:

Information retrieval system and method that generates weighted comparison results to analyze the degree of dissimilarity between a reference corpus and a candidate document US 6167398 A

ABSTRACT An internet information agent accepts a reference document, performs an analysis upon it in accordance with metrics defined by its analysis algorithm and obtains respective lists (word, character-level n-gram, word-level n-gram), derives weights corresponding to the metrics, applies the metrics to a candidate document and obtains respective returned values, applies the weights to the returned values and sums the results to obtain a Document Dissimilarity (DD) value. This DD is compared with a Dissimilarity Threshold (DT) and the candidate document is stored if the DD is less than the DT. A user can apply relevance values to the search results and the agent modifies the weights accordingly. The agent can be used to improve a language model for use in speech recognition applications and the like.

Answer 4

I'm going to add the beginning of another possible set of sources here, but I'd like to know if people think they sound right. The way the the described process basically looks for mix-and-match meaning that web pages have regions, a lot of the regions may be identical, but other regions are different, and then also that they may be somewhat rearranged on the page (think of the menu bar on this page which is the same as other stackexchange sites, and then the part that is the same for all pages on patents.stackexchange.com but not the other sites, and then the sidebar and footer. They are pretty similar everywhere but not identical.

This led me to think about plagiarism as a similar problem, because you may have a document that is like another one but has been rearranged or has a few words changed or parts of it it may be copied from many different original documents. In searching Google Scholar there are a lot of automated plagiarism detection articles some going back to the 1980s. There are a lot of algorithms for doing this, some use weighting and some don't. It seemed like some of them, although not specifically designed for the web, could well be prior art for this.

Answer 5

Updated: To me this seems similar to Google's US8554561 "Efficient indexing of documents with similar content"

It is also trying to find out if two documents are identical or near identical and uses similarity hashes.

Answer 6

I implemented a system for identifying similar documents, in a version control system called Meta-CVS, in 2002, three years before the initial filing of this patent in 2005.

This is the basis for the mcvs grab command, for importing a snapshot of a document collection into a branch of the repository. The document collection is understood to be derived from the baseline that is already in the branch, but the document contents may have changed. In addition, the tree structure of the documents may have changed (moves and renames), and documents may have been added or removed.

The software unravels the situation and perform an accurate import, matching the new documents to their correct base documents which are their "near duplicates" (to borrow a term from the patent), and scheduling all the necessary adds, deletes and renames for the new commit.

The strategy is to reduce each document to elements, exactly like in the patent, and, furthermore, to determine which elements are more important than others by considering a cluster of documents. In the case of my implementation, an element is a word-like "token": important tokens are those that occur only in a small number of documents. Thus, effectively, a binary weight is assigned: some elements get weight 0 (they are ignored because they are considered common, and are not useful in identifying similar documents within the cluster), whereas other elements are weighted as 1 (not ignored, because they are not common).

This refinement to the algorithm did indeed make it more accurate, having the effect of amplifying the important similarities between two texts (the sharing of rare features, indicators that the pair are near duplicates), while suppressing their unimportant similarities (traits they share with the whole cluster under consideration).

Everything I coded in that piece of software was obvious stuff that any decent programmer can come up with before breakfast.