Recently, an algorithm for merging counter-based data summaries which are the output of the Frequent algorithm (Frequent summaries) has been proposed by Agarwal et al. In this paper, we present a new algorithm for merging Frequent summaries. Our algorithm is fast and simple to implement, and retains the same computational complexity of the algorithm presented by Agarwal et al. while providing better frequency estimation.
In 2011, we presented an algorithm [
Given a data set A of n items t1, t2, . . . , tn, the frequency of an item i is fi = |{j |tj = i} |. Let f˜i be the frequency reported by the algorithm for item i. The absolute error of item i is defined as the difference |fi − f˜i|. The (absolute) total error is then the sum of the absolute errors related to the items reported by an algorithm.
In this paper, we present a new algorithm for merging Frequent summaries
(based on our previous algorithm) which is fast and simple to implement, and
retains the same computational complexity of the algorithm presented in [
Definition 1. Given a multiset N , with |N | = n, and 2 ≤ k ≤ n, a frequent item (or k–majority element) is an element x ∈ N whose frequency fN (x) is such that fN (x) ≥ nk + 1. The frequent items (or k–majority) problem takes as input an array N of n numbers (a multiset), and requires as output the set S = x ∈ N : fN (x) ≥ nk + 1 Copyright c by the paper’s authors. Copying permitted for private and academic purposes. Definition 2. Merged summary.
Given k, the k-majority parameter, let A1 and A2 be respectively the data sets from which the data summaries S1 and S2 are derived by an application of the Frequent algorithm, and let n = |A1| + |A2|. The merged summary M is the multiset which contains all of the k-majority elements, i.e., all of the elements whose frequency in A1 U A2 is greater than or equal to nk + 1. Moreover, all of the guarantees assured by Frequent on its output continue to hold for the summary M with reference to the input A1 U A2.
Definition 3. 2-way merging problem.
Input: k, the k-majority parameter; two summaries S1 and S2 derived by an application of the Frequent algorithm.
Output: The merged summary M.
The paper is organized as follows. We present in Section 3 our algorithm. In Section 4, the proposed algorithm is analyzed in terms of correctness, computational complexity and total error committed. Full details and proofs will appear in a forthcoming extended version. We draw our conclusions in Section 5. 2
In [
Algorithm 1 Merging Algorithm by Agarwal et al.
Require: S1; an array of counters; S2; an array of counters; k, k-majority parameter (the number of counters is k − 1); Ensure: an array containing k–majority candidate elements 1: procedure m e rg e(S1, S2, k) . a merged summary of S1 and S2 2: S ← c o m b i n e(S1, S2); 3: if S.nz > k − 1 then . prune counters in S 4: for i = k to 2k − 2 do 5: Cif ← Cif − Ckf−1; 6: end for 7: end if 8: return S[k . . . (2k − 2)]; . return the last k − 1 counters 9: end procedure
The algorithm works as follows. It starts combining as usual the two data summaries, by adding the frequencies of counters monitoring the same item. This could entail, for Frequent summaries, the use of up to 2k − 2 counters in the worst case, when S1 and S2 share no item. Let S be the combined summary, and S.nz the number of nonzero counters. Moreover, assume, without loss of generality, that the total number of counters in S, denoted by S.length, is exactly 2k − 2 and they are stored in sorted ascending order. Indeed, it is always possible to pad the first S.length − S.nz positions in S with dummy counters whose frequency is zero.
If S.nz ≤ k − 1 the algorithm returns the last k − 1 counters of S. Otherwise,
a pruning operation is required. Then, the algorithm subtracts from the last k − 1
counters the frequency of the Ck−1-th counter and returns the pruned counters.
The algorithm requires in the worst case time linear in the total number of
counters, i.e., O(k) if implemented as described in [
We now analyze the total error committed by this algorithm. Clearly, combining the two data summaries can be done without any additional error. However, the pruning operation occurring when the size of S is greater than k − 1 induces f a total error ET = (k − 1)Ck−1, i.e., k − 1 times the frequency of the Ck−1-th counter in S. The authors proved that the additional error introduced by the merge is within the error bound guaranteed by Frequent. 3
In this Section we present our algorithm, shown in pseudo-code as Algorithm 2 for merging two Frequent summaries.
Algorithm 2 starts by combining the two input summaries into a combined
summary S. Then, if the number of nonzero counters in S is less than or equal
to k − 1, the algorithm returns as merged summary the last k − 1 counters of
S. Otherwise, the last k − 1 counters are first updated using exact closed-form
equations and then reported as output. Actually, these determining equations
produce the same merged summary that we would obtain applying the Frequent
algorithm to the combined summary S, a procedure we described and proved to
be correct in [
Lemma 1. The computational complexity of our Algorithm 2 is O(k) in the worst case. 4.2
By construction, the combine step producing S preserves the frequent items in S1 U S2 since no item is discarded and no occurrences are lost. Therefore, it suffices to show that our closed-form equations produce the same merged summary which would be outputted by an application of Frequent (the one-shot update version) to the combined summary. Let S.length = 2k − 2 and assume k ≤ S.nz ≤ 2k − 2. We denote by Cj the j–th counter in S, j = 1, . . . , 2k − 2, and by eij and mij , respectively, the item monitored by the j–th counter of Frequent (denoted as Mj ) and its value at the end of the i–th update step, i = 0, . . . , k − 1 and j = 1, . . . , k − 1. We define ej0 = Cje and mj0 = Cjf , j = 1, . . . , k − 1. Indeed, the step zero reflects the situation in which we have already filled the first k − 1 counters in the Frequent data structure with the corresponding initial k − 1 counters in S. This is correct owing to the following facts: (i) the counters in S are stored in ascending sorted order with respect to the frequencies, (ii) the items in S are distinct and (iii) Frequent works by assigning an item which is not currently monitored to a new counter if available and maintaining the ascending sorted order with respect to the frequencies.
Theorem 1. For each update step i = 1, . . . , k − 1 and position j = 1, . . . , k − 1, the values eij and mij can be defined as follows: eij = Cie+j j = 1, . . . , k − 1 (1) mij = ( Ciff+j − Cif f j = 1, . . . , k − i
Ci+j − Cif + Ci+j−k j = k − i + 1, . . . , k − 1 4.3
In what follows, we assume that after the combine step we are left with a data summary S consisting of more than k − 1 nonzero counters. Otherwise, both algorithms do not commit any additional error, owing to the fact that the combine step obviously does not incur any error. Therefore, assuming that S consists of more than k − 1 nonzero counters, the total error committed by our algorithm is the total error committed by Frequent when applied to S. The counters’ frequencies at the end of the (k − 1)–th update step are mk−1, j = 1, . . . , k − 1. Consequently, j since Frequent underestimates the frequencies, the total error committed is ET = j=1 k−1
X Ckf−1+j − mjk−1
We claim that the total error committed by Algorithm 2 is less than or equal
to the total error committed by algorithm [
Theorem 2. The following inequality holds k−1 X(Ckf−1+j − mjk−1) ≤ (k − 1)Ckf−1.
j=1 5
In this paper we have introduced a new algorithm for merging Frequent summaries and compared it to the algorithm proposed by Agarwal et al. from a theoretical perspective. Our algorithm uses exact closed-form equations for determining the outputs; we have shown that it retains the same computational complexity, whilst providing better frequency estimation. Future work includes designing and carrying out several numerical experiments in order to compare the two algorithms we have discussed from a quantitative perspective. (2) (3) (4)