Date-based web page annotation

Methods and apparatus for date annotating and displaying a web page. A web page is segmented into search data fragments. A date map is searched for matching target data fragments. Stop-words and punctuation symbols can be removed from the search and target data fragments, which can be arranged in alphanumerical order. A target data fragment matches a search data fragment when the edit distance between them is less than a threshold. The publication date of a search data fragment is the publication date of a matching target data fragment, otherwise, the current date. A search data fragment with no matching target data fragment is stored in the date map with the current date. Search data fragments are displayed using indicia to convey their publication dates. Indicia include search data fragment fonts or background colors on which search data fragments are displayed.

BACKGROUND

Today, a wealth of information is published in web pages on the world-wide-web. Often, metadata, or data about the information that is itself published in web pages, is just as important as the published information itself. For example, metadata that indicates when a web page or information in the web page was first published can be just as important as the information itself. Regrettably, it is often difficult to determine when information in a web page was first published on the world-wide-web since the content of web page can change over time and the history of that content change is generally not recorded in the web page. As a result, unless the author of a web page maintains and publishes all previous versions of the page, a reader cannot usually determine whether the information in the page was published at the same time or whether different parts of the page were published at different times. In addition, a reader cannot usually determine when a given part or section of a web page was first published in the web page.

Some efforts have been made to date web pages. For example, some wiki-based websites allow users to see differences between different versions of a web page published on the wiki-based website. However, these websites only allow two versions of a web page to be compared, and the information on either version may have first been published in a third and earlier version of the page. Moreover, these websites are generally limited to comparing different versions of web pages that are published on their own website. They do not allow a user to compare or contrast different versions of arbitrary pages on the world-wide-web. Other websites do attempt to catalogue and store different versions of arbitrary pages published on the world-wide-web, however, these websites generally do not provide a convenient mechanism for automatically determining the changes that have been made to a web page as a function of time, or for automatically determining when a particular part of a web page was first added to the web page. In short, none of the existing efforts to date web pages allow a user to systematically determine when different parts of an arbitrary web page were first published on the world-wide-web.

SUMMARY

In one aspect, methods and apparatus for date annotating a web page are disclosed. The method includes receiving a web page identified by a uniform resource identifier. The web page is then segmented into one or more search data fragments, including at least one search data fragment. A date map, previously generated from the contents of the web page, is searched for a target data fragment that matches the search data fragment. The date map includes one or more data fragments taken from the web page, where each data fragment is associated with a date indicating when the data fragment was first published on the web page. If the search data fragment does not match any target data fragment in the date map, the search data fragment is added to the date map, and is associated with the current date in the date map.

In another aspect, methods and apparatus for displaying a date annotated web page are disclosed. The method includes receiving a web page identified by a uniform resource identifier. The web page is then segmented into one or more search data fragments, including at least one search data fragment. A date map, previously generated from the contents of the web page, is searched for a target data fragment that matches the search data fragment. The date map includes one or more data fragments taken from the web page, where each data fragment is associated with a date indicating when the data fragment was first published on the web page. A publication date for the search data fragment is determined based on the results from the date map search. The search data fragment is displayed within the web page using indicia to convey its publication date.

Advantages of the disclosed methods and apparatus include one or more of the following. The search data fragment and the target data fragments can have one or more stop-words removed and can have one or more punctuation symbols removed. The terms in the search data fragment and the terms in the target data fragments can be stored in alphanumerical order. A target data fragment in the date map can match the search data fragment when the edit distance between the target data fragment and the search data fragment is less than a threshold distance. If the search data fragment does not match any target data fragment in the date map, the publication date for the search data fragment based on the date map search is the current date. If the search data fragment matches a target data fragment in the date map, the publication date for the search data fragment based on the date map search is the date associated with the matching target data fragment. The indicia used to convey the publication date of the search data fragment can be the font of the search data fragment or the color of the background on which the search data fragment is displayed.

Further advantages of the disclosed methods and apparatus can include one or more of the following. An input signal conveying a search date can be received. The received input signal can be the position of a slider on a slider bar that is displayed in a graphical user interface. A search data fragment can be displayed within the web page using indicia to convey its publication date only when the search date matches the search data fragment's publication date. The search date can match the search data fragment's publication date when the search data fragment's publication date lies within a period that includes the search date.

DETAILED DESCRIPTION

InFIGS. 1A through 1D, a simple web page100is displayed in a web browser110. The web page100consists of three sentences, each of which was added to the web page and published on the world-wide-web at different times.

FIG. 1Ais an illustration of a conventional method of displaying a web page. InFIG. 1A, web page100(e.g., MyPage.com) is conventionally displayed in web browser110in a manner that lacks any indicia, and does not convey any information indicating when different parts of the page were first published. By contrast,FIGS. 1B through 1Dillustrate a method of displaying a web page that includes indicia or conveys information that indicates when different parts of the page were first published.

InFIG. 1B, when web page100contains (or web browser110receives) information that indicates when different parts of web page100were first published, web page100is displayed in a manner that conveys that information. For example, the parts of web page100that were published at different times can be displayed in different fonts. Thus, as shown inFIG. 1B, since each sentence in web page100was added to the page at a different time, each sentence in web page100is displayed in a different font. Of course, different indicia can be used to convey the information that is available in web page100or that is made available to browser110to indicate when different parts of web page100were first published. For example, the parts of web page100that were published at different times can be displayed on different background colors rather than in different fonts. Thus, colors ranging from red-to-blue can be used to convey the different times at which different parts of web page100were first published, e.g., with the oldest published parts displayed over a red background and the newest published parts displayed over a blue background, or vice-versa.

Of course, other methods of conveying the metadata available in web page100or made available to web browser110that indicates when different parts of web page100were first published are possible. For example, as shown inFIGS. 1C and 1D, the web browser110can display a slider bar130with web page100. The slider bar130can have a horizontal configuration as shown inFIGS. 1C and 1D, or a vertical configuration (not shown), or can be oriented at an arbitrary angle within the web browser display area. A slider135, positioned within the slider bar130, can be moved to an arbitrary position along the slider bar130. The web browser110can interpret the position of slider135along the slider bar130to be a time between the first time any part of web page100was published and the last time any part of web page100was published. The web browser110can then use indicia such as font or background color to display those parts of web page100that were published at the time indicated by the slider bar135or within a certain range that is centered about that time (e.g., within 1 day, 1 week or 1 month).

For example, when slider135is positioned mid-way along the slider bar130as shown inFIG. 1C, web-browser110can interpret the position of slider135to be a time halfway between the earliest time that any part of web page100was first published and the latest time that any part of web page100was first published. This time may, for example, be the time when the second sentence in web page100was first added to the page. As a result, web browser110can display the second sentence in web page100in a bold font, thereby indicating to a user that the second sentence of web page100was first added at or around the time corresponding to the position of slider135along slider bar130. The web browser110can also display (not shown) the time that corresponds to the position of slider135along slider bar135.

Similarly, when slider135is positioned further along the slider bar130as shown inFIG. 1D, web-browser110can interpret the position of slider135to be the latest time that any part of web page100was first published. This time may, for example, be the time when the third sentence in web page100was first added to the page. As a result, web-browser110can display the third sentence in web page100in a bold font, thereby indicated to a user that the third sentence of web page100was first added at or around the time corresponding to the position of slider135along slider bar130. As before, the web browser110can also display (not shown) the time that corresponds to the position of slider135along slider bar135.

FIG. 2is a schematic illustration of a system for collecting and disseminating information indicating when different parts of a web page were first published on the world-wide-web. The system disclosed inFIG. 2can be used, for example, to collect and disseminate the metadata that can be used to display web page100in the manner shown inFIGS. 1B through 1D, i.e., in a manner that indicates when different parts of the web page100were first added to the page.

The metadata collection portion of the system includes a web crawling engine210, a date annotation engine220and a data repository, which can be a conventional relational database230. When the web crawling engine210crawls a web page (e.g., web page100shown inFIGS. 1A through 1D), it stores the content of the web page in the database230. It then alerts the date annotation engine220, which can analyze the content of the web page to determine when different parts of the page were first published. Date annotation engine220can then store the results of that analysis in a date map280consisting of one or more records in database230. In addition to storing the date map280in database230, date annotation engine220can annotate the web page100with indicia to indicate when different parts of the web page were first published, and store the annotated web page in database230.

As shown inFIG. 2, except for a special informational record280i, each record in the date map280stored by date annotation engine220in database230can include the URI281(uniform resource identifier) of the analyzed web page, a data fragment282ataken from the web page, and the date283athe data fragment282awas first identified by the date annotation engine220. The date283acan subsequently be used as a proxy to indicate when the data fragment282awas first added to or published in the web page. Optionally, each record in the date map280can also include indicia284a(e.g., font size or background color) specifying how the data fragment282ashould be displayed by a web browser based upon the date283athe data fragment282awas first added to the web page.

The metadata dissemination portion of the system includes the database230, a web date server240and a web browser110or a web browser110a. Web browser110includes a plug-in250that interacts with the web date server240to retrieve metadata such as the date map280indicating when different parts of a web page were first published, and uses that metadata to annotate and display the web page with indicia indicating when different parts of the page were first published. Alternatively, a conventional web browser110acan retrieve an annotated web page directly from web date server240. The web date server240can either retrieve the annotated web page directly from database230(e.g., retrieve a web page that has been annotated and stored by date annotation engine220), or can use the metadata stored in the date map280to generate the annotated web page.

FIG. 3is a flow chart illustrating a method for collecting and storing information indicating when different parts of a web page were first published on the world-wide-web. The method can be executed, for example, by the date annotation engine220shown inFIG. 2. The date annotation engine220can begin by receiving a web page identified by a URI (300). For example, the web page can be the web page100shown inFIGS. 1A through 1D, and can be received from the web crawling engine210shown inFIG. 2. Once the web page is received, the date annotation engine220can search a data repository (e.g., database230shown inFIG. 2) for a date map that indicates when different parts of the web page were first added to the page (305). The date map can be, for example, the date map280shown inFIG. 2, and can consist of one or more database records280athat identify the web page100by its URI281and that indicate the date283athat a particular data fragment282awas first added to the web page100. If no such date map280exists for the web page100, the date annotation engine220creates one (315).

Thereafter, the date annotation engine220can segment the web page into a plurality of data fragments (320). As used herein, a data fragment is the smallest part of a web page that is analyzed to determine when that part was first added to the web page. The date annotation engine220can segment the web page into data fragments at different levels of granularity. For example, the date annotation engine220can segment the web page into data fragments consisting of chapters, sections, paragraphs, sentences, phrases, n-words (i.e., n adjacent words), words, or letters of the web page, or into any other unit into which the web page can be divided. Of course, the more finely the date annotation engine220segments the web page (i.e., the smaller the size of the data fragments), the more resources will be needed to determine, store and display the data that indicates when those data fragments were first added to the web page. The date annotation engine220can record the granularity of the data segmentation in a special informational record in the date map. For example, as shown inFIG. 2, the date annotation engine220can store the level of segmentation285in a special information record280iin the web page's date map280.

After segmenting the web page into data fragments, the date annotation engine220can identify and remove any punctuation and any so-called “stop-words” from the data fragments (325). As used herein, “stop-words” are words, like articles or prepositions, that while a part of the web page convey very little information and add very little meaning to the web page. Stop-words can include words such as “a”, “the”, “of”, “if”, “such”, and the like. While lists of stop-words can be found on the world-wide-web and elsewhere, there is no universally agreed upon list of stop-words, and any conventional or reasonable list of stop-words can be used in the method described herein. Alternatively, the date annotation engine220can be configured so that it does not remove any stop-words and/or any punctuation symbols from the web page. Of course, if the date annotation engine220does not remove any stop-words or punctuation symbols, more resources will be required to determine, store and display the data that is used to indicate when different parts of the web page were first added to the web page. When the date annotation engine220removes stop-words or punctuation from the data fragments, it can record the list of stop words or punctuation it removed in the date map's special informational record. For example, as shown inFIG. 2, the date annotation engine220can record the list of stop words286and the list of punctuation symbols287removed from the web page in the special information record280iin the date map280.

After removing any stop words or punctuation from the data fragments (325), the date annotation engine220processes each of the data fragments in a sequence (330-345), until all of the data fragments have been processed. For each data fragment taken from the web page, the date annotation engine220can search the web page's date map for that data fragment (330). For example, as shown inFIG. 2, the date annotation engine220can search for each data fragment in all the records in database230that contain the web page's URI281. If the date annotation engine220finds the current data fragment in the web page's date map (335), it processes the next data fragment in the web page, if one exists (345). If, however, the date annotation engine220fails to find the current data fragment in the web page's date map (335), it creates a new database record that contains the data fragment, the current date, and the URI of the web page, and it adds the new database record to the web page's date map (340). In addition, the date annotation engine220can also include indicia (e.g., font type or background color) in the new database record that indicates how the data fragment should be displayed when the web page is rendered by a web browser. When all of the data fragments in the web page have been so analyzed (345), the process run by date annotation engine220ends.

FIG. 4is a schematic illustration showing the information collected for different parts of a web page published at different times on the world-wide-web. As shown inFIG. 4, three different versions of a web page having a URI281(e.g., MyPage.com) are published at three different times. A first version400, which consists of a single sentence282acan be published, for example, on Mar. 1, 2010. A second version410, which adds a second sentence282bto the web page can be published, for example, on Mar. 21, 2010. And a third version420, which adds a third sentence282ccan be published, for example, on Mar. 25, 2010. The content of the web page having URI281, including the metadata indicating when different parts of the web page were first published on the world-wide-web, can be collected and stored in a date map280for the web page. The date map280can consist of a plurality of database records280a-cand a special informational database record280i. The informational database record280iidentifies the URI281of the web page, the list of stop words286and punctuation287removed from the web page, and the segmentation285used to generate data fragments from the web page. Each of the remaining database records, for example record280c, identifies the URI281of the web page, a data fragment282ctaken from the web page, the date283cthe data fragment282cwas first identified, and optionally indicia284cindicating how the data fragment282cshould be displayed when the web page is rendered. This information can be collected and stored, for example, by the date annotation engine220shown inFIG. 2using the method described above inFIG. 3.

As explained above, when the date annotation engine220receives a web page having a URI281, it searches a database230for a date map280for that web page. If no such date map exists, the date annotation engine220creates it. Next, the date annotation engine220segments the web page into one or more data fragments at a given level of granularity. For example, the date annotation engine220can segment the web page into data fragments consisting of a single sentence. As shown inFIG. 4, if the first version400of the web page consists of a single sentence, and the date annotation engine is configured to segment the web page into sentence wide data fragments, the date annotation engine220will create a date map280consisting of a special information record280iand a single data fragment record280a, both of which include the web page's URI281. The data fragment record280aalso include a single data fragment282a(consisting of the first and only sentence in version400of the web page), the publication date283aof the data fragment282a, and optionally the indicia284athat can be displayed to convey the publication date283aof the data fragment282awhen the web page is rendered.

If the web page having a URI281is crawled daily by the web crawling engine210, it will be annotated daily by the date annotation engine220. However, while the content of the web page remains unchanged, the content of the date map for the web page will also remain unchanged. It is only when the content of the web page changes, such as when a second sentence is added to the web page to create a second version410, that the date annotation engine220will discover the content change and update the web page's date map. For example, as shown inFIG. 4, when version410of the web page is first crawled and analyzed, the date annotation engine220will segment the web page into two data fragments282aand282b, each of which is a single sentence long. Next, the date annotation engine220will discover that data fragment282ais already stored in a date map280for the web page, but that data fragment282bis not. The date annotation engine220will therefore create a new data fragment record280bthat includes the web page's URI281, a single data fragment282b(consisting of the second and last sentence in version410of the web page), the publication date283bof the data fragment282b, and optionally the indicia284bthat can be displayed to convey the publication date283bof the data fragment282bwhen the web page is rendered. Similarly, when a third version420of the web page is first crawled and analyzed, the date annotation engine220will segment the third version420of the web page into three data fragments282athrough282c(each consisting of a single sentence), and will search for and discover that data fragments282aand282bare already stored in the date map280, but that data fragment282cis not. The date annotation engine220will therefore create a new data fragment record280cthat includes the web page's URI281, a single data fragment282c(consisting of the third and last sentence in version420of the web page), the publication date283cof the data fragment282c, and optionally the indicia284cthat can be displayed to convey the publication date283cof the data fragment282cwhen the web page is rendered.

FIG. 5is a flow chart illustrating a method for displaying a web page in a manner that illustrates when different parts of the web page were first published. The method can be executed, for example, by the web browser110shown inFIG. 2. The web browser110can include a plug-in250that allows it to access the contents of database230through a web date server240. The web browser110can begin by receiving a web page identified by a URI (500). For example, the web page can be the web page100shown inFIGS. 1A through 1D. Once the web page is received, the web browser110can search a database for a date map that indicates when different parts of the web page were first added to the page (505). For example, as shown inFIG. 2, the web-browser can search a database230(via a web date server240) for a date map280whose records contain the URI281of the web page. The date map280can include a special informational record280iand one or more data fragment records280a, each of which identify the web page by its URI281. If the browser110does not find a date map for the web page100, the browser110can display the web page100in a conventional manner (515). For example, the web browser110can display the web page100in the manner shown inFIG. 1A, which lacks any indicia or information indicating when different parts of the web page100were first published.

If, however, the web browser110finds a date map for the web page100in the database230, the web browser110segments the web page100into a plurality of data fragments at the same level of granularity as the level used to generate the web page's date map (520). This can be done, for example, by retrieving from the web page's date map the level of segmentation that was used to create the date map. For example, as shown inFIG. 2, the web browser110can read the special informational record280iof the web page's date map280to determine the segmentation285that was used to generate the date map. The web browser110can then segment the received web page at the same level of segmentation.

Next, the web browser110can identify and remove any punctuation and any so-called “stop-words” from the data segments (525) in the same manner that stop-words and punctuation were removed from the data segments when the web page's date map was created. This can be done, for example, by retrieving from the web page's date map the list of stop-words and the list of punctuation that was removed (if any) from the data segments when the web page's date map was created. For example, as shown inFIG. 2, the web browser110can read the special informational record280iof the date map280to determine the list of stop-words286and punctuation287that were removed from the data fragments (if any) when the web page's date map was created. Once the web browser110removes the stop words and punctuation (if any) from the data fragments, it processes each of the data fragments in a sequence (530-550), until all of the data fragments have been processed.

FIG. 6is flow chart illustrating an alternate method for displaying a web page in a manner that illustrates when different parts of the web page were first published. The method can be executed, for example, by the convention web browser110ainteracting with the web date server240shown inFIG. 2. As shown inFIG. 6, the web browser110areceives the URI for a web page (600), and sends the URI to the web date server240(605).

In one embodiment, the web date server240receives the URI from the web browser110a(650), then requests and receives the web page from the website identified by the URI (655). Once the web page is received, the web date server240can use a modified version of the method disclosed inFIG. 5to annotate the web page with indicia indicating when different parts of the web page were first published. In particular, the web date server240can segment the web page into data fragments (660), search a database for a date map that contains metadata indicating when the different data fragments were first published on the web page (665), and annotate the web page with indicia indicating when the different fragments were first published using the publication metadata (670). It is to be noted herein that whereasFIG. 5discloses displaying the web page in a conventional manner when no date map is found for the web page (515), the web date server240would instead not annotate any of the data fragments in the received web page. Similarly, whereasFIG. 5discloses displaying a data fragment per the current date (540) or the date stored in the date map (545), the web date server240would instead annotate the web page with indicia indicating the data fragment was first published on the current date or the date stored in the date map. Once the web date server240has annotated the web page (670), it returns the annotated web page to the browser110a(675). The browser110areceives the annotated web page from the web date server240(610), and displays it (615). For example, the browser110acan display the annotated web page in the manner shown inFIGS. 1A through 1D.

In another embodiment (not shown), when the web data server240receives the URI of the web page from the web browser110a, rather than retrieving the web page from the website identified by the URI, the web data server240searches for a date annotated version of that web page a in data repository such as the database230shown inFIG. 2. A date annotated version of the web page could have been created and stored in the database, for example, by the date annotation engine220as described above. If the web data server240finds a date annotated version of the web page in the data repository, it retrieves the date annotated version from the database and sends it the web browser110a, where it is displayed. If, however, the web data server240does not find a data annotated version of the web page in the data repository, it returns an error message to the web server110a, which then displays the web page without annotation.

While the invention has been described with respect to the methods and apparatus disclosed inFIGS. 1 through 6above, variations in these methods and apparatus are possible and within the scope of the invention. For example, inFIGS. 3and5above, a web page's data map is searched to determine whether the date map contains a target data fragment that “matches” a query data fragment. The degree of matching required can, of course, be variable. For example, the degree of matching can be exact, in which case the target data fragment will only “match” the query data fragment if the two data fragments are identical. Alternatively, the degree of matching can be less than exact, in which case the target data fragment will “match” the query data fragment if the edit distance between the two data fragments is less than a threshold distance. As is well known in information theory, the edit distance between two strings is the number of operations required to transform one string into the other. Thus, the smaller the edit distance between two strings, the closer the strings “match” one another. Various algorithms for determining and computing the edit distance between strings are known to those of skill in the art, including the Hamming distance and the Levenshtein distance, and can be used to determine whether a query data fragment taken from a recently received version of a web page “matches” a target data fragment recorded in the web page's date map. Allowing less than exact matching between the query data fragment and the target data fragment reduces the sensitivity of the disclosed method and apparatus to minor changes to the content of a web page. Thus, only significant changes to the web page will be detected and recorded, where the degree of significance is measured by the size of the threshold distance. The larger the threshold distance, the bigger or more significant the changes to the web page must be before they are recorded.

Similarly, in some implementations, especially where the web page is segmented into data fragments consisting of sentences, phrases, or n words, it is possible to ignore the ordering of the words within the data fragments when determining whether a query data fragment “matches” a target data fragment. In these implementations, the words in the data fragments can be sorted in alphabetical or alphanumerical order when they are created, and stored in that order to make the comparison between the query and target data fragments easier. Disregarding the ordering of words within data fragments also reduces the sensitivity of the disclosed method and apparatus to minor changes to the content of a web page.

Method steps may be performed by one or more programmable processors executing a computer program to perform functions by operating on input data and generating output. Method steps also may be performed by special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit).

Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read-only memory or a random access memory or both. Elements of a computer may include at least one processor for executing instructions and one or more memory devices for storing instructions and data. Generally, a computer may also include, or be operatively coupled to receive data from and/or transfer data to, one or more mass storage devices, e.g., magnetic, magneto-optical disks, or optical disks. Information carriers suitable for embodying computer program instructions and data include all forms of non-volatile memory, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks. The processor and the memory may be supplemented by, or incorporated in special purpose logic circuitry such as an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit).

To provide for user interaction, the disclosed methods or apparatus may be implemented on a computer having a display device for displaying information to the user, e.g., a cathode ray tube (CRT) or liquid crystal display (LCD), a keyboard, and a pointing device such as a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide for use interaction. For example, feedback can be provided to the user as visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in the form of speech or tactile input.

The methods and apparatus disclosed herein may be implemented in a computing system that includes a back-end component, e.g., a data server, or that includes a middleware component, e.g., an application server, or that includes a front-end component, e.g., a client computer having a graphical user interface or a Web browser, or through any combination of such back-end, middleware, or front-end components. System components may be interconnected by any form of communication network, such as a local area network (LAN), a wide area network (WAN), or the Internet.

While certain features of the described methods and apparatus have been illustrated as described herein, many modifications, substitutions, changes and equivalents will occur to those skilled in the art. All such modifications, substitutions, changes and equivalents fall within the scope of following claims.