# US 2014/0195510 A1 · Partitioning a search space for distributed crawling > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0195510 A1 - Document ID: US20140195510A1 - Status: Published application - Kind: A1 - Application number: 14/035,626 - Filed: 2013-09-24 - Published: 2014-07-10 - Earliest claimed: 2012-09-24 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Guy-Vincent Jourdan; losif Viorel Onut; Seyed M. Taheri; Gregor von Bochmann - Web page: https://patentgrep.com/patent/US20140195510A1 ## CPC - G06F 16/951: Indexing; Web crawling techniques - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract An illustrative embodiment of a computer-implemented process for partitioning a crawling space computes an event identifier for each event in the set of events to form an identified set of events, segments the identified set of events into a number of partitions, assigns a partition to each node in a set of nodes and executes each event in each assigned partition by a respective node. In response to a determination that a new state is discovered, other nodes are notified of the new state, in which information associated with the new state is added to a respective assigned set of event IDs at each node. In response to a determination that no more notifications exist, the computer-implemented process determines whether more events to process exist and terminates in response to a determination that no more events to process exist. ## Claims ### Claim 1 A computer-implemented process for partitioning a crawling space, comprising: computing an event identifier for each event in a set of events to form an identified set of events; segmenting the identified set of events into a number of partitions; assigning a partition to each node in a set of nodes; executing each event in each assigned partition by a respective node; determining whether a new state is discovered; responsive to a determination that the new state is discovered, notifying other nodes of the new state; adding information associated with the new state to a respective assigned set of event IDs at each node; determining whether more notifications exist; responsive to a determination that no more notifications exist, determining whether more events to process exist; and responsive to a determination that no more events to process exist, terminating. ### Claim 2 (depends on 1) The computer-implemented process of claim 1 wherein the computing an event identifier for each event in the set of events to form an identified set of events further comprises receiving a document object model including the set of events, wherein each event in the set of events is a JavaScript event. ### Claim 3 (depends on 1) The computer-implemented process of claim 1 wherein the computing an event identifier for each event in the set of events to form an identified set of events further comprises selecting a computation method from a group comprising: a first computation using an index of events in a document object model, wherein the index is computed by traversing the document object model starting from a root outward towards leaves using a breadth first search, wherein a first JavaScript event encountered is assigned an index value of 0, and each next JavaScript event encountered is assigned an index value incremented by 1 from a previous JavaScript event encountered; and a second computation in which an XPath of an identified event in the set of events forms an event identifier. ### Claim 4 (depends on 3) The computer-implemented process of claim 3 wherein the segmenting the identified set of events into a number of partitions further comprises: dividing identified event identifiers among nodes, wherein a division is determined according to the computation method used to compute the event identifiers, wherein when the first computation is used, division of the event identifiers uses ranges and a modulo function, wherein for n nodes each node receives 1/n set of events and for each event the identifier modulo n provides an index of a node responsible for executing that particular event identifier, and wherein when the second computation is used, the division is determined using a tree structure of the document object model, assigning each different branch to a different node. ### Claim 5 (depends on 1) The computer-implemented process of claim 1 wherein the computing an event identifier for each event in the set of events to form an identified set of events that further defines a crawling space of a rich Internet application for distributed crawling. ### Claim 6 (depends on 1) The computer-implemented process of claim 1 wherein the adding information associated with the new state to a respective assigned set of event IDs at each node further comprises adding information including sequences of JavaScript actions required to reach the new state. ### Claim 7 (depends on 1) The computer-implemented process of claim 1 wherein the notifying other nodes of the new state further comprises communicating the information by one of nodes broadcasting, using a token ring, posting to a common site where other nodes periodically view posts to identify additional work items of the newly discovered states that have not been notified previously. ### Claim 8 A computer program product for partitioning a crawling space, comprising a storage medium embodied with machine-readable program instructions, which when executed by a computer causes the computer to implement a process, the process comprising: computing an event identifier for each event in the set of events to form an identified set of events; segmenting the identified set of events into a number of partitions; assigning a partition to each node in a set of nodes; each event in each assigned partition by a respective node; determining whether a new state is discovered; responsive to a determination that the new state is discovered, notifying other nodes of the new state; adding information associated with the new state to a respective assigned set of event IDs at each node; determining whether more notifications exist; responsive to a determination that no more notifications exist, determining whether more events to process exist; and responsive to a determination that no more events to process exist, terminating. ### Claim 9 (depends on 8) The computer program product of claim 8 wherein the computing an event identifier for each event in the set of events to form an identified set of events further comprises receiving a document object model including the set of events, wherein each event in the set of events is a JavaScript event. ### Claim 10 (depends on 8) The computer program product of claim 8 wherein the computing an event identifier for each event in the set of events to form an identified set of events further comprises selecting a computation method from a group comprising: a first computation using an index of events in a document object model, wherein the index is computed by traversing the document object model starting from a root outward towards leaves using a breadth first search, wherein a first JavaScript event encountered is assigned an index value of 0, and each next JavaScript event encountered is assigned an index value incremented by 1 from a previous JavaScript event encountered; and a second computation in which an XPath of an identified event in the set of events forms an event identifier. ### Claim 11 (depends on 10) The computer program product of claim 10 wherein the segmenting the identified set of events into a number of partitions further comprises: dividing identified event identifiers among nodes, wherein a division is determined according to the computation method used to compute the event identifiers, wherein when the first computation is used, computer executable program code for division of the event identifiers uses ranges and a modulo function, wherein for n nodes each node receives 1/n set of events and for each event the identifier modulo n provides an index of a node responsible for executing that particular event identifier, and wherein when the second computation is used, computer executable program code for the division uses a tree structure of the document object model, assigning each different branch to a different node. ### Claim 12 (depends on 8) The computer program product of claim 8 wherein the computing an event identifier for each event in the set of events to form an identified set of events that further defines a crawling space of a rich Internet application for distributed crawling. ### Claim 13 (depends on 8) The computer program product of claim 8 wherein the adding information associated with the new state to a respective assigned set of event IDs at each node further comprises adding information including sequences of JavaScript actions required to reach the new state. ### Claim 14 (depends on 8) The computer program product of claim 8 wherein the notifying other nodes of the new state further comprises communicating the information by one of nodes broadcasting, using a token ring, and posting to a common site where other nodes periodically view posts to identify additional work items of the newly discovered states that have not been notified previously. ### Claim 15 An apparatus for partitioning a crawling space, the apparatus comprising: a communications fabric; a memory connected to the communications fabric, wherein the memory contains computer executable program code; a communications unit connected to the communications fabric; an input/output unit connected to the communications fabric; a display connected to the communications fabric; and a processor connected to the communications fabric configured to: compute an event identifier for each event in the set of events to form an identified set of events, segment the identified set of events into a number of partitions, assign a partition to each node in a set of nodes, execute each event in each assigned partition by a respective node, determine whether a new state is discovered, responsive to a determination that the new state is discovered, notify other nodes of the new state; add information associated with the new state to a respective assigned set of event IDs at each node, determine whether more notifications exist, responsive to a determination that no more notifications exist, determine whether more events to process exist; and responsive to a determination that no more events to process exist, terminate. ### Claim 16 (depends on 15) The apparatus of claim 15 wherein the processor is further configured to compute an event identifier for each event in the set of events to form an identified set of events and to receive a document object model including the set of events, wherein each event in the set of events is a JavaScript event. ### Claim 17 (depends on 15) The apparatus of claim 15 wherein the processor is further configured to compute an event identifier for each event in the set of events to form an identified set of events further directs the apparatus to: select a computation method from a group comprising: a first computation using an index of events in a document object model, wherein the index is computed by traversing the document object model starting from a root outward towards leaves using a breadth first search, wherein a first JavaScript event encountered is assigned an index value of 0, and each next JavaScript event encountered is assigned an index value incremented by 1 from a previous JavaScript event encountered; and a second computation in which an XPath of an identified event in the set of events forms an event identifier. ### Claim 18 (depends on 17) The apparatus of claim 17 wherein the processor is further configured to segment the identified set of events into a number of partitions: dividing identified event identifiers among nodes, wherein a division is determined according to the computation method used to compute the event identifiers, wherein when the first computation is used, division of the event identifiers uses ranges and a modulo function, wherein for n nodes each node receives 1/n set of events and for each event the identifier modulo n provides an index of a node responsible for executing that particular event identifier, and wherein when the second computation is used, the division is determined using a tree structure of the document object model, assigning each different branch to a different node. ### Claim 19 (depends on 15) The apparatus of claim 15 wherein the processor is further configured to compute an event identifier for each event in the set of events to form an identified set of events that further defines a crawling space of a rich Internet application for distributed crawling. ### Claim 20 (depends on 15) The apparatus of claim 15 wherein the processor unit is further configured to add information associated with the new state to a respective assigned set of event IDs at each node and add information including sequences of JavaScript actions required to reach the new state.