Light Agents Searching for Hot Information

1 TheModel and the Problem

Finding elements occurring above certain frequency φ, so called hot items, is one of the fundamental tools in mining online streams and histogram study, c.f., [Ioannidis and Christodoulakis, 1993; Ioannidis and Poosala, 1995]. It can also be applied in data warehousing, data mining and information retrieval, decision support systems, databases, caching, load balancing, network management, anomaly detection, c.f., [Demaine et al., 2002; Fang et al., 1998; Gibbons and Matias, 1999; Karp et al., 2003].

We consider a stream of operations, also called transactions, involving elements in the universe N of size n. We do not limit the distribution of elements in the stream - they could be created arbitrarily, even by an online adversary, which aims at "fooling" the agent processing the stream aiming to find hot elements. Each operation involves a single element x∈N and could be either an insertion or deletion of this element (to/from some large data repository). Observe that if a large Θ(n) space is allowed at an agent, then a simple heap data structure could process each insertion or deletion operation in O(log n) time, and find the hot items in O( 1ϵ log n) time, for any stream, c.f.,[Aho et al., 1983]. However, in case of large universe N (Big Data), such a solution is not practical. Therefore, for more than 20 years the research in this area focused on finding a summary data structure, of sublinear (in n) size and processing/enlisting time.

There is, however, a subtle twist - could sublinear algorithms return all and only hot elements? [Cormode and Muthukrishnan, 2005b] showed that enlisting all and only hot elements is impossible with sublinear memory o(n). (They were inspired by a seminal paper [Alon et al., 1996] proving that estimating highest frequency is impossible in sublinear memory o(n).) This also applies to randomized algorithms: any algorithm which guarantees outputting all and only hot elements with probability at least 1-σ, for some constant σ, must also use Ω(n) memory. This generalization uses a related result on the Index problem in communication complexity, c.f., [Kushilevitz and Nisan, 1997]. This argument implies that, if we are to use less than Θ(n) memory, then we must sometimes output items with frequency smaller than φ. Therefore, the main challenge is:

To design an efficient (light) deterministic online algorithm (agent) processing any stream of operations and, upon request, listing all elements of frequency at least φ and no element of frequency at most φ-ϵ. Light, or well-scalable, agent means that it should process an operation or output an element in time at most polylogarithmic in n (i.e., logcn for some constant c>0), as n=|N| could be very large, while using memory linear in 1/ϵ and polylogarithmic in n. Light algorithms have already been designed in some cases:

• When randomness is allowed, c.f., [Cormode and Muthukrishnan, 2005b]; however, false positives and false negatives are possible; also, it is not known if the result holds against adversarial streaming, i.e., if the adversary decides on consecutive elements in the stream online, seeing the past choices of the algorithm,
• When second pre-processing or processing in larger batches (so called window-based) is allowed, c.f., [Misra and Gries, 1982; Lin et al., 2005] however, such agents are not pure online.

Our results. In this work (Section 2) we design a deterministic algorithm that overcomes all of the abovementioned obstacles: it is fully online (it does not go backwards or look ahead when processing current stream location), it does not use any random bits, and it works for arbitrary streams even created by an online adaptive adversary. It handles both insertions and deletions. Finally, it is also light and well-scalable (as we analyze formally in Section 3), in the sense that it uses only polylogarithmic time per operation and returning a hot element while using only O( log3 n ϵ ) local memory. This memory space is close to optimal, as we show in the proof of a lower bound in Section 4. Table 1 compares performance of our agent with most relevant previous work. Finally, we discuss possible extensions (including multi-agent parallelization) and open problems in Section 5.

Model and problem. Consider an incoming very long stream of operations on elements of a very large universe N of size n= |N|, where each operation is of a form op(x), for op∈{insert,delete} and x∈N. We assume that each operation contains a O(log n)-bit identifier of an element x involved; we will be using "element" and "item" interchangeably throughout this paper. The net occurrence of an item x∈N in step t, denoted by nt(x), is the number of insertions of x minus the number of deletions of x in the first t operations of the stream. The frequency of element x in step t is denoted by ft(x)=nt(x)/t. The stream satisfies Basic Integrity Constraint, as defined in [Cormode and Muthukrishnan, 2005b]: in each round a frequency of any element is non-negative, in particular, the number of deletions never exceeds the number of insertions of an element.

The problem of finding hot elements (also called frequent elements) is parametrized by 1 > φ > ϵ > 0; we denote it by finding (φ, ϵ)-hot elements. The objective is to design an agent, consisting of data structures and algorithms, capable of processing the operations of the stream online in sequence (without the possibility of returning to already processed operations). At any point, upon external request the agent should be able to return a set of frequent elements. We will say that the output of the algorithm is correct if the returned set contains O(1/φ) elements, including all elements with frequency at least φ and no element with frequency smaller than or equal to φ-ϵ.

Performance of an agent is measured in terms of time to process a single operation from the stream, time to output all the (φ, ϵ)-hot elements, and the total local memory used. In the measurement, the atomic operation concerns so called Machine word: a unit of memory that is sufficient to store a single element, step number and all problem parameters; every basic operation on machine words, e.g., arithmetics, is accounted as 1 in time complexity. We aim at time and memory efficient agents, i.e., performing each operation (or outputting an element) in time O( polylog n) and using O( 1ϵ polylog n) memory units (each storing a machine word). Additional notation. By t denote the current step number (i.e., the number of operations of the stream that have already been handled by the algorithm). We will also use notation γ= ϵ6 . 1

1.1 Previous andRelatedWork

Handling insertions anddeletions. [Cormode andMuthukrishnan, 2005b] proposed randomized online algorithm with memory O(k logk logn), processing each operation in time O(logklogm), and outputting hot elements in time O(k logk logm), where k= 1φ -1. The algorithms return no items with frequencies less than 1 k+1 -ϵ with some user-specified probability. A deterministic summary structure for data streams in [Ganguly and Majumder, 2007] finds the most frequent elements however it requires space O(log3n/(φ2ε2)). In [Cormode andMuthukrishnan, 2005a], the objective is to return an approximate frequency of any element using memory ˜O(1/ε) and time ˜O(1), but the error was proportional to ε times the total frequency of all the elements. In [Gilbert et al., 2002b] the considered problem is to return approximate quantiles of the data - the solution uses space O(1/ε2).

Earlier results include the problem of histogram maintenance, which involves finding a piecewise-constant approximation of data distribution. The optimal histogram is close to the data vector in terms of ℓ1 or ℓ2 norms hence it approximates all the data points, whereas in the problem of hot elements the objective is to approximate the frequencies of only the most frequent elements.[Gibbons et al., 1997] were the first who considered insertions and deletions in the context of maintaining various histograms, however their methods need periodical access to large portion of the data in the presence of deletes. [Gibbons and Matias, 1998;

1 Auxiliary parameters in this work are chosen for convenience of mathematical analysis in our general streaming model, without harming asymptotic performance. Further optimization of constants could be possible through more detail case study and/or specific experimental optimization for selected datasets.

Gibbons and Matias, 1999] analyzed mainly insertion operations, but also performed experimental study in the presence of deletions. [Gilbert et al., 2002a] designed and analyzed algorithms for maintaining histograms with guaranteed accuracy and small space.

Insertion-only streams. For streams with only insertions, in a special case without a lower bound on the frequency of returned elements (which is equivalent to ϵ = φ), [Misra and Gries, 1982] designed a deterministic algorithm with processing and enlisting time O(klogk) and memory O(k) (which in this case equals to O(1/ϵ)). Their algorithm however is not fully online, as it requires a second pass on the stream. In the same model, [Demaine et al., 2002] proposed a single-pass randomized algorithm for finding frequent elements using O(k) memory and O(1) expected time for processing one item.

In the more general case, [Manku and Motwani, 2002] proposed a deterministic algorithm Lossy Counting that processes finds hot elements using O(log(n/ϵ)/ϵ) memory. [Charikar et al., 2002] proposed a randomized algorithm using O(klogn/ϵ2) memory and and O(log(1/σ)) time per operation that succeeds with probability at least 1-σ.

Recent works. Recently, results on finding frequent items in streams include models where later items in the stream have higher weight [Wu et al., 2017; Cafaro et al., 2017], as well as many applications, e.g., finding frequent elements in two-dimensional data streams [Lahiri et al., 2016; Epicoco et al., 2018].

2 Algorithm

2.1 Data Structures withOperations

Our agent maintains two data structures: a disperser-based structure of group counters and a structure of individual entries built on the top of balanced Binary Search Trees.

Definition of disperser. Formally, a disperser G=(V,W,E) is a bipartite graph satisfying the following criteria:

Left-degree: G has left-degree d (i.e., each vertex in V has d neighbors inW),

Right-set: |W|=ϕℓd/δ,

Dispersion: for every L⊆V such that |L| ≥ℓ, the set ΓG(L) of neighbors of L in graph G is of size at least (1-ξ)|W|.

Construction of disperser. [Ta-Shma et al., 2001] showed a construction of a disperser with construction parameters: left-degree d= polylog n and entropy loss δ=O(log3n), such that for each v ∈ V neighborhood ΓG(v) can be enlisted in time and memory polylog n. They also mentioned existence of dispersers with d,δ = O(log n).

Group counters. To build this structure, we use a is an (ℓ,d,ξ)-disperser graph G with entropy loss δ for parameters: |V |=n, |W|=ϕ d 2ξγ for some sufficiently large constant ϕ>1, 0<ξ <1/2 is an arbitrary chosen constant, d,δ depend on the construction of disperser (see the construction comments later on), and ℓ= δ 2ξγ (recall our notation γ= ϵ6 ). Each element x∈N is associated with a unique vertex vx ∈V and each node wg ∈W is associated with a group counter g, where the group is the set ΓG(vx)⊆V of neighbors of wg in G. The set of group counters G(x) of an element x∈N is the set of group counters associated with neighbors of vx in graph G, i.e., G(x)={g :wg ∈ΓG(vx)}.

We will be using vx and x interchangeably, whenever it does not raise any confusion; similarly, wg and g.

Individual entries. To account for operations on elements that need to be counted precisely, we introduce a new structure C of individual entries with supporting procedures. The entries will be kept for two types of elements: candidates (potential hot elements with large number of insertions minus deletions) and recently modified elements (elements for which there exists an operation insert or delete at most ⌈2/γ⌉ steps ago). The reason why we need to keep individual entries for recently modified elements is that we do not process an incoming operation immediately. Instead, upon arrival of an operation our agent inserts it to an auxiliary queue Q and updates group counters and individual entries (at most) ⌈2/γ⌉ steps later. All these happen in the local memory of the agent (of limited capacity) and does not cause the agent to go backwards the stream nor looking ahead. Individual entry of an element x consists of:

• key x of the element x∈N;
• candidate counter c(x), which is incremented/decremented by 1 upon handling of each insertion/deletion of element x;
• recent counter r(x), which stores the number of insertions minus the number of deletions of element x in recent operations in the stream;
• number of operations λ(x), which stores the number of recent operations on element x.

In each step, our agent receives a single operation from the stream. Note that after the algorithm processes an operation, it cannot go back to it (i.e., its algorithm only makes a single online pass over the stream). In the processing, the following procedures are used on datastructure C:

check(x): it checks if there is an entry with key x. If there is, it returns ⟨c(x),r(x),λ(x)⟩, otherwise it returns null; it takes time O(log|C|);

add(x): it adds an entry element with key x and initial values of all counters c(x), r(x), λ(x) equal to 0; it takes time O(log|C|);

size(): it returns the number of entries; works in time O(1);

apply recent(op,x): it applies operation op on recent counter r(x) of element x; it checks if there is an entry with key x in the balanced tree T ; if there is no such entry, it creates it; then it increments λ(x) and increments or decrements (depending on the type of op) the recent counter r(x); it takes time O(log|C|);

rollback recent(op,x): it performs rollback of operation op on an entry with key x; it accesses entry with key x; decrements λ(x), decrements (if op=insert) or increments (if op=delete) r(x); it takes time O(log|C|);

apply candidate(op,x): it applies operation op on the candidate counter of entry with key x; it finds a copy of an entry with key x in the balanced tree and increments (if op=insert) or decrements (if op=delete) its counter c(x) by 1; it takes time O(log|C|);

remove if small(x,s): it removes element key x if the minimum group counter of x is below threshold s and if the number of recent operations equals to zero (i.e., λ(x)=0); it takes time O( polylog n) (because this is the time to access all the group counters to which v belongs);

get larger than(s): it returns a list of keys for which the corresponding candidate counter plus recent counter exceeds s; it accesses the entries in order (the structure is sorted by c(x)+r(x)) and returns the elements as long as the value is greater than s. It takes time proportional to the number of returned elements.

Implementation of datastructure C. Implementation of datastructure C with time complexities of individual operations, as claimed in the previous paragraph, can be achieved using standard datastructures. We use a balanced Binary Search Tree T1 (e.g., Red-Black Tree, c.f., [Aho et al., 1983]), with keys being the identifiers of all the elements for which an individual entry exists and entries being tuples of a type ⟨r(x),c(x),λ(x),px⟩. This ensures that searching and returning the individual entry of an element (if it exists) takes logarithmic time. Each entry of T1 has a pointer px to an entry in a second Balanced Binary Search Tree T2 with keys being the values of r(x)+c(x) and entries being tuples ⟨x,qx⟩, where qx points towards the entry of element x in tree T1. Clearly, any update of counters r(x),c(x),λ(x) for some element x requires logarithmic time operation to find the entry in T1 and then logarithmic time to modify the key of a corresponding entry in T2. Inserting and deleting elements also requires logarithmic time. Listing the elements (operation get larger than(s)) quickly is feasible since the inorder traversal of tree T2 returns the elements in order of decreasing r(x)+c(x). The time of the operation is proportional to the number of returned elements, multiplied by O(logn).

2.2 MainAlgorithm

Intuitions. There is a following interplay between the two data structures (group counters and individual entries) in the agent's algorithm. The group counters determine which elements should be included in the individual entries as candidates for hot elements. The individual entries keep track of the operations on the candidates for hot elements and determine which elements should be returned as hot.

Processing of an operation. In our algorithm, each element x∈N has an associated set of group counters G(x) (note that each group counter is shared by multiple elements). Processing of operation op(x) (where op is either insert or delete) involves updating (incrementing or decrementing, resp.) each of the counters G(x). If all the group counters G(x) are above a threshold γ ·t, it indicates that the element may be a candidate for being a hot element. In this case, the agent checks the structure of individual entries C and updates the candidate counter c(x) in the entry of x, or creates it if it does not exist. In our algorithm we define the candidate as an element with at least γ · t net occurrences (insertions minus deletions) in the first t operations of the stream.

Group counters. A group counter g is incremented when any element from the group (recall that the group is determined by the topology of the used disperser G) is inserted in the stream. This means that some element x might have all its group counters G(x) above γ · t while its net occurrence nt(x) could be below γ · t (because insertions of other elements have caused the counters in G(x) to exceed the γ·t threshold). Hence, some 'false positive' candidates might be included in C. In our analysis we will bound the number of such false positives. We ensure this by proving that in any set of size Θ(δ/γ),some element will have a group counter with value at most γ·t. (Recall δ is the disperser's entropy loss.)

Algorithm 1: Handling 2⌈ 1 γ ⌉ consecutive operations.

1 t←current step number; 2 γ←ϵ/6,τ←⌈1/γ⌉; // Phase 1 3 Divide elements included in C into τ chunks E1,...,Eτ each of (at most) ⌈C.size()/τ⌉ elements; 4 for i←1 to τ do 5 Receive the next operation op(x); 6 Q.enqueue(op(x)); 7 C.apply recent(op,x); 8 foreach v∈Ei do 9 C.remove if small(v,⌈γt⌉); // Phase 2 10 for i←1 to τ do 11 Receive the next operation op(x); 12 Q.enqueue(op(x)); 13 C.apply recent(op,x); // Process two items from the queue 14 Process(Q.dequeue(),C,γ,t+2(i-1)); 15 Process(Q.dequeue(),C,γ,t+2(i-1)+1);

Algorithm 2: Extracting hot elements at step t.

• 1 return C.get larger than((φ-ϵ)t);

Procedure Process(op(x), C,γ, t)

// Processing a single operation 1 Compute set G(x) of group counters of x; 2 foreach g∈G(x) do 3 if op = insert then g←g+1 ; 4 else g←g-1; 5 C.rollback recent(op,x); 6 if C.check(x) then 7 C.apply candidate(op,x); 8 else 9 gmin ←min{g : g ∈G(x)}; 10 if gmin≥⌈γt⌉ then 11 C.add(x); 12 C.apply candidate(op,x);

Candidates. The key property guarantying that our algorithm is correct is the following: in every step t, each element with at least γ·t net occurrences has its individual entry in C. It is nontrivial to show, as this property must hold in every step, and the set of such elements might change over time. We have to make sure that when an element exceeds the threshold, an individual entry for this element must be created immediately. We ensure this by (1) keeping individual entries for all elements for which there is even a single recent operation, and (2) inserting an element into C when each of its group counters exceeds γ·t. With these properties, we know that each hot element is at any time in C and, moreover, at the moment such an element is inserted into C it is just crossing the γ·t threshold. Because the occurrences are counted precisely after an element is added to C, we miss only γ ·tx net occurrences of an element x inserted into C at step tx. Since γ<ϵ and tx ≤t, each hot element has at least (φ-ϵ)·t net occurrences while having an individual entry. This allows our algorithm to correctly find all the hot elements.

Pseudo-codes. The algorithm is described on three pseudocodes: one handling 2⌈1/γ⌉ consecutive operations in the stream, c.f., a pseudo-code in Algorithm 1, a sub procedure that processes a single operation, c.f., procedure Process, and the final pseudo-code enlisting hot elements in the processed stream, c.f., a pseudo-code in Algorithm 2. Note that a request to return hot elements can arrive at any step (also while handling 2⌈1/γ⌉ consecutive operations). In such case, the execution of Algorithm 1 is paused and Algorithm 2 is immediately executed.

The latter is a single execution of procedure get larger than(s) for s=(φ-ϵ)t, where t is the current position in the stream.

The former, Algorithm 1, works as follows. In a single iteration of the algorithm, processes 2⌈1/γ⌉ consecutive operations, online one-by-one. This part of the stream, also called a window (recall though the agent does not process whole window at once, but online one-by-one), is further divided into two sub-windows of ⌈1/γ⌉ operations each. In the first sub-window the agent performs Phase 1, during which it executes the cleanup of C (see Algorithm 1 lines 4-9). During these steps, the new operations are pre-processed (using apply recent method of C) and inserted into the queue Q. In each step of processing the second sub-window (Phase 2), the agent finishes processing of some pair of operations from the queue (see Algorithm 1 lines 10-15). Hence, the length of the queue decreases by 1 in each step of Phase 2, and thus after the last step the queue is empty. Note that our algorithm, even though it processes operations in windows, is strictly online, because in each step the agent receives a new operation from the stream and each received operation is immediately handled.

3 Analysis of the Algorithm

In the analysis, for the sake of clarity, we sometimes add lower index t to some model variables to indicate that the values of these variables are taken just after processing t operations from the stream, e.g., Gt(x) denotes the set of all group counters of element x after processing the first t operations.

The first lemma shows that there is a limited number of elements x ∈ N, namely δ 2ξγ , having all its group counter at least ⌈γt⌉. The second lemma shows that the number of recent operations stored in the recent counters is at most ⌈1/γ⌉+1. Thus procedure remove if small executed on all the elements from C removes all but at most δ 2ξγ +⌈1/γ⌉+1 entries. When an operation arrives we first pre-process it by inserting into queue Q (and upon insertion, this operation is accounted for in a recent counter). Some number of steps later we finish processing the operation, by executing procedure Process with this operation as the first argument.

Lemma 1. After processing first t stream operations by Algorithm 1, for any set S⊆N, where |S|= δ 2ξγ , there is an element s∈S, such that g<γt for some of its group counters g∈Gt(s).

Proof. First observe, that since in upon processing an operation, we increment at most d= polylog n group counters (recall that d is the left-degree of the disperser G used for the construction, c.f., [Ta-Shma et al., 2001]), then after processing t operations from the stream the sum of the group counters is at most td. Since there are |W|= ϕd 2ξγ group counters (where a constant ϕ>1), associated 1-1 with the right vertices of disperser G, then the average value of a group counter is at most td/|W|. At least 2ξ-fraction of the counters must be below 1/(2ξ) times the average; thus, there are at least 2ξ|W| group counters with values smaller than td/(2ξ|W|)≤γt, where ξ<1/2 is a parameter of the disperser G andW of size |W|≥ d 2ξγ is the number of its right-side vertices. If we take any set S⊆N of size at least δ 2ξγ ,the set NG(S) of neighbors of S in graph G is of size at least (1-ξ)|W|, by dispersion. Hence at least 2ξ|W|+(1-ξ)|W|-|W|=ξ|W| counters associated with some elements in S must be below γt.

Lemma 2. At any step of the algorithm, the total number of operation stored in recent counters is at most τ+1.

Proof. It is easy to see that the size of queue Q in Algorithm 1 is always at most τ+1. It is because it is empty at the beginning of the algorithm and then we add a single operation to it in each iteration of for-loop in lines 4-9 of Algorithm 1 and then in each iteration of the for-loop in lines 10-15 of Algorithm 1 we first add a single operation and then remove two. Since both for-loops have τ iterations each, the maximum size of the queue is after line 12 during the first iteration of the second for-loop and equals to τ+1. Hence the total number of operations stored in the recent counters is also at most τ+1. It remains to observe that each operation in the queue contributes exactly one to the sum ∑v∈N λ(v).

Lemmas 1 and 2 imply an upper bound on the size of structure C.

Lemma 3. 1. After each Phase 1, the number of individual entries in C is at most δ 2ξγ +⌈1/γ⌉+1;

1. After each Phase 2, the number of individual entries in C is at most δ 2ξγ +3⌈1/γ⌉+1.

Next we relate the number of net occurrences nt(x) of an element x∈N in the stream by position t, to counters c(x) and r(x).

Lemma 4. After first t steps of Algorithm 1:

1. for every element x∈N, if nt(x)≥⌈γt⌉, then x∈Ct ,
2. for every element x ∈ Ct we have nt(x) - ⌈γt⌉ ≤ ct(x)+rt(x)≤nt(x).

Proof. To show (1), we need to show, that in the algorithm after processing t′ operations all elements with at least ⌈t′γ⌉ occurrences are in C. To prove this we need to show that we never remove from C an element with at least ⌈t′γ⌉ net occurrences and that we always add to C an element when its number of net occurrences becomes equal to or larger than ⌈t′γ⌉. We prove this fact by induction. Assume that it holds for all phases up to some step t′ . We then consider the following Phase 1 and Phase 2. Note that the queue Q is empty at the beginning of each Phase 1. It is because each Phase 1 adds τ operations to it and each Phase 2 removes τ operations from the queue. Note that, when the queue is empty, each group counter contains the total number of insertions minus number of deletions of all the elements from the group (because we processed all the operations up to this step). This means that any element removed from C by operation remove if small has some group counter at most ⌈tγ⌉, hence it surely has at most ⌈tγ⌉ occurrences in the first t operations in the stream. Additionally, we keep in C individual entry for each element with at least one (recent) operation in the interval [t,t+τ]. Hence after Phase 1 we have in C all the elements that have at least ⌈tγ⌉ occurrences in the first t operation or at least one operation in the interval [t,t+τ]. Hence after Phase 1 we have that C contains all the elements that have at least ⌈(t+τ)γ⌉ occurrences. In Phase 2 we add elements to C only upon handling of some t′-th operation op(x) if each group counter of x equals to at least ⌈t′γ⌉. Hence, after handling t′-th operation in Phase 2, the claim holds. This finishes the inductive proof.

To show (2), we first observe that if an element x ∈ C, then upon processing an opration on x, this operation is immediately accounted for in counter r(x). Hence r(x) is incremented/decremented upon each insertion/deletion of element x as long as x belongs to C. Note that upon handling of an operation, the sum r(x) + c(x) does not change. Hence rt(x)+ct(x) stores the number insertions minus the number of deletions of element x since the step when x was inserted into C. This means that ct(x)+rt(x)≤nt(x). To show that left side of (2), consider the largest time step t′ <t, such that at step t′ , x /∈C. We know from (1), that nt′(x)<⌈γt′⌉. We also know that as long as x belongs to C, ct(x)+rt(x) counts all the occurences of x, hence ct(x)+rt(x)=nt(x)-nt′+1(x)≥nt(x)-⌈γt′⌉.

Theorem 1. Algorithms 1 and 2 correctly solve the problem of deterministically finding (φ, ϵ)-hot elements using O(log3n/ϵ) memory, O( polylog n) worst-case time for processing a single operation, and O(logn/φ) time for enlisting the (φ,ϵ)-hot elements.

Proof. To show that the main algorithm, consisting of Algorithms 1 and 2, is correct we need to show two facts:

1. it returns all elements with at least tφ occurrences,
2. it returns no element with less than t(φ-ϵ) occurrences.

The second fact follows directly from Lemma 4(2), because if t(φ-ϵ) > nt(x), then also t(φ-ϵ) > c(x)+r(x), and such element is not returned by procedure get larger than.

The first part follows from Lemma 4(1). If t≤1/γ, then all the insertions minus deletions are stored in the recent counters (i.e., rt(x)=nt(x)), hence if nt(x)≥tφ, then r(x)≥t(φ-ϵ) and this element will be returned by procedure get larger than(). Otherwise, if t > 1/γ if we have an element x, with nt(x) > tφ = t(φ - ϵ) + 6γt > t(φ - ϵ) + tγ + 5 > t(φ-ϵ) = t(φ-ϵ)+⌈tγ⌉. Then by Lemma 4(1) x ∈ Cc and ct(x)+rt(x)≥nt(x)-⌈γt⌉≥t(φ-ϵ) and this element will be returned by procedure get larger than().

The memory complexity of our algorithm is straighforward from the definition of the data structures (the dominating part is the structure of group counters, and the overhead log3n comes from the value of δ in the constructive disperser). The time of enlisting the hot elements is in fact: O(1/(φ-ϵ)) elements times O(logn) per element (see the definition of procedure get larger than()), which clearly gives O(logn/φ) for φ - ϵ = Θ(φ); in case 1/(φ - ϵ) = o(1/φ) we can run our algorithm for finding (φ,φ/2)-hot elements rather than original parameters φ,ϵ, which clearly returns only valid (φ, ϵ)-hot elements. Polylogarithmic time per operation follows from the polylogarithmic time of enlisting group counters of a single element (using disperser) and a constant number of calls to logarithmic-time procedures on the individual entries structure.

4 Lower Bound onMemory

Theorem 2. Any deterministic algorithm finding (φ, ϵ)-hot elements requires memory Ω( 1ϵ ), even for insertions.

Proof. Let α=⌈ 1 φ-ϵ ⌉-1. W.l.o.g. assume α∈Z. Consider any deterministic algorithm finding (φ, ϵ)-hot elements. We design a stream to enforce the lower bound Ω( 1ϵ ) on its memory size.

Let X be an arbitrary set of x= ⌊ 1-φ+ϵ ϵ ⌋ elements. Note that x=Θ(1/ϵ). First part of the stream S(X) associated with set X contains α insertions of each element from set X, starting from α insertions of the first element in X, then α insertions of the second element, etc. Next, the adversary adds x insertions of element v∈ N to the previously constructed stream and checks whether element v is hot after these operations. Observe that if v /∈X, we have f(v)= x αx+x = 1 α+1 ≤φ-ϵ. Otherwise, i.e., if v∈X, we get

Since there are (nx) choices of set X, the number of bits to uniquely encode all possible sets X is log2 (nx) =Θ((1-(φ-ϵ))/ϵ · log n), which is Θ(1/ε) machine words. Consider an algorithm A for finding (φ, ϵ)-hot elements using less memory. Since the memory size is smaller than log2(nx) machine words, there exist two sets X1 ̸=X2, |X1|,|X2|=x, such that after processing stream S(X1) the memory state is exactly the same as after processing stream S(X2). We showed that after processing S(X1) all and only elements from X1 can be returned by the algorithm as hot element. On the other hand, in S(X2), all and only elements from X2 can be returned by the algorithm as hot element. This is a contradiction with the assumption that A is a correct deterministic algorithm for finding (φ,ϵ)-hot elements.

5 Extensions, Discussion andOpenDirections

False positives/negatives and stochastic counterpart. Our approach guarantees no false-negatives, one could turn it into no false-positives by running the agent for parameters φ+ϵ,ϵ instead of φ,ϵ, resp. If the stream is stochastic, our agent returns all and only elements with frequency at least φ with probability corresponding to the distribution of hot items, e.g., for power-law distribution the probability of false positive/negative is polynomial in ϵ.

Graphs, hypergraphs, relationships andweights. Our agent could be applied if the universe N contains a relationship R on some set N, e.g., a graph or a hypergraph. Our agent not only monitors high frequencies of (hyper-)edges, but also vertices from set N or sets in any other sub-relation R′ of R, with a slight performance overhead maxR∈R|{R′ : R′ ⊆ R & R′ ∈ R′}|. Moreover, instead of inserting or deleting elements, we could implement more complex operations of updating variables in set N.

Parallel version. When operations appear faster than a single agent can handle, we can employ multiple agents to process the operations. Parallelization of our algorithm is possible assuming that the agents have parallel access to queue Q, structure C and the structure of group counters. When having κ agents, for κ<τ , we can parallelize the loops in lines 4 - 9 and 10 - 15 of Alg. 1. We handle κ operations in each parallel step (and κmodτ once every ⌈τ/κ⌉ parallel step) and we retain the same memory complexity of the algorithm (i.e., agents could use a small shared memory).

Acknowledgments

Partially supported by Polish National Science Center (NCN) grant 2019/33/B/ST6/02988 and by the NSF grant 2131538.