US20100287152A1 - System, method and computer readable medium for web crawling - Google Patents

Abstract

In a web crawler, a URL selection module selects URLs for pages to be downloaded. The URL selection module accesses an interaction data store that stores interaction data for web pages, including interaction data that indicates human interactions with the pages. To reduce the effects of link farms, the URL selection module filters the URLs to select only those URLs that have human interaction histories and provides the selected URLs to a download module for web page downloading.

Description

FIELD OF THE INVENTION
• This invention relates to a system, method and computer medium for crawling the web to find relevant internet content.
BACKGROUND OF THE INVENTION
• In internet technology, web crawlers are used to find new web pages by collecting and following URLs (Uniform Resource Locators). By following an URL and downloading the corresponding web page the links within that web page can be added to the web crawler's URL collection. The web pages are stored for indexing and ranking by internet search engines. Internet search engines use web page ranking algorithms that relate the links within a web page to the relevance of the web page.
• The use of link popularity algorithms to rank web pages has lead to the problem of “link farms”. In order to manipulate a web page's ranking, a large sub-web of interlinked web pages is created and linked to a web page so that the page receives a high search engine ranking. In addition to distortion of web page rankings, a problem with link farms is that a web crawler spends a lot of resources following links and collecting web pages for eventual indexing into a search engine, even though many of these pages are created only for page ranking and are not otherwise used by, nor useful for humans.
• What is required is a system, method and computer readable medium that provides enhanced web crawling.
SUMMARY OF THE INVENTION
• In one aspect of the disclosure, there is provided a method for web crawling comprising determining a plurality of Uniform Resource Locators (URL)s, determining a subset of the plurality of URLs that have associated interaction data, selecting at least one URL of the subset, and downloading a web page corresponding to the at least one selected URL.
• In one aspect of the disclosure, there is provided a web crawler comprising at least one Uniform Resource Locator (URL) data store that stores a plurality of URLs, at least one interaction data store that stores interaction data for a plurality of web pages, at least one download module that downloads web page content corresponding to a URL, and at least one URL selection module in communication with the at least one URL data store and the at least one interaction data store. The interaction data indicates an interaction between a human and a web page corresponding to a URL. The at least one URL selection module selects at least one URL from the at least one URL data store that has interaction data in the at least one interaction data store. The at least one URL selection module provides the at least one selected URL to the at least one download module.
• In one aspect of the disclosure, there is provided a computer-readable medium comprising computer-executable instructions for execution by a processor, that, when executed, cause the processor to select a Uniform Resource Locator (URL) from a URL data store, look up the selected URL in an interaction data store to determine if interaction data exists for the selected URL in the interaction data store, and if interaction data exists for the selected URL, provide the selected URL to a download module.
BRIEF DESCRIPTION OF THE DRAWINGS
• Reference will now be made, by way of example only, to specific embodiments and to the accompanying drawings in which:
• FIG. 1 illustrates a web crawler in accordance with an embodiment of the disclosure;
• FIG. 2 illustrates a method for web crawling;
• FIG. 3 illustrates a method for downloading web pages in the web crawler ofFIG. 1;
• FIG. 4 illustrates a method of a URL selection module;
• FIG. 5 illustrates a system for recording and analyzing event data;
• FIG. 6 illustrates an event header message;
• FIG. 7 illustrates an event stream message;
• FIG. 8 illustrates an alternative web crawler embodiment;
• FIG. 9 illustrates an alternative method of the URL selection module;
• FIG. 10 illustrates a processor and memory of a URL selection module;
• FIG. 11 illustrates an instruction set that may be executed on the processor and memory ofFIG. 10; and
• FIG. 12 illustrates the processor and memory ofFIG. 10 in association with a processor and memory of an download module.
DETAILED DESCRIPTION OF THE EMBODIMENTS
• Asystem10 for providing web crawling in accordance with an embodiment of the disclosure is illustrated inFIG. 1. In thesystem10, aweb crawler12 provides URL requests21 to theinternet20 and downloadsweb pages22 corresponding to the URL requests. Theweb crawler12 includes adownload module14 that downloads theweb pages22 and provides theweb pages22 to a webpage data store15. Theweb crawler12 also includes aURL data store16, aURL selection module18 and aninteraction data store19. While the components of the web crawler are shown within theweb crawler12, a person skilled in the art will readily understand that these components may be provided in a distributed form. For example, the various data stores may be co-located with processing modules such as thedownload module14 orURL selection module18. Alternatively, the various data stores may be located offsite with data retrieval occurring through appropriate communication links.
• A web crawling method using thesystem10 ofFIG. 1 is illustrated in theflowchart100 ofFIG. 2. Atstep101, theURL selection module18 determines from the URL data store16 a plurality of URLs for which web page content is to be downloaded. The URLs may represent new web pages or web pages for which web page content, ranking statistics etc have not been updated for a period of time. Atstep102, theURL selection module18 accesses theinteraction data store19 to determine which URLs have interaction data associated with them. URLs for which interaction data exist are formed into a subset. At least one URL is selected from the subset (step103) and provided to thedownload module14 so that the web page corresponding to the URL can be downloaded (step104).
• Thedownload module14downloads web pages22 from theinternet20 and extracts linkedURLs13 from the download pages. The operation of the download module in accordance with an embodiment of the disclosure is illustrated in theflowchart200 ofFIG. 3. The download module receives aURL11 to fetch from theURL selection module18 atstep201. Thedownload module14 sends aURL request21 to an appropriate web server within the internet20 (step202) and downloads theweb page22 corresponding to theURL request21 from the internet20 (step203). Atstep204, thedownload module14 extracts anyURLs13 found within theweb page22. These URLs are added to the URL data store16 (step205). As is known, duplicate URLs are not stored multiple times and links extracted from web pages may need to be normalized into their respective URLs. Theweb page22 is also loaded into the web page data store15 (step206).
• The operation of theURL selection module18 in accordance with an embodiment of the disclosure is shown in theflowchart300 ofFIG. 4. Atstep301, theURL selection module18 reviews theURL data store16 for URLs that have not yet been submitted to thedownload module14. Atstep302, theURL selection module18 accesses theinteraction data store19 to determine the subset of the selected URLs that have interaction data records. The URL selection module then selects the highest ranked URLs according to human interaction behavior (step303). In general, there are at least two types of human interaction behaviour that may be considered. There is a first type of human interaction in selecting a link (URL) that corresponds to a web page, even though the selected linked URL/web page may not have been downloaded and may not have any interaction data. This “human interaction” uses the analysis of the source element ranking and attention shift that happens in the various web pages that link to the URL/web-page-of-interest. Another case of “human interaction” utilizes the content of interest ranking within the URL/web-page-of-interest. This helps rank the importance of this URL in the link-graph. That is, how much, if any, content on the web-page/URL gets human attention time (independent of any links within the page). In ranking the URLs, a specific human behavior is an out-click of the URL on web pages that have the URL as a link. One ranking measure for human out-clicks may be the ratio of human out-clicks to total interaction exits per web page that display the URL as a link. Another ranking could rely on the attention ranking of the content area containing the URL/link (the location of the URL/link within human attentive areas of the web pages containing the URL as a link). Within the web page corresponding to a URL, the most preferred URLs have corresponding web pages that have highly ranked content areas, ranked by the amount of human attention, e.g time, that those content areas receive. Other ranking and selection policies may be applied to filter the URLs atstep304 and a filtered set of the URLs is sent to the download module atstep305, returning the cycle to step201 ofFIG. 3.
• The interaction data in theinteraction data store19 may be derived from interactions between users and the web page at client browsers, for example as described in any of the Applicant's co-pending patent applications Attorney Docket Nos. HAUSER001, HAUSER002, HAUSER006, HAUSER007, HAUSER007B, HAUSER008, HAUSER009, HAUSER010, the entire contents of each of which are explicitly incorporated herein by reference. In particular, event recorders provided within the web pages may record event data during these interactions and provide event streams to an event server. An example of an event data processing system is illustrated inFIG. 5. In thesystem110, aclient118 provides web page requests113 to aweb server114, in response to which, theweb server114 providespage content111 for display in abrowser115 of theclient118. Typically, theweb page111 will includevisible content127 as well as javascript applications.
• Theweb server114 may be modified such that the web page content provided to theclient118 includes anevent observer module126 which may be provided as appropriate code or scripts that run in the background of the client'sbrowser115. In one embodiment, code for providing theevent observer module126 is provided to theweb server114 by a third party service, such as provided from anevent server112, described in greater detail below.
• Theevent observer module126 observes events generated in a user interaction with theweb page111 at theclient118. Theevent observer module126 records events generated within theweb browser115, such as mouse clicks, mouse moves, text entries etc., and generates event streams121 including anevent header message122 and one or moreevent stream messages123. It will be apparent to a person skilled in the art that terms used to describe mouse movements are to be considered broadly and to encompass all such cursor manipulation devices and will include a plug-in mouse, on board mouse, touch pad, pixel pen, eye-tracker, etc.
• Theevent observer module126 provides the event streams121 to theevent server112. An example of anevent header message30 is illustrated inFIG. 6 and an example of anevent stream message40 is illustrated inFIG. 7. Themessages30,40 show a number of components that can be included, though in various embodiments, not all of these components may be required and additional components may be added. Primarily, anInteraction_ID32,42 uniquely identifies an interaction between theclient18 and theweb server14 and aids to identify theparticular event stream121. Theevent header message30 and theevent stream message40 may also identify the Uniform Resource Locator (URL)31,41. Fixed parameters such as theoperating system33 andbrowser type34 may form part of theevent header message30.Screen parameters36,46 such as the screen size, depth and orientation may be included in either or both of theevent header message30 or theevent stream message40. Acapture event stream43 and abubble event stream44 specifies the events recorded in respective event capture and bubbling phases during the web page interaction. Each event may be indicated by the event type, time and x/y location relative to the viewport. Not all web browser types support event capture, and thus thecapture event stream43 may be empty. Where required, events missing from the event bubble stream may be inferred, for example as described in the Applicant's co-pending application Attorney Docket No. HAUSER002, referenced above. Anevent_count field45 may indicate the total number of unique events observed by the event observer module including those events not included in theevent stream message40 due to a current sampling function excluding them. Timingparameters48 may indicate the relevant period over which theevent stream message40 is current.
• During an interaction with theweb page111, a user navigates theweb page111 and may enter content where appropriate, such as in the HTML form elements. During this interaction events are generated and recorded by theevent observer module126. Periodically, theevent observer module126 formulates anevent stream message123 preceded by anevent header message122 if one has not yet been sent. Theevent observer module126 passes theevent stream messages123 to anevent module125 of theevent server112. In the embodiment illustrated inFIG. 5, theevent stream121 is provided directly to theevent module125. However, theevent stream121 may also be provided indirectly, e.g. via theweb server114.
• Theevent server112 processes theevent stream121 in theevent module125 or an equivalent component, to analyze the event stream data. Analyzed data may be stored with the raw event stream messages in acontent data store128. Additional modules of the event server may include anattention analysis module139 as described in the Applicant's co-pending application HAUSER008 reference above, and a contentinterest processing module138 as described in the Applicant's co-pending application HAUSER009 referenced above. In one embodiment, the event stream data can be analyzed to determine the probability that the interaction that created the event stream at the client is a human dependent interaction, for example as described in the Applicant's co-pending patent application Attorney Docket No. HAUSER001 referenced above. In the present embodiment, the existence of any human interaction within the content areas of the web page, such as hints, lingers or clicks within the content areas, may be used to indicate the validity of a URL, and such statistics may be loaded into theinteraction data store19. In one embodiment, theweb crawler12 may include theevent server112 such that the web crawler is self contained. In an alternative embodiment, human interaction data may be provided to the interaction data store as a third party service by an event server operator. Alternatively, theevent server112 may maintain its own interaction data store and provide access to the interaction data store as a service.
• Theinteraction data store19 may store raw event streams with processing of the event streams being performed by theURL selection module18, for example to rank the URLs according. Alternatively, the interaction data store may have an associated processing module (not shown) that pre-processes the interaction data so that the interaction data store stores the URLs in a ranked form. For example, a processing module may process the event streams to determine an event generator type (e.g. human, non-human, computer assisted human, etc) as described in the Applicant's co-pending patent application HAUSER001 and HAUSER006 referenced above. Once an interaction with a webpage has been classified as a human interaction, the data may be further processed to rank the particular behavior of the interactions. For example, the event streams may be processed to select those events streams containing out-click events, i.e. events that a user produces to exit a web page. The event streams and/or the page content may also be analyzed to determine additional preferred behavior, such as a breadth-first traversal of the web site, backlink count, partial page-rank calculations, page-rank calculations using a link graph with URLs only if those URLs have sufficient human interaction, etc. In one embodiment, the interaction pattern for parked pages, link farms, auto generated “spam” pages (that use random snippets from a variety of authentic web pages just to get high search engine ranking based on the keywords in the snippets) may be identified and used to remove these URLs from the crawl graph (not pursue the links) and/or remove such URLs from page-rank calculations.
• A summary of the event statistics including any data used to rank the web pages may be stored in theinteraction data store19.
• An alternative embodiment is illustrated inFIG. 8. In this embodiment, theweb crawler212 is modified to include a contentinterest data store218, which may be the same as the content interest data store described in the Applicant's co-pending application Attorney Docket No. HAUSER009 referenced above. The contentinterest data store218 may store content interest data including a content interest score that ranks the various elements of a web page by the interest they receive during interactions between users and the respective web page. In one particular embodiment, the elements are document object model (DOM) elements of the web page. Content interest may be derived from an attention analysis of the event streams to determine where a user's attention focus was directed during an interaction, as described in the Applicant's co-pending application Attorney Docket No. HAUSER008 referenced above.
• An operation of thedownload module214 is illustrated in theflowchart400 ofFIG. 9. Steps401-405 are equivalent to steps201-205 of thedownload module14 described with reference toFIG. 3 above. Once the URLs found within a web page are added to theURL data store16 atstep405, the content interest data store217 may be queried (step406) to determine if the web page being downloaded has content interest data. If no content interest data is available, the process proceeds as before by storing the web page content into the web page data store15 (step407). If content interest data is available, then the page elements may be ranked by their respective content interest score (step408). Atstep409, a filter policy may be applied to the content elements. For example, content elements may be filtered for the most interesting content or for content above a certain threshold content interest score. Alternatively, content elements, such as DOM elements, may be grouped by similar content interest scores for an indexer or search engine. After filtering, the content elements of the web page, or at least those elements that pass the filter, may be stored in the web page data store15 (step410).
• In a further embodiment, the modifiedweb crawler212 ofFIG. 8 may be used to apply alternative URL selection policies in theURL selection module18. In one embodiment, the URL selection module may select only URLs having human out-clicks, where the source element, i.e. the content element where a user's attention was directed prior to the out-click event, is a content element with a high content interest score. This selection policy requires a data correlation between the last content element to have the focus of the user's attention and the link (URL) of a human out-click. Such a data correlation may be built from the event stream and attention analysis data.
• An alternative URL selection policy may specify that URLs (or human out-click URLs) will only be followed if there is some form of human area of interest within the page where the URL was found, e.g. a content element with a high enough content interest score. A further alternative URL selection policy may specify that URLs (or human out-click URLs) will only be followed if they are found within a content element with high enough content interest.
• The URL selection policies followed by the URL selection module focus the web crawlers resources towards those web pages that are actively used by humans and thus generate particular attention events. Using the selection policies may significantly increase the efficiency of the web crawler and assist in providing higher quality page ranking statistics. Furthermore, as described above, common human browsing patterns, can be recognized via attention analysis for link farm pages, parked pages where the most interesting content is advertisements, and auto-generated “spam” pages. Human outclicks on pages that have no content of interest other than ads can be ignored by the URL selection module.
• The embodiments described herein provide an enhanced system and method for web crawling that avoids spending resources collecting web pages that are not useful to humans. The effect of these embodiments is to reduce or eliminate the advantages of a link farm and to remove search engine spam. At current internet growth rates, the requirement to crawl less of the internet can provide large resource savings as well as making page ranking of web pages more efficient and useful for humans. By focusing crawling to the web pages relevant to and used by humans, the ability of artificially manipulate search engine rankings is reduced.
• Theweb crawler12 may be embodied in hardware, software, firmware or a combination of hardware, software and/or firmware. In a hardware embodiment, components of theweb crawler12 may be embodied in a device, such as server hardware, computer, etc. For example, theURL selection module18 may include aprocessor61 operatively associated with amemory62 as shown inFIG. 10. Thememory62 may store instructions that are executable on theprocessor61. In addition, thememory62 may provide elements of theURL data store16 and/orinteraction data store19. Aninstruction set500 that may be executed on the URLselection module processor61 is depicted in the flowchart ofFIG. 11. Specifically, when executed, theinstruction set500 allows the processor to select (step501) a URL from the URL data store and look up the URL in the interaction data store to determine if interaction data for the URL exists (step502). If interaction data does exist, theprocessor61 provides the selected URL to the download module. The download module may also be embodied in hardware and have aprocessor71 and operatively associatedmemory72 as shown inFIG. 12. Thedownload module processor71 may communicate with the URLselection module processor61 by an appropriate communication link. If appropriate, aspects of the URL selection module may be performed by the download module. For example, the download module may perform ranking of the URLs to be downloaded or may choose to ignore URLs provided by the URL selection module if content interest data for a URL is unavailable or indicates an insufficient content interest score.
• Although embodiments of the present invention have been illustrated in the accompanied drawings and described in the foregoing description, it will be understood that the invention is not limited to the embodiments disclosed, but is capable of numerous rearrangements, modifications, and substitutions without departing from the spirit of the invention as set forth and defined by the following claims. For example, the capabilities of the invention can be performed fully and/or partially by one or more of the blocks, modules, processors or memories. Also, these capabilities may be performed in the current manner or in a distributed manner and on, or via, any device able to provide and/or receive information. Further, although depicted in a particular manner, various modules or blocks may be repositioned without departing from the scope of the current invention. Still further, although depicted in a particular manner, a greater or lesser number of modules and connections can be utilized with the present invention in order to accomplish the present invention, to provide additional known features to the present invention, and/or to make the present invention more efficient. Also, the information sent between various modules can be sent between the modules via at least one of a data network, the Internet, an Internet Protocol network, a wireless source, and a wired source and via plurality of protocols.

Claims (20)

1. A method for web crawling comprising:

determining a plurality of Uniform Resource Locators (URL)s;

determining a subset of the plurality of URLs that have associated interaction data;

selecting at least one URL of the subset; and

downloading a web page corresponding to the at least one selected URL.

2. The method according toclaim 1 wherein determining the subset comprises:

accessing an interaction data store that stores interaction data that associates a URL with an interaction with a web page corresponding to the respective URL; and

selecting a URL into the subset if a web page corresponding to the URL has interaction data.

3. The method according toclaim 2 comprising ranking the subset of URLs using the interaction data.

4. The method according toclaim 3 wherein the interaction data indicates one or more out-click events from the corresponding web page of an associated URL and wherein ranking the subset of URLs comprises ranking the URLs dependent on the one or more out-click events.

5. The method according toclaim 4 wherein ranking a URL is dependent on a source content element of the web page prior to an out-click event.

6. The method according toclaim 5 wherein ranking a URL is dependent on an attention analysis ranking of the source content element.

7. The method according toclaim 3 wherein selecting at least one URL comprises selecting a highest ranked URL.

8. The method according toclaim 2 comprising selecting a URL into the subset if a web page corresponding to the URL has interaction data that indicates at least one human dependent interaction with a web page associated with the URL.

9. The method according toclaim 1 wherein downloading a web page comprises determining content interest of one or more content elements of the web page.

10. The method according toclaim 9 comprising storing content elements that satisfy a threshold content interest requirement.

11. The method according toclaim 1 wherein said downloading comprises providing the subset of URLs to a download module.

12. The method according toclaim 1 further comprising storing the interaction data comprising:

receiving an event stream from an interaction between a user and a web page;

analyzing the event stream; and

storing the analyzed event stream in association with a URL for the respective web page.

13. A web crawler comprising:

at least one Uniform Resource Locator (URL) data store that stores a plurality of URLs;

at least one interaction data store that stores interaction data for a plurality of web pages, the interaction data indicating an interaction between a human and a web page corresponding to a URL;

at least one download module that downloads web page content corresponding to a URL; and

at least one URL selection module in communication with the at least one URL data store and the at least one interaction data store;

wherein the at least one URL selection module selects at least one URL from the at least one URL data store that has interaction data in the at least one interaction data store; and

wherein the at least one URL selection module provides the at least one selected URL to the at least one download module.

14. The web crawler according toclaim 13 further comprising:

at least one content interest data store that stores an attention ranking of one or more content elements of a web page; and

at least one web page data store;

wherein the download module is configured to:

utilize the at least one content interest data store to determine a content interest score of one or more content elements of a downloaded web page; and

store the one or more content elements of the downloaded web page in the at least one web page data store dependent on the respective content interest score.

15. The web crawler according toclaim 14 wherein the at least one web page data store is configured to group content elements of a plurality of web pages according to their content interest score.

16. The web crawler according toclaim 13 comprising an event server that:

receives at least one event stream generated during an interaction with a web page on a client browser;

analyzes the event stream; and

stores the analyzed event stream in the interaction data store.

17. The web crawler according toclaim 16 wherein the event server analyzes the at least one event stream to determine an event generator type of the event stream.

18. The web crawler according toclaim 13 wherein the at least one interaction data store receives interaction data from an event server.

19. A computer-readable medium comprising computer-executable instructions for execution by a processor, that, when executed, cause the processor to:

select a Uniform Resource Locator (URL) from a URL data store;

look up the selected URL in an interaction data store to determine if interaction data exists for the selected URL in the interaction data store; and

if interaction data exists for the selected URL, provide the selected URL to a download module.

20. The computer readable medium according toclaim 19 comprising computer-executable instructions for execution by the processor, that, when executed, cause the processor to:

select a plurality of URLs from the URL data store that have corresponding interaction data in the interaction data store;

rank the plurality of URLs according to out-click event data of the interaction data;

provide at least one of the plurality of URLs to the download module;

wherein the at least one URL provided to the download module is provided depending on the rank.

Images