Graph-based seed selection algorithm for web crawlers

One or more search seeds for Web crawling operations are selected. In a directed graph with Web pages represented by vertices and links represented by edges, characteristics of vertices connected to potential seed vertices are considered in making a seed selection.

FIELD OF THE INVENTION

The present invention relates to web crawling technology. In particular, the present invention relates to seed selection technology for web crawlers.

BACKGROUND

World Wide Web-General

The Internet is a worldwide system of computer networks and is a public, self-sustaining facility that is accessible to tens of millions of people worldwide. The most widely used part of the Internet is the World Wide Web, often abbreviated “WWW” or simply referred to as just “the Web”. The Web is an Internet service that organizes information through the use of hypermedia. The HyperText Markup Language (“HTML”) is typically used to specify the contents and format of a hypermedia document (e.g., a Web page).

In this context, an HTML file is a file that contains the source code for a particular Web page. A Web page is the image or collection of images that is displayed to a user when a particular HTML file is rendered by a browser application program. Unless specifically stated, an electronic or Web document may refer to either the source code for a particular Web page or the Web page itself. Each page can contain embedded references to images, audio, video or other Web documents. The most common type of reference used to identify and locate resources on the Internet is the Uniform Resource Locator, or URL. In the context of the Web, a user, using a Web browser, browses for information by following references that are embedded in each of the documents. The HyperText Transfer Protocol (“HTTP”) is the most common protocol used to access a Web document and the references that are based on HTTP are referred to as hyperlinks (formerly, “hypertext links”).

Search Engines

Through the use of the Web, individuals have access to millions of pages of information. However, a significant drawback with using the Web is that because there is so little organization to the Web, at times it can be extremely difficult for users to locate the particular pages that contain the information that is of interest to them. To address this problem, a mechanism known as a “search engine” has been developed to index a large number of Web pages and to provide an interface that can be used to search the indexed information by entering certain words or phases to be queried. These search terms are often referred to as “keywords”.

Although there are many popular Internet search engines, they are generally constructed using the same three common parts. First, each search engine has at least one, but typically more, “web crawler” (also referred to as “crawler”, “spider”, “robot”) that “crawls” across the Internet in a methodical and automated manner to locate Web documents. Upon locating a document, the crawler may take any number of actions, depending on the configuration of the crawler. In some cases, the crawler stores the document's URL, and follows any hyperlinks associated with the document to locate other Web documents. Second, each search engine contains an indexing mechanism that indexes certain information about the documents that were located by the crawler. In general, index information is generated based on the contents of the HTML file associated with the document. The indexing mechanism stores the index information in large databases that can typically hold an enormous amount of information. Third, each search engine provides a search tool that allows users, through a user interface, to search the databases in order to locate specific documents, and their locations on the Web (e.g., a URL), that contain information that is of interest to them.

The quality of the documents or Web pages available to users via a search system is directly impacted by the crawler configuration. Large search providers often have multiple crawlers operating simultaneously. Each crawler may have unique logic, as well as multiple configuration options determining the context, duration, and goals of the crawl.

One configuration option is the starting page, or a “seed.” This setting represents the page from which a crawler will begin crawling the web. For example, if the seed is set to the “flickr” home page at www.flickr.com, then the crawler will begin the crawling operation at that page, following links found on that page.

Another configuration option defines the depth, degree, or number of levels of crawling. For example, a crawler may be configured to crawl Web pages or documents that are within ten links, or “hops,” away from the seed page. This ensures a certain proximity to the seed page. Likewise, a crawler may be configured to crawl only within the domain of the seed page.

A different configuration may specify that a crawler crawl only within a certain number of domains away from the seed page domain. In this context, a domain represents a set of documents available via URLs residing under a common Internet domain name. For example, the URLs http://www.flickr.com/photos/ and http://www.flickr.com/tour/ can be said to reside in the same domain, because they share a common Internet domain name: www.flickr.com. Portions of the domain name may be ignored if the crawler is configured to do so. For example, the “www” portion of the domain name may be ignored, so that http://flickr.com/photos/ and http://www.flickr.com/tour/ can be said to reside in the same domain. A domain that is accessible via one link from the seed page domain may be said to be a first degree domain of the seed domain. Likewise, a domain that is directly accessible from a first degree domain may be said to be a second degree domain, and so on. In this scenario, a crawler may recognize that the domain links directly to pages in several first degree domains, which in turn link to pages in second degree domains. A crawler may be configured to crawl only 1stthrough nthdegree domains.

Crawlers are often configured with logic that allows them to recognize and respond to undesirable circumstances. For example, a crawler may recognize that it is crawling an infinite path. Infinite paths are often created by dynamic website generation scripts, such as calendar applications, where following each link to the next year infinitely creates new calendars representing each subsequent year. A crawler in this situation will often revert back to a page that has a known quality, and continue the operation while avoiding the infinite path.

Crawlers often employ dynamic logic, enabling the crawler to adjust crawling preferences. For example, crawlers often adjust the above configurations based on user feedback, changes in system configuration, structure and quality of websites, and business priorities.

Seed Selection

The infinite path scenario provides just one example of why crawlers with less than infinite resources must be configured to find quality information, rather than pure quantity. For this reason, the seed at which the crawling operation is started is crucial. Also, pages closest to the seed often get updated more frequently, increasing the importance of seed selection.

Seed selection is currently performed in several ways. The four most popular methods are: random seed selection, manual seed selection, specialized seed selection, and seed selection based upon characteristics of the potential seed page.

Random seed selection techniques are based on the goal of crawling every available Web document. The logic follows from the assumption that all pages are connected and every page will be crawled at some point, so the starting point does not matter.

Manual seed selection relies on a human determination of quality. Popular home pages such as news outlets or other media sites such as “portals” are chosen, as they have perceived quality and link to large amounts of content.

Specialized seed selection is similar to manual seed selection, but is more focused. A crawler with a goal of indexing Web pages related to the automotive industry may be configured by an administrator to start the crawl at a well-known automotive industry related website. The logic behind this selection is that the website, when used as a seed, will probably yield content from other sites related to the automotive industry.

There is a potential problem with the manual and specialized methods. Popular sites often fail to produce a path to other popular sites. For example, using a popular computer manufacturer website as a seed will usually fail to lead a crawler to another popular computer manufacturer within a reasonable degree of link traversal.

More advanced methods of seed selection take into consideration characteristics of the potential seed. Each Web page, or potential seed, is analyzed to determine the number of inlinks to the page representing the number of links from other Web pages to the potential seed, outlinks from the page representing the number of links from the potential seed to other Web pages, or other quality determination associated with the potential seed. Other quality determinations may be made based on user activity associated with the Web page, search engine ranking, or other search-related data.

Even the advanced methods of seed selection may have undesirable side-effects. For example, many low-quality websites have a large number of outlinks by their very nature, or in an attempt to “spam” search engines. Likewise, Web pages that have a large number of inlinks are often quality pages, or “destination pages” rather than Web pages having paths to many quality pages. Additionally, if multiple seeds are chosen for multiple crawling operations and those seeds link to each other within a few hops, resources are wasted as each crawler has an overlapping territory, since each seed has an overlapping territory.

DETAILED DESCRIPTION

General Overview

In an embodiment, a web graph comprises a directed graph with web pages as vertices and links as edges. A quality metric is determined for a plurality of vertices. The vertex quality metric measures the ability of a vertex to facilitate discovery of web pages, and is based in part on attributes of vertices to which the vertex is connected. A web crawling starting seed is determined based on the quality metrics. A web crawling operation is performed based on the starting seed.

In another embodiment, a plurality of strongly connected components is determined based on a web graph. A strongly connected component is a set of vertices in a directed graph, where for every pair of vertices in a strongly connected component, there is a path from each vertex to the other. A quality metric is determined for each strongly connected component. The quality metric measures the ability of a strongly connected component to facilitate discovery of web pages. Based on the quality metrics, a strongly connected component is selected. A vertex in the selected strongly connected component is selected to be a starting seed. A web crawling operation is performed based on the starting seed.

Structural and Functional Overview

FIG. 1is a block diagram representing a system on which an embodiment may be utilized. Search system100is communicatively connected to Internet150, and comprises Database110, seed selector logic120, crawler logic130, and Search logic140.

Seed selector120, crawler130, and search140are each communicatively coupled to Database110. In an embodiment, seed selector120, crawler130, and search140are each communicatively coupled to one another.

Search system100may reside on one computing system. Alternatively, search system100may comprise multiple computing systems. Any logical portion of search system100may be separate from the other logical portions of search system100. For example, separate computing systems may be used for seed selector120, crawler130, and search140.

In an embodiment, seed selector120, crawler130, search140, and Database110each reside at different physical locations. In another embodiment, seed selector120, crawler130, search140, and Database140reside on a desktop computer or mobile computing device such as a smartphone or personal digital assistant.

Database110stores and retrieves data for use in crawling and search operations. Database110may be a relational database, multidimensional database, flat file, or any other structure capable of storing search related information such as text. A database management system (DBMS) may be used to manage the database. Alternatively, custom routines may be used to manage data.

Seed selector120selects a starting point, or a “seed” for a web crawling operation. The selection is made based on data found in Database110. Seed selector may also store seed information in Database110. Alternatively, seed selector may store seed information in a location other than Database110. For example, seed information may be stored in volatile or non-volatile memory when seed selector120runs in the same process as crawler130.

Crawler130performs a web crawling operation. More than one crawler program may be executed, and each crawler may use a different seed as a starting point. Alternatively, a single crawler may use more than one seed. Also, more than one crawler may share logic allowing the crawlers to divide the work of crawling based on a single seed. Thus, although the application may present a one-to-one seed-to-crawler ratio for the sake of convenience and clarity, there need not be a one-to-one crawler-to-seed ratio. Crawler130stores data gathered during a crawling operation in Database110.

Search140accepts user input requesting matching items. Search140retrieves matching data from the database and returns the data to the requesting user.

Directed Graphs

The Internet consists of several logically separated portions. The portion most well known is the World Wide Web, often called “the Web.” This terminology describes the vast number of interconnected Web pages and their interconnections. A single page may link to many pages. Likewise, many pages may link to a single page.

Directed graphs provide a means for organizing and visualizing the Web at the same time.FIG. 2shows a directed graph that represents several web pages and their interconnecting links.

Website A210contains links AA212, BB214, CC216, and a link to Website B218. Website B220contains links DD222, AA224, BB226, and a link to Website A. Websites AA250, BB252, CC254, and DD256are not shown, but are represented in graph240.

Graph240shows the relationships between the websites. Each website is represented by a vertex of the graph, and each link is represented by an edge of the graph. For example, vertex210represents Website A210. Edge212represents the link from Website A210to Website AA250. Likewise, vertex220represents website B, while edge226represents the link from Website B220to Website BB252. Links212-218are represented by edges212-218, while links222-228are represented by edges222-228.

This application will use convenient terminology to describe the use and traversal of a directed graph. Each link will be referred to as a “hop,” so that the distance between vertices in a directed graph may be understood. For example, the distance between Website A210and Website DD256can be said to be two hops. Another way of determining the number of hops measuring the distance between two vertices is to count the number of edges separating the two vertices. If there are multiple paths connecting two vertices, a path having the minimal number of edges should be used as a measure of distance.

The term “level” may be used to describe each vertex at a specified number of hops from the starting point of a graph. The level may also be described or implied to be inclusive, in order to include intervening levels.

Seed Selection

A good quality seed is a seed that will lead, in some number of hops, to the most high-quality pages.

The number of hops is a parameter configured in the seed selection logic. Another parameter configured in seed selection logic is the number of seeds. The configuration may be manual or automatic. These parameters are based, at least partially, on available system resources such as processor and memory usage.

Web pages may be measured by any quality metric available. Seed selector120does not require a particular definition of quality to operate. For example, a Web page that has been returned in a set of search results, thereafter being selected by the user, may be considered a high-quality page. Another measurement of quality is the number of links the page has to other pages that have not been crawled before. The opportunity to gather new content may command a higher quality metric than web pages with links to known data.

Characteristics affecting quality may be considered independently of one another, and weighted differently depending on their location on the graph or proximity to the potential seed. In an embodiment, however, characteristics may be pooled together into a quality metric representing the quality of the Web page represented by a vertex. Any method of determining quality may be used.

Two distinct seed selection methods are described hereafter. Each seed selection method has alternative embodiments that provide additional features.

Directed Graph-Based Seed Selection

The first method of seed selection is based on a directed graph of the Web. Unlike prior methods of seed selection, which take into consideration only properties of the potential seed, the directed graph based seed selection technique takes into consideration the characteristics of pages in the same “neighborhood” as the potential seed.

“Neighborhood” is a way to describe a set of vertices in a directed graph, and represents a group of vertices that lie on the graph within a number of hops defined for that neighborhood. For example, a neighborhood may be defined with a two-hop radius. In this example, a potential seed is selected. The characteristics of those vertices within one hop are considered. Likewise, the characteristics of those vertices within two hops are considered. Based on the considered characteristics of the vertices in the neighborhood, seed selector120makes a determination as to whether the vertex is a desirable seed.

A neighborhood may be defined in other ways if desired by the operator. For example, an operator may choose to consider only the characteristics of pages that are more than one hop away, or exactly three hops away. As long as characteristics of vertices representing Web pages other than the potential seed itself are considered, a more desirable seed may be chosen.

In the following example, a quality determination for each vertex, based on information known to search system100, exists prior to seed selection. To simplify the example, the quality metric is based solely on the number of inlinks to the vertex being quantified. Thus, if a Web page is linked to by three other Web pages, the vertex representing that Web page in this example has a vertex quality metric of three.

FIG. 3illustrates a directed graph300containing vertices310-332. Each quality determination is shown inside each respective vertex inFIG. 3. In an embodiment, each potential seed is ranked against all other potential seeds in an effort to determine which potential seed to use. Each vertex is a potential seed, and is assigned a “seed score” that represents the ability of the seed to facilitate the finding of quality Web pages. In this example, the seed score represents the total of all vertex quality metrics within the specified number of hops of the potential seed. The number of hops that will be used in this example is one.

For example, vertex324has five edges representing outlinks, and therefore has five vertices within a one-hop radius. Vertex324links to vertices318,322,332,330, and326, having vertex quality scores of 3, 1, 1, 2, and 1, respectively. Adding these scores, along with the quality score of vertex324(1) results in a total seed score of 9. The same operation is carried out for each vertex in the graph, leading to the following table of seed scores:

As can be seen in Table 1, the potential seed with the highest seed score is vertex316, with a score of 13. Vertex314has a high vertex quality metric, surpassing other metrics. Although vertex324has the most outlinks, and vertex314has the most inlinks (not shown, but represented by the quality metric of 10), neither of these vertices has been chosen as the best seed. By taking into consideration properties of neighboring vertices, a seed is chosen that will result in a higher overall crawl quality.

The best seed determination depends on the number of hops configured. The example above might have led to a different result if the number of hops were set to a higher number.

A noticeable side-effect of increasing the hop count to two is a double-counting anomaly. Vertex324has an edge to vertex326, which has an edge to vertex330. But vertex324also has an edge to vertex330. However, seed selector120may be configured with logic that detects such loops and reduces the seed score accordingly.

Although the previous example discusses a single seed selection, multiple seeds may be desirable. For example, a high-capacity search system100may be capable of running many crawlers concurrently.

When selecting multiple seeds, choosing seeds that are too close in proximity to one another on a directed graph leads to wasted resources. For example, if the hop count is set to two, and two seeds are desired, choosing vertex316as a first seed and318as a second seed would be counter-productive. This choice would lead to a large overlap in the Web pages crawled, since all but one of the vertices covered by a crawl using the first seed will also be covered by a crawl initiated using the second seed.

Seed selection may take place all at once, or in a sequence. In an embodiment, each seed selection requires a recalculation of the vertex quality values in the directed graph, taking into consideration the coverage of a crawl that will be initiated by previously determined seeds. For example, once a first seed is chosen, all vertices expected to be covered by a crawl initiated using the first seed as a starting point may have their vertex quality metric reduced or set to zero.

Using graph300FIG. 3to illustrate, a seed selection process selecting three seeds for a one-hop crawl radius is shown below:

Table 2 shows three seed selection operations taking place one after another. The first seed, vertex316, is selected. Following this selection, all vertices expected to be crawled, or those vertices within one hop of the seed, are given a new vertex quality metric of zero. Seed selector120performs the seed selection operation again, basing the selection on the new values assigned to affected vertices, as well as the values of unchanged vertices.

Vertex324wins the selection process for the second seed, as its seed quality metric remained unchanged after the first operation, leaving vertex324to have the highest probability of leading a crawler to the most valuable content based on our definition of high quality content.

By the time the third iteration of seed selection begins, only two vertices remain. Vertex328remains with a vertex quality score of 1, and vertex310remains with a vertex quality score of zero. Vertices328and332have an equivalent seed score, because they will both result in the crawling process reaching vertex328within one hop. A tie-breaking mechanism, such as a determination of resources required to finish the crawl or a random selection agent may be used to decide between two potential seeds with equivalent quality values.

There may also be a situation where a zeroed-out vertex will have the highest seed score. For example, if the vertex was included on the outer edge of the crawling territory defined by a previous seed, that is to say that the vertex resides at the last hop available to the crawler, it may be the case that a seed with a quality score of zero is one hop away from several high-quality vertices.

Directed Graph Approximation

Given enough resources, directed graph based seed selection may be performed on a directed graph representing the entire Internet, or a portion thereof. Even infinite paths may be represented by a terminal vertex with a vertex quality score representative of the quality of the entire infinite path; such paths have diminishing returns. However, not every organization is capable of dedicating the resources required to perform seed selection on large quantities of data. This lack of resources becomes apparent as the number of seeds and the number of hops required increases. Calculation of a seed score for 20 hops, for example, could require the consideration of millions of vertices. Thus, a method of approximating the quality of a potential seed may make more sense for some organizations.

One way to approximate a seed score for a seed candidate is to consider a smaller neighborhood. In one embodiment, for example, even when the hop count is set to ten, the seed score for a potential seed is to be determined based only on those vertices within 2 hops or any other radius smaller than ten hops.

In an embodiment, other approximation methods are used. These approximation methods may take into consideration a subset of the selected neighborhood in different ways. Alternatively, approximation methods consider the global structure of the graph. For example, strongly connected components are to be considered in an embodiment.

Strongly Connected Components

In the context of a directed graph, a strongly connected component is defined by its properties: For every pair of vertices in a strongly connected component, there is a path from each vertex to the other. A strongly connected component includes as many vertices as possible. Therefore, although a strongly connected component cannot be said to be made up of smaller strongly connected components, even though a smaller set of vertices within the strongly connected component may, for each pair of vertices, have a path from each vertex to the other. This set would only be considered to be a strongly connected set of vertices. Only when a set of vertices is at a maximum of strongly connected vertices can the set be considered a strongly connected component.

FIG. 4is a diagram showing three separate strongly connected components in a string of strongly connected components. Strongly connected component SCC1420is connected to strongly connected component SCC2440, which is in turn connected to strongly connected component SCC3460. In this way, SCC1420, SCC2440, and SCC3460are represented as a “parent” or “super” directed graph, each strongly connected component containing a sub-graph or child graph.

An expanded view of SCC2440is shown inFIG. 4. True to the definition of a strongly connected component, there exists a path from each vertex441-456to each other vertex441-456. For example, a path from vertex441to vertex455exists as follows: vertex441—vertex442—vertex443—vertex450—vertex453—vertex446—vertex44—vertex448—vertex451—vertex452—vertex454—vertex455.

Vertex421is not part of SCC2440because there is no path back to vertex421once SCC2440is entered. This would violate the definition of a strongly connected component. Likewise, vertex461in not part of SCC2440, because although there exists a path to vertex461from SCC2440via vertex454, there is no path returning to SCC2440once SCC3460is reached.

Strongly connected components form “chains” that may be represented by a directed graph. These chains may interconnect with one another, or may exist as a single chain such as the chain shown isFIG. 4. These chains may be connected with any number of connecting components. However, any directed loop in a chain of strongly connected components redefines the set of strongly connected components in the loop as a single strongly connected component. This is because a loop of strongly connected components creates a path from each vertex in the loop to each other vertex in the loop. Therefore, a chain of properly defined strongly connected components does not form a loop.

Strongly Connected Component-Based Seed Selection

Strongly connected components assist in providing an approximation of quality for a portion of a directed graph such as a Web graph.

A strongly connected component may be assigned a component quality metric based any criteria available. In an embodiment, a quality metric is assigned by summing up the vertex quality values of the vertices contained in the strongly connected component.

Once a quality metric has been assigned to each strongly connected component, the strongly connected component with the highest component quality value may be selected as the component from which a seed should be selected. The highly interconnected nature of a strongly connected component suggests that any vertex chosen within the component will result in the coverage of a large portion of the vertices in the component. That is to say any vertex that resides in SCC2440, if chosen as a seed, will lead to a large portion of the other vertices in the component within a certain number of hops. Thus, an expectation of quality may be approximated.

In an embodiment, directed graph based seed selection may be used to select a vertex within the selected strongly connected component to be used as the seed. Alternatively, other simpler methods may be used to select the vertex. For example, the vertex with the highest number of outlinks may be selected as the seed.

Since multiple seeds are often desirable, the strongly connected components may employ a technique of selecting seeds similar to the technique used in the graph based seed selection method discussed above. In an embodiment, seed selector120determines which vertices will be visited by a crawler when a crawling operation is performed based on a first seed. Those vertices are then assigned a reduced vertex quality metric. The reduction of the vertex quality metrics in turn causes a reduction in the component quality metrics of components having vertices with reduced metrics. Since a path may exist from one strongly connected component to another within the number of hops specified in a crawling operation, many strongly connected components may be affected by a crawl, even though the crawl may have started in a particular strongly connected component.

FIG. 5Ais a diagram illustrating a directed graph of strongly connected components. Each edge represents a connection from a vertex in one strongly connected component to a vertex in the next strongly connected component. Although strongly connected components510-560are shown in sequence with no intervening chains, intervening component chains are possible.

In an embodiment illustrated inFIG. 5A, strongly connected component560has the highest quality value, represented by the number inside the vertex on the graph. In this case, strongly connected component560has a component quality metric of 250. Strongly connected component560is chosen as the component from which to choose a vertex to be a seed. Before selecting a second strongly connected component from which to select a second seed, it is determined that vertices with a sum total vertex quality metric of 213 will be visited by the crawler. Thus,FIG. 5Bshows a reduced value of 37 for strongly connected component560. An advantage of this method is that only the values of affected strongly connected components need be changed.

In this example, however, no other strongly connected components were affected by the crawl. This may occur for at least two reasons. First, the hop count may be low enough that the edge of the strongly connected component cannot be reached by the crawl. Second, the strongly connected component itself is an “edge component” that is the final strongly connected component in a chain of strongly connected components. InFIG. 5A, there is no path from strongly connected component560to any other strongly connected component.

To avoid choosing an “edge component,” an additional step may be used to determine the radius of a crawling operation. If crawling paths are cut significantly short, another strongly connected component may be chosen.

In another embodiment, strongly connected component directed graphs may employ the techniques discussed with respect to directed graph based seed selection to select a strongly connected component. For example, quality values strongly connected components within proximity of a strongly connected component may be considered when determining which strongly connected component to choose a seed from.

For example, strongly connected component540may be chosen if the hop count is high enough to cause the crawling operation to visit strongly connected component560, the highest scoring component.

In another embodiment, a score of a particular strongly connected component may be increased based on the scores of strongly connected components that are reachable from the particular strongly connected component.

In another embodiment, a seed may be chosen based on a score of at least two strongly connected components in which the vertices reached from the seed lie.

Hardware Overview

Computer system600further includes a read only memory (ROM)608or other static storage device coupled to bus602for storing static information and instructions for processor604. A storage device610, such as a magnetic disk or optical disk, is provided and coupled to bus602for storing information and instructions.