Estimating document similarity using bit-strings

Each of a plurality of documents is divided into samples. Small bit-strings are generated for selected samples from each of the documents and used to create a sketch for each document. Because the bit-strings are small (e.g., only one, two, or three bits in length), the generated sketches are smaller than the sketches generated using previous methods for generating sketches, and therefore use less storage space. The generated sketches are compared to determine documents that are near-duplicates of one another.

BACKGROUND

Large collections of documents typically include many documents that are identical or nearly identical to one another. Determining whether two digitally-encoded documents are bit-for-bit identical is straightforward, using hashing techniques for example. Quickly identifying documents that are roughly or effectively identical, however, is a more challenging and, in many contexts, a more useful task.

The World Wide Web is an extremely large set of documents, and has grown exponentially since its birth. Web indices currently include approximately five billion to 120 billion web pages, up to a third of which may be duplicates or near-duplicates. Applications such as web crawlers and search engines benefit from the capacity to efficiently detect many near-duplicates.

SUMMARY

Each of a plurality of documents is divided into samples. Small bit-strings are generated for selected samples from each of the documents and used to create a sketch for each document. Because the bit-strings are small (e.g., only one, two, or three bits in length), the generated sketches are smaller than the sketches generated using previous methods for generating sketches, and therefore use less storage space. The generated sketches are compared to determine documents that are near-duplicates of one another.

In an implementation, a set of samples is received at a computing device. The set of samples is associated with a document. For each sample, a sequence of bits is generated until a predetermined bit value is generated by the computing device. A subset of samples from the set of samples is selected based on a length of each sequence of bits by the computing device. For each sample in the subset of samples, a bit-string is generated for the sample. The generated bit-string for each sample in the subset is used to estimate the similarity of the document to one or more other documents.

In an implementation, a first set of samples and a second set of samples are received at a computing device. The first set of samples is associated with a first document and the second set of samples is associated with a second document. A first plurality of bit-strings is generated based on the first set of samples by the computing device. A second plurality of bit-strings is generated based on the second set of samples by the computing device. A similarity between the first document and the second document is estimated based on the first and second plurality of bit-strings.

DETAILED DESCRIPTION

FIG. 1shows an arrangement100of a distributed computing system. A plurality of server computers (referred to as servers)110,115are connected to each other by a communications network120, for example, the Internet. The Internet includes an application level interface called the World Wide Web (web121). The servers maintain web content111, which may comprise, for example, multimedia content such as web pages. The location of web content111is specified by its uniform resource locator (URL) address112. Although only two servers110,115are shown, any number of servers may be connected to the network120and to each other.

A client computer (referred to as a client)130may also be connected to the network120. Although only one client130is shown, any number of clients may be connected to the network120. An example client130is described in with respect toFIG. 5. Usually, the client130is equipped with a web browser. During operation of the arrangement100, a user of the client130may monitor the web content111of the servers. The user may want to monitor specific content that has changed in a substantial way.

In order to assist the user of the client130to locate web content111, one or more search engines140are also connected to the network120. A search engine140may use a crawler141to periodically scan the web121for changed or new content. An indexer142may maintain an index143of content located by the search engine. The search engine140may also be equipped with a query interface to process queries submitted by users to quickly locate indexed content. A user of the client130may interact with the query interface via a web browser.

In systems like a large web index, a sketch of each document may be generated and/or maintained by a sketch engine145. For example, the content of complex documents expressed as many thousands of bytes can be reduced to a sketch of just dozens of bytes. The sketch is constructed by the sketch engine145so that the resemblance of two documents can be approximated from the sketches of the documents with no need to refer to the original documents. The generated sketches of the documents may be stored and maintained by the sketch engine145in a sketch storage147.

FIG. 2is a block diagram of an implementation of a sketch engine145. The sketch engine145may generate a sketch200of each document of the web content111that is retrieved and indexed by the search engine140. In some implementations, a sketch200may comprise a plurality of bit-strings. The sketch200may be stored in the sketch storage147. The sketches for documents can be determined in isolation in a time which is directly proportional to the size of the documents. The sketches generated for documents can be used to estimate the similarity of the corresponding documents, and to determine whether the documents are near-duplicates based on the estimation. Thus, by using the sketches rather than the documents themselves to determine near-duplicate documents, the amount of storage resources needed for near-duplicate document determination is reduced.

Documents may have a high similarity (e.g., are near-duplicates) when they have the same content, except for minor differences such as formatting, corrections, capitalization, web-master signature, logos, etc. The sketches may be used to estimate a measure of the similarity between two documents be determining the intersection of the sketches associated with the documents. One way of doing this is to take samples from the document using a technique with the property that similar documents are likely to yield similar samples.

Accordingly, in an implementation, the sketch engine145may receive a document from the search engine140, and may extract a set of N samples from the document, where each sample may correspond to a term, or sequence of bits, from the document. The size of N may be dependent on the size of the document.

The sketch engine145may include a bit-string generator210. The bit-string generator210may select a subset of samples from the set of N samples, and may generate a plurality of bit-strings corresponding to each of the samples from the selected set of samples. The set of generated bit-strings for a document may be associated with the document and stored in the sketch storage147as the sketch200for the document. In some implementations, each generated bit-string may be small. For example, the generated bit-strings may be one, two, or three bits in length. However, other sized bit-strings may be supported.

The bit-string generator210may select K samples for the subset of samples from the set of N samples. Each selected sample may correspond to a slot of the sketch200. In some implementations, the bit-string generator210may select a sample for the subset by, for each sample in the set of N samples, generating a sequence of bits for each slot until a predetermined bit is generated. For example, where the predetermined bit is a bit with a value of one, the search engine140may generate a sequence of bits until a bit with a value of one is generated.

After generating a sequence of bits for a slot, the bit-string generator210may compare the length of the generated sequence of bits with a length of the largest sequence of bits generated for that slot thus far. If the length of the generated sequence of bits for the slot is greater than the length of the generated sequence of bits previously generated for the slot, an indicator of the sample associated with the greater length sequence of bits may be recorded for the slot.

The bit-string generator210may generate each bit in a generated sequence of bits by flipping what is known as an unbiased coin. Unbiased coins are well known. In probability theory and statistics, a sequence of independent Bernoulli trials with probability ½ of success on each trial is called an unbiased coin. A sequence of independent Bernoulli trails for which the probability is not ½ is called a biased coin. A “heads” of the unbiased coin may correspond to a bit-value of zero and a “tails” of the unbiased coin may correspond to a bit-value of one, or vice-versa.

The indicators of the samples with the generated sequence of bits for each slot so far may be recorded by the bit-string generator210in a data structure215. The data structure215may include an entry for each of the available K slots. An indicator of the sample with the largest length sequence of bits for a slot may be recorded in the entry for that slot by the bit-string generator210. By generating the samples bit by bit using a coin rather than generating the bits for each sample in its entirety, the overall number of bits that are generated to select the minimum length sample for each slot is reduced.

In some implementations, where a sample for a slot has a generated sequence of bits with a length that is equal or tied with the maximum generated length sequence of bits for the slot, the search engine140may record an indicator of the sample with the tying length sequence of bits. After the sequences of bits have been generated for each sample for each slot, the bit-string generator210may break the ties for each slot. For example, in some implementations, the bit-string generator210may break ties by flipping an unbiased coin for each tying sample until all coins but one coin results in a heads. Alternatively, the unbiased coins may be flipped until all coins but one coin results in a tails. The tying sample associated with the last remaining coin may be selected by the bit-string generator210as the sample for the slot. Other methods for breaking ties may be used.

Alternatively, the bit-string generator210may not break ties between generated sequences of bits for a particular sample. Rather, when a generated sequence of bits for a slot is tied with another generated bit-string, the bit-string generator210may record the parity of the generated bit-string for the tying sample. The recorded parity may indicate that there was a tie and may be stored by the bit-string generator210with an indicator of the tying sample.

After selecting the samples, the bit-string generator210may generate a bit-string for each of the selected samples for each of the K slots as indicated by the data structure215. The generated bit-strings may be one bit, two bit, or three bit bit-strings. However, other size bit-strings may be generated. In some implementations, the bit-strings may be generated by the bit-string generator210using an unbiased coin. Alternatively or additionally, the bit-string generator210may generate a bit-string for a selected sample based on the position of the sample in the set of samples, or the parity of the generated sequence of bits for the sample, for example. The bit-strings may be generated such that a bit-string generated from the kthsample of a document A will be identical to the bit-string generated from the kthsample of document B, if the two samples are identical.

The generated bit-strings based on the selected samples from a document may be used by sketch engine145to generate the sketch200for the document. The generated sketch200may be stored by the sketch engine145in the sketch storage147.

In some implementations, rather than generating sequences of bits for each sample by flipping biased coins, the generated sequence of bits may be generated by the bit-string generator210by first generating a large sequence of bits. The bit-generator210may then generate the sequence of bits for each sample by parsing the large sequence of bits into smaller sequences of bits based on predetermined bit values. For example, the bit-string generator210may parse the large sequence into a smaller sequence of bits for a sample every time a bit with a value of one is reached. Each bit-string starting with a one for each position may be expected to occur about 1 time in e for a sample. Accordingly, the bit-string generator210may then use a small expected number of bits to determine a comparison to lie to select the sequence of bits for the sample and may use the remainder of the bits in the large sequence of bits if the comparison fails.

In another implementation, the bit-string generator210may select K samples from a set of samples by flipping a strongly biased coin to determine if any generate string of bits starts with a one (i.e., flipping a tail). The coin may be strongly biased towards heads. If a heads is flipped, the bit-string generator210may consider the next sample. If a tails is flipped, the bit-string generator210may select the sample and may determine the next sample that begins with a one by continuing to flip the strongly biased coin. The bit-string generator210may continue flipping biased coins until K samples have been selected. The bit-string generator210may then generate the bit-strings for the selected samples.

The sketch engine145may further include a similarity engine220. The similarity engine220may determine a similarity between two or more documents based on the similarity of the sketches associated with each document. The greater the similarity between two documents, the greater the likelihood that the documents are duplicate or near-duplicate documents. The search engine140may use the similarity engine220of the sketch engine145to determine documents from the index143that are duplicate or near-duplicate documents. The duplicate or near-duplicate documents may be removed from the index143, or otherwise flagged by the search engine140.

The similarity engine220may estimate the similarity between two documents. The similarity between two documents may be estimated by the similarity engine220using a variety of techniques including, but not limited to, estimating the Jaccard similarity coefficient of the documents, estimating the intersection of the documents, and estimating the 1-norm distance between the documents. However, other methods for estimating the similarity of documents may be used.

The similarity engine220may estimate the Jaccard similarity for the sketches associated with the two documents based on a number of the generated bit-strings from each sketch200that agree and a number of the generated bit-strings from each sketch200that disagree. A first bit-string agrees with a second bit-string if it is equal to the second bit-string, and the first bit-string disagrees with the second bit-string if it is not equal to the second bit-string.

The similarity engine220may estimate the Jaccard similarity for two sketches by maintaining a count for the number of bit-strings that agree and a number of bit-strings that disagree. The similarity engine220may compare the bit-strings from each sketch200position by position, and may increment the corresponding count depending on whether the bit-strings at the same position in the sketches agree or disagree. For example, the similarity engine220may compare the first bit-string in a first sketch200with the first bit-string in a second sketch200, followed by the second bit-string in the first sketch200with the second bit-string in the second sketch200, etc.

In some implementations, the similarity engine220may estimate the Jaccard similarity for two sketches using the counts of the number of bit-strings that agree and the number of bit-strings that disagree. Because the sketches are generated using bit-strings that are small (e.g., one, two, or three bits), the similarity engine220may overestimate the Jaccard similarity of the sketches. Accordingly, in some implementations the Jaccard similarity may be estimated using the formula (1) to account for the overestimation, where #agree is the count of the number of bit-strings that agree and #disagree is the count of the number of bit-strings that disagree and b is the number of bits in each generated bit-string:

In some implementations, the similarity engine220may further estimate the similarity of two documents by determining the 1-norm distance (i.e., the Manhattan distance) between the two documents using a determined 1-norm of each document and the determined Jaccard similarity of the two documents. The similarity engine220may calculate the 1-norm distance using the following formula (2) where L1(A-B) is the 1-norm distance of a document A and a document B, L1(A) and L1(B) are the 1-norms of the documents A and B respectively, and J(A,B) is the Jaccard similarity of the documents A and B:

FIG. 3is an operational flow of an implementation of a method300of generating bit-strings for use the in the estimation of the similarity of documents. The method300may be implemented by the sketch engine145of a search engine, for example.

A set of samples is received at301. The set of samples may be received by the sketch engine145. In some implementations, the samples may be taken from, or associated with, a document. The document may be part of web content111retrieved by a crawler141of the search engine140from a server110, for example. Each sample in the set of samples may correspond to a term from the document.

For each sample, a sequence of bits is generated at303. The sequence of bits may be generated by the bit-string generator210of the sketch engine145. In some implementations, each sequence of bits may be generated by the bit-string generator210until a predetermined bit value, such as a one or a zero, is generated. For example, in some implementations, the bit-string generator210may generate bit-values using an unbiased coin. A “heads” may correspond to a bit-value of zero and a “tails” may correspond to a bit-value of one, or vice-versa. The bit-string generator210may generate a sequence of bits by flipping the unbiased coin until a tails is flipped.

In some implementations, the bit-string generator210, for each sample, may generate a sequence of bits for each of K available slots. The slots may correspond to positions in a sketch200. If the length of a generated sequence of bits (i.e., the number of bits that are generated before a zero value is generated) is greater than a length of a previously generated sequence of bits for the slot, then an indicator of the sample is recorded for the slot along with an indicator of the length. Where there is a tie between the length of the sequence of bits for a sample and the length of a previously generated sequence of bits, the tie may be broken by generating additional bits. Alternatively, the parity of the generated sequence of bits may be recorded for the slot. In some implementations, the indicators of samples, bit lengths, and parities may be stored in a data structure215associated with the set of samples.

A subset of samples is selected from the set of samples at305. The subset of samples may be selected by the bit-string generator210. The subset of samples may be selected from the set of samples by selecting the samples with associated sequence of bits having the greatest length. For example, the samples associated with the top K lengths may be selected for the subset. In implementations having a data structure215with indicators of each sample having the greatest length sequence of bits, the subset of samples may be selected according to the indicators stored for each slot.

For each sample in the selected subset, a bit-string is generated at307. Each bit-string may be generated by the bit-string generator210. The generated bit-strings may be small, and may each have a length of one, two, or three bits, for example. In some implementations, greater length bit-strings may be generated.

The generated bit-strings are provided for estimating the similarity of documents and the document associated with the received set of samples at309. In some implementations, the similarity estimation may be an estimation of the Jaccard similarity coefficient.

Identifiers of one or more documents that are duplicates or near-duplicates of the document associated with the received set of samples are provided at311. The identifiers may be provided by similarity engine220and may identify documents with estimated similarities that are above a threshold similarity. In an implementation, the identified duplicate or near-duplicate documents may be removed from an index (e.g., the index143) or otherwise output to a user or administrator.

FIG. 4is an operational flow of an implementation of a method400for determining the similarity between two documents. The method400may be implemented by the sketch engine145of the search engine140.

A first set of samples and a second set of samples are received at401. The first set of samples and the second set of samples may be received by the sketch engine145. In some implementations, the first set of samples may include terms associated with a first document, and the second set of samples may include terms associated with a second document.

A first plurality of bit-strings is generated based on the first plurality of samples at403. The first plurality of bit-strings may be generated by the bit-string generator210based on the first plurality of samples. In some implementations, each bit-string may be a small bit-string and may be generated for selected samples from the first plurality of samples. The samples may be selected from the first plurality of samples by, for each sample, generating a sequence of bits until a predetermined bit, such as zero, is generated. The samples with the generated sequences of bits that have the greatest length may be selected.

A second plurality of bit-strings is generated based on the second set of samples at405. The second plurality of bit-strings may be generated by the bit-string generator210similarly as described above for the first plurality of bit-strings.

A similarity between the first document and the second document is estimated based on the generated first and second plurality of bit-strings at407. The similarity between the first and second documents may be determined by the similarity engine220. In some implementations, the similarity between the first document and the second document may be determined by determining a first count of the number of bit-strings from the first plurality of bit-strings and the second plurality of bit-strings that agree, and a second count of the number of bit-strings from the first plurality of bit-strings and the second plurality of bit-strings that disagree.

A determination is made as to whether the estimated similarity is greater than a threshold similarity at409. The determination may be made by the similarity engine220. The threshold may be set by a user or administrator.

If the estimated similarity is greater than the threshold similarity, the first and second documents are duplicate or near-duplicate documents, and the second document may be removed at411. For example, the second document may be removed from the index143by the similarity engine220. Otherwise, the documents are not duplicate or near-duplicate documents, and both documents may be left in the index143by the similarity engine220at413.

FIG. 5shows an exemplary computing environment in which example implementations and aspects may be implemented. The computing system environment is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality.

With reference toFIG. 5, an exemplary system for implementing aspects described herein includes a computing device, such as computing device500. In its most basic configuration, computing device500typically includes at least one processing unit502and memory504. Depending on the exact configuration and type of computing device, memory504may be volatile (such as random access memory (RAM)), non-volatile (such as read-only memory (ROM), flash memory, etc.), or some combination of the two. This most basic configuration is illustrated inFIG. 5by dashed line506.

Computing device500may have additional features/functionality. For example, computing device500may include additional storage (removable and/or non-removable) including, but not limited to, magnetic or optical disks or tape. Such additional storage is illustrated inFIG. 5by removable storage508and non-removable storage510.

Computing device500typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by the computing device500and include both volatile and non-volatile media, and removable and non-removable media.

Computing device500may contain communications connection(s)512that allow the device to communicate with other devices. Computing device500may also have input device(s)514such as a keyboard, mouse, pen, voice input device, touch input device, etc. Output device(s)516such as a display, speakers, printer, etc. may also be included. All these devices are well known in the art and need not be discussed at length here.