US Patent 11403302 Quantile data sketches based on frequent data items

Data items are aggregated in a quantile sketch according to a compactor hierarchy. A first number of data items are stored in a first buffer corresponding to a first (i.e., lowest) compaction level of the compactor hierarchy, and a top level number of data items are stored in a top buffer corresponding to a top compaction level of the compactor hierarchy. For a first subset of the first number of data items, each data item is already stored in the top buffer, and a weight of the respective data item stored in the top buffer is increased by 1. For a second subset of the first number of data items, each data item does not match any data item stored in the top buffer, and a second number of data items are selected from the second subset and stored in a second buffer of a second compaction level.