One-sentence Summary

Researchers at Eindhoven University of Technology propose OmniSketch, the first sketch data structure that scales to high-velocity multi-attribute data streams and supports count aggregates with arbitrary filters on multiple attributes chosen dynamically at query time, providing probabilistic guarantees, a favorable space-accuracy trade-off, and logarithmic worst-case complexity for both updates and queries while outperforming state-of-the-art methods on real and synthetic data.

Key Contributions

• OmniSketch provides a sketch-based summary for fast-paced, multi-attribute data streams and supports count aggregates with filters on arbitrary attribute subsets selected at query time.

• The summary builds a compact nested sketch from K-minwise hashing while providing probabilistic accuracy guarantees, a favorable space-accuracy tradeoff, and worst-case logarithmic complexity for updating and query execution.

• Experiments on real and synthetic streams show that OmniSketch approximates complex ad hoc queries within configured accuracy guarantees with small memory, outperforms prior state-of-the-art techniques by more than two orders of magnitude in throughput, and reaches more than 89,000 updates per second on an 11-attribute stream with a 200 MB sketch.

Introduction

High-velocity multi-attribute streams, such as network monitoring data, require compact summarization so that aggregate queries can be answered without storing the entire stream, making sketch-based analytics important. Existing sketches usually support single-attribute or predefined predicate combinations, and covering arbitrary multi-attribute predicates requires exponentially many sketches, while prior multi-dimensional solutions such as Hydra incur rapidly growing update time and error as the number of attributes increases. The authors leverage a hybrid design called OmniSketch, which combines Count-Min-like sketching with fixed-size k-minwise summaries inside sub-sketches, enabling query-time predicates over many attributes with linear or near-linear complexity, formal error guarantees, and an automated memory-efficient initialization procedure.

Dataset

• Dataset composition and sources: The authors make the source code, data, and other artifacts available in the artifact repository linked to the paper.

• Key subset details: The provided text does not include dataset subset sizes, source breakdowns, filtering rules, schema fields, or summary statistics.

• How the data is used: The material is presented as accompanying artifacts for the paper, rather than as a described training corpus with explicit training splits or mixture ratios.

• Processing and metadata: The excerpt does not describe cropping strategies, metadata construction, cleaning steps, or other dataset processing details.

Method

The authors leverage a Count-Min backbone that is extended with record identifiers so that cardinality queries with multiple predicates can be answered without materializing the underlying dataset. The method is organized around a common architecture that is shared by three variants, with each variant differing primarily in how much per-cell record information is retained and in how that information is used during estimation.

For a set of searchable attributes $\mathcal{A} = \{a_1, a_2, \ldots, a_{|\mathcal{A}|}\}$A={a1​,a2​,…,a∣A∣​}, the authors maintain one attribute sketch per attribute. Each attribute sketch is a two-dimensional array $CM_i$CMi​ of size $w \times d$w×d and is associated with $d$d pairwise-independent hash functions $h_i^1(\cdot), h_i^2(\cdot), \ldots, h_i^d(\cdot)$hi1​(⋅),hi2​(⋅),…,hid​(⋅). When a record arrives, its value on attribute $a_i$ai​ is hashed into a bucket in sketch $CM_i$CMi​ for every row $j$j. Unlike a conventional Count-Min sketch, where a bucket stores only a frequency counter, each bucket stores a set of record identifiers, or rid values, associated with all records whose corresponding attribute value falls into that bucket. This design allows query execution to transform each predicate into a lookup in the corresponding attribute sketch and then combine the retrieved rid sets by set intersection.

The common architecture is illustrated below.

In the base construction, referred to as $\mathbb{S}0$S0, every matching record is inserted into all attribute sketches. At initialization, the authors choose $w = 1 + \lceil e/\epsilon \rceil$w=1+⌈e/ϵ⌉ and $d = \lceil \ln(1/\delta) \rceil$d=⌈ln(1/δ)⌉ to obtain $(\epsilon, \delta)$(ϵ,δ) guarantees. During insertion of a record with identifier $r_0$r0​, the record id is added to the linked list stored in each bucket $CM_i[j, h_i^j(r_i)]$CMi​[j,hij​(ri​)], where $r_i$ri​ is the record’s value on attribute $a_i$ai​.

For a query $q$q containing predicates $q_i$qi​, such as $a_i = v_{q_i}$ai​=vqi​​, the authors first consider the straightforward estimator $\mathbb{S}0_{\min}$S0min​. For each row $j$j, they retrieve one bucket from each relevant attribute sketch and intersect the stored rid sets. The row-wise estimates are then combined by taking the minimum across rows:

$$\hat{f}_{\min}(q) = \min_{j = \{1, \ldots, d\}} \left| \bigcap_{q_i \in q} CM_i\left[j, h_i^j(v_{q_i})\right] \right|.$$f^​min​(q)=j={1,…,d}min​​qi​∈q⋂​CMi​[j,hij​(vqi​​)]​.

This estimator follows the standard Count-Min philosophy: all true matching records are guaranteed to be included because equal values hash to the same bucket in every row, but the estimate may be inflated by false positives caused by hash collisions. The authors prove that this construction satisfies the probabilistic bound

$$\Pr\left( \left|\hat{f}(q) - f(q)\right| \le \epsilon N \right) \ge 1 - \delta.$$Pr(​f^​(q)−f(q)​≤ϵN)≥1−δ.

The authors then observe that the full rid information already present in $\mathbb{S}0$S0 can support a tighter estimator without changing the sketch structure. In $\mathbb{S}0_{\cap}$S0∩​, the row-wise minimum is removed. Instead, the algorithm intersects rid sets across both predicates and rows:

$$\hat{f}(q) = \left| \bigcap_{i = \{1, \ldots, p\},\, j = \{1, \ldots, d\}} CM_i\left[j, h_i^j(v_{q_i})\right] \right|.$$f^​(q)=​i={1,…,p},j={1,…,d}⋂​CMi​[j,hij​(vqi​​)]​.

This stronger estimator exploits the fact that a true matching record must collide in all rows for all predicates, while a false positive is much less likely to do so. As a result, the error bound improves to

$$\Pr\left( \left|\hat{f}(q) - f(q)\right| \le \epsilon^d (N - f(q)) \le \epsilon^d N \right) \ge 1 - \delta.$$Pr(​f^​(q)−f(q)​≤ϵd(N−f(q))≤ϵdN)≥1−δ.

The final OmniSketch variant, denoted $\mathbb{S}1$S1, preserves the same overall architecture but replaces full rid sets with bounded minwise samples so that space becomes sublinear in the stream length. Each cell $CM_i[j, k]$CMi​[j,k] stores three pieces of information: the total number of records hashed into that cell, a sample of at most $B$B hashed rid values produced by an auxiliary hash function $g(r_0)$g(r0​), and the maximum sampled hash value in that cell. The hash function $g$g maps record identifiers into $b$b-bit values, with $b$b chosen to support the minwise sampling guarantee.

During insertion, the algorithm first increments the counter of every cell to which the new record maps across the attribute sketches. Then it decides whether to insert the record’s $g(r_0)$g(r0​) value into the cell’s sample. If the sample is not full, the value is added directly. If the sample is full, the value replaces the current maximum only when the new hash value is smaller than that maximum. This produces a $B$B-sized minwise sample per cell.

Query estimation in $\mathbb{S}1$S1 mirrors the improved $\mathbb{S}0_{\cap}$S0∩​ logic but operates on samples instead of complete rid sets. The query identifies the relevant cells across all attribute sketches and all rows, computes $n_{\max}$nmax​ as the largest cell count among those cells, and intersects the samples stored in those cells:

$$S_{\cap} = \bigcap_{i = \{1, \ldots, p\},\, j = \{1, \ldots, d\}} S_i\left(j, h_i^j(v_{q_i})\right).$$S∩​=i={1,…,p},j={1,…,d}⋂​Si​(j,hij​(vqi​​)).

The OmniSketch estimator is then

$$\hat{f}(q) = \frac{n_{\max}}{B} \times |S_{\cap}|.$$f^​(q)=Bnmax​​×∣S∩​∣.

This scaling corrects for the fact that only a bounded number of records is retained per cell. The authors also provide a sanity bound for cases in which the sampled intersection is too small to support a reliable scaled estimate. The method maintains logarithmic insertion time with respect to the sample size and supports multi-way joins over samples efficiently when the per-cell samples are stored in ordered data structures.

The framework can also be extended to range predicates by adding dyadic-range versions of each numeric attribute sketch. For a numeric attribute, multiple internal sketches store statistics for ranges of increasing powers of two. A record is inserted into the sketches corresponding to all dyadic ranges that contain its value, while a range query is decomposed into its canonical dyadic cover, and the corresponding sampled or rid-based cell sets are merged during query execution.

Experiment

The experiments evaluate the proposed sketches on real network monitoring streams and synthetic data, using varied query workloads to assess ingestion efficiency, memory use, accuracy, and query execution. Comparisons show that S1 provides the best overall tradeoff, scaling more efficiently than the S0 variants and outperforming Hydra especially on streams with many attributes. Additional results indicate that S1 remains efficient and accurate across different data distributions, large stream sizes, and range query settings.

The example stream shows how queries can apply predicates over network attributes such as source, destination, length, and DSCP. In the reported experiments, the range-enabled S1 summarizes multiple attributes with linear growth in memory and ingestion time. Supporting range queries adds overhead, but the observed impact remains modest while accuracy stays high. Memory and ingestion time grow linearly with the number of summarized attributes. Range support adds dyadic range state, but the overhead is smaller than expected because many large ranges are sparse. Mean error for range queries remained low and within the expected bound.

The notation defines the stream size, query cardinality, sketch dimensions, per-cell sample capacity, and attribute sketches used for frequency estimation. Experiment results show that range-enabled sketches keep time and memory growth linear with the number of attributes, while incurring extra overhead compared with standard sketches at the same sample budget. Their range-query estimates remain accurate, with low mean errors that are within the reported theoretical bound. Storage and ingestion scale linearly with the number of searchable attributes. Adding range support uses more memory and time because more internal attribute sketches store dyadic ranges. Range-query estimates show low mean error and remain within the reported theoretical guarantee.

The S1 variants execute queries much faster than the S0 estimators, with larger memory quotas tending to increase query time. The S0∩ estimator has the lowest observed average error, while S0min has the slower query execution and larger error among S0 methods. S1 maintains low error across memory settings despite slower execution as more memory is allowed. S1 query execution is substantially faster than S0 execution. S0∩ provides the most accurate estimates, while larger S1 memory settings keep error low but increase query time.

The table compares query execution time for S1 and Hydra under equal memory budgets across queries with increasing predicate count. Hydra remains faster overall, with execution times staying very low and changing little as more predicates are added. S1 is slower, especially at larger memory quotas, although its query time generally decreases when queries include more predicates. Hydra achieves lower query execution times than S1 across all compared memory budgets. S1 query times grow noticeably with larger memory allocations but tend to shrink as predicate count increases.

The experiments evaluate range-enabled S1 sketches for network-stream queries by measuring memory, ingestion, range-query accuracy, query execution against S0 estimators, and performance relative to Hydra. They find that supporting multiple attributes and range predicates scales linearly in memory and ingestion time, with modest overhead and estimates that remain accurate within theoretical bounds. Query comparisons show that S1 is substantially faster than S0 estimators and maintains low error, while S0 offers higher accuracy, and Hydra achieves lower execution times than S1 across settings, though S1 query time tends to decrease as predicate count increases.