MULTI-TIERED CASCADING CRAWLING SYSTEM

• US 20080228675A1
• Filed: 10/15/2007
• Published: 09/18/2008
• Est. Priority Date: 10/13/2006
• Status: Abandoned Application

• Current Assignee: Move Sales, Inc. (News Corporation)
• Original Assignee: Move Incorporated (News Corporation)
• Inventors: Whitley, Sean, DeTuno, Joe, Moore, Matthew, Zhang, Zhe, Piaseczny, Wojtek, Duffy, Paul
• Application Number:
  US11/872,380
• Publication Number:
  US 20080228675A1
• Time in Patent Office: Days
• US Class Current: 706/10
• CPC Class Codes: G06F 40/295 Named entity recognition

Abstract

Provided is a multi-tiered cascading crawling system for finding on a network information related to one or more predetermined topics or subtopics of interest. In general, embodiments of the present invention provide a system that operates in multiple “tiers,” where at least some of the output of one tier is used to comprise the input of the next tier. Each tier generally analyzes collections of documents on the network using successively more restrictive criteria about the subject matter of each collection and/or about which collections may be related to the one or more topics or subtopics. In general, only the final tier performs an exhaustive crawl of all of the documents of the collections that are identified by the system as being relevant to the topic or subtopic of interest.

Claims

1. A method of searching a network for information related to a topic of interest, wherein the network comprises a plurality of documents containing information, and wherein one or more of the documents are grouped together into a collection of documents so that the network comprises a plurality of collections of documents, the method comprising:

exploring the contents of one or more individual documents of a collection of documents;

making a determination of the relevancy of the one or more individual documents of the collection to the topic of interest; and

making a determination of the relevancy of the collection based at least partially on the relevancy of the one or more individual documents in the collection.

2. The method of claim 1, further comprising:

repeating the steps of exploring the contents of one or more documents, making a determination of the relevancy of the one or more documents, and making a determination of the relevancy of the collection, for a plurality of the collections on the network.

3. The method of claim 2, further comprising:

exploring the contents of every available document in a collection if the determined relevancy of the collection is greater than a threshold relevancy.

4. The method of claim 1, wherein the network is the Internet, wherein each document comprises a web page, and wherein each collection of documents comprises a collection of web pages.

5. The method of claim 4, wherein each collection of web pages comprises web pages from a common website or a common branch of a website.

6. The method of claim 4, wherein the network comprises a plurality of hosts that make one or more web pages available on the network, and wherein each collection of web pages comprises web pages from a common host.

7. The method of claim 1, further comprising:

locating one or more collections of documents on the network.

8. The method of claim 7, wherein the network comprises the Internet, wherein the documents comprise web pages, wherein the collections of documents comprise websites, and wherein the step of locating one or more collections on the network comprises:

providing a list of one or more web page URLs;

exploring one or more web pages using URLs from the list; and

recording any website URLs found on the one or more web pages being explored.

9. The method of claim 8, further comprising:

recording any web page URLs found on the one or more web pages being explored;

adding the recorded web page URLs to the list of one or more URLs; and

repeating the steps of exploring one or more web pages from the list, recording any website URLs, recording any web page URLs, and adding the web page URLs to the list.

10. The method of claim 8, further comprising:

generating URLs to simulate entering information into a form found on the one or more web pages being explored;

adding the generated URLs to the list of one or more URLs;

11. The method of claim 1, further comprising:

providing a plurality categories related to a plurality of sub topics of the topic of interest;

exploring the contents of one or more of the documents of the collection if the determined relevancy of the collection is greater than a threshold relevancy; and

placing at least some of the collections of documents into one or more of the categories based at least partially on the contents of the one or more documents being explored.

12. The method of claim 11, further comprising:

searching one or more documents of a collection that has been placed into a category for a predetermined type of information related to the topic or subtopic, wherein the search and/or the type of information searched for is based at least partially on the category in which the collection has been placed.

13. The method of claim 12, further comprising:

extracting the predetermined type of information from the documents that contain the predetermined type of information.

14. The method of claim 12, wherein the topic of interest comprises real estate, and wherein the predetermined type of information comprises information related to the real estate sale or rental listings.

15. The method of claim 3, further comprising:

searching one or more documents of a collection for a predetermined type of information related to the topic or subtopic, if the determined relevancy of the collection is greater than a threshold relevancy; and

extracting the predetermined type of information from the documents that contain the predetermined type of information.

16. A system for gathering information related to at least one topic of interest, the system comprising:

a multi-tiered system configured for searching a network for information related to at least one topic of interest, wherein each tier comprises more restrictive criteria than the previous tier for locating the at least one topic of interest.

17. The system of claim 16, wherein the network comprises a plurality of collections of documents, each collection comprising one or more documents, the multi-tiered system comprising:

a first tier configured to obtain a list of collections of documents on the network;

a second tier configured to classify each of the collections in the list as being a member of one or more of a plurality of categories; and

a third tier configured to examine the documents of at least some of the collections based at least partially on the classification of collections by the second tier.

18. The system of claim 17, wherein the first tier is configured to search the network to locate collections of documents.

19. The system of claim 17, wherein the plurality of categories comprises a category for collections considered to be relevant to the one or more topics of interest and a category for collections considered to be irrelevant to the one or more topics of interest.

20. The system of claim 17, wherein the plurality of categories comprises one or more categories based on language or dialect.

21. The system of claim 17, wherein the one or more topics of interest comprise subtopics of interest related to the one or more topics of interest, and wherein the plurality of categories comprises one or more categories related to the one or more subtopics of interest.

22. The system of claim 17, wherein the second tier comprises a plurality of tiers each tier comprising more restrictive criteria for classify each of the collections in the list as being a member of one or more of a plurality of categories.

23. The system of claim 17, wherein the second tier comprises a sampler module for examining one or more documents in each collection in order to classify the collection as being a member of one or more of a plurality of categories.

24. The system of claim 23, wherein the sampler module comprises a crawler system for locating the one or more documents in each collection that are used to classify the collection.

25. The system of claim 24, wherein the network comprises the Internet, wherein the documents comprise web pages, wherein the crawler system comprises a web crawler system, wherein the web crawler system is configured to locate the one or more documents of a collection by searching one or more documents in the collection for links in the text of the document that provide access to other documents in the collection, and wherein the web crawler system is configured assign a rank to the documents that it locates based on text in the immediate vicinity of the links related to those documents, and wherein the sampler chooses one or more documents to examine based on the rank of the document.

26. The system of claim 23, wherein the sampler module is configured to classify the collection by examining a plurality of documents of the collection and assigning a score to each document based on the relevancy of the document to one or more of the plurality of categories.

27. The system of claim 23, wherein the one or more documents of a collection used by the sampler module to classify the collection comprise less than all of the documents of the collection.

28. The system of claim 17, wherein the network comprises the Internet, and wherein the documents comprise web pages, the third tier further comprising a web crawler for locating the documents of a collection.

29. The system of claim 17, wherein the third tier is further configured to examine the documents of a collection to determine whether each document of the collection relates to the at least one topic of interest.

30. The system of claim 29, wherein the third tier is further configured to examine the documents of a collection to determine whether each document of the collection comprises a particular type of information related to the at least one topic of interest, and wherein the system further comprises a fourth tier for extracting the particular type of information from each document that the third tier determines comprises the information.

31. A method for requesting web pages from a plurality of web hosts, each web host supporting a finite number of web pages, the method comprising:

grouping the plurality of web hosts into one or more arrays of web hosts, each array comprising a finite number of web hosts; and

submitting a first web page request to each web host in an array before submitting a second web page request to any web host in the array.

32. The method of claim 31, wherein the hosts in the array are ordered from a first web host to a last web host, and wherein the array comprises a cyclic array so that the first host follows the last host in the array, the method further comprising:

submitting a web page request to each web host in the array in order, beginning with the first web host and ending with the last web host; and

,

after a web page request is submitted to the last web host, submitting another web page request to each web host remaining in the array in the same order, beginning with the first web host and ending with the last web host.

33. The method of claim 32, wherein submitting another web page request to each host in the same order is repeated until all of the web pages of all of the hosts of the group have been requested.

34. The method of claim 32, wherein the time between submitting a first web page request to one web host and submitting another web page request to the same web host is greater than or equal to the time required to be polite to the web host.

35. The method of claim 33, wherein submitting another web page request to each host in the same order is repeated until all of the web pages of one of the hosts of the group have been requested, and wherein the method further comprises:

replacing the host that has had all of the web pages requested with another host supporting a finite number of web pages to be requested.

36. The method of claim 31, wherein the plurality of web hosts are grouped into one or more arrays based on the number of web pages to be requested to each web host, so that each array of web hosts comprises web hosts having a similar amount web pages to be requested.

37. A method of ranking hyperlinks found on the Internet during a web crawling scheme, the method comprising:

analyzing text in the immediate vicinity of a hyperlink as the hyperlink is found;

computing a weight for that hyperlink based on the relevancy of the text to a set of interest; and

storing the hyperlink in a datastore where hyperlinks stored therein are ranked based on the relative computed weights of each hyperlink.

38. The method of claim 37, wherein the text has a positive effect on the computed weight of a hyperlink if the text is considered to provide an indication that the hyperlink will likely relate to the set of interest.

39. The method of claim 37, wherein the text has a negative effect on the computed weight of the hyperlink if the text is considered to provide an indication that the hyperlink will likely not relate to the set of interest.

40. The method of claim 37, wherein the hyperlink was found in a web page document, wherein the web page document was found on the Internet by accessing one or more links in other web pages, and wherein computing the weight for the hyperlink is further based on information obtained from the one or more links or web pages through which the web page document was found.

41. A system for ranking hyperlinks found in a document on the Internet, the system comprising:

a link weighting system for analyzing text in the immediate vicinity of a hyperlink and for computing a weight for the hyperlink based on the relevancy of the text to a set of interest; and

a datastore for storing the hyperlink with other hyperlinks in a ranked list based on the relative computed weights of each hyperlink.

42. The system of claim 41, wherein the link weighting system is configured so that the analyzed text has a positive effect on the computed weight of a hyperlink if the link weighting system considers the text to provide an indication that the hyperlink will likely relate to the set of interest.

43. The system of claim 41, wherein the link weighting system is configured so that the analyzed text has a negative effect on the computed weight of the hyperlink if the link weighting system considers the text to provide an indication that the hyperlink will likely not relate to the set of interest.

44. The system of claim 41, wherein the text in the immediate vicinity of the hyperlink comprises text from the URL associated with the hyperlink.

45. The system of claim 41, wherein the text in the immediate vicinity of the hyperlink comprises text from the hyperlink.

46. The system of claim 41, wherein the text in the immediate vicinity of the hyperlink comprises text surrounding the hyperlink but between punctuation marks located on either side of the hyperlink.

47. The system of claim 41, wherein the text in the immediate vicinity of the hyperlink comprises text located within a particular number of words coming before the hyperlink in the document.

48. The system of claim 41, wherein the document was obtained on the Internet by accessing one or more links in other web pages, and the link weighting system computes the weight for the hyperlink also based on information obtained from the one or more links or web pages through which the document was obtained.

49. A method of determining whether a collection of web pages relates to a topic of interest, the method comprising:

exploring a web page of the collection of web pages;

determining the relevancy of the web page to the particular topic of interest; and

making a determination of the relevancy of the entire collection of web pages to the topic of interest based at least partially on the determined relevancy of the web page.

50. The method of claim 49, further comprising:

searching the web page for one or more links to other web pages of the same collection of web pages;

storing the one or more links to other web pages of the same collection in a datastore;

selecting a link to a web page from the datastore;

exploring the selected web page;

determining the relevancy of the selected web page to the particular topic of interest;

searching the selected web page for one or more links to other web pages of the same collection of web pages;

storing the one or more links to other web pages of the same collection in the datastore; and

repeating the steps of selecting, storing, exploring, determining, searching, and storing until the number of web pages explored is equal to some predetermined number of web pages less than the total number of web pages in the collection,

wherein the step of making a determination of the relevancy of the entire collection of web pages to the topic of interest comprises basing the determination of the relevancy of the collection based on the determined relevancy of the explored web pages.

51. The method of claim 50, wherein the steps of searching a web page for one or more links to other web pages further comprises:

for each link found on the web page, analyzing the text in the immediate vicinity of the link, and making a determination of the likelihood that the linked web page will relate to the topic of interest based on the analysis of the text in the immediate vicinity of the link;

wherein the steps of storing the one or more links comprises storing the links in order based on the likelihood that each linked web page will relate to the topic of interest; and

wherein the step of selecting a link from the datastore comprises selecting the link in the datastore that has the greatest likelihood of relating to the topic of interest but has not been selected yet.

52. A system of using a web crawler to classify a collection of web pages, the system comprising:

a web crawler module configured to search a web page from the collection for links to other web pages in the collection, and further configured to request web pages corresponding to the link that the web crawler finds and to examine such web pages for more links to other web pages in the collection;

a classifier module configured to make a determination of the relevancy of each web page that the web crawler examines to a set of interest; and

a collection classifying system for making a determination of the relevancy of the collection to the set of interest based on the determined relevancy of the web pages that the web crawler examines.

53. The system of claim 52, wherein the web crawler is configured to examine some number of web pages in the collection less than all of the web pages in the collection.

54. A method of gathering information related to a particular topic of interest, the method comprising:

searching a network for information related to at least one topic of interest, wherein searching the network comprises searching the network in a multi-tiered format such that each tier comprises more restrictive criteria for locating the at least one topic of interest than a previous tier; and

extracting data from the searched information relating to the at least one topic of interest searched on the network.

55. The method of claim 54, wherein searching comprises searching a plurality of websites to find information on the Internet related to a particular topic of interest, wherein each website comprises a plurality of web pages.

56. The method of claim 55, further comprising harvesting a plurality of websites to determine a plurality of websites for searching for information on the Internet related to a particular topic of interest.

57. The method of claim 55, further comprising converting each of the plurality of web pages into a HTML tree prior to, or subsequent to, extracting data from the searched information.

58. The method of claim 54, further comprising altering a format of the searched information prior to extracting data from the information.

59. The method of claim 54, further comprising grouping a plurality of entities of extracted data based on at least one grouping rule.

60. The method of claim 54, wherein extracting comprises extracting at least one image relating to the at least one topic of interest searched on the network.

61. The method of claim 54, wherein searching comprises searching in a multi-tiered format with a plurality of crawlers.

62. The method of claim 61, wherein each of the crawlers comprises at least one classifier to determine the relevancy of the searched information.

63. The method of claim 54, wherein searching comprises searching for information relating to a plurality of real estate listings.

64. The method of claim 63, wherein extracting comprises extracting at least one of price, number of bedrooms, number of bathrooms, address, and amenities from each real estate listing.

65. The method of claim 54, further comprising indexing the extracted data for searching with a search engine.

66. The method of claim 54, wherein extracting comprises extracting data from the searched information using a plurality of extraction rules.

67. The method of claim 54, further comprising outputting the extracted information in a standard XML format.

68. A system for gathering information related to a particular topic of interest, the system comprising:

a multi-tiered system configured for searching a network for information related to at least one topic of interest, wherein each tier comprises more restrictive criteria for locating the at least one topic of interest than a previous tier; and

an information extraction engine configured for extracting data from the searched information relating to the at least one topic of interest searched on the network.

69. The system of claim 68, wherein the multi-tiered system is configured for searching a plurality of websites to find information on the Internet related to a particular topic of interest, and wherein each website comprises a plurality of web pages.

70. The system of claim 69, further comprising at least one harvester configured for harvesting a plurality of websites to determine a plurality of websites for searching for information on the Internet related to a particular topic of interest.

71. The system of claim 69, wherein the information extraction engine comprises a HTML structure analyzer module configured for converting each of the plurality of web pages into a HTML tree prior to, or subsequent to, extracting data from the searched information.

72. The system of claim 68, wherein the information extraction engine comprises a transformation module configured for altering a format of the searched information prior to extracting data from the information.

73. The system of claim 68, wherein the information extraction engine comprises a data analyzer module configured for grouping a plurality of entities of extracted data based on at least one grouping rule.

74. The system of claim 68, wherein the information extraction engine comprises a data analyzer module configured for extracting at least one image relating to the at least one topic of interest searched on the network.

75. The system of claim 68, wherein each tier of the multi-tiered system comprises a plurality of crawlers.

76. The system of claim 75, wherein each of the crawlers comprises at least one classifier to determine the relevancy of the searched information.

77. The system of claim 68, wherein the multi-tiered system is configured for searching for information relating to a plurality of real estate listings.

78. The system of claim 77, wherein the information extraction engine comprises an entity extraction module configured for extracting at least one of price, number of bedrooms, number of bathrooms, address, and amenities from each real estate listing.

79. The system of claim 68, wherein the information extraction engine comprises a data export module configured for outputting the extracted information in a standard XML format.

80. The system of claim 68, wherein the information extraction engine comprises an entity extraction module configured for extracting data from the searched information using a plurality of extraction rules.