Higher-order data sketching for ad-hoc query estimation

A system comprising:

• a memory;
• and
• a processing device operatively coupled to the memory, the processing device to:
• receive a data item of a set of data items, the data item comprising a first item value and a second item value;
• access a first probabilistic data structure representing the set of data items, the first probabilistic data structure comprising elements with references to a plurality of second probabilistic data structures;
• evaluate the first probabilistic data structure in view of the first item value to identify a set of the second probabilistic data structures, wherein the evaluating comprises applying a set of hash functions to the first item value to generate hash values indicating the set of second probabilistic data structures corresponding to the first item value;
• evaluate one of the set of second probabilistic data structures in view of the second item value to identify a set of elements of the second probabilistic data structure corresponding to the second item value;
• and
• update the set of elements of the second probabilistic data structure to represent the data item.

A non-transitory machine-readable storage medium storing instructions that cause a processing device to:

• access a first probabilistic data structure representing a set of data items, the first probabilistic data structure comprising elements with references to a plurality of second probabilistic data structures;
• evaluate the first probabilistic data structure in view of a first item value of the set to identify a set of the second probabilistic data structures, wherein the evaluating comprises applying a set of hash functions to the first item value to generate hash values indicating the set of second probabilistic data structures corresponding to the first item value;
• evaluate one of the set of second probabilistic data structures in view of a second item value of th set to identify a set of elements of the second probabilistic data structure corresponding to the second item value;
• and
• analyze the set of elements of the second probabilistic data structure to determine a property of the set of data items.

A method comprising:

• accessing a first probabilistic data structure representing a set of data items, the first probabilistic data structure comprising elements with references to a plurality of second probabilistic data structures;
• evaluating the first probabilistic data structure in view of a first item value of the set to identify a set of the second probabilistic data structures, wherein the evaluating comprises applying a set of hash functions to the first item value to generate hash values indicating the set of second probabilistic data structures corresponding to the first item value;
• evaluating one of the set of second probabilistic data structures in view of a second item value of th set to identify a set of elements of the second probabilistic data structure corresponding to the second item value;
• and
• analyzing the set of elements of the second probabilistic data structure to determine a property of the set of data items.

An apparatus comprising:

• means to receive a data item of a set of data items, the data item comprising a first item value and a second item value;
• means to access a first probabilistic data structure representing the set of data items, the first probabilistic data structure comprising elements with references to a plurality of second probabilistic data structures;
• means to evaluate the first probabilistic data structure in view of the first item value to identify a set of the second probabilistic data structures, wherein the evaluating comprises applying a set of hash functions to the first item value to generate hash values indicating the set of second probabilistic data structures corresponding to the first item value;
• means to evaluate one of the set of second probabilistic data structures in view of the second item value to identify a set of elements of the second probabilistic data structure corresponding to the second item value;
• and
• means to update the set of elements of the second probabilistic data structure to represent the data item.