{
  "id": "enwiki-001359913167",
  "slug": "pointer-jumping",
  "title": "Pointer jumping",
  "qid": "",
  "lead": "Pointer jumping or path doubling is a design technique for parallel algorithms that operate on pointer structures, such as linked lists and directed graphs. Pointer jumping allows an algorithm to follow paths with a time complexity that is logarithmic with respect to the length of the longest path. It does this by \"jumping\" to the end of the path computed by neighbors. The basic operation of pointer jumping is to replace each neighbor in a pointer structure with its neighbor's neighbor. In each step of the algorithm, this replacement is done for all nodes in the data structure, which can be done independently in parallel. In the next step when a neighbor's neighbor is followed, the neighbor's path already followed in the previous step is added to the node's followed path in a single step. Thus, each step effectively doubles the distance traversed by the explored paths. Pointer jumping is best understood by looking at simple examples such as list ranking and root finding.",
  "body": "Pointer jumping or path doubling is a design technique for parallel algorithms that operate on pointer structures, such as linked lists and directed graphs. Pointer jumping allows an algorithm to follow paths with a time complexity that is logarithmic with respect to the length of the longest path. It does this by \"jumping\" to the end of the path computed by neighbors. The basic operation of pointer jumping is to replace each neighbor in a pointer structure with its neighbor's neighbor. In each step of the algorithm, this replacement is done for all nodes in the data structure, which can be done independently in parallel. In the next step when a neighbor's neighbor is followed, the neighbor's path already followed in the previous step is added to the node's followed path in a single step. Thus, each step effectively doubles the distance traversed by the explored paths. Pointer jumping is best understood by looking at simple examples such as list ranking and root finding. if successor_next = successor then break for i ← 1 to length(successor) do in parallel successor[i] ← successor_next[i] return successor The following image provides an example of using pointer jumping on a small forest. On each iteration the successor points to the vertex following one more successor. After two iterations, every vertex points to its root node.",
  "categories": [
    "109374363",
    "20476448",
    "22903405",
    "22947099",
    "22974238",
    "23118434",
    "23603337",
    "24043274"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1359913167",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1781737663.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001359913167",
    "type": "webpage",
    "title": "Pointer jumping",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/pointer-jumping",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001359913167",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1359913167",
    "note": "Immutable snapshot enwiki-001359913167"
  }
}