Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-10-06
2003-09-02
Vu, Kim (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06615209
ABSTRACT:
§1. BACKGROUND OF THE INVENTION
§1.1 Field of the Invention
The present invention concerns information retrieval in general. More specifically, the present invention concerns detecting and/or removing duplicate information or duplicate content in response to, and based on, an information search query.
§1.2 Related Art
§1.2.1 The Migration from Data Entry, Manipulation and Storage, to Information Access
The ways in which people use computing machines has evolved over the last 50 or so years. The proliferation of networks, along with the increased availability of inexpensive data storage means, has afforded computer users unprecedented access to a wealth of content. Such content may be presented to a user (or “rendered”) in the form of text, images, audio, video, etc.
Although people continue to use computers to enter, manipulate and store information, in view of the foregoing developments, people are using computers (or more generally, information access machines) to access information to an ever increasing extent. Unfortunately, however, the very vastness of available information which has attracted many users, can overwhelm users. Consequently, desired information can become difficult to find.
§1.2.2 Known Techniques for Finding Desired Information
Various techniques have been employed to help users locate desired information. In the context of the Internet for example, some services have organized content based on a hierarchy of categories. A user may then navigate through a series of hierarchical menus to find content that may be of interest to them. An example of such a service is the YAHOO™ web site on the Internet.
Again in the context of the Internet for example, some services provide “search engines” which search content or “web sites” pursuant to a user query. In response to a user's query, a rank ordered list, which typically includes brief descriptions of the content, as well as hyper-text links (i.e., text, having associated URLs) to the content is returned. The rank ordering of the list is typically based on a degree of match between words appearing in the query and words appearing in the content.
§1.2.2.1 Automated Indexing and its Perceived Shortcomings
Most search engines perform three main functions: (i) crawling the World Wide Web; (ii) indexing the content of the World Wide Web; and (iii) responding to a search query using the index to generate search results. The crawl operation collects web pages. The indexing operation associates document(s) (e.g., web page(s)) with words or phrases, and also creates an inverted index which associates words or phrases with documents. The search operation then (i) uses that inverted index to find documents (e.g., web pages) containing various words of a search query, and (ii) ranks or orders the documents found in accordance with some heuristic(s). Given the large amount of information available, these three main functions are automated to a large extent.
Although it is believed that automating the indexing operation is the only way to make searching a large amount of diverse material feasible, automating indexing operations introduces some challenges. More specifically, one of the problems of automated indexing is that the World Wide Web may include the same information duplicated in different forms or at different places on the World Wide Web. For example, some content is “mirrored” at different sites on the World Wide Web. Such mirroring is used to alleviate potential delays when many users attempt to request the same information at the same time, and/or to minimize network latency (e.g., by caching web pages locally). Some content will have plain text and HTML (hyper-text markup language) versions so that users can render or download the content in a form that they prefer. Finally, some web pages aggregate or incorporate content available from another source on the World Wide Web.
When users submit a query to a search engine, most users do not want links to (and descriptions of) web pages that have duplicate information. For example, search engines typically respond to search queries by providing groups of ten results. If pages with duplicate content were returned, many of the results in one group may include the same content. Thus, there is a need for a technique to avoid providing search results to web pages having duplicate content.
Some duplicate avoidance techniques are effected during the automated indexing operation. Similar documents can be flagged by (i) defining a similarity measure between two documents, and (ii) defining the two documents as “duplicates” if the similarity measure exceeds a predetermined threshold.
Unfortunately, however, often duplicate information may be found in documents that are not exactly the same or even very similar. For example: (i) identical content may be presented with different formatting. (e.g., plain text versus HTML); (ii) different headers and/or footers may be prepended and/or appended, respectively, to identical content; (iii) hit counters may be appended to identical content; (iv) last modified dates may be appended, to identical content; and (v) one web site may include a copy of content found elsewhere (e.g., as a part of a compilation or aggregation of content, or simply as an insertion). Cases (ii)-(iv) are illustrated by the Venn diagrams of
FIGS. 1 and 2
.
FIG. 1
illustrates the case where a second document merely adds a small amount of information (e.g., a counter, a footer, etc.) to a first document, whereas
FIG. 2
illustrates the case where a second document slightly changes some information (e.g., a last modified date) of a first document. The present invention may be used to detect such “duplicates” with slight changes.
Furthermore, the present invention may be used to detect duplicate content within documents that have a lot of different information, such as documents with different formatting codes or documents that aggregate or incorporate other content. Many prior techniques are not well-suited for such cases. For example, assume that documents A and B each contain basic financial information about companies. Assume further that document A has information on 50 companies, while document B has information on 100 companies, at least some of which are the same as those in document A. (For example, document B could be a later, expanded version of document A.) The Venn diagrams of
FIGS. 3 and 4
illustrate such examples.
Many known document similarity techniques would not consider documents A and B to be very similar even though they may contain a lot of identical content. A user searching for information about the 50 companies included in document A, however, would likely become frustrated if a search engine provides links not only to document A, but also to other documents (e.g., document B) that contain the same information about the 50 companies. The articles, A. Broder et al, “Syntactic Clustering of the Web,” Proc. 6
th
International WWW Conference (1997), A. Broder et al, “Filtering Near-Duplicate Documents,” FUN' 98 and A. Broder et al, “On the Resemblance and Containment of Documents,” SEQUENCES' 98, pp. 21-29 (hereafter referred to as “the Broder articles”) describe a method (hereafter referred to as “the Broder method”) for detecting duplicate documents. The Broder method may be used to find documents that are “roughly the same” and “roughly contained” in each other. More specifically, for each pair of documents, the Broder method generates a number that indicates the extent to which the documents appear to be related. A threshold is then used to determine whether or not the two documents are related enough (or similar enough) to be declared “duplicates”. The Broder method, however, does not consider the specific information that a user is looking for in its analysis.
In view of the foregoing, there is a need for an improved duplicate detection technique. Such a technique should be automated so that processing a large amount of content from a large number of sources is feasible.
§2. SUMMARY OF THE INVENTION
The present inventio
Gomes Benedict
Smith Benjamin Thomas
Google Inc.
Liang Gwen
Pokotylo John C.
Straub & Pokotylo
Vu Kim
LandOfFree
Detecting query-specific duplicate documents does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Detecting query-specific duplicate documents, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detecting query-specific duplicate documents will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3070146