Hierarchical data skipping using data sketches

Patent metadata

Field	Value
Publication number	US-11954085-B1
Application number	US-202217934440-A
Country	US
Kind code	B1
Filing date	Sep 22, 2022
Priority date	Sep 22, 2022
Publication date	Apr 9, 2024
Grant date	Apr 9, 2024

Abstract

A computer implemented method performs data skipping in a hierarchically organized computing system. A group of processor units determines leaf node data sketches for data in leaf nodes in the hierarchically organized computing system. The leaf node data sketches summarize attributes of data in the leaf nodes. The group of processor units aggregates the leaf node data sketches at intermediate nodes in the hierarchically organized computing system to form aggregated data sketches at the intermediate nodes and retains data sketches received at the intermediate nodes from a group of child nodes to form retained data sketches. The retained data sketches are one of leaf node data sketches and the aggregated data sketches. The group of processor units searches the data using the retained data sketches and the data skipping within the hierarchically organized computing system in response to queries made to the intermediate nodes in the hierarchically organized computing system.

First claim

What is claimed is:

1. A computer implemented method for data skipping in a hierarchically organized computing system, the computer implemented method comprising:
determining, by a group of processor units, leaf node data sketches for data in leaf nodes in the hierarchically organized computing system, wherein the leaf node data sketches summarize attributes of the data in the leaf nodes;
aggregating, by the group of processor units, the leaf node data sketches at intermediate nodes in the hierarchically organized computing system to form aggregated data sketches at the intermediate nodes;
retaining, by the group of processor units, data sketches received at the intermediate nodes from a group of child nodes to form retained data sketches, wherein the retained data sketches are one of leaf node data sketches and the aggregated data sketches;
searching, by the group of processor units, the data using the retained data sketches and the data skipping within the hierarchically organized computing system in response to queries made to the intermediate nodes in the hierarchically organized computing system;
wherein the leaf nodes in the hierarchically organized computing system are client devices and the intermediate nodes in the hierarchically organized computing system are server computers, and further comprising:
updating, by the group of processor units, the leaf node data sketches from the data in the leaf nodes in response to an event to form updated leaf node data sketches; and
aggregating, by the group of processor units, the updated leaf node data sketches at the intermediate nodes in the hierarchically organized computing system.

2. The computer implemented method of claim 1 , wherein the event is one of a periodic event and a non-periodic event.

3. The computer implemented method of claim 1 , wherein updating the leaf node data sketches from the data in the leaf nodes comprises:
determining, by the group of processor units, the updated leaf node data sketches from the data in changed leaf nodes, which are a subset of the leaf nodes;
replacing prior corresponding leaf node data sketches with the updated leaf node data sketches; and
aggregating, by the group of processor units, the updated leaf node data sketches at the intermediate nodes in the hierarchically organized computing system to form updated aggregated data sketches in response to replacing the prior corresponding leaf node data sketches with the updated leaf node data sketches.

4. The computer implemented method of claim 1 , wherein an intermediate node in the intermediate nodes is a data generator and the method further comprising:
generating an intermediate data sketch for the data in the intermediate node; and
aggregating child data sketches received from child nodes of the intermediate node and the intermediate data sketch generated by the intermediate node to form an aggregated data sketch.

5. The computer implemented method of claim 1 further comprising:
receiving, by the group of processor units, a query at an intermediate node in the intermediate nodes,
comparing, by the group of processor units, the query to the group of retained data sketches at the intermediate node;
sending, by the group of processor units, the query to a set of child nodes in the group of child nodes based on a match of the query to a set of retained data sketches for the set of child nodes, wherein a child node in the group of child nodes is skipped when a retained data sketch received from the child node does not have a match to an associated retained data sketch at the intermediate node;
aggregating, by the group of processor units, a group of results received in response to the query to form an aggregated result; and
returning, by the group of processor units, the aggregated result to a requestor.

6. The computer implemented method of claim 5 further comprising:
receiving, at a leaf node in the set of child nodes, the query sent from the intermediate node through a hierarchy in the hierarchically organized computing system;
running the query on the data in the leaf node; and
returning a result to the intermediate node through the hierarchy in the hierarchically organized computing system.

7. A computer system comprising:
a group of processor units, wherein the group of processor units executes program instructions to:
determine leaf node data sketches for data in leaf nodes in a hierarchically organized computing system, wherein the leaf node data sketches summarize attributes of the data in the leaf nodes;
aggregate the leaf node data sketches at intermediate nodes in the hierarchically organized computing system to form aggregated data sketches at the intermediate nodes;
retain data sketches received at the intermediate nodes from a group of child nodes to form retained data sketches, wherein the retained data sketches are one of leaf node data sketches and the aggregated data sketches;
search the data using the retained data sketches and the data skipping within the hierarchically organized computing system in response to queries made to the intermediate nodes in the hierarchically organized computing system;
wherein the leaf nodes in the hierarchically organized computing system are client devices and the intermediate nodes in the hierarchically organized computing system are server computers, and wherein the group of processor units executes program instructions to:
update the leaf node data sketches from the data in the leaf nodes in response to an event to form updated leaf node data sketches; and
aggregate the updated leaf node data sketches at the intermediate nodes in the hierarchically organized computing system.

8. The computer system of claim 7 , wherein the event is one of a periodic even and a non-periodic event.

9. The computer system of claim 7 , wherein as part of updating the leaf node data sketches from the data in the leaf nodes, the group of processor units executes program instructions to:
determine the updated leaf node data sketches from the data in changed leaf nodes, which are a subset of the leaf nodes;
replacing prior corresponding leaf node data sketches with the updated leaf node data sketches; and
aggregate the updated leaf node data sketches at the intermediate nodes in the hierarchically organized computing system to form updated aggregated data sketches in response to replacing the prior corresponding leaf node data sketches with the updated leaf node data sketches.

10. The computer system of claim 7 , wherein an intermediate node in the intermediate nodes is a data generator and the group of processor units executes program instructions to:
generate an intermediate data sketch for the data in the intermediate node; and
aggregate child data sketches received from child nodes of the intermediate node and the intermediate data sketch generated by the intermediate node to form an aggregate data sketch.

11. The computer system of claim 7 , wherein the group of processor units executes program instructions to:
receive a query at an intermediate node in the intermediate nodes, compare the query to the group of retained data sketches at the intermediate node;
send the query to a set of child nodes in the group of child nodes based on a match of the query to a set of retained data sketches for the set of child nodes, wherein a child node in the group of child nodes is skipped when a retained data sketch received from the child node does not have a match to an associated retained data sketch at the intermediate node;
aggregate a group of results received in response to the query to form an aggregated result; and
returning, by the group of processor units, the aggregated resu

Assignees

• IBM

Inventors

• Srivatsa Mudhakar
• Ganti Raghu Kiran
• Rosenkranz Joshua M
• Chu Linsong
• Hoang Trong Tuan Minh
• Mangla Utpal
• Sadagopan Satishkumar
• Thomas Mathews

Classifications

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F16/24556

  Aggregation; Duplicate elimination · CPC title

• G06F16/282

  Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes · CPC title