US6182085B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Collaborative team crawling:Large scale information gathering over the internet
Assignee: International Business Machines Corp
•
Filing: 1998-05-28
•
Granted: 2001-01-30
•
Expires: 2018-05-28
Abstract
Abstract A distributed collection of web-crawlers to gather information over a large portion of the cyberspace. These crawlers share the overall crawling through a cyberspace partition scheme. They also collaborate with each other through load balancing to maximally utilize the computing resources of each of the crawlers. The invention takes advantage of the hierarchical nature of the cyberspace namespace and uses the syntactic components of the URL structure as the main vehicle for dividing and assigning crawling workload to individual crawler. The partition scheme is completely distributed in which each crawler makes the partitioning decision based on its own crawling status and a globally replicated partition tree data structure.
Inventors
- 👤 Matthias Eichstaedt
- 👤 Daniel Alexander Ford
- 👤 Tobin Jon Lehman
- 👤 Qi Lu
- 👤 Shang-Hua Teng
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 06:43
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5083; G06F16/00; G06F16/90; G06F16/95; G06F16/951; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99943; Y10S707/99944; Y10S707/99945; Y10S707/99948
Claims Analysis
Total Claims: 47
Claim 1
Independent Claim
78 words
A method to gather data objects from an information system, comprising: constructing logical web-graphs defining logical relationships between specified objects in the information system; partitioning the web-graph into sub-graphs; and processing the specified objects to locate desired objects by: balancing the processing of the specified objects by mapping the sub-graphs to one or more preferred processors, wherein a processor is preferred if it reduces processing time or overhead; and re-balancing the processing if the processing load becomes unbalanced.
Claim 2
Independent Claim
78 words
A method to gather data objects from an information system, comprising: constructing logical web-graphs defining logical relationships between specified objects in the information system; partitioning the web-graph into sub-graphs; and processing the specified objects to locate desired objects by: balancing the processing of the specified objects by mapping the sub-graphs to one or more preferred processors, wherein a processor is preferred if it reduces processing time or overhead; and re-balancing the processing if the processing load becomes unbalanced.
Claim 3
Dependent Claim
20 words
The method recited in claim 1 , further comprising pushing the located desired objects to a user desiring the objects.
Claim 4
Dependent Claim
47 words
The method recited in claim 1 , wherein the web-graph defines a resource identification space containing resource identifications, the resource identification space being a directed graph having a collection of vertices and ordered nodes connecting the vertices, each resource identification defining a vertex of the directed graph.
Claim 5
Dependent Claim
41 words
The method recited in claim 3 , partitioning the web-graph into sub-graphs comprising: coarsening the web-graph to create sub-graphs, the sub-graphs comprising identifiable groupings of objects, where coarsening comprises contracting the vertices in the web-graph; and dynamically recognizing each identifiable sub-graph.
Claim 6
Dependent Claim
21 words
The method recited in claim 4 , further comprising creating sub-graphs comprising clusters of resources having physical closeness to one another.
Claim 7
Dependent Claim
21 words
The method recited in claim 5 , further comprising creating sub-graphs comprising clusters of resources having hyperlink closeness to one another.
Claim 8
Dependent Claim
46 words
The method recited in claim 6 , further comprising estimating a weight for each node of a graph, the weight reflecting a number of visits to the node, a cumulative total of the weights for nodes contained in a sub-graph being used for processing (load) balancing.
Claim 9
Dependent Claim
44 words
The method recited in claim 7 , load balancing including: maintaining information regarding average access time and processing time of an object or a sub-graph, these access and processing times forming a processing rate; mapping sub-graphs to desired processors based upon processing rate differences.
Claim 10
Dependent Claim
27 words
The method recited in claim 8 , further comprising: identifying communities of sub-graphs that have numerous connections; and mapping sub-graphs having numerous connections to a same processor.
Claim 11
Dependent Claim
20 words
The method recited in claim 9 , further comprising using a hierarchically structured namespace having syntactic components to identify objects.
Claim 12
Dependent Claim
79 words
The method recited in claim 9 , further comprising: maintaining a queue and a hit-hash for each processor of sub-graphs, the hit-hash maintained for objects having a potentially large in-degree; checking the processors hit-hash for the object if a new object is encountered by a processor, and processing the object if is the hit-hash, otherwise; moving the object to a temporary location; having each another processor check its hit-hash and queue for the object; and further processing the object.
Claim 13
Dependent Claim
30 words
The method recited in claim 9 , further comprising using non-preferred (lightweight) processors and preferred processors for processing, wherein a lightweight processor can be removed from processing at any time.
Claim 14
Dependent Claim
26 words
The method recited in claim 12 , further comprising not re-balancing the processing load between processors when a lightweight processor is added or removed from processing.
Claim 15
Dependent Claim
97 words
A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for gathering objects from an information system, said method comprising: constructing logical web-graphs defining logical relationships between specified objects in the information system; partitioning the web-graph into sub-graphs; and processing the specified objects to locate desired objects by: balancing the processing of the specified objects by mapping the sub-graphs to one or more preferred processors, wherein a processor is preferred if it reduces processing time or overhead; and re-balancing the processing if the processing load becomes unbalanced.
Claim 16
Dependent Claim
97 words
A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for gathering objects from an information system, said method comprising: constructing logical web-graphs defining logical relationships between specified objects in the information system; partitioning the web-graph into sub-graphs; and processing the specified objects to locate desired objects by: balancing the processing of the specified objects by mapping the sub-graphs to one or more preferred processors, wherein a processor is preferred if it reduces processing time or overhead; and re-balancing the processing if the processing load becomes unbalanced.
Claim 17
Dependent Claim
22 words
The medium recited in claim 14 , the method further comprising pushing the located desired objects to a user desiring the objects.
Claim 18
Dependent Claim
47 words
The medium recited in claim 15 , wherein the web-graph defines a resource identification space containing resource identifications, the resource identification space being a directed graph having a collection of vertices and ordered nodes connecting the vertices, each resource identification defining a vertex of the directed graph.
Claim 19
Dependent Claim
41 words
The medium recited in claim 16 , partitioning the web-graph into sub-graphs comprising: coarsening the web-graph to create sub-graphs, the sub-graphs comprising identifiable groupings of objects, where coarsening comprises contracting the vertices in the web-graph; and dynamically recognizing each identifiable sub-graph.
Claim 20
Dependent Claim
21 words
The medium recited in claim 17 , further comprising creating sub-graphs comprising clusters of resources having physical closeness to one another.
Claim 21
Dependent Claim
21 words
The medium recited in claim 18 , further comprising creating sub-graphs comprising clusters of resources having hyperlink closeness to one another.
Claim 22
Dependent Claim
44 words
The medium recited in claim 18 , load balancing including: maintaining information regarding average access time and processing time of an object or a sub-graph, these access and processing times forming a processing rate; mapping sub-graphs to desired processors based upon processing rate differences.
Claim 23
Dependent Claim
27 words
The medium recited in claim 20 , further comprising: identifying communities of sub-graphs that have numerous connections; and mapping sub-graphs having numerous connections to a same processor.
Claim 24
Dependent Claim
20 words
The medium recited in claim 21 , further comprising using a hierarchically structured namespace having syntactic components to identify objects.
Claim 25
Dependent Claim
79 words
The medium recited in claim 21 , further comprising: maintaining a queue and a hit-hash for each processor of sub-graphs, the hit-hash maintained for objects having a potentially large in-degree; checking the processors hit-hash for the object if a new object is encountered by a processor, and processing the object if is the hit-hash, otherwise; moving the object to a temporary location; having each another processor check its hit-hash and queue for the object; and further processing the object.
Claim 26
Dependent Claim
30 words
The medium recited in claim 21 , further comprising using non-preferred (lightweight) processors and preferred processors for processing, wherein a lightweight processor can be removed from processing at any time.
Claim 27
Dependent Claim
26 words
The medium recited in claim 24 , further comprising not re-balancing the processing load between processors when a lightweight processor is added or removed from processing.
Claim 28
Dependent Claim
46 words
The medium recited in claim 17 , further comprising estimating a weight for each node of a graph, the weight reflecting a number of visits to the node, a cumulative total of the weights for nodes contained in a sub-graph being used for processing (load) balancing.
Claim 29
Independent Claim
148 words
An apparatus for traversing an information system to retrieve designated objects, the apparatus comprising: a recognizer to determine a format for each object retrieved; a summarizer to read varying data formats communicatively coupled to the recognizer; an expander for expanding objects having a compressed format communicatively coupled to the recognizer and the summarizer; storage and processors included in one or more of the above, the processors capable of reading digital signals to traverse the information system to retrieve designated objects by: constructing logical web-graphs defining logical relationships between specified objects in the information system; partitioning the web-graph into sub-graphs; and processing the specified objects to locate desired objects by: balancing the processing of the specified objects by mapping the sub-graphs to one or more preferred processors, wherein a processor is preferred if it reduces processing time or overhead; and re-balancing the processing if the processing load becomes unbalanced.
Claim 30
Independent Claim
148 words
An apparatus for traversing an information system to retrieve designated objects, the apparatus comprising: a recognizer to determine a format for each object retrieved; a summarizer to read varying data formats communicatively coupled to the recognizer; an expander for expanding objects having a compressed format communicatively coupled to the recognizer and the summarizer; storage and processors included in one or more of the above, the processors capable of reading digital signals to traverse the information system to retrieve designated objects by: constructing logical web-graphs defining logical relationships between specified objects in the information system; partitioning the web-graph into sub-graphs; and processing the specified objects to locate desired objects by: balancing the processing of the specified objects by mapping the sub-graphs to one or more preferred processors, wherein a processor is preferred if it reduces processing time or overhead; and re-balancing the processing if the processing load becomes unbalanced.
Claim 31
Dependent Claim
20 words
The apparatus recited in claim 27 , further comprising pushing the located desired objects to a user desiring the objects.
Claim 32
Dependent Claim
47 words
The apparatus recited in claim 27 , wherein the web-graph defines a resource identification space containing resource identifications, the resource identification space being a directed graph having a collection of vertices and ordered nodes connecting the vertices, each resource identification defining a vertex of the directed graph.
Claim 33
Dependent Claim
41 words
The apparatus recited in claim 29 , partitioning the web-graph into sub-graphs comprising: coarsening the web-graph to create sub-graphs, the sub-graphs comprising identifiable groupings of objects, where coarsening comprises contracting the vertices in the web-graph; and dynamically recognizing each identifiable sub-graph.
Claim 34
Dependent Claim
21 words
The apparatus recited in claim 30 , further comprising creating sub-graphs comprising clusters of resources having physical closeness to one another.
Claim 35
Dependent Claim
21 words
The apparatus recited in claim 31 , further comprising creating sub-graphs comprising clusters of resources having hyperlink closeness to one another.
Claim 36
Dependent Claim
46 words
The apparatus recited in claim 32 , further comprising estimating a weight for each node of a graph, the weight reflecting a number of visits to the node, a cumulative total of the weights for nodes contained in a sub-graph being used for processing (load) balancing.
Claim 37
Dependent Claim
44 words
The apparatus recited in claim 33 , load balancing including: maintaining information regarding average access time and processing time of an object or a sub-graph, these access and processing times forming a processing rate; mapping sub-graphs to desired processors based upon processing rate differences.
Claim 38
Dependent Claim
27 words
The apparatus recited in claim 34 , further comprising: identifying communities of sub-graphs that have numerous connections; and mapping sub-graphs having numerous connections to a same processor.
Claim 39
Dependent Claim
20 words
The apparatus recited in claim 35 , further comprising using a hierarchically structured namespace having syntactic components to identify objects.
Claim 40
Dependent Claim
79 words
The apparatus recited in claim 35 , further comprising: maintaining a queue and a hit-hash for each processor of sub-graphs, the hit-hash maintained for objects having a potentially large in-degree; checking the processors hit-hash for the object if a new object is encountered by a processor, and processing the object if is the hit-hash, otherwise; moving the object to a temporary location; having each another processor check its hit-hash and queue for the object; and further processing the object.
Claim 41
Dependent Claim
30 words
The apparatus recited in claim 35 , further comprising using non-preferred (lightweight) processors and preferred processors for processing, wherein a lightweight processor can be removed from processing at any time.
Claim 42
Dependent Claim
26 words
The apparatus recited in claim 38 , further comprising not re-balancing the processing load between processors when a lightweight processor is added or removed from processing.
Claim 43
Independent Claim
163 words
An apparatus for traversing an information system to retrieve designated objects, the apparatus comprising: a means for recognizing a format for an object retrieved; a means for summarizing and reading varying data formats communicatively coupled to the recognizing means; a means for expanding objects having a compressed format and communicatively coupled to the recognizing means and the summarizing means; storage means and processor means included in one or more of the above, the storage means for storing digital signals, the processor means for reading digital signals and traversing the information system to retrieve designated objects by: constructing logical web-graphs defining logical relationships between specified objects in the information system; partitioning the web-graph into sub-graphs; and processing the specified objects to locate desired objects by: balancing the processing of the specified objects by mapping the sub-graphs to one or more preferred processors, wherein a processor is preferred if it reduces processing time or overhead; and re-balancing the processing if the processing load becomes unbalanced.
Claim 44
Independent Claim
163 words
An apparatus for traversing an information system to retrieve designated objects, the apparatus comprising: a means for recognizing a format for an object retrieved; a means for summarizing and reading varying data formats communicatively coupled to the recognizing means; a means for expanding objects having a compressed format and communicatively coupled to the recognizing means and the summarizing means; storage means and processor means included in one or more of the above, the storage means for storing digital signals, the processor means for reading digital signals and traversing the information system to retrieve designated objects by: constructing logical web-graphs defining logical relationships between specified objects in the information system; partitioning the web-graph into sub-graphs; and processing the specified objects to locate desired objects by: balancing the processing of the specified objects by mapping the sub-graphs to one or more preferred processors, wherein a processor is preferred if it reduces processing time or overhead; and re-balancing the processing if the processing load becomes unbalanced.
Claim 45
Dependent Claim
23 words
The apparatus recited in claim 40 , further comprising a means for pushing the located desired objects to a user desiring the objects.
Claim 46
Dependent Claim
47 words
The apparatus recited in claim 40 , wherein the web-graph defines a resource identification space containing resource identifications, the resource identification space being a directed graph having a collection of vertices and ordered nodes connecting the vertices, each resource identification defining a vertex of the directed graph.
Claim 47
Dependent Claim
47 words
The apparatus recited in claim 42 , partitioning the web-graph into sub-graphs comprising: a means for coarsening the web-graph to create sub-graphs, the sub-graphs comprising identifiable groupings of objects, where coarsening comprises contracting the vertices in the web-graph; and a means for dynamically recognizing each identifiable sub-graph.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-01-30 | 2004-07-31 | 2005-01-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-01-30 | 2008-07-31 | 2009-01-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-01-30 | 2012-07-31 | 2013-01-30 | $7700.00 | Window Closed / Lapsed |