Document similarity is a topic that has been studied extensively for decades in the field of information retrieval and for data engineering. Document similarity techniques commonly involve comparing a pair of documents to determine how related the two may be. The similarity of documents has been determined based on the similarity of text and images or other content and based on the similarity of the layouts of the documents.
Comparing layouts typically allows determining that two documents are similar regardless of how the content may or may not match. Determining how similar the layouts of documents are to one another has various applications. For example, phone bills issued to a subscriber from a same company generally have a same layout but differ in content from one month to the next. Although a content similarity analysis can result in a finding of dissimilarity, a layout similarity can identify that two phone bills are related. As such, if the subscriber is more interested in finding whether two documents are phone bills rather than whether the phone bills are for the same month, the layout similarity analysis may provide a good solution.
Further, a layout similarity analysis can be performed using a low-level representation or a high-level representation of the compared documents. An example of the former representation includes comparing bit maps of the documents. Although easy to compute, this type of representation does not capture the inherent layouts of the documents and, thus, can be inaccurate. An example of the latter representation includes partitioning the documents into portions of M rows and N columns (M and N being integers) and comparing equivalent portions, such as the top-left portion of one document to the top-left portion of another document. The comparison involves assessing an amount of pixel area in each of the portions (e.g., total amount of text, image, etc. in the top-left portions). However, this type of representation can also lead to inaccurate results. For example, although two phone bills may have a similar layout, the pixel area within each portion may change from one month to the next (e.g., if the top-left corner represents a list of calls made in a month, that list can be blank—no calls—in one month and can be full—a large volume of calls—in the next month). In another example, two magazine pages may have a similar layout but an image may be found in the top-left corner in one magazine and in the top-right corner in the other magazine. In both examples, a layout analysis using a high-level representation can incorrectly result in a dissimilarity finding.