US 11,886,413 B1Granted

Time-sliced approximate data structure for storing group statistics

AssigneeRapid7, Inc.

InventorsMiguel Angel Casanova, David Christopher Tracey

Life of this patent

Estimating the term…

Loading patent…

Abstract

Systems and methods are disclosed to implement a bounded group by query system that computes approximate time-sliced statistics for groups of records in a dataset according to a group by query. In embodiments, a single pass scan of the dataset is performed to accumulate exact results for a maximum number of groups in a result grouping structure (RGS) and approximate results for additional groups in an approximate result grouping structure (ARGS). RGSs and ARGSs are accumulated by a set of accumulator nodes and provided to an aggregator node, which combines the received structures to generate exact or approximate statistical results for at least a subset of the groups in the dataset. Advantageously, the disclosed query system is able to produce approximate results for at least some of the groups in a single pass of the dataset using size-bounded data structures, without predetermining the actual number of groups in the dataset.

Claims20

Dependent claims

A method comprising:

performing, by a computing system having one or more hardware processors and associated memory:
creating in memory a time-sliced approximate data structure (TSADS) that includes a counts matrix and a statistics matrix, wherein:
(a) the statistics matrix is used to store approximate statistics for different groups of timestamped datapoints in a plurality of time slices,
(b) the counts matrix implements a count-min sketch to store approximate counts of datapoints in the different groups in the time slices,
(c) the counts matrix is a three-dimensional matrix, wherein a first dimension corresponds to a set of hash functions used to hash the group key, a second dimension corresponds to respective hash buckets of the hash functions, and a third dimension corresponds to individual ones of the time slices, and
(d) the statistics matrix has the same dimensions as the counts matrix:
receiving a retrieve request to retrieve, from the TSADS, approximate statistics for a group of datapoints in the time slices, wherein the retrieve request specifies a group key of the group;
in response to the retrieve request:
for each of the time slices:
selecting a set of cells in the count-min sketch in the counts matrix based on the group key and the time slice, wherein each cell in the set stores an approximate count of datapoints in the group in the time slice;
determining a first cell from the set that stores a best approximate count;
and
determining a best approximate statistic of the group in the time slice, wherein the best approximate statistic is retrieved from a second cell in the statistics matrix that corresponds to the first cell in the counts matrix;
and
returning a time series of best approximate statistics of the group determined for each time slice.

12 more elements

A system, comprising:

a computer system comprising one or more hardware processors and associated memory that stores program instructions that when executed on the one or more hardware processors cause the computer system to:
create in memory a time-sliced approximate data structure (TSADS) that includes a counts matrix and a statistics matrix, wherein:
(a) the statistics matrix is used to store approximate statistics for different groups of timestamped datapoints in a plurality of time slices,
(b) the counts matrix implements a count-min sketch to store approximate counts of datapoints in the different groups in the time slices,
(c) the counts matrix is a three-dimensional matrix, wherein a first dimension corresponds to a set of hash functions used to hash the group key, a second dimension corresponds to respective hash buckets of the hash functions, and a third dimension corresponds to individual ones of the time slices, and
(d) the statistics matrix has the same dimensions as the counts matrix:
receive a retrieve request to retrieve, from the TSADS, approximate statistics for a group of datapoints in the time slices, wherein the retrieve request specifies a group key of the group;
in response to the retrieve request:
for each of the time slices:
select a set of cells in the count-min sketch in the counts matrix based on the group key and the time slice, wherein each cell in the set stores an approximate count of datapoints in the group in the time slice;
determine a first cell from the set that stores a best approximate count;
and
determine a best approximate statistic of the group in the time slice, wherein the best approximate statistic is retrieved from a second cell in the statistics matrix that corresponds to the first cell in the counts matrix;
and
return a time series of best approximate statistics of the group determined for each time slice.

12 more elements

One or more non-transitory computer-accessible storage media storing program instructions that when executed on or across one or more processors cause the one or more processors to:

create in memory a time-sliced approximate data structure (TSADS) that includes a counts matrix and a statistics matrix, wherein:
(a) the statistics matrix is used to store approximate statistics for different groups of timestamped datapoints in a plurality of time slices,
(b) the counts matrix implements a count-min sketch to store approximate counts of datapoints in the different groups in the time slices,
(c) the counts matrix is a three-dimensional matrix, wherein a first dimension corresponds to a set of hash functions used to hash the group key, a second dimension corresponds to respective hash buckets of the hash functions, and a third dimension corresponds to individual ones of the time slices, and
(d) the statistics matrix has the same dimensions as the counts matrix;
receive a retrieve request to retrieve, from the TSADS, approximate statistics for a group of datapoints in the time slices, wherein the retrieve request specifies a group key of the group;
in response to the retrieve request:
for each of the time slices:
select a set of cells in the count-min sketch in the counts matrix based on the group key and the time slice, wherein each cell in the set stores an approximate count of datapoints in the group in the time slice;
determine a first cell from the set that stores a best approximate count;
and
determine a best approximate statistic of the group for the time slice, wherein the best approximate statistic is retrieved from a second cell in the statistics matrix that corresponds to the first cell in the counts matrix;
and
return a time series of best approximate statistics of the group determined for each time slice.

11 more elements

Dependencies are inferred from the claim text.