arXiv:2607.20830v1 [cs.DS] 23 Jul 2026
An Improved Linear Extractable Sketch Data Structure for Flow Count Statistics Patthadon Tantiameorn
Grittin Nuntasombat
Jittat Fakcharoenphol
Department of Computer Engineering Kasetsart University Bangkok, Thailand [email protected]
Department of Computer Engineering Kasetsart University Bangkok, Thailand [email protected]
Department of Computer Engineering Kasetsart University Bangkok, Thailand [email protected]
Abstract—Sketch data structures are very useful for computing statistics on streaming data, including network traffic, server requests, and financial transactions. In recent work, FermatSketch was introduced as an underlying data structure used to monitor changes in network states. It is a linear data structure that maintains an associated array of counters and supports listing all key-counter pairs while using almost linear space. Because it is linear, it can be used to monitor changes between two streams with space proportional to the number of items that change. The data structure is based on a hash table, and all key-counter pairs can be successfully listed when there are slots in the table with exactly one key hashed to them. We show how to relax this requirement by using additional computational resources when listing the key-counter pairs, thereby improving space efficiency with only a small overhead when collecting statistics. We achieve this by storing, for each bucket, multiple linear combinations of the counters whose coefficients are generated from the keys. With this information, certain linear systems can be solved to obtain the key-counter pairs. A preliminary experiment shows a significant reduction of memory needed for the data structure. Our work can be viewed as a trade-off between space and time. Index Terms—Sketches, data structures, linearity, network measurement
I. I NTRODUCTION Data structures that use memory efficiently are crucial for system measurements, as equipment storages are typically limited and hard to expand, unlike that of personal computing devices. In this paper, we consider a data structure design problem in a network monitoring setting where we would like to track the packet losses. While standard techniques (see e.g., [1], [2]) may require space proportional to the total traffic or proportional to the number of distinct flows, the FermatSketch data structure proposed by Kaicheng et al. [3] uses space only proportional to the number of distinct lost flows (which can be much smaller than the total number of flows). The crucial design decision of the FermatSketch is that it is a linear data structure; therefore, the difference of two sketches is still a sketch and when lost flows are considered, the difference sketch has non-zero counters only for the lost flows (referred to later as victim flows), see Figure 1. Moreover, this implies that the data structures only need the space
Fig. 1. We can use linear sketch data structures to track lost flows. Linear sketches SA , SB , SC , and SD track flows on links A, B, C, and D, respectively. To compute lost flows, we can find the difference SA − (SB + SC + SD ).
large enough to keep the victim flows. The FermatSketch is the key to the design of ChameleMon [3], a network measurement system that supports flow-level measurement, and is also an underlying data structure in the DaVinci Sketch [4]. The FermatSketch data structure follows the idea of invertible bloom lookup tables [5]–[7] introduced by Goodrich and Mitzenmacher [5] with a crucial modification to handle count statistics. In this work, we present an improvement on the space usage of FermatSketch by a flow extraction procedure that works on relaxed conditions. In turn, the flow extraction procedure may run much slower. This can be viewed as a space-time tradeoff for data structures that maintain flow counters and support flow counter listing, like the FermatSketch. We note that while it takes longer to extract flow statistics, we believe that the compute needed can be managed much more efficiently and effectively in centralized infrastructure than the limited memory available on networking devices which are more distributed. Our main idea is to let each bucket keep multiple linear combinations of the values stored as in the FermatSketch. The linear combinations are formed using coefficients that are generated from the keys. This information is enough to solve the inverse problem using simply Gaussian elimination, if the coefficients are known. We design the procedure so that the coefficients are selected from a small set of values; thus, by brute force searching through all possible coefficient choices, we can find the correct coefficients and solve the linear system. A preliminary experiment presented in Section V
shows at least 5.8% reduction in memory usage for the 99% accuracy level. When the number of lost flows is small, the advantage is more significant (i.e., when the number of lost flows is 100, we get 34.9% reduction in memory usage). As our data structure can be parameterized to use more time, we believe that we can even further reduce the memory usage. We formally describe the problem in Section II. The key previous work, the FermatSketch data structure [3] is also reviewed in that section. We describe our improvement in Section III and analyze its correctness and its running time requirements in Section IV. Finally, Section V shows the experimental results. A. Related Work Sketch data structures [8] enable memory efficient building blocks for many applications. Among them, CountMin Sketch [9], CountSketch [10], and varieties of Bloom filters [5]–[7], [11] are widely used in practice. For network measurements, sketches have been used to track flow sizes [9], [10], heavy hitters [12], and flow size distributions [13], [14]. Sketches have also been used to track packet losses [1]–[3]. See survey in [15]. II. P ROBLEM STATEMENT Here we describe the requirement for the sketch data structure, abstracted from the interface of FermatSketch from [3], and review its implementation. We are given a multiset F of flow ids F = {f1 , f2 , . . . , fn } and we would like a data structure that reports a count statistics, i.e., it returns a list (f, cf ) for each flow f ∈ F where cf is the number of times f appears in F . We also want the data structure to be linear. As an example, consider a network configuration in Figure 1 where traffics come through link A, go though an interconnect, and exit through links B, C, and D. We can keep the flow count statistics for each link as a linear data structure: SA , SB , SC , and SD . To find the lost flows, we can compute SA − (SB + SC + SD ), and extract the flow count statistics from this sketch. We shall design a data structure S that maintains a counter for each flow (using the flow id f as a key). It should support the following operations: • addF low(S, f ) – adds 1 to the counter for flow id f • extract(S) – returns the list of tuples (f, cf ) where f is the flow id and cf is the counter for flow id f . We also want the data structure to be linear. More specifically, if we have data structures S and S ′ for input multisets F and F ′ , the data structure for multiset a · F ′ + b · F , where a · F represents a multiset whose elements from F are duplicated for a times, is just a · S ′ + b · S. In particular, we can compute S ′ − S such that for each flow f with counter c in S and c′ in S ′ where c ̸= c′ , the sketch S ′ − S keeps the counter of c′ − c for flow f . This is extremely crucial as the sketch is used to keep counter differences.
Since the data structure is probabilistic, we are interested in the case where we can successfully extract all the flow counters. A. Review of FermatSketch FermatSketch maintains d equal-sized bucket arrays B1 , B2 , . . . , Bd , each of size m. There is also a pairwiseindependent hash function hi for each array Bi . Each bucket Bi [j] in the array Bi has two components: the counter Bic [j] and the ID sum Biid [j]. The data structure also specifies a prime p, which is larger than any flow id’s and any counter values. Every computation on this sketch would be done modulo p; thus, each memory item in the data structure should be large enough to keep an integer as large as p. We let Zp denote the set of integers modulo p. We define a more general procedure addF low(S, f, c). When it is called we do the following for each bucket array i, i = 1, . . . , d c c • Bi [hi (f )] = (Bi [hi (f )] + c) mod p id id • Bi [hi (f )] = (Bi [hi (f )] + c · f ) mod p When we perform this updated, we say that flow f is hashed into this bucket Bi [hi (f )]. To implement addF low(S, f ), we simply call addF low(S, f, 1). We say that bucket Bi [j] is pure if there exists a unique flow f that is hashed into Bi [j] The key primitive operation for FermatSketch is the following pure bucket check. • isP ure(Bi [j]) – checks if Bi [j] is pure.. Note that if the bucket is pure, i.e., there exists a single flow f we should have that Biid [j] = f · Bic [j]
(mod p)
Solving this modular equation for f , we can obtain the candidate flow id f . Kaicheng et al. [3] uses the Fermat Little Theorem to solve this equation, i.e., they use theorem to find the modular multiplicative inverse of Bic [j] modulo p; this inspires the name of the sketch. After the candidate flow f is obtained, we can verify that f is the actual flow id by testing if j = hi (f ), i.e., bucket j is the possible bucket for flow f . This pureness test can be incorrect, i.e., a bucket may contain multiple flows, but the incorrect flow id f obtained actually satisfies hi (f ) = j. This occurs with probability 1/m. In [3], the authors discussed this issue and stated a theorem (Theorem 3.1 in [3]) that if the total number of buckets md is of the same order of the number M of victim flows and M is not too small, the extraction procedure succeeds with high probability. They also describe a fingerprint verification (in Appendix A.4) to reduce the false positive rate, but this requires more memory. To implement extract(S), referred to as the decoding procedure in [3], one could perform the pure bucket check for all non-zero buckets Bi [j]. If the bucket is pure with flow f , we can take the count c = Bi [j] and call addF low(S, f, −c) to “remove” flow f from the sketch. One could repeat this procedure until all buckets are zero or no pure buckets are left. In the former case, we say that we have successfully extracted all the flows.
We remark that the FermatSketch is linear as all bucket components Bic [j] and Biid [j] are linear. III. T HE I MPROVED S KETCH C OMPONENTS In FermatSketch, pure buckets are starting points for flow extraction. However, when the ratio betwen the number of flows and the number of buckets is relatively high, the number of non-pure buckets can get too large, leading to flow extraction failures. Our key observation is that when the number of flows hashed into a bucket is a small constant (not necessarily 1), we might still be able to recover all the flow ids. We start with an illustrative example. When two flows f1 and f2 are hashed into the same bucket, we do not have enough information to recover their counters. However, if we keeps 4 values: c1 + c2 , c1 · f 1 + c 2 · f 2 ,
c1 + 2c2 , c1 · f1 + 2c2 · f2 ,
where c1 and c2 are counters for f1 and f2 , we can solve for all the needed values: f1 , f2 , c1 , and c2 . With this idea, we hope that by keeping more values (as independent linear combinations) in each bucket, we can deal with higher numbers of hash collisions. With this advantage, by storing k values in a bucket, we hope to extract k flows from a bucket. To keep the total space intact, we can reduce the number of buckets by a factor of k as well. Our intuition is that the increase in the average load factor would in turn reduce the “variance” on the number of pure buckets, resulting in the increase of the number of flows in pure buckets. We perform a preliminary experiments to investigate this idea. Section V-A presents the results. The challenge is how to make this idea works while ensuring that the data structure remains linear. Our key idea is to add a “random” flow-dependent coefficient to each value added to the bucket. Let k be a small constant, representing the maximum number of flows we can accept in a pure bucket. We modify each bucket Bi [j] to have 2k slots of two types: c c c • the counters Bi [j][1], Bi [j][2], . . . , Bi [j][k] id id id • the ID sums Bi [j][1], Bi [j][2], . . . , Bi [j][k] We also pick k random hash functions g1 , g2 , . . . , gk that map flow ids to Zp − {0}, the set of non-zero integers less than p. We also require that the range of each gi is of size L and all ranges are disjoint. The parameter L will be determined later. In our implementation, we let gi return values from a set of L prime numbers in Zp . This is slightly different from the formal analysis in Section IV-B. When addF low(S, f, c) is called, we do the following for each bucket array i, i = 1, . . . , d, and for each index r = 1, . . . , k c c • Bi [hi (f )][r] = (Bi [hi (f )][r] + c · gr (f )) mod p id id • Bi [hi (f )][r] = (Bi [hi (f )][r] + c · gr (f ) · f ) mod p
With this modification, we shall analyze the values kept in a bucket Bi [j] to devise a procedure for flow extraction. We start with a single bucket Bi [j] with k slots. Following [3], we say that Bi [j] is pure if there are at most k flows hashed into it. Suppose that bucket Bi [j] is pure and it has k flows f1 , f2 , . . . , fk hashed into it, with counters c1 , c2 , . . . , ck . We first focus on the counters. For each r = 1, . . . , k, we have k X
Bic [j][r] =
ct · gr (ft )
(mod p)
t=1
Treating all gr (ft )’s as known, we have a linear system with k equations and k variables c1 , c2 , . . . , ck , as follows: c1 b1 g1 (f1 ) g1 (f2 ) · · · g1 (fk ) g2 (f1 ) g2 (f2 ) · · · g2 (fk ) c2 b2 .. .. .. .. ≡ .. (mod p) .. . . . . . . gk (f1 )
gk (f2 )
···
gk (fk )
ck
bk
where br = Bic [j][r] for r = 1, . . . , k. The coefficient matrix, denoted by M , is a k × k matrix where the entry at row r and column t is gl (ft ). If M is full-rank, we can solve for all ct ’s. Similarly, we can also form a linear system to solve for all ft ’s using the ID sums Biid [j][r]’s, given that we already know all ct ’s. To do this, first solve for y = [y1 , y2 , . . . , yk ]T such that M y ≡ b′
(mod p),
where b′ = [b′1 , b′2 , . . . , b′k ]T and b′r = Biid [j][r] for r = 1, . . . , k. Since we already know all ct ’s, we can compute ft = yt /ct modulo p for each t = 1, . . . , k. Thus, the key to our approach is to ensure that the matrix M is full-rank. We shall analyze the probability of this event in Section IV-B. The catch is that we do not know the matrix M . However, we do know that each entry in row r is from the range of gr which is of size L. Thus, we can try all possible choices for the matrix M and solve the corresponding linear systems. 2 Since there are L choices for each entry in M , there are Lk possible choices for M . For each choice of M , we can solve the two linear systems to obtain candidate values for ct ’s and ft ’s. We can verify if these values are correct by checking if j = hi (ft ) for each t = 1, . . . , k. If this holds, we can call addF low(S, ft , −ct ) for each t = 1, . . . , k to remove these flows from the sketch. We can repeat this procedure until no more buckets can be extracted. Procedure for testing bucket pureness and extracting k flows from a pure bucket Bi [j] is describe in Algorithm 1. IV. A NALYSIS A. Correctness There are two properties that we need to ensure. First, the linearity of the sketch. This is fairly straightforward since after all hash functions are chosen, all coefficients gi (f ) is fixed for each flow f . Thus, invoking addF low(S, f, c1 ) after addF low(S, f, c2 ) is equivalent to calling addF low(S, f, c1 + c2 ), for any c1 and c2 .
Algorithm 1 extractBucket(S, Bi [j]) ▷ extractBucket tests bucket pureness and extracts k flows from a pure bucket Bi [j]. M ← all possible k × k matrices where the entry at row r is from the range of gr for all M ∈ M do if M is not full-rank (modulo p) then continue end if ▷ solve the two linear systems b ← [b1 , b2 , . . . , bk ]T where br = Bic [j][r] b′ ← [b′1 , b′2 , . . . , b′k ]T where b′r = Biid [j][r] Solve for c such that M c ≡ b (mod p) Solve for y such that M y ≡ b′ (mod p) for t = 1 to k do if ct ̸= 0 then ft ← yt /ct (mod p) else ft ← null end if end for ▷ verify the solution if hi (ft ) = j for t = 1, . . . , k when ft ̸= null then return {(f1 , c1 ), (f2 , c2 ), . . . , (fk , ck )} end if end for return “fail”
satisfies (1) at least two αi and αi′ are nonzero and (2) α1 + α2 + · · · + αj ≡ 1 modulo p is neglegible. Lemma 1. For k > 1, under the above assumption, the prob ability that M is full-rank is at least 1− k2 /Lk −2k /(p−k 2 ). Proof. Denote k columns of M as C1 , C2 , . . . , Ck . We first consider the probability that M is singular due to two columns Ci and Cj being equal. The probability that this occurs is 1/Lk . Since there are k2 pairs of columns, using the union bound, the probability that M is singular due to this reason is at most k2 /Lk . Assuming that no two columns are equal, we now consider the probability that column Ci is a linear combination of columns C1 , C2 , . . . , Ci−1 , given that columns C1 , . . . , Ci−1 are linearly independent. We analyze a linear system over Zp modulo p with i − 1 variables α1 , α2 , . . . , αi−1 such that α1 C1 + α2 C2 + · · · + αi−1 Ci−1 ≡ Ci
Since there are k rows and i − 1 < k, the number of equations is more than the number of variables. Since C1 , C2 , . . . , Ci−1 are linearly independent, there exists a set of rows R = {r1 , r2 , . . . , ri−1 } such that the submatrix M ′ of M formed by rows in R and columns C1 , C2 , . . . , Ci−1 is full-rank. Without loss of generality, we assume that R = {1, 2, . . . , i − 1}, and define Cj′ to be the columns Cj restricted to rows in R. The linear subsystem ′ α1 C1′ + α2 C2′ + · · · + αi−1 Ci−1 ≡ Ci′
Second, we need to analyze the success probability of the extraction procedure. This depends on two factors: (1) how flow hashing works, and given that a bucket contains at most k flows, (2) the probability that the corresponding linear system is solvable. We perform experiments to demonstrate the first factor in Section V. The second factor can be analyzed more regorously, as we shall do in the next subsection, Section IV-B. We note that the solvability probability can be made arbitrarily close to 1 by increasing L. However, this drastically increases the running time. Section IV-C provides the analysis. B. Analysis of the solvability probability We shall analyze the probability that the modular linear system from our algorithm is solvable. Recall that we use modular arithematics and perform every operation modulo a large prime p. Let k denote that size of the matrix and also let L be the number of coefficient choices. The random coefficients are from set of numbers P1 , P2 , . . . , Pk where each Pi is a set of L from Zp −{0}, the set of non-zero integers less than p, and all Pi ’s are disjoint. Consider a k × k matrix M where each entry on row i is chosen uniformly from Pi . In our proof, we require a certain assumption related to the solution of a certain linear system modulo p below. Assumption. The probability that a solution α1 , α2 , . . . , αj to a certian random linear system modulo p with j variables
(mod p)
(mod p)
with i − 1 equations and i − 1 variables has a unique ′ solution α1 , α2 , . . . , αi−1 , since C1′ , C2′ , . . . , Ci−1 are linearly independent. We now consider the probability that this solution also satisfies the remaining equations, especially the equation w.r.t the last row k, i.e., we want to analyze the probability that α1 C1 [k] + α2 C2 [k] + · · · + αi−1 Ci−1 [k] ≡ Ci [k]
(mod p),
where Cj [k] is the entry of column Cj at row k. Recall that every entry Cj [k] is chosen uniformly from the same set Pk . We first show that conditioning on the fact that at least one entry Cj [k] is different from Ci [k], the probability that the above equation holds is at most 2i−1 /(p − k 2 − 1). For a nonempty subset I ⊆ {1, . . . , i − 1}, consider the case where Cj [k] ̸= Ci [k] for all j ∈ I, and Cj [k] = Ci [k] for all j∈ / I. Since αj ’s are fixed, assume that all αj ’s for j ∈ I are already chosen, there is only one value for Ci [k] that satisfies the above equation, i.e., P j∈I αj Cj [k] P (mod p). Ci [k] ≡ 1 − j̸∈I αj Since Ci [k] is chosen from a set of size at least p − 1 − (k 2 − 1) = p − k 2 , the probability that it takes this value is at most 1/(p − k 2 ). Taking the union bound over all subsets I, we have that the probability that the equation holds is at most 2i−1 /(p − k 2 ).
To see why we can ensure the conditioning, first of all, we can discard the case where exactly one αj = 1 and all other αj ′ = 0 for j ′ ̸= j, since this would imply that Ci = Cj , contradicting our assumption. We are left with two cases, either there is exactly one nonzero αj and αj ̸= 1, or there are at least two nonzero αj ’s. In the first case, since αj ̸= 1, we know that Cj [k] ̸= Ci [k]. InPthe second case, by our assumption, the probability that P j αj ≡ 1 modulo p is negligible; thus, we may assume that j αj ̸≡ 1 modulo p, implying that there must be at least one j such that Cj [k] ̸= Ci [k] as needed. Combining all bad events for columns C2 , C3 , . . . , Ck , using the union bound, the that M is singular due Pprobability k to this reason is at most i=2 2i−1 /(p − k 2 ) < 2k /(p − k 2 ), as desired. The lemma thus follows. We note that since p is very large and k is a very small constant, the term 2k /(p−k 2 ) is also negligible; the key factor to solvability is L. Section V-A presents some preliminary experiments to verify this analysis.
Fig. 2. The percentage of flows in pure buckets for k = 1, 2, 3, 4, for varying ratios between the number of flows and the total number of slots (i.e., mk slots for m buckets).
C. Running time analysis Assume that all hash functions are evaluated in O(1) time. The running time for addF low(S, f, c) is O(d · k); since both numbers are small constants, this is effectively O(1) time. The running time for flow extraction is dominated by function extractBucket(), which solves linear systems of size k × k many times. For a particular parameter L, there are 2 at most Lk choices for the coefficient matrix M . Testing if it is full rank can be done in O(k 3 ) time. In fact, we can find the inverse M −1 modulo p in that time as well; therefore, solving the two linear systems can be done later in O(k 2 ) time. Thus, the total running time for extractBucket() is 2
O(k 3 Lk ). To fully extract all flows, we need to call extractBucket() successfully md times. By maintaining a list of successfully extracted buckets, and only calling extractBucket() on affected buckets after each successful extraction, we can reduce the number of calls to O(md) time. Let denote the time function extractBucket() is called as N . In the worst case, the total running time for successful flow extraction is 2
O(k 3 Lk · N ), where N = O(md). We remark that the factor of N also appears in the original FermatSketch [3], but since k = 1, extractBucket runs in O(1) time. Hence, the overhead of 2 our approach is the additional multiplicative factor of k 3 Lk . V. E XPERIMENTS A. Preliminary experiments We perform preliminary experiments to investigate the idea of using k slots per bucket. The first experiment verifies that increasing k while reducing the number of buckets by the same factor to maintain the same space leads to improved percentage of flows in pure buckets.
Fig. 3. The solvability probability for k = 2, 3, 4, for varying values of L.
We set the total number of slots to be m · k = 6000 and vary k from 1 to 4. Note that the original FermatSketch corresponds to k = 1. We vary the number of flows n from 300 to 6000, and measure the percentage of flows in pure buckets after all flows are added. The results shown in Figure 2 are averaged over 100 trials. One can see clear advantages even when k = 2. Another issue we address is the solvability of the linear systems used in flow extraction, as analyzed in Section IV-B. As our goal is to get the probability of successful extraction very close to 1, for each k, we vary L to see the effect on the solvability probability. However, using large L leads to larger computational overhead as described in the running time analysis. Therefore, we have to carefully choose L to balance the success probability and the running time. Figure 3 shows the results for k = 2, 3, 4 This experiment guides our choice of L in the next set of experiments.
Fig. 4. The success extraction probability for 100 victim flows for FermatSketch and our sketch with k = 2 for varying values of L ∈ {6, 8, 10, 12}.
Fig. 5. The required number of slots for successful extraction for varying numbers of victim flows for FermatSketch and our sketch with k = 2 and L = 10.
B. Successful extraction probability To demonstrate the advantages of using k slots per bucket, we perform experiments to estimate the success extraction probabilities for the FermatSketch and for our new sketch design for 100 victim flows. We vary the number of slots m′ from 40 to 60, and for each value m′ we run FermatSketch with m = m′ buckets and for our sketch we set k = 2 and m = m′ /2 buckets; thus, both data structures use the same amount of space. For our data structure, we vary L from 6 to 12. The results shown in Figure 4 are averaged over 2, 000 trials. C. Required space for successful extraction In [3], FermatSketch is used as a subroutine to the ChameleMon system. Kaicheng et al. [3] performed experiments to determine the required space for successful extraction of all flows with 99.9% probability. Because of limited computation resource, in this current work we perform experiments with 99% success probability. We perform experiments to determine the required number of slots (i.e., the number of buckets in the FermatSketch and k times the number of buckets in our case). We run our experiments for 50, 100, 150, 200, 300, and 500 victim flows. To find the number of slots, we perform a binary search, and for each guess, we run 1, 000 trials to estimate the success probability. Figure 5 shows the results. Our best choice of L is 10 and this gives us roughly 34.9% reduction in space when the number of victim flows is small (100), but the improvement drops to 8% when the number of flows increases. We note that we use the provided the implementation of FermatSketch available at https://github.com/ChameleMoncode/ChameleMon. The hash familiy used is MurmurHash3 [16].
R EFERENCES [1] Y. Li, R. Miao, C. Kim, and M. Yu, “Flowradar: a better netflow for data centers,” in Proceedings of the 13th Usenix Conference on Networked Systems Design and Implementation, ser. NSDI’16. USA: USENIX Association, 2016, p. 311–324. [2] ——, “Lossradar: Fast detection of lost packets in data center networks,” in Proceedings of the 12th International on Conference on Emerging Networking EXperiments and Technologies, ser. CoNEXT ’16. New York, NY, USA: Association for Computing Machinery, 2016, p. 481–495. [Online]. Available: https://doi.org/10.1145/2999572.2999609 [3] K. Yang, Y. Wu, R. Miao, T. Yang, Z. Liu, Z. Xu, R. Qiu, Y. Zhao, H. Lv, Z. Ji, and G. Xie, “Chamelemon: Shifting measurement attention as network state changes,” in Proceedings of the ACM SIGCOMM 2023 Conference, ser. ACM SIGCOMM ’23. New York, NY, USA: Association for Computing Machinery, 2023, p. 881–903. [Online]. Available: https://doi.org/10.1145/3603269.3604850 [4] Y. Wang, J. Ji, C. Liu, H. Zhou, and T. Yang, “DaVinci Sketch: A Versatile Sketch for Efficient and Comprehensive Set Measurements,” in 2025 IEEE 41st International Conference on Data Engineering (ICDE), May 2025, p. 210223. [5] M. T. Goodrich and M. Mitzenmacher, “Invertible bloom lookup tables,” in 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2011, pp. 792–799. [6] A. Mizrahi, D. Bar-Lev, E. Yaakobi, and O. Rottenstreich, “Invertible bloom lookup tables with listing guarantees,” Proc. ACM Meas. Anal. Comput. Syst., vol. 7, no. 3, Dec. 2023. [Online]. Available: https://doi.org/10.1145/3626792 [7] N. Fleischhacker, K. G. Larsen, M. Obremski, and M. Simkin, “Invertible Bloom Lookup Tables with Less Memory and Randomness,” in 32nd Annual European Symposium on Algorithms (ESA 2024), ser. Leibniz International Proceedings in Informatics (LIPIcs), T. Chan, J. Fischer, J. Iacono, and G. Herman, Eds., vol. 308. Dagstuhl, Germany: Schloss Dagstuhl – LeibnizZentrum für Informatik, 2024, pp. 54:1–54:17. [Online]. Available: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.54 [8] G. Cormode, “Applications of sketching and pathways to impact,” in Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, ser. PODS ’23. New York, NY, USA: Association for Computing Machinery, 2023, p. 5–10. [Online]. Available: https://doi.org/10.1145/3584372.3589937 [9] G. Cormode and S. Muthukrishnan, “An improved data stream summary: the count-min sketch and its applications,” Journal of
Algorithms, vol. 55, no. 1, pp. 58–75, 2005. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0196677403001913 [10] M. Charikar, K. Chen, and M. Farach-Colton, “Finding frequent items in data streams,” Theoretical Computer Science, vol. 312, no. 1, pp. 3– 15, 2004, automata, Languages and Programming. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0304397503004006 [11] B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,” Commun. ACM, vol. 13, no. 7, p. 422–426, Jul. 1970. [Online]. Available: https://doi.org/10.1145/362686.362692 [12] G. Cormode and S. Muthukrishnan, “What’s hot and what’s not: tracking most frequent items dynamically,” ACM Trans. Database Syst., vol. 30, no. 1, p. 249–278, Mar. 2005. [Online]. Available: https://doi.org/10.1145/1061318.1061325 [13] T. Yang, J. Jiang, P. Liu, Q. Huang, J. Gong, Y. Zhou, R. Miao, X. Li, and S. Uhlig, “Elastic sketch: adaptive and fast network-wide measurements,” in Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, ser. SIGCOMM ’18. New York, NY, USA: Association for Computing Machinery, 2018, p. 561–575. [Online]. Available: https://doi.org/10.1145/3230543.3230544 [14] K. Yang, S. Long, Q. Shi, Y. Li, Z. Liu, Y. Wu, T. Yang, and Z. Jia, “Sketchint: Empowering int with towersketch for per-flow per-switch measurement,” IEEE Transactions on Parallel and Distributed Systems, vol. 34, no. 11, pp. 2876–2894, 2023. [15] H. Han, Z. Yan, X. Jing, and W. Pedrycz, “Applications of sketches in network traffic measurement: A survey,” Information Fusion, vol. 82, pp. 58–85, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1566253521002578 [16] H. Senuma, “mmh3: A Python extension for MurmurHash3,” Journal of Open Source Software, vol. 10, no. 105, p. 6124, Jan. 2025.