# New Verification Schemes for Frequency-Based Functions on Data Streams

Prantar Ghosh Department of Computer Science, Dartmouth College. Email:
<EMAIL_ADDRESS>Work supported in part by NSF under award
CCF-1907738.

###### Abstract

We study the general problem of computing frequency-based functions, i.e., the
sum of any given function of data stream frequencies. Special cases include
fundamental data stream problems such as computing the number of distinct
elements ($F_{0}$), frequency moments ($F_{k}$), and heavy-hitters. It can
also be applied to calculate the maximum frequency of an element
($F_{\infty}$).

Given that exact computation of most of these special cases provably do not
admit any sublinear space algorithm, a natural approach is to consider them in
an enhanced data streaming model, where we have a computationally unbounded
but untrusted prover sending proofs or help messages to ease the computation.
Think of a memory-restricted client delegating the computation to a stronger
cloud service whom it doesn’t want to trust blindly. Using its limited memory,
it wants to verify the proof that the cloud sends. Chakrabarti et al. (ICALP
’09) introduced this setting as the annotated data streaming model and showed
that multiple problems including exact computation of frequency-based
functions—that have no sublinear algorithms in basic streaming—do have
annotated streaming algorithms, also called schemes, with both space and
proof-length sublinear in the input size.

We give a general scheme for computing any frequency-based function with both
space usage and proof-size of $O(n^{2/3}\log n)$ bits, where $n$ is the size
of the universe. This improves upon the best known bound of
$O(n^{2/3}\log^{4/3}n)$ given by the seminal paper of Chakrabarti et al. and
as a result, also improves upon the best known bounds for the important
special cases of computing $F_{0}$ and $F_{\infty}$. We emphasize that while
being quantitatively better, our scheme is also qualitatively better in the
sense that it is simpler than the previously best scheme that uses intricate
data structures and elaborate subroutines. Our scheme uses a simple technique
tailored for this model: the verifier solves the problem partially by running
an algorithm known to be helpful for it in the basic (sans prover) streaming
model and then takes the prover’s help to solve the remaining part.

##  1 Introduction

Interactive proof systems have contributed a very important conceptual message
to computer science: it is possible for a computationally bounded entity to
reduce its computational cost for a problem if it is only required to verify a
proof of the solution instead of finding a solution on its own. This concept
led to celebrated results such as IP = PSPACE [Sha92] and the PCP Theorems
[ALM+98, AS98]. It is natural to incorporate this idea to deal with
challenging problems in massive data streams so as to reduce the impractical
computational costs for such problems. This incorporation led to the following
setting: a space-restricted client reading a huge data stream outsources the
computation to a more powerful entity, such as a cloud service, with unbounded
space. The cloud sends the result of the computation to the client who refuses
to blindly trust it since it might be malicious or might have incurred some
hardware failure. Therefore, the cloud (henceforth named “Prover”) also sends
the client (henceforth named “Verifier”) a proof in support of its results.
Verifier needs to use his limited space to collect sufficient information from
the stream so as to verify the proof. In the case that Prover is honest,
Verifier can use it as a help message to find the solution to the underlying
problem. Otherwise, he rejects the proof. This combination of data streaming
with prover-verifier systems has been fruitful: multiple works [ADRV16,
CCGT14, CCMT14, CCM+15, CG19, CGT20, CMT13, CTY11, KP13, KP14, Tha16b] have
shown that several intractable problems in the basic data streaming model turn
out to be solvable in prover-enhanced models using verification space and
proof-length sublinear in the input size.

Chakrabarti et al. [CCMT14] formally defined this enhanced data streaming
model as the annotated data streaming model. An algorithm in this model is
called a scheme. In designing a scheme, the two important complexity
parameters that we need to focus on are the space used by Verifier and the
size of the proof sent by Prover. A scheme that has a proof-length of $O(h)$
bits and uses $O(v)$ bits of space is called an $(h,v)$-scheme.

Since its inception, data streaming algorithms have been extensively studied
for fundamental statistical problems such as counting the number of distinct
elements in a stream $(F_{0})$ [AMS99, BJK+02, FM85, KNW10b], the $k$th
frequency moment for $k>0$ ($F_{k}$) [AMS99, GC07, IW05, Woo04], the maximum
frequency of an element ($F_{\infty}$) [AMS99, KNW10a], and the
$\ell_{p}$-norm of the frequency vector for some $p\geqslant 0$ [KNW10a,
KNW10b, NNW12]. All of these problems are special cases of (or can be solved
by easily applying) the general problem of computing frequency-based
functions: given a function $g:\mathbb{Z}\to\mathbb{Z}^{+}$, find
$\sum_{j=1}^{n}g(f_{j})$, where, for each $j$ in the universe
$\\{1,\ldots,n\\}$, $f_{j}$ is the frequency of the $j$th element. This
general problem was notably addressed by the celebrated seminal paper by Alon,
Matias, and Szegedy [AMS99]: they asked for a characterization of precisely
which frequency-based functions can be approximated efficiently in the basic
streaming model. The aforementioned paper by Chakrabarti et al. [CCMT14]
studied such statistical problems in the annotated streaming setting and gave
several interesting schemes. In particular, for the general problem of
computing frequency-based functions, they gave an
$(n^{2/3}\log^{4/3}n,n^{2/3}\log^{4/3}n)$-scheme. Their scheme uses an
intricate data structure with binary trees and calls upon a subroutine for
heavy-hitters that uses an elaborate framework called hierarchical heavy
hitters.

Given how general the problem is, with several important special cases having
numerous applications, it is important and beneficial to have a simple scheme
for the general problem. In this work, we design such a simple scheme that
uses the most basic and classical data structure for frequency estimation: the
Misra-Gries summary [MG82]. Our scheme ends up improving the best known
complexity bounds for the problem: we give an $(n^{2/3}\log n,n^{2/3}\log
n)$-scheme. No better bounds or simpler algorithms were known even for the
special cases of computing $F_{0}$ or $F_{\infty}$. Our result thus simplifies
and improves the bounds for these problems as well.

The aforementioned scheme works for streams of length $m=O(n)$, an assumption
that was also made by Chakrabarti et al. [CCMT14]. However, their scheme can
be made to work for longer turnstile streams as long as
$\|\mathbf{f}\|_{1}=O(n)$. We show how to use the Count-Median Sketch [CM05],
an estimation algorithm with stronger guarantees than Misra-Gries, to get a
scheme with similar complexity bounds for these long streams. But since the
Count-Median Sketch is randomized (contrary to Misra-Gries), we incur a non-
zero completeness error for this scheme. The high-level idea of both our
schemes is the following: we use the estimation algorithm as a primitive to
“partially” solve the problem. Prover then helps Verifier with the “remaining”
unsolved part.

###  1.1 Setup and Terminology

We formalize the setting described above. A scheme for computing a function
$g(\sigma)$ of the input stream $\sigma$ is a triple
$(\mathcal{H},\mathcal{A},\operatorname{out})$, where $\mathcal{H}$ is a
function that Prover uses to generate the help message or proof-stream for
$\sigma$, given by $\mathcal{H}(\sigma)$, $\mathcal{A}$ is a data streaming
algorithm that Verifier runs on the stream $\sigma$ using a random string $R$
to produce a summary $\mathcal{A}_{R}(\sigma)$, and $\operatorname{out}$ is a
streaming algorithm that Verifier runs on the proof-stream
$\mathcal{H}(\sigma)$ and also uses $\mathcal{A}_{R}(\sigma)$ and $R$ to
generate an output
$\operatorname{out}_{R}(\mathcal{H}(\sigma),\mathcal{A}_{R}(\sigma))$ in
range$(g)\cup\bot$, where the symbol $\bot$ denotes rejection of the proof.
Note that if the proof-length $|\mathcal{H}(\sigma)|$ is larger than the
memory of Verifier, then he needs to process $\mathcal{H}(\sigma)$ as a
stream.

A scheme $(\mathcal{H},\mathcal{A},\operatorname{out})$ has completeness error
$\varepsilon_{c}$ and soundness error $\varepsilon_{s}$ if it satisfies

  * •

(completeness)
$\forall\sigma:\Pr_{R}[\operatorname{out}_{R}(\mathcal{A}_{R}(\sigma),\mathcal{H}(\sigma))=g(\sigma)]\geqslant
1-\varepsilon_{c}$;

  * •

(soundness)
$\forall\sigma,H:\Pr_{R}[\operatorname{out}_{R}(\mathcal{A}_{R}(\sigma),H)\notin\\{g(\sigma),\bot\\}]\leqslant\varepsilon_{s}$.

Informally, this means that an honest Prover can convince Verifier to produce
the correct output with high probability. Again, if Prover is dishonest, then,
with high probability, Verifier rejects the proof. We usually aim for
$\varepsilon_{c},\varepsilon_{s}\leqslant 1/3$ (they can be boosted down using
standard techniques incurring a small increase in the space usage). A scheme
is said to have perfect completeness if $\varepsilon_{c}=0$.

The hcost (short for “help cost”) of a scheme
$(\mathcal{H},\mathcal{A},\operatorname{out})$ is defined as
$\max_{\sigma}|\mathcal{H}(\sigma)|$, i.e., the maximum number of bits
required to express a proof. The vcost (short for “verification cost”) is the
maximum bits of space used by the algorithms $\mathcal{A}_{R}(\sigma)$ and
$\operatorname{out}_{R}(\sigma)$, where the maximum is taken over all inputs
$\sigma$ and possible random strings $R$. A scheme with hcost $O(h)$ and vcost
$O(v)$ is called an $(h,v)$-scheme. An $(h,v)$-scheme is interesting if $h>0$
and $v$ is asymptotically smaller than the best bound achievable for $h=0$,
i.e., in the basic (sans prover) streaming model.

###  1.2 Our Results and Techniques

In this section, we state our results and give an overview of our techniques.

Results. Given a stream with elements in $[n]$, let $\mathbf{f}$ denote its
frequency vector $\langle f_{1},f_{2},\ldots,f_{n}\rangle$, where $f_{j}$ is
the frequency of the $j$th element. A _frequency-based function_ is a function
$G(\mathbf{f})$ of the form $G(\mathbf{f}):=\sum_{j=1}^{n}g(f_{j})$ for some
function $g:\mathbb{Z}\to\mathbb{Z}^{+}$.

Our main result is captured in the following theorem which we prove in Section
3.2.1.

######  Theorem 1.1.

There is an $(n^{2/3}\log n,n^{2/3}\log n)$-scheme for computing any
frequency-based function in any turnstile stream of length $m=O(n)$. The
scheme is perfectly complete and has soundness error at most
$1/\text{poly(n)}$.

With some modifications, we obtain a similar scheme for longer streams at the
cost of imperfect completeness. This is given by the following theorem which
we prove in Section 3.2.2.

######  Theorem 1.2.

There is an $(n^{2/3}\log n,n^{2/3}\log n)$-scheme for computing any
frequency-based function in any turnstile stream with
$\|\mathbf{f}\|_{1}=O(n)$. The scheme has completeness and soundness errors at
most $1/3$.

As a consequence, we get schemes with the same complexity bounds for the
problems of computing $F_{0}$, $F_{\infty}$, and checking multiset inclusion
(see Corollary 1.5 for formal definition). Just as for frequency-based
functions, our schemes also improve upon the best known bounds for these
special cases and applications111Computing $F_{k}$ for constant $k>0$ is a
well-studied special case for which better bounds are known [CCMT14].. We
discuss these results in detail in Section 3.3.

######  Corollary 1.3.

For any turnstile stream with $\|\mathbf{f}\|_{1}=O(n)$, there is an
$(n^{2/3}\log n,n^{2/3}\log n)$-scheme for computing $F_{0}$, the number of
distinct elements with non-zero frequency, with completeness and soundness
errors at most $1/3$. The scheme can be made perfectly complete with soundness
error $1/\text{poly}(n)$ if the stream has length $m=O(n)$.

######  Corollary 1.4.

For any turnstile stream with $\|\mathbf{f}\|_{1}=O(n)$, there is an
$(n^{2/3}\log n,n^{2/3}\log n)$-scheme for computing $F_{\infty}$, the maximum
frequency of an element, with completeness and soundness errors at most $1/3$.
The scheme can be made perfectly complete with soundness error
$1/\text{poly}(n)$ if the stream has length $m=O(n)$.

######  Corollary 1.5.

Let $X,Y\subseteq[n]$ be multisets of size $O(n)$. Given a stream where
elements of $X$ and $Y$ arrive in interleaved manner, there is an
$(n^{2/3}\log n,n^{2/3}\log n)$-scheme for determining whether $X\subseteq Y$.

Techniques. Computing frequency-based functions is challenging simply because
we don’t have enough space to store all the exact frequencies. However, there
are efficient small-space algorithms—e.g., Misra-Gries algorithm [MG82],
Count-Median Sketch [CM05]—that return reasonably good estimates of the
frequencies. We use such an algorithm as a primitive in our schemes. The
estimates returned partially solve the problem by helping us identify the
“heavy-hitters” or the most frequent items. There cannot be too many heavy-
hitters and hence, the all-powerful Prover can send Verifier the exact
frequencies of these elements (which of course need to be verified) without
too much communication. On the other hand, the rest of the elements, though
large in number, have relatively small frequency. We show a way to encode the
answer in terms of a low-degree polynomial when the frequencies are small.
Prover can then send us this polynomial using few bits, enabling us to solve
the problem with small communication overall.

We remark that the high-level technique used in our first scheme—using Misra-
Gries as a subroutine—might be more widely applicable than that used in the
second one, i.e., using Count-Median Sketch. This is because Misra-Gries is
deterministic while Count-Median is randomized. In general, both Prover and
Verifier can locally run a deterministic algorithm on the input, and then,
Prover can send messages based on the final state of that algorithm. Note that
it isn’t clear if a randomized algorithm can always help in this regard since
we assume that Prover and Verifer do not have access to shared
randomness222This assumption is made so that it corresponds to the MA
communication model. Access to shared randomness corresponds to the AMA
communication model where better bounds are known [GR13].. Hence, the final
states of the algorithm might vary drastically for Prover and Verifier if they
run it locally with their own private randomness. For our problem, we don’t
run into this issue since we don’t require Prover to know the exact output of
the Verifier’s local estimation algorithm.

Other techniques used are pretty standard in this area. We use techniques
based on the famous sum-check protocol of Lund et al. [LFKN92] that encodes
answers as sum of low-degree polynomials. In our case, where Prover sends only
a single message to Verifier, a quantity of interest is expressed as the sum
of evaluations of a low-degree univariate polynomial. Since the polynomial has
low-degree, it can be expressed with a small number of monomials. Thus, Prover
needs only a few bits to express the set of coefficients that describe the
polynomial, leading to short proof-length. Moreover, to verify the
authenticity of the polynomial, Verifier needs to evaluate it at just a single
random point, the space for which he can afford. The main challenge in this
technique is to find the proper low-degree polynomials to encode the answer,
and in this work, we give such new polynomial encodings for the underlying
sub-problems. Another standard technique we use is the shaping technique that
transforms a one-dimensional vector into a two-dimensional array. On a high-
level, this helps in “distributing” the work between Prover and Verifier as
they each “take care of” a single dimension. Pertaining to the streaming
model, we exploit the popular technique of linear sketching where we express a
quantity of interest as a linear combination of the stream updates, which
helps us to maintain the quantity dynamically as the stream arrives.

###  1.3 Related Work

Early works on the concept of stream outsourcing and verification were done by
the database community [LYHK07, PYP07, TMD+05, YLH+08]. Motivated by these
works, Chakrabarti et al. [CCMT14] abstracted out and formalised the
theoretical aspects of the settings. They defined two types of stream
verification settings: (i) the annotated data streaming setting—calling the
schemes as online schemes—where Prover and Verfier read the input stream
together and Prover sends help messages during and/or after the stream arrival
based on the part of the stream she has seen so far, and (ii) the prescient
setting where Prover knows the entire stream upfront, i.e., before Verifies
sees it, and can send help messages accordingly. Several subsequent works
[CCGT14, CG19, CGT20, CMT13, KP13, Tha16b] studied these non-interactive
models. Natural generalizations of the model, where we allow multiple rounds
of interaction between Prover and Verifier, have also been explored. These
include Arthur-Merlin streaming protocols (Prover is named “Merlin” and
Verifier is named “Arthur” following a long-standing tradition in complexity
theory) of Gur and Raz [GR13] and the streaming interactive proofs (SIP) of
Cormode et al. [CTY11]. The latter setting was further studied by multiple
works [ADRV16, CCM+15, KP14]. We refer the reader to the expository article by
Thaler [Tha16a] for a detailed survey of this area.

We state the results with the standard assumption [CCMT14, CTY11] that the
stream length $m=O(n)$. Chakrabarti et al. [CCMT14] gave two schemes for
computing any general frequency-based function: an online
$(n^{2/3}\log^{4/3}n,n^{2/3}\log^{4/3}n)$-scheme and a prescient $(n^{2/3}\log
n,n^{2/3}\log n)$-scheme. They noted that the schemes apply to get best known
schemes for the special cases of computing the number of distinct elements
($F_{0}$), the maximum frequency ($F_{\infty}$), and for checking multiset
inclusion. They also showed a lower bound that any online or prescient
$(h,v)$-scheme for the problem (even for the aforementioned special cases)
requires $hv\geqslant n$. They designed schemes with better bounds for certain
other frequency-based functions, often matching this lower bound up to
polylogarithmic factors. For instance, for any $hv=n$, they gave an online
$(k^{2}h\log n,kv\log n)$-scheme for calculating the $k$th frequency moment
$F_{k}$ for any positive integer $k$, and a $(\phi^{-1}\log^{2}n+h\log n,v\log
n)$-scheme for computing the $\phi$-heavy hitters (elements with frequency of
at least a $\phi$-fraction of the stream length).

The specific problem of computing $F_{0}$ has been studied by multiple works
in various stream verification models. Cormode, Mitzenmacher, and Thaler
[CMT10] studied the problem in the stronger SIP-model and gave a
$(\log^{3}n,\log^{2}n)$-SIP with $O(\log^{2}n)$ rounds of communication. For
the case where we restrict the number of rounds to $O(\log n)$, Cormode,
Thaler, and Yi [CTY11] gave a $(\sqrt{n}\log^{2}n,\log^{2}n)$-SIP. Klauck and
Prakash [KP14] improved this to a $(\log^{4}n\log\log n,\log^{2}n\log\log
n)$-SIP. Gur and Raz [GR13] designed an
$(\tilde{O}(\sqrt{n}),\tilde{O}(\sqrt{n}))$-AMA-streaming protocol333AMA
stands for the communication pattern Arthur-Merlin-Arthur (the
$\tilde{O}(\cdot)$ notation hides polylog$(n)$ factors) for $F_{0}$.

##  2 Preliminaries

Here, we discuss the streaming models we study and some standard results that
we use in our schemes.

Throughout this paper, the stream elements come from the universe
$[n]:=\\{1,\ldots,n\\}$ and the stream length is $m$. In the turnstile
streaming model, tokens are of the form $(j,\Delta)\in[n]\times\mathbb{Z}$,
which means $\Delta$ copies of the element $j$ are inserted (resp. deleted) if
$\Delta>0$ (resp. $\Delta<0$). The _cash register_ or insert-only streaming
model is the special case when $\Delta$ is always positive. In this paper, for
simplicity, we assume unit updates, i.e., $\Delta\in\\{-1,1\\}$ always. The
assumption can be easily removed by looking at an update as a collection of
multiple unit updates.

For a stream
$\sigma=\langle(a_{1},\Delta_{1}),\ldots,(a_{m},\Delta_{m})\rangle$, the
_frequency vector_ $\mathbf{f}(\sigma)$ is defined as $\langle
f_{1},\ldots,f_{n}\rangle$ where $f_{j}$ is the frequency of element $j$,
given by $f_{j}:=\sum_{\begin{subarray}{c}i\in[m]:\\\
a_{i}=j\end{subarray}}\Delta_{i}$. We denote estimates of $f_{j}$ by
$\hat{f}_{j}$. We drop the argument $\sigma$ when the stream is clear from the
context.

In our schemes, we use the standard technique of _sketching_ a frequency
vector by evaluating its _low-degree extension_ at a random point. We explain
what this means. We transform (or shape) our frequency vector of length $n$
into a $2$-dimensional $d_{1}\times d_{2}$ array $f$, where $d_{1}d_{2}=n$,
using some canonical bijection from $[n]$ to $[d_{1}]\times[d_{2}]$. This
means that the domain of the function $f$ can now be seen as
$[d_{1}]\times[d_{2}]$. We work on a finite field $\mathbb{F}$ with large
enough characteristic such that the values don’t “wrap around” under
operations in $\mathbb{F}$. By Lagrange’s interpolation, there is a unique
polynomial $\tilde{f}(X,Y)\in\mathbb{F}[X,Y]$ with
$\deg_{X}(\tilde{f})=d_{1}-1$ and $\deg_{Y}(\tilde{f})=d_{2}-1$ such that
$\tilde{f}(x,y)=f(x,y)$ for all $(x,y)\in[d_{1}]\times[d_{2}]$. We call
$\tilde{f}$ the low-degree $\mathbb{F}$-extension of $f$. For each
$(x,y)\in[d_{1}]\times[d_{2}]$, we have “Lagrange basis polynomials” defined
as

$\displaystyle\delta_{x,y}(X,Y):=\left(\prod_{x_{i}\in[d_{1}]\setminus\\{x\\}}\frac{X-x_{i}}{x-x_{i}}\right)\cdot\left(\prod_{y_{i}\in[d_{2}]\setminus\\{y\\}}\frac{Y-y_{i}}{y-x_{i}}\right)$
(1)

We can write $\tilde{f}$ as a linear combination of these polynomials as
follows:

$\tilde{f}(X,Y)=\sum_{(x,y)\in[d_{1}]\times[d_{2}]}f(x,y)\,\delta_{x,y}(X,Y)$

In particular, if $f$ is built up from a stream of turnstile updates
$\langle((x,y)_{j},\Delta_{j})\rangle$, then

$\tilde{f}(X,Y)=\sum_{j}\Delta_{j}\,\delta_{(x,y)_{j}}(X,Y)\,.$ (2)

Thus, we can use eq. 2 to maintain $\tilde{f}(x^{*},y^{*})$ at some fixed
point $(x^{*},y^{*})$ dynamically with stream updates. We formalize this in
the following fact.

######  Fact 2.1.

Given a point $(x^{*},y^{*})\in\mathbb{F}^{2}$ and a stream of updates to an
initially-zero $d_{1}\times d_{2}$-dimensional array $f$, we can maintain
$\tilde{f}(x^{*},y^{*})$ using $O(\log|\mathbb{F}|)$ space. For implementation
details and generalizations, see Cormode et al. [CTY11].

An important subroutine in one of our schemes s the classic Misra-Gries
algorithm for frequency estimation [MG82] which, given an input stream of $m$
elements and a fraction $\phi$, estimates the frequency of the stream elements
within an additive factor of $\phi m$. We recall this algorithm in Algorithm
1.

Informally, the algorithm does the following: it keeps an array or
“dictionary” $K$ indexed by “keys” that are elements of the stream and each of
them has an associated counter $K[i]$. At any point of time, the array has at
most $\lceil{\phi^{-1}}\rceil$ keys. When a stream element arrives, it
increments the counter for the element if it’s present in the keys (it
includes it in the keys if there are less than $\lceil{\phi^{-1}}\rceil$
keys), and otherwise decrements the counter of every key. If a counter for a
key becomes $0$, it is removed from $K$. Finally, the estimate $\hat{f}_{j}$
is given by $K[j]$ (which is $0$ if $j$ is not in the keys). The guarantees of
the algorithm is given in 2.2.

Algorithm 1 [MG82] Misra-Gries algorithm for frequency estimates in insert-
only streams

1:Stream $\sigma$; $\phi\leqslant 1$

2:Initialize $K\leftarrow$ empty array Process(token $j\in\sigma$):

3:if $j\in\text{keys}(K)$ then

4: $K[j]\leftarrow K[j]+1$

5:else

6: if $|\text{keys}(K)|<\lceil{\phi^{-1}}\rceil$ then

7: $K[j]\leftarrow 1$

8: else

9: for $i\in\text{keys}(K)$ do:

10: $K[i]\leftarrow K[i]-1$

11: if $K[i]=0$ then remove $i$ from keys$(K)$ Output:

12:for $j\in[n]$ do:

13: if $j\in\text{keys}(K)$ then return $\hat{f}_{j}=K[j]$; else return
$\hat{f}_{j}=0$

######  Fact 2.2 ([MG82]).

For an insert-only stream of $m$ elements in $[n]$, given any $\phi\leqslant
1$, Algorithm 1 uses $O(\phi^{-1}(\log n+\log m))$ space and returns frequency
estimates $\langle\hat{f}_{j}:j\in[n]\rangle$ such that, for all tokens
$j\in[n]$, we have $f_{j}-\phi m\leqslant\hat{f}_{j}\leqslant f_{j}$.

Note that this algorithm was designed for insert-only streams and doesn’t work
for turnstile streams. To use it for turnstile streams, we need to make
appropriate modifications (which we do in Section 3.1).

##  3 Computing Frequency-based Functions in Turnstile Streams

Let $\mathbf{f}$ be the frequency vector of a stream as defined in Section 2.
Recall that a _frequency-based function_ is a function $G(\mathbf{f})$ of the
form $G(\mathbf{f}):=\sum_{j\in[n]}g(f_{j})$ for some function
$g:\mathbb{Z}\to\mathbb{Z}^{+}$. In this section, we obtain an improved
$(n^{2/3}\log n,n^{2/3}\log n)$-scheme for computing any frequency-based
function for some predetermined function $g$. As stated earlier, we design a
scheme exploiting the Misra-Gries algorithm (Algorithm 1). We want to use it
as a subroutine in our problem for turnstile streams, but it works only in the
insert-only model. Therefore, in Section 3.1, we provide a simple extension of
the algorithm that attains a similar guarantee for turnstile streams. In
Section 3.2, first, we use this extended Misra-Gries (EMG) algorithm as a
subroutine for our scheme for computing frequency-based functions. Next, we
show that we can instead use the Count-Median Sketch [CM05] to make it work
for longer streams. In Section 3.3, we discuss some important applications of
our schemes.

###  3.1 Extension of Misra-Gries Algorithm for Turnstile Streams

The extended Misra-Gries algorithm (henceforth called “EMG algorithm”) works
as follows: we process the positive and negative updates separately in two
parallel copies of Algorithm 1 to estimate the total positive update and
(absolute value of) the total negative update. In the second copy, we can
actually think of the updates as “increments” since only negative updates are
processed there. Thus, what we are actually estimating is the absolute value
of the total negative update.

For each $j$, let the total positive update be $f_{j}^{+}$ and (absolute value
of) the total negative update $f_{j}^{-}$. Then, the actual frequency is
$f_{j}=f_{j}^{+}-f_{j}^{-}$. Denote the corresponding estimates given by the
copies of Algorithm 1 by $\hat{f}_{j}^{+}$ and $\hat{f}_{j}^{-}$. Then
$\hat{f}_{j}:=\hat{f}_{j}^{+}-\hat{f}_{j}^{-}$ gives a similar guarantee as
2.2 for turnstile streams; this time, we also incur an additive error of $\phi
m$ on the upper bound.

To see this, note that by 2.2, we have, $\forall j\in[n]$,

$\displaystyle f_{j}^{+}-\phi m\leqslant\hat{f}_{j}^{+}\leqslant f_{j}^{+}$
(3) $\displaystyle f_{j}^{-}-\phi m\leqslant\hat{f}_{j}^{-}\leqslant
f_{j}^{-}$ (4)

Thus, eqs. 3 and 4 give $f_{j}^{+}-f_{j}^{-}-\phi
m\leqslant\hat{f}_{j}^{+}-\hat{f}_{j}^{-}\leqslant f_{j}^{+}-f_{j}^{-}+\phi
m$, i.e.,

$f_{j}-\phi m\leqslant\hat{f}_{j}\leqslant f_{j}+\phi m$ (5)

Hence, this time we get double sided error. This estimate would suffice for
getting our desired scheme. Therefore, we get the following lemma.

######  Lemma 3.1.

Given a turnstile stream of $m$ elements in $[n]$, the EMG algorithm uses
$O(\phi^{-1}(\log n+\log m))$ space and returns a summary
$\langle\hat{f}_{j}:j\in[n]\rangle$ such that, for all $j\in[n]$, we have
$f_{j}-\phi m\leqslant\hat{f}_{j}\leqslant f_{j}+\phi m$.

######  Remark.

The guarantee given by the EMG algorithm may not be very useful in general for
turnstile streams. This is because the total number of stream updates $m$ can
be huge, whereas the frequency of each token can be small since we allow both
increments and decrements in the turnstile model. The classic Misra-Gries
algorithm for insert-only model, on the other hand, has a good guarantee (2.2)
since $m=\|\mathbf{f}\|_{1}$ in this model. However, for our purpose, the
guarantee in Lemma 3.1 is good enough since we assume that $m=O(n)$.

###  3.2 Schemes for Frequency-based Functions

First, in Section 3.2.1, we describe a protocol for computing frequency-based
functions in turnstile streams of length $O(n)$ and prove Theorem 1.1. Next,
in Section 3.2.2, we show that the scheme can be modified to work for any
turnstile stream with $\|\mathbf{f}\|_{1}=O(n)$, proving Theorem 1.2. The
completeness error in the latter scheme is, however, non-zero.

####  3.2.1 Perfectly Complete Scheme for $O(n)$-Length Streams

As in prior works [CCMT14, CTY11], we solve the problem for stream length
$m=O(n)$. Hence, by Lemma 3.1, the EMG algorithm takes $O(\phi^{-1}\log n)$
space and gives, for some constant $c$,

$\forall j\in[n]:~{}f_{j}-\phi cn\leqslant\hat{f}_{j}\leqslant f_{j}+\phi
cn\,.$ (6)

Set $\phi=(cn^{2/3})^{-1}$. Therefore, we have an $O(n^{2/3}\log n)$ space
algorithm that guarantees

$\forall j\in[n]:~{}f_{j}-n^{1/3}\leqslant\hat{f}_{j}\leqslant
f_{j}+n^{1/3}\,.$

Let $K$ denote the set of keys in the final state of the EMG algorithm for the
setting of $\phi=1/(cn^{2/3})$. Observe that if $\hat{f}_{j}=0$ for some $j$
(i.e., $j\not\in K$), we know that $f_{j}\in[-n^{1/3},n^{1/3}]$.

Define $h(j)=\mathbb{I}\\{j\not\in K\\}$ where $\mathbb{I}$ is the $0$-$1$
indicator function. We have

$\sum_{j\in[n]}g(f(j))=\sum_{j\in K}g(f(j))+\sum_{j\not\in
K}g(f(j))=\sum_{j\in K}g(f(j))+\sum_{j\in[n]}g(f(j))h(j)$

Let $L:=\sum_{j\in K}g(f(j))$ and $R:=\sum_{j\in[n]}g(f(j))h(j)$. We shall
compute $L$ and $R$ separately and add them to get the desired answer.

We shape (see Section 2) the $1$D array $[n]$ into a $2$D $n^{1/3}\times
n^{2/3}$ array. Thus, we get

$R=\sum_{x\in[n^{1/3}]}\sum_{y\in[n^{2/3}]}g(f(x,y))h(x,y)$

As is standard [CCMT14], we assume that the range of the function $g$ is upper
bounded by some polynomial in $n$, say $n^{p}$. Pick a prime $q$ such that
$n^{p+1}<q<2n^{p+1}$. We will work in the finite field $\mathbb{F}_{q}$ and
the upper bound on the range of $g$ ensures that $G(\mathbf{f})$ will not
“wrap around” under arithmetic in $\mathbb{F}_{q}$.

Let $\tilde{f},\tilde{h}$ be polynomials of lowest degree over the finite
field $\mathbb{F}_{q}$ that agree with $f,h$ respectively at all values in
$[n^{1/3}]\times[n^{2/3}]$. Note that, by Lagrange’s interpolation, both
$\tilde{f}$ and $\tilde{h}$ have degrees $n^{1/3}-1$ and $n^{2/3}-1$ in the
two variables (see Section 2). Again, let $\tilde{g}$ denote the polynomial of
lowest degree that agrees with $g$ at all values in $[-n^{1/3},n^{1/3}]$.
Thus, $\tilde{g}$ has degree $2n^{1/3}$.

Therefore, we have

$R=\sum_{x\in[n^{1/3}]}\sum_{y\in[n^{2/3}]}\tilde{g}(\tilde{f}(x,y))\tilde{h}(x,y)$

i.e., we can write

$R=\sum_{x\in[n^{1/3}]}P(x)\,,$ (7)

where the polynomial $P$ is given by

$P(X)=\sum_{y\in[n^{2/3}]}\tilde{g}(\tilde{f}(X,y))\tilde{h}(X,y)$ (8)

To compute $L$, it suffices to obtain the values $f_{j}$ for all $j\in K$
since $g$ is predetermined. In our protocol, Prover would send values
$f^{\prime}_{j}$ that she claims to be $f_{j}$ for all $j\in K$. Define

$T:=\sum_{j\in K}(f_{j}-f^{\prime}_{j})^{2}$

Note that we have $f_{j}=f^{\prime}_{j}$ for each $j$ if and only if $T=0$.
Set $f^{\prime}_{j}:=0$ for all $j\not\in K$. Thus, we can rewrite $T$ as

$T=\sum_{j\in[n]}(f_{j}-f^{\prime}_{j})^{2}(1-h(j))$

Using shaping as before, we get

$T=\sum_{x\in[n^{1/3}]}\sum_{y\in[n^{2/3}]}(f(x,y)-f^{\prime}(x,y))^{2}(1-h(x,y))$
(9)

Let $\tilde{f}^{\prime}$ denote the polynomial of lowest degree over
$\mathbb{F}_{q}$ that agrees with $f^{\prime}$ at all values in
$[n^{1/3}]\times[n^{2/3}]$. Therefore, we have

$T=\sum_{x\in[n^{1/3}]}Q(x)$ (10)

where the polynomial $Q$ is given by

$Q(X)=\sum_{y\in[n^{2/3}]}(\tilde{f}(X,y)-\tilde{f}^{\prime}(X,y))^{2}(1-\tilde{h}(X,y))\,.$
(11)

We are now ready to describe the protocol.

Stream processing.

Verifier picks $r\in\mathbb{F}_{q}$ uniformly at random. As the stream
arrives, he maintains $\tilde{f}(r,y)$ for all $y\in[n^{2/3}]$ (2.1). In
parallel, he runs the EMG algorithm setting $\phi=(cn^{2/3})^{-1}$.

Help message.

Prover sends polynomials $P^{\prime}$ and $Q^{\prime}$, and values
$f^{\prime}_{j}$ for all $j\in K$. She claims that
$P^{\prime},Q^{\prime},f^{\prime}$ are identical to $P,Q,f$ respectively. The
polynomials are sent as streams of their coefficients following some canonical
order of their monomials. Verifier evaluates $P^{\prime}(r)$ and
$Q^{\prime}(r)$ as the polynomials are streamed.

Verification and output.

Looking at the final state of the EMG subroutine, Verifier constructs
$\tilde{h}(r,y)$ for all $y\in[n^{2/3}]$ (he can treat the keys as a stream
and use 2.1). Also, from the values $f^{\prime}_{j}$, he constructs
$\tilde{f}^{\prime}(r,y)$ for all $y\in[n^{2/3}]$. The $O(n^{1/3})$-degree
polynomial $\tilde{g}$ is computed and stored in advance (we need to evaluate
$g$ at all points in $[-n^{1/3},n^{1/3}]$ and then use Lagrange interpolation
to get $\tilde{g}$).

Thus, Verifier can now use eq. 8 to compute $P(r)$ and eq. 11 to compute
$Q(r)$. He checks whether $P(r)=P^{\prime}(r)$ and $Q(r)=Q^{\prime}(r)$. If
the checks pass, he believes $P^{\prime},Q^{\prime}$ are correct. He further
checks whether $\sum_{x\in[n^{1/3}]}Q^{\prime}(x)=0$, i.e., by Equation 10,
whether $T=0$. If so, he believes that $f^{\prime}_{j}=f_{j}$ for all $j\in
K$. Next, he computes $L=\sum_{j\in K}g(f^{\prime}(j))$, and using Equation 7,
he computes $R=\sum_{x\in[n^{1/3}]}P^{\prime}(x)$. Finally, $L+R$ gives the
answer.

Error probability.

The correctness analysis follows along standard lines of sum-check protocols.
The scheme is perfectly complete since it follows from above that we always
output correctly if Prover is honest. For soundness, note that the protocol
fails if either $P\neq P^{\prime}$ or $Q\neq Q^{\prime}$, but
$P(r)=P^{\prime}(r)$ and $Q(r)=Q^{\prime}(r)$. Then, $r$ is a root of the non-
zero polynomial $P-P^{\prime}$ or $Q-Q^{\prime}$. Since degree of
$P-P^{\prime}$ is $O(n^{2/3})$ and that of $Q-Q^{\prime}$ is $O(n^{1/3})$,
they have at most $O(n^{2/3})$ roots in total. Since $r$ is drawn uniformly at
random from $\mathbb{F}_{q}$, where $q>n^{p+1}$, the probability that $r$ is
such a root is at most $O(n^{2/3})/n^{p+1}\leqslant 1/\text{poly}(n)$ for
sufficiently large $n$. Thus, the soundness error is at most
$1/\text{poly}(n)$.

Help and Verification costs.

The polynomials $P$ and $Q$ have degree $O(n^{2/3})$ and $O(n^{1/3})$
respectively. Thus, it requires $O(n^{2/3}\log n)$ bits in total to express
their coefficients since each coefficient comes from $\mathbb{F}_{q}$ that has
size $\text{poly}(n)$. Recall that for the setting of $\phi=(cn^{2/3})^{-1}$,
there are $O(\phi^{-1})=O(n^{2/3})$ keys in the EMG algorithm. Prover sends
$f^{\prime}_{j}$ for each $j\in K$, and since each frequency is at most
$m=O(n)$, this requires $O(n^{2/3}\log n)$ bits to communicate. Therefore, the
total hcost is $O(n^{2/3}\log n)$.

As noted above, the invocation of EMG algorithm takes $O(n^{2/3}\log n)$
space. Verifier maintains $\tilde{f}(r,y)$ and stores the values
$\tilde{h}(r,y)$ and $\tilde{f}^{\prime}(r,y)$ for all $y\in[n^{2/3}]$. Each
value is an element in $\mathbb{F}_{q}$, and hence they take up $O(n^{2/3}\log
n)$ space in total. The $O(n^{1/3})$-degree polynomial $\tilde{g}$ takes
$O(n^{1/3}\log n)$ space to store. Hence, the total vcost is $O(n^{2/3}\log
n)$.

Thus, we have proved the following theorem. See 1.1

####  3.2.2 Handling longer streams at the cost of imperfect completeness

The scheme in Section 3.2.1 requires stream length $m=O(n)$. Note that a
turnstile stream with massive cancellations can have length $m\gg n$, but
$\|\mathbf{f}\|_{1}$ can still be $O(n)$. Chakrabarti et al. [CCMT14]
presented their scheme under the assumption of $m=O(n)$, but their scheme can
be made to work for longer streams as long as $\|\mathbf{f}\|_{1}=O(n)$. We
can modify our scheme to handle such streams as well without increasing the
costs, but we no longer have perfect completeness. We give a sketch of this
scheme below highlighting the modifications.

We cannot use the EMG algorithm anymore because it doesn’t give a strong
guarantee with respect to $\|\mathbf{f}\|_{1}$ for turnstile streams. We use
the Count-Median Sketch instead which gives the following guarantee.

######  Fact 3.2 (Count-Median Sketch [CM05]).

For all $\phi,\,\varepsilon>0$, there exists an algorithm that, given a
turnstile stream of elements in $[n]$ with $\|\mathbf{f}\|_{1}=O(n)$, uses
$O(\phi^{-1}\log(\varepsilon^{-1})\log n)$ space and returns frequency
estimates $\langle\hat{f}_{j}:j\in[n]\rangle$ such that, with probability at
least $1-\varepsilon$, for all tokens $j\in[n]$, we have
$f_{j}-\phi\|\mathbf{f}\|_{1}\leqslant\hat{f}_{j}\leqslant
f_{j}+\phi\|\mathbf{f}\|_{1}$.

If $\|\mathbf{f}\|_{1}\leqslant cn$ for some constant $c$, then setting
$\phi=(4cn^{2/3})^{-1}$ and $\varepsilon=1/4$, we get that there is an
$O(n^{2/3}\log n)$ space algorithm that, with probability at least $3/4$,
gives

$\forall j\in[n]:f_{j}-n^{1/3}/4\leqslant\hat{f}_{j}\leqslant f_{j}+n^{1/3}/4$
(12)

For this protocol, redefine the set $K$ as $K:=\\{j:|f_{j}|\geqslant
n^{1/3}/2\\}$. Prover sends a set $K^{\prime}$ that she claims is identical to
$K$. Let $M$ denote the set $\\{j:|\hat{f}_{j}|\geqslant 3n^{1/3}/4\\}$.
Verifier checks whether $M\subseteq K^{\prime}$, and if the check passes, he
computes $\sum_{j\in K^{\prime}}g(f_{j})$ and $\sum_{j\not\in
K^{\prime}}g(f_{j})$ separately, similar to the earlier protocol, and adds
them to obtain the answer.

Error probability. For completeness, note that if Prover is honest and
$K^{\prime}=K$, then with probability at least $3/4$, we have $M\subseteq
K^{\prime}$. To see this, observe that, by the guarantees of the Count-Median
Sketch (eq. 12), for all $j\in[n]$ with $|\hat{f}_{j}|\geqslant 3n^{1/3}/4$,
we have $|f_{j}|\geqslant n^{1/3}/2$ with probability at least $3/4$. The rest
of the completeness analysis is as before, and hence, there is no additional
completeness error. Thus, the total completeness error of the scheme is at
most $1/4$.

For soundness, suppose that $K^{\prime}\neq K$. By the guarantees of the
Count-Median Sketch, for all $j\in[n]$ with $|f_{j}|\geqslant n^{1/3}$, we
have $|\hat{f}_{j}|\geqslant 3n^{1/3}/4$ with probability at least $3/4$.
Thus, $\\{j:|f_{j}|\geqslant n^{1/3}\\}\subseteq M$. Hence, if the check
$M\subseteq K^{\prime}$ passes, then with probability at least $3/4$, we have
$\\{j:|f_{j}|\geqslant n^{1/3}\\}\subseteq K^{\prime}$. Thus, if $j\not\in
K^{\prime}$, we have $|f_{j}|<n^{1/3}$. Therefore, the computation of
$\sum_{j\not\in K^{\prime}}g(f_{j})$ goes through as before. The additional
soundness error is at most $1/\text{poly}(n)$ as analyzed earlier. Thus, the
total soundness error of the protocol is at most $1/4+1/\text{poly}(n)<1/3$.

Help and Verification costs. Clearly, since $\|\mathbf{f}\|_{1}\leqslant cn$,
we have $|K|=O(n^{2/3})$ which adds $O(n^{2/3}\log n)$ bits to the hcost. The
Count-Median Sketch takes space $O(n^{2/3}\log n)$, similar to the EMG
algorithm. The rest of the cost analysis is as before, and hence we have an
$(n^{2/3}\log n,n^{2/3}\log n)$-scheme.

Thus, we have the following theorem. See 1.2

######  Remark.

We compare the schemes for Theorem 1.1 and Theorem 1.2 (call them Scheme 1 and
Scheme 2 respectively). Scheme 2 works for streams of length $m\gg n$ as long
as $\|\mathbf{f}\|_{1}=O(n)$, while Scheme 1 requires $m=O(n)$. On the
negative side, Scheme 2 has imperfect completeness, contrary to Scheme 1.
Furthermore, the space dependence on the error $\varepsilon$ for Scheme 2 is
worse than Scheme 1: given any $\varepsilon$, Scheme 2 uses $O(n^{2/3}\log
n\log(\varepsilon^{-1}))$ space to bound the completeness and soundness errors
by at most $\varepsilon$, while Scheme 1 takes $O\left(n^{2/3}(\log
n+\log(\varepsilon^{-1}))\right)$ space to bound the soundness error by
$\varepsilon$. This means that to bound the error by $1/\text{poly}(n)$,
Scheme 2 takes $O(n^{2/3}\log^{2}n)$ space, making it weaker (though simpler)
than the scheme of Chakrabarti et al. [CCMT14], which takes
$O(n^{2/3}\log^{4/3}n)$ space for the same and is also perfectly complete. For
this, Scheme 1 takes only $O(n^{2/3}\log n)$ space.

###  3.3 Special Instances and Applications

Here, we note important implications of Theorems 1.1 and 1.2. They can be
applied to get similar results for multiple well-studied problems such as
computing the number of distinct elements in the stream ($F_{0}$), the highest
frequency of an element in the stream ($F_{\infty})$, and checking multiset
inclusions. Note that for these problems, to the best of our knowledge, the
best-known schemes were $(n^{2/3}\log^{4/3}n,n^{2/3}\log^{4/3}n)$-schemes
obtained by direct application of the general scheme. Hence, we improve the
bounds and simplify the schemes for these problems as well.

As a direct corollary of Theorems 1.1 and 1.2, we get the same bounds for
$F_{0}$. It is an extensively studied problem in both basic streaming and
stream verification. It is the special case of frequency-based functions where
the function $g$ is defined as $g(x)=0$ if $x=0$, and $g(x)=1$ otherwise.
Therefore, we obtain the following result. See 1.3 Another well-studied
problem related to frequency-based functions is computing $F_{\infty}$. Unlike
$F_{0}$, it is not a direct special case, but a protocol for it follows by
easily applying a scheme for frequency-based functions. Chakrabarti et al.
[CCMT14] noted one way in which it can be applied to solve $F_{\infty}$. Here,
we note a slightly alternate way which doesn’t use a subroutine that their
scheme uses and is tailored to our protocols: Prover sends the element
$j^{*}\in[n]$ that she claims has the highest frequency and a value
$f_{j^{*}}^{\prime}$ that she claims to be equal to $f_{j^{*}}$. By the above
protocols, Verifier can check whether $f_{j*}^{\prime}=f_{j^{*}}$. If the
check passes, he computes $G(\mathbf{f}):=\sum_{j=1}^{n}g(f_{j})$ using the
scheme above, where $g$ is defined as $g(x)=0$ if $x\leqslant f_{j*}^{\prime}$
and $g(x)=1$ otherwise. He accepts Prover’s claim if $G(\mathbf{f})=0$. Thus,
we get the following result. See 1.4 The problem of checking multiset
inclusion has two multisets arriving in a stream arbitrarily interleaved
between each other, and we need to check if one of them is contained in the
other. This abstract problem is used as a subroutine in several other
problems, e.g., some graph problems considered in the annotated settings
[CCMT14, CG19, CGT20]. Thus, an improved scheme for multiset inclusion implies
improved subroutines for the corresponding problems. It can be solved by easy
application of frequency-based functions. The reduction is already noted in
Chakrabarti et al. [CCMT14], but we repeat it here for the sake of
completeness. See 1.5

###### Proof.

Think of $X$ and $Y$ as $n$-length characteristic vector representation of the
multisets (with an entry denoting the multiplicity of the corresponding
element). Then, $X\subseteq Y$ if and only if $X_{j}\leqslant Y_{j}$ for each
$j\in[n]$. As the elements arrive, we increment an entry if belongs to $Y$ and
decrement it if it belongs to $X$. Thus, the vector $\mathbf{f}$ is given by
$f_{j}=Y_{j}-X_{j}$. Define $g$ as $g(x)=0$ if $x\geqslant 0$ and $g(x)=1$
otherwise. Therefore, computing $G(\mathbf{f}):=\sum_{j=1}^{n}g(f_{j})$ and
checking if it equals $0$ solves the problem. The multisets having size $O(n)$
ensures that the length of the stream is $O(n)$, and so we can safely apply
our scheme. ∎

##  4 Conclusions and Open Problems

In this work, we designed two new schemes for the broad class of frequency-
based functions. These schemes are much simpler than the previously best
scheme known for the problem, and furthermore, they even improve upon the
complexity bound for space usage and proof-size from $O(n^{2/3}\log^{4/3}n)$
to $O(n^{2/3}\log n)$. The best known upper bound for prescient schemes, given
by Chakrabarti et al. [CCMT14], is $O(n^{2/3}\log n)$ for both of these
complexity parameters. Hence, we also close this small gap between the
prescient and online scheme complexities, and show that prescience is not
necessary here to bring the polylogarithmic factor down to $\log n$.
Additionally, the high-level framework used in our schemes is generic enough
to be applicable for multiple other problems.

An important open problem in this area is to determine the asymptotic
complexity of the general problem of computing frequency-based functions in
the stream verification settings. Chakrabarti et al. [CCMT14] showed that any
online or prescient $(h,v)$-scheme for the problem requires $hv\geqslant n$.
Note that this lower bound leaves open the possibility of a
$(\sqrt{n},\sqrt{n})$-scheme, while the best known scheme achieves
$(\tilde{O}(n^{2/3}),\tilde{O}(n^{2/3}))$ for both online and prescient
settings. Can we match the lower bound (up to polylogarithmic factors) and get
an $(\tilde{O}(\sqrt{n}),\tilde{O}(\sqrt{n}))$-scheme for the problem, even if
prescient? What about for even special cases like $F_{0}$ or $F_{\infty}$?
Recall that there exist such online schemes for the $k$th frequency moment for
some constant $k\in\mathbb{Z}^{+}$ [CCMT14]. Also, it is possible to get such
a scheme for $F_{0}$ if we allow multiple rounds of interaction [GR13]. Any
strict improvement on the lower bound would be extremely interesting and a
breakthrough. Currently, we don’t know of a function in the turnstile
streaming model for which any online $(h,v)$-scheme must have total cost
$h+v\geqslant\omega(\sqrt{N})$ where $N$ is the lower bound on its basic
streaming complexity. This is related to the major open question of breaking
the “$\sqrt{N}$ barrier” for the Merlin-Arthur (MA) communication model.

## Acknowledgements

The author would like to thank Amit Chakrabarti and Justin Thaler for several
helpful discussions. He is also grateful to the anonymous FSTTCS 2020
reviewers for their valuable comments, especially to the reviewer who gave a
sketch of a scheme using a randomized estimation algorithm, pointing out that
it can handle longer streams and that determinism isn’t strictly necessary for
the subroutine.

## References

  * [ADRV16] Amirali Abdullah, Samira Daruki, Chitradeep Dutta Roy, and Suresh Venkatasubramanian.  Streaming verification of graph properties.  In Proc. 27th International Symposium on Algorithms and Computation, pages 3:1–3:14, 2016.
  * [ALM+98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.  Proof verification and the hardness of approximation problems.  J. ACM, 45(3):501–555, 1998.  Preliminary version in Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 14–23, 1992.
  * [AMS99] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  J. Comput. Syst. Sci., 58(1):137–147, 1999.  Preliminary version in Proc. 28th Annual ACM Symposium on the Theory of Computing, pages 20–29, 1996.
  * [AS98] Sanjeev Arora and Shmuel Safra.  Probabilistic checking of proofs: A new characterization of NP.  J. ACM, 45(1):70–122, 1998.  Preliminary version in Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 2–13, 1992.
  * [BJK+02] Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan.  Counting distinct elements in a data stream.  In Proc. 6th International Workshop on Randomization and Approximation Techniques in Computer Science, pages 128–137, 2002.
  * [CCGT14] Amit Chakrabarti, Graham Cormode, Navin Goyal, and Justin Thaler.  Annotations for sparse data streams.  In Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 687–706, 2014.
  * [CCM+15] Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian.  Verifiable stream computation and Arthur-Merlin communication.  In Proc. 30th Annual IEEE Conference on Computational Complexity, pages 217–243, 2015.
  * [CCMT14] Amit Chakrabarti, Graham Cormode, Andrew McGregor, and Justin Thaler.  Annotations in data streams.  ACM Trans. Alg., 11(1):Article 7, 2014.
  * [CG19] Amit Chakrabarti and Prantar Ghosh.  Streaming verification of graph computations via graph structure.  In Proc. 33rd International Workshop on Randomization and Approximation Techniques in Computer Science, pages 70:1–70:20, 2019.
  * [CGT20] Amit Chakrabarti, Prantar Ghosh, and Justin Thaler.  Streaming verification for graph problems: Optimal tradeoffs and nonlinear sketches.  To appear in RANDOM, 2020.
  * [CM05] Graham Cormode and S. Muthukrishnan.  An improved data stream summary: the count-min sketch and its applications.  J. Alg., 55(1):58–75, 2005.  Preliminary version in Proc. 6th Latin American Theoretical Informatics Symposium, pages 29–38, 2004.
  * [CMT10] Graham Cormode, Michael Mitzenmacher, and Justin Thaler.  Streaming graph computations with a helpful advisor.  In Proc. 18th Annual European Symposium on Algorithms, pages 231–242, 2010.
  * [CMT13] Graham Cormode, Michael Mitzenmacher, and Justin Thaler.  Streaming graph computations with a helpful advisor.  Algorithmica, 65(2):409–442, 2013.
  * [CTY11] Graham Cormode, Justin Thaler, and Ke Yi.  Verifying computations with streaming interactive proofs.  Proc. VLDB Endowment, 5(1):25–36, 2011.
  * [FM85] Philippe Flajolet and G. Nigel Martin.  Probabilistic counting algorithms for data base applications.  J. Comput. Syst. Sci., 31(2):182–209, 1985.
  * [GC07] Sumit Ganguly and Graham Cormode.  On estimating frequency moments of data streams.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, volume 4627 of Lecture Notes in Computer Science, pages 479–493, 2007.
  * [GR13] Tom Gur and Ran Raz.  Arthur–Merlin streaming complexity.  In Proc. 40th International Colloquium on Automata, Languages and Programming, pages 528–539, 2013.
  * [IW05] Piotr Indyk and David P. Woodruff.  Optimal approximations of the frequency moments of data streams.  In Proc. 37th Annual ACM Symposium on the Theory of Computing, pages 202–208, 2005.
  * [KNW10a] Daniel M. Kane, Jelani Nelson, and David P. Woodruff.  On the exact space complexity of sketching and streaming small norms.  In Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1161–1178, 2010.
  * [KNW10b] Daniel M. Kane, Jelani Nelson, and David P. Woodruff.  An optimal algorithm for the distinct elements problem.  In Proc. 29th ACM Symposium on Principles of Database Systems, pages 41–52, 2010.
  * [KP13] Hartmut Klauck and Ved Prakash.  Streaming computations with a loquacious prover.  In Proc. 4th Conference on Innovations in Theoretical Computer Science, pages 305–320, 2013.
  * [KP14] Hartmut Klauck and Ved Prakash.  An improved interactive streaming algorithm for the distinct elements problem.  In Automata, Languages, and Programming - 41st International Colloquium (ICALP), volume 8572 of LNCS, pages 919–930, 2014.
  * [LFKN92] Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan.  Algebraic methods for interactive proof systems.  J. ACM, 39(4):859–868, 1992.
  * [LYHK07] Feifei Li, Ke Yi, Marios Hadjieleftheriou, and George Kollios.  Proof-infused streams: Enabling authentication of sliding window queries on streams.  In Proc. 33rd International Conference on Very Large Data Bases, pages 147–158, 2007.
  * [MG82] Jayadev Misra and David Gries.  Finding repeated elements.  Sci. Comput. Program., 2(2):143–152, 1982.
  * [NNW12] Jelani Nelson, Huy L. Nguyên, and David P. Woodruff.  On deterministic sketching and streaming for sparse recovery and norm estimation.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, volume 7408 of Lecture Notes in Computer Science, pages 627–638, 2012.
  * [PYP07] Stavros Papadopoulos, Yin Yang, and Dimitris Papadias.  Cads: Continuous authentication on data streams.  In Proc. 33rd International Conference on Very Large Data Bases, pages 135–146, 2007.
  * [Sha92] Adi Shamir.  IP = PSPACE.  J. ACM, 39(4):869–877, 1992.
  * [Tha16a] Justin Thaler.  Data stream verification.  In Encyclopedia of Algorithms, pages 494–499. Springer Berlin Heidelberg, 2016.
  * [Tha16b] Justin Thaler.  Semi-streaming algorithms for annotated graph streams.  In Proc. 43rd International Colloquium on Automata, Languages and Programming, pages 59:1–59:14, 2016.
  * [TMD+05] Peter A. Tucker, David Maier, Lois M. L. Delcambre, Tim Sheard, Jennifer Widom, and Mark P. Jones.  Punctuated data streams, 2005.
  * [Woo04] David P. Woodruff.  Optimal space lower bounds for all frequency moments.  In Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 167–175, 2004.
  * [YLH+08] Ke Yi, Feifei Li, Marios Hadjieleftheriou, George Kollios, and Divesh Srivastava.  Randomized synopses for query assurance on data streams.  In Proc. 24th International Conference on Data Engineering, pages 416–425, 2008.


# AI Algorithm for Predicting and Optimizing Trajectory of UAV Swarm

Amit Raj11footnotemark: 1 Kapil Ahuja22footnotemark: 2<EMAIL_ADDRESS>Yann
Busnel33footnotemark: 3

###### Abstract

This paper explores the application of Artificial Intelligence (AI) techniques
for generating the trajectories of fleets of Unmanned Aerial Vehicles (UAVs).
The two main challenges addressed include accurately predicting the paths of
UAVs and efficiently avoiding collisions between them.

Firstly, the paper systematically applies a diverse set of activation
functions to a Feedforward Neural Network (FFNN) with a single hidden layer,
which enhances the accuracy of the predicted path compared to previous work.

Secondly, we introduce a novel activation function, AdaptoSwelliGauss, which
is a sophisticated fusion of Swish and Elliott activations, seamlessly
integrated with a scaled and shifted Gaussian component. Swish facilitates
smooth transitions, Elliott captures abrupt trajectory changes, and the scaled
and shifted Gaussian enhances robustness against noise. This dynamic
combination is specifically designed to excel in capturing the complexities of
UAV trajectory prediction. This new activation function gives substantially
better accuracy than all existing activation functions.

Thirdly, we propose a novel Integrated Collision Detection, Avoidance, and
Batching (ICDAB) strategy that merges two complementary UAV collision
avoidance techniques: changing UAV trajectories and altering their starting
times, also referred to as batching. This integration helps overcome the
disadvantages of both—reduction in the number of trajectory manipulations,
which avoids overly convoluted paths in the first technique, and smaller batch
sizes, which reduce overall takeoff time in the second.

###### keywords:

Artificial Intelligence , UAV Swarm Path Prediction , Activation Functions ,
Collision Avoidance

[label1]organization=Math of Data Science & Simulation (MODSS) Lab, Computer
Science & Engineering,addressline=IIT Indore, city=Indore, postcode=453552,
state=Madhya Pradesh, country=India

[label3]organization=IMT Nord Europe – Campus de Recherche,city=Douai,
postcode=F-59508, state=Nord, country=France

##  1 Introduction

UAVs have become increasingly popular in recent years due to their versatility
and potential for a wide range of applications, from surveillance and
monitoring to delivery and transportation. However, safe and efficient
operation of UAVs in complex environments remains a significant challenge,
particularly when multiple UAVs are involved. A key issue is the need to
optimize the trajectories of the UAVs to achieve various objectives, such as
minimizing travel time, avoiding collisions, and maximizing coverage.
Traditional methods for trajectory planning and control are often limited in
their ability to handle the complexity and uncertainty of real-world scenarios
and may not be scalable to large fleets of UAVs.

Prior research, exemplified by Lai (2020), Xue (2017), and Qiu and Duan
(2020), has demonstrated the efficacy of leveraging non-linear optimization
techniques. Recently, Xu et al. (2024) have used multi-objective optimization
for trajectory generation. When quick trajectory changes are required, the
optimization routine is too slow and not adaptive, and hence, AI techniques
are preferred. AI techniques, particularly those based on machine learning and
neural networks, have shown great promise in addressing these challenges by
enabling UAVs to learn from data and adapt to changing conditions Lai (2020).

These studies involved training FFNN with a single hidden layer, utilizing
activation functions such as the Hyperbolic Tangent function (Tanh), Sigmoid,
etc. The activation functions used do not predict the path with much accuracy,
and hence, we first improve this aspect. We systematically apply a diverse set
of activation functions to an FFNN with a single hidden layer, conducting a
comprehensive comparative analysis. Besides Sigmoid and Tanh, we use Rectified
Linear Unit (ReLU), Leaky ReLU, Swish, Elliot, and Maxout.

In our pursuit of enhanced trajectory accuracy, second, we introduce a novel
activation function, AdaptoSwelliGauss, which surpasses commonly used
counterparts in the same neural network architecture. This function combines
the Swish activation function, which captures smooth transitions and maintains
trajectory continuity, with the Elliot activation function, which captures
abrupt shifts in direction and velocity, as well as a scaled and shifted
Gaussian, which makes the activation function robust against noisy data.

In autonomous UAVs, the crucial components of collision detection and
avoidance play a paramount role in ensuring the safety and efficiency of their
operations, which is our third focus. The significance of these features
becomes even more pronounced when considering multiple UAVs taking off
simultaneously. Collision detection between UAVs is straightforward, however,
there are many ways to avoid collisions by changing their trajectories. Guo et
al. (2021) introduces one such popular approach, the Circular Arc Trajectory
Geometric Method (CTGA). Assuming two UAVs are colliding at a point in the
path, this technique adds a small perturbation to the path of one of these
UAVs. A drawback of this algorithm is its susceptibility to getting stuck in a
manipulation loop. Any alteration in the trajectory of one UAV may
inadvertently create collision candidates with other UAVs, leading to a
challenging situation. Additionally, frequent manipulations in a UAV’s
trajectory can result in a convoluted flight path, compromising the overall
efficiency of the UAV swarm.

Another complementary technique to avoid UAV collisions is to change their
starting times. Sastre et al. (2022a) and Sastre et al. (2022b) propose such a
popular approach. They employ a batching mechanism, creating groups of UAVs
with non-colliding trajectories to facilitate safe flight. However, the
creation of multiple batches introduces a time-intensive process, delaying the
overall launch of the UAV swarm.

In this paper, we introduce an advanced collision detection and avoidance
algorithm, referred to as the ICDAB algorithm. Here, we first improve the CTGA
algorithm from Guo et al. (2021), and then we integrate this avoidance
algorithm with the batching mechanism leading to our algorithm.

The remainder of the paper is organized as follows: Section 2 reviews the
literature, Section 3 describes our proposed algorithms and methodology,
Section 4 presents the results, and Section 5 concludes the paper and suggests
directions for future work.

##  2 Literature Review

In this section, we analyze the previous works on applying AI algorithms in
optimizing UAV trajectories, and their collision detection and avoidance.

Firstly, we highlight the earlier studies on AI for UAVs, as summarized in
Table 1. As evident, these papers address different kinds of problems. Papers
Xue (2017), Xiao et al. (2019) and Lai (2020) are closest to our problem. The
activation functions used by them are standard, archiving errors (Mean Squared
Error or MSE and Root MSE or RMSE) in the order of $10^{-3}$. However, we
experiment with a large number of activation functions (including our new
activation function), achieving error in the order of the order $10^{-11}$ to
$10^{-14}$.

Table 1: Summary on AI for UAVs. Studies |  Focus |  AI Architecture |  Activation Function |  Error
---|---|---|---|---
Xue (2017) |  Trajectory Modelling |  FFNN |  Tanh |  MSE: 0.003
Xiao et al. (2019) |  Predict UAV’s Position |  Recurrent Neural Network |  Tanh |  MSE: 0.005
Lai (2020) |  Trajectory Generation |  FFNN |  Tanh |  RMSE: 0.170
Sarkar et al. (2020) |  Flight Time Prediction |  FFNN |  Tanh |  MSE: 0.0016
Jeong et al. (2021) |  Wind-induced Trajectory Deviation |  Deep Neural Network (DNN12) |  ReLU |  RMSE: 0.007
Jiang et al. (2022) |  UAV Control |  FFNN |  Sigmoid |  RMSE: 0.126

Second, we review literature on collision detection and avoidance,
specifically trajectory manipulation during flight in Table 2. The most common
technique used is detailed in Guo et al. (2021). As mentioned earlier, we
further improve this algorithm and integrate it with a collision avoidance
technique involving changes to the UAVs’ start times (or batching), which is
discussed in the next table.

Table 2: Summary on UAV Swarm Collision Avoidance. Studies |  Focus |  Key Techniques/Methods Employed
---|---|---
Lin and Saripalli (2017) |  Collision-free path planning |  Closed-loop rapidly-exploring random tree algorithm
Elmkaiel and Serebrenny (2019) |  Quadcopter swarm collision avoidance algorithm |  Algorithm based on repulsive force fields
Wan et al. (2019) |  Distributed conflict detection and resolution |  Consensus and leader-follower strategy algorithms
Han (2019) |  Efficient collision-free 3D path planning |  Critical obstacles and surrounding point set
Guo et al. (2021) |  3D obstacle avoidance for UAV |  Circular Arc Trajectory Geometric Avoidance (CTGA) algorithm
Ourari et al. (2022) |  Decentralized collision avoidance |  Based on starling flocks’ behavior
Huang et al. (2023) |  Energy efficient collision avoidance |  Artificial potential field and particle swarm planning
Table 3: Summary on UAV Batching. Studies |  Focus |  Key Techniques/Methods Employed
---|---|---
Fabra et al. (2020) |  Swarm takeoff procedure for VTOL of UAVs |  Heuristic for optimizing UAV positions and implementing a sequential phased takeoff
Hernández et al. (2021) |  Swarm takeoff optimization |  Kuhn-Munkres algorithm for optimal, low-computation assignments
Sastre et al. (2022a) |  Trajectory-based collision detection algorithm and batch generation mechanism |  Grouping of UAVs into batches to enable simultaneous take-offs
Sastre et al. (2022b) |  Improved collision detection algorithm |  Introduction of novel methods: CSTH and ED-CSTH

Third and finally, past work done on batching is given in Table 3. The table
shows that all papers employ very similar techniques. However,
Hernández et al. (2021) and Sastre et al. (2022a) are more popular. We
directly adopt this approach and integrate it with the collision avoidance
approach discussed above.

##  3 Methodology

Our research employs a FFNN architecture, as illustrated in Figure 1,
comprising an input layer, a hidden layer, and an output layer. The input
layer of the FFNN is structured to incorporate the initial, intermediate, and
final states of the UAV across all three spatial coordinates: X, Y, and Z.
These states collectively form a multidimensional input vector that
encapsulates the complete trajectory information of the UAV.

Figure 1: FFNN Architecture.

The hidden layer plays a pivotal role in capturing and representing complex
patterns within the input data. Comprising 15 neurons, this layer employs
various activation functions to nonlinearly transform the input, facilitating
the extraction of relevant features and patterns essential for accurate
prediction. This is the layer where we experiment with different types of
activation functions and propose a new activation function as well, which is
discussed below.

Responsible for producing the final predictions, the output layer is
meticulously designed with 201 output neurons which comprise of linear
polynomials. The deliberate choice of linear activation functions in this
layer aligns with the nature of regression tasks, where the objective is to
predict continuous numerical values. We don’t change these activation
functions in this layer.

To effectively train our neural network architecture, we employ the Levenberg-
Marquardt backpropagation algorithm. This optimization technique combines the
advantages of both the gradient descent and Gauss-Newton methods, making it
well-suited for training neural networks, especially in cases where
convergence and speed are of paramount importance as here.

The combination of a diverse set of activation functions in the hidden layer
and the linear output layer forms a comprehensive framework for our research,
allowing us to address the specific complexities and intricacies of our
dataset. The rest of this section has three parts. In Section 3.1, we describe
an array of activation functions, including the newest ones. In Section 3.2,
we describe our novel AdaptoSwelliGauss activation function, in Section 3.3,
we discuss our ICDAB technique.

###  3.1 Activation Functions

In a neural network, an activation function plays a crucial role by applying a
mathematical operation to the weighted sum of inputs. This introduces non-
linearity, which is essential for the network to comprehend intricate patterns
and connections within the data. Essentially, the activation function decides
whether a neuron should fire or remain inactive, thereby impacting the flow of
information throughout the network. In this sub-section, we delve into the
various standard activation functions commonly employed in neural networks.

Here, $x$ represents the input to each activation function.

####  3.1.1 Sigmoid

The Sigmoid function maps input values into a probability range between 0 and
1, which is ideal for binary classification outputs. The formula for this is

$f(x)=\frac{1}{1+e^{-x}}.$ (1)

Its major drawback is the vanishing gradient problem.

####  3.1.2 Tanh

Tanh extends the Sigmoid shape, mapping inputs to a range between -1 and 1,
which is zero-centered. Thus, it typically results in faster convergence
during training and is chosen for layers that benefit from data normalization.
The formula for this is

$f(x)=\frac{e^{x}-e^{-x}}{e^{x}+e^{-x}}.$ (2)

Like Sigmoid, it suffers from vanishing gradients, affecting its utility in
deep networks.

####  3.1.3 ReLU

ReLU addresses some of the critical issues of earlier activation functions by
enabling faster training and deeper network compatibility thanks to its simple
computation. It prevents the vanishing gradient issue, promoting healthy
gradient levels during learning. It is given by

$f(x)=\max(0,x).$ (3)

Nonetheless, ReLU is susceptible to the “dying ReLU” problem, where neurons
can irreversibly cease activity if they stop firing across many data points.

####  3.1.4 Leaky ReLU

Leaky ReLU modifies ReLU to allow a small input gradient when the unit is
inactive. This modification ensures that all neurons have the opportunity to
update during training, thereby avoiding the dying ReLU problem. It is given
by

$f(x)=\max(\alpha x,x).$ (4)

where $\alpha$ is a small coefficient. This function requires careful tuning
of $\alpha$, adding complexity to the network’s training process.

####  3.1.5 Swish

Swish is a newer function that blends input and Sigmoid output. Its smooth
gradient helps avoid issues seen in ReLU variants, maintaining robustness
during deep network training. It is given by

$f(x)=x\cdot\sigma(\beta x),$ (5)

where $\sigma$ is the Sigmoid function and $\beta$ is a trainable parameter.

####  3.1.6 Maxout Activation

Maxout, proposed as a generalization of ReLU and its variants, is highly
flexible, allowing the model to learn a piecewise linear approximation of any
function. It is given by

$f(x)=\max(w_{1}\cdot x+b_{1},w_{2}\cdot x+b_{2},\ldots).$ (6)

####  3.1.7 Elliot Activation

Elliot activation quickly responds to changes in input values, making it
particularly useful for tasks involving crucial variations. It is given by

$f(x)=\frac{x}{1+|x|}.$ (7)

###  3.2 Novel Activation Function

We propose the activation function as below.

$\text{AdaptoSwelliGauss}(x)=\begin{cases}\text{Swish}(x),&\text{if
}x\leq\alpha\\\
\text{Elliott}(x)\times\text{Scale.Shift.Gaussian}(x),&\text{otherwise}\end{cases}$
(8)

In this formulation,

  * 1.

$x$ represents the input to the activation function,

  * 2.

$\text{Swish}(x)$ is the output when the Swish activation is applied to input
$x$,

  * 3.

$\text{Elliott}(x)$ is the output when the Elliott activation is applied to
input $x$,

  * 4.

$\text{Scale.Shift.Gaussian}(x)$ is the output of the scaled and shifted
Gaussian function applied to input $x$.

  * 5.

$\alpha$ is the hyperparameter adjusted based on experimentation and learning.

Figure 2: AdaptoSwelliGauss activation function.

The benefit of using the different components described above is discussed
next.

  1. 1.

Swish Activation: As UAVs navigate through various trajectory phases, the
Swish component seamlessly adjusts its activation levels to accommodate both
gradual and subtle changes. This inherent adaptability ensures the activation
function captures smooth transitions and maintains trajectory continuity,
crucial for precise trajectory prediction.

  2. 2.

Elliott Activation: Complementing Swish’s smoothness, the Elliott component
infuses AdaptoSwelliGauss with heightened sensitivity to abrupt trajectory
changes. When UAVs encounter sudden shifts in direction, altitude, or
velocity, the Elliott activation swiftly responds with amplified gradients.
Thereby delivering pinpoint accuracy during critical trajectory transitions.

  3. 3.

Scaled and Shifted Gaussian: The scaled and shifted Gaussian component adds a
unique dimension to AdaptoSwelliGauss by mitigating the impact of noisy data
points and preventing erratic activations that could compromise the accuracy
of trajectory predictions. This is implemented by adapting its parameters that
help to fine-tune the activation function’s behavior according to the noise
characteristics present in the trajectory data.

  4. 4.

Dynamic Adaptation and Learning: The dynamic nature of AdaptoSwelliGauss is a
critical asset. By adjusting the hyperparameter $\alpha$ during training, the
activation function fine-tunes its response based on the specifics of the
trajectory data.

AdaptoSwelliGauss, as in Figure 2, is unbounded above and bounded below. It is
smooth, facilitating differentiability, and non-monotonic.

###  3.3 Integrated Collision Detection, Avoidance, and Batching (ICDAB)

As discussed in the introduction and literature review, this section presents
our system designed to not only streamline the detection and avoidance of
collisions among UAVs but to also optimize the deployment of UAV fleets. The
novelty of this work lies in the integration of the below components. Each
component has been designed to function synergistically, enhancing the overall
efficacy of the UAV management system.

  1. 1.

Collision Detection: A geometric approach, as described in the works of
Elmkaiel and Serebrenny (2019), Lin and Saripalli (2017), and Huang et al.
(2023), is employed for collision detection. This method is widely accepted as
standard.

  2. 2.

Collision Avoidance: Here, we build upon the framework established in Guo et
al. (2021). To facilitate integration with the subsequent component, a novel
tracking array is introduced, which monitors the number of trajectory
manipulations for each UAV. We also introduce a batching list, which stores
the UAVs for whom this collision avoidance strategy fails.

  3. 3.

Batching: The batching technique, as outlined in Sastre et al. (2022a), is
adopted here. This approach is also recognized as a common standard in the
literature, including in works like Sastre et al. (2022b) and Wubben et al.
(2023). We synchronize this with the above collision avoidance component.

Next, we discuss the above three components in detail.

####  3.3.1 Collision Detection

As practically common, we assume that all UAVs take off and fly
simultaneously, following predefined trajectories between their respective
pickup and delivery points. In our collision detection methodology, we employ
a three-dimensional virtual sphere around each UAV referred to as the
“collision sphere”. This sphere is defined by a parameter “R” that denotes its
radius (See Figure 3). On a broader level, a collision is defined when any UAV
collision sphere intersects with the collision sphere of another UAV. Next, we
make this statement precise.

Figure 3: Collision sphere around the UAV.

Let we be given a list of UAVs, their respective trajectories in terms of X,
Y, and Z coordinates, their timestamps, and predefined point on the trajectory
of each UAV where collision is to be checked (also called waypoints). Without
loss of generality (WLOG) for a UAV pair, the standard algorithm calculates
the Euclidean distance between their position at each waypoint along their
paths and checks if this distance falls below a user-defined distance
threshold when the timestamps of the UAV pair also meet a user-defined time
threshold. If a collision is detected, then instead of the standard procedure
of building a list of colliding pairs of UAVs, we apply the collision
avoidance strategy discussed below. Finally, this procedure is repeated for
all pairs.

####  3.3.2 Collision Avoidance

The primary objective here is to dynamically adjust the trajectory of two UAVs
on a collision course. WLOG, we assume UAV1 and UAV2 are two UAVs that would
collide. WLOG again, we change the trajectory of UAV1. This standard algorithm
takes the following inputs: precise collision point of the two UAVs, and an
array for padding adjustments to UAV1.

Figure 4: Collision avoidance between two UAVs.

The distribution of values within the padding array follows a uniform pattern,
incrementing uniformly from 0 to 2R+safe distance and then uniformly
decrementing back to 0. Here safe distance is the extra distance between the
“collision sphere” of two UAVs. Next, UAV1 is checked for collision with all
the remaining UAVs, and if there is one, then again collision avoidance
strategy as above is applied. This strategic design, as shown in Figure 4,
facilitates a gradual and balanced transition in UAV trajectories, optimizing
collision avoidance effectiveness while maintaining trajectory simplicity.

Next, we discuss our contribution that involves integration with batching. The
trajectory manipulations, stored in an introduced tracking array for a UAV,
are done up to a limit so as to avoid infinite adjustment (as happening in the
standard approach). If this limit is exceeded for a UAV, then we look at the
trajectory manipulation of the other UAV in the colliding pair. If adjustment
for the other UAV also exceeds this limit, then both are moved to a batching
list, as separate entries (not as a pair).

####  3.3.3 Batching Mechanism

The batch generation algorithm is responsible for organizing UAVs into batches
to facilitate coordinated flight. Its goal is to form collision-free batches
that can be managed as a single unit. In the standard approach, the list of
colliding pairs of UAVs is used as a input here.

Next, we describe our approach, which integrates with the above collision
avoidance strategy. Here, the input to the batching algorithm is the batching
list. The UAVs that are not on the batching list are free from any collision
and outputted as one batch.

Next, the $1^{st}$ UAV from the batching list is picked for the next batch.
This $1^{st}$ UAV is checked for a collision with all the subsequent UAVs in
the list ($2^{nd}$ UAV onwards).

WLOG, let the $i^{th}$ UAV does not collide with the $1^{st}$ UAV, then
$1^{st}$ and $i^{th}$ UAVs are added to this next batch, and both are further
checked for collision from $(i+1)^{th}$ UAV in the batching list. WLOG let
$j^{th}$ UAV does not collide with both the $1^{st}$ and $i^{th}$ UAV. Then,
$j^{th}$ UAV is also added to the next batch. Further, all three are checked
for collision from $(j+1)^{th}$ UAV in the batching list.

This process is recursively done to determine this final next batch as well as
all subsequent batches.

##  4 Results

Data for 500 UAVs is generated using a UAV simulator implemented with the UAV
toolbox of Simulink in MATLAB. The simulation is run on a PC equipped with an
Intel Core i7 12th generation processor, a 64-bit operating system, and 8GB of
RAM.

Each UAV’s trajectory is generated with a total of 201 waypoints, providing a
rich and detailed dataset conducive to robust algorithm development. The
configuration of initial and destination coordinates for each UAV is taken
from Lai (2020), which provides guidance on setting realistic ranges. The X
and Y coordinates for the initial position range from [10-50], with a fixed
initial Z-coordinate at 0. Destination coordinates are constrained within X, Y
[200-300] with the Z-coordinate again fixed at zero. The maximum altitude
achievable by the UAVs is set between [30-40].

A pictorial representation of the paths of all the UAVs is shown in Figure 5.
The dataset is partitioned into three distinct segments: 70% is allocated for
training, 15% for validation, and the remaining 15% for testing. The
computational process iterates over 1000 epochs to optimize outcomes.

Figure 5: Dataset of 500 UAVs.

The choice of a loss function is pivotal in training neural networks as it
quantifies the disparity between predicted and actual values. An effectively
chosen loss function facilitates efficient learning and generalization,
mitigating the risk of overfitting and enhancing model robustness. Loss
functions are task-specific; for instance, cross-entropy is typically used for
classification tasks, while Mean Squared Error (MSE) is often employed for
regression tasks.

To measure the quality of trajectory prediction, various types of loss
functions given in Table 4. Here, $y_{i}$ represents the actual value,
$\hat{y}_{i}$ denotes the predicted value, and $n$ symbolizes the number of
observations. Also, the first two measures have been used extensively in the
literature and the remaining three are less explored in this context.

Table 4: Summary of Loss Functions. S. No. |  Loss Function |  Formula
---|---|---
1. |  Mean Squared Error (MSE) |  $MSE=\frac{1}{n}\sum_{i=1}^{n}(y_{i}-\hat{y}_{i})^{2}.$
2. |  Root MSE (RMSE) |  $RMSE=\sqrt{MSE}.$
3. |  Mean Absolute Error (MAE) |  $MAE=\frac{1}{n}\sum_{i=1}^{n}|y_{i}-\hat{y}_{i}|.$
4. |  Mean Absolute Percentage Error (MAPE) |  $MAPE=\frac{1}{n}\sum_{i=1}^{n}\left|\frac{y_{i}-\hat{y}_{i}}{y_{i}}\right|\times 100\%.$
5. |  Symmetric MAPE (SMAPE) |  $SMAPE=\frac{1}{n}\sum_{i=1}^{n}\frac{2|y_{i}-\hat{y}_{i}|}{|y_{i}|+|\hat{y}_{i}|}\times 100\%.$

Although MSE is the most commonly used loss function in the literature,
according to Kreinovich et al. (2014) and Chicco et al. (2021), SMAPE provides
a symmetric measure that offers a better comparison in certain scenarios. We
use SMAPE in conjunction with MSE to understand the performance of the dataset
comprehensively.

The rest of this section has two parts. In Section 4.1, we present appropriate
loss function values on the standard activation functions and our novel
AdaptoSwelliGauss activation function (from Sections 3.1 and 3.2). In Section
4.2, we give experimental results using ICDAB techniques (from Section 3.3)

###  4.1 Relevant Loss Functions Values Using Different Activations

For these experiments, the values of hyperparameters $\beta$, $\alpha$,
$scale$, and $shift$ that work best for us are the median of the input to the
activation functions, and are given by $0.5,0.14,0.5,$ and $0.25$,
respectively.

X-coordinates results are given in Table 5. Among the standard activation
functions, the ReLU and Elliot activation functions demonstrate the best
performance achieving MSEs of $1.733\times 10^{-10}$ and $3.605\times
10^{-11}$ respectively, and SMAPEs of 0.19% and 0.15%, respectively.
AdaptoSwelliGauss substantially surpasses both, attaining an MSE of
$3.059\times 10^{-14}$ and a SMAPE of 0.14%.

Table 5: Error Metrics for the X-coordinate. No. | Activation Function | MSE | SMAPE
---|---|---|---
1 | Sigmoid | $9.200\times 10^{-5}$ | 0.16%
2 | Tanh | $1.406\times 10^{-7}$ | 0.29%
3 | ReLU | $1.733\times 10^{-10}$ | 0.19%
4 | Leaky ReLU | $5.510\times 10^{-5}$ | 0.21%
5 | Swish | $1.638\times 10^{-9}$ | 0.20%
6 | Maxout | $3.462\times 10^{-6}$ | 0.15%
7 | Elliot | $3.605\times 10^{-11}$ | 0.15%
8 | AdaptoSwelliGauss | $3.059\times 10^{-14}$ | 0.14%

For Y-coordinates, are given in Table 6. Among the standard activation
functions, Swish and Elliot activation functions exhibit very good performance
with MSE values of $6.805\times 10^{-10}$ and $3.780\times 10^{-9}$
respectively, and SMAPE values of 0.21% and 0.18%, respectively.
AdaptoSwelliGauss outperforms them, achieving an MSE of $5.127\times 10^{-11}$
and a SMAPE of 0.15%.

Table 6: Error Metrics the for Y-coordinate. No. | Activation Function | MSE | SMAPE
---|---|---|---
1 | Sigmoid | $1.822\times 10^{-8}$ | 0.17%
2 | Tanh | $8.664\times 10^{-7}$ | 0.68%
3 | ReLU | $1.793\times 10^{-8}$ | 0.29%
4 | Leaky ReLU | $2.934\times 10^{-6}$ | 0.29%
5 | Swish | $6.805\times 10^{-10}$ | 0.21%
6 | Maxout | $2.192\times 10^{-6}$ | 0.18%
7 | Elliot | $3.780\times 10^{-9}$ | 0.18%
8 | AdaptoSwelliGauss | $5.127\times 10^{-11}$ | 0.15%

For Z-coordinates, results are given in Table 7. Among the standard activation
functions Swish and Maxout activation functions stand out with superior
performance metrics achieving MSEs of $2.182\times 10^{-13}$ and $2.630\times
10^{-12}$, respectively, and SMAPE values of 0.13% for both. AdaptoSwelliGauss
slightly surpasses these, attaining an MSE of $1.739\times 10^{-13}$ and a
SMAPE of 0.12%.

Table 7: Error Metrics for the Z-coordinate.  No. | Activation Function | MSE | SMAPE
---|---|---|---
1 | Sigmoid | $4.588\times 10^{-11}$ | 0.34%
2 | Tanh | $8.031\times 10^{-7}$ | 0.61%
3 | ReLU | $5.851\times 10^{-9}$ | 0.31%
4 | Leaky ReLU | $1.344\times 10^{-7}$ | 0.29%
5 | Swish | $2.182\times 10^{-13}$ | 0.13%
6 | Maxout | $2.630\times 10^{-12}$ | 0.13%
7 | Elliot | $4.851\times 10^{-8}$ | 0.36%
8 | AdaptoSwelliGauss | $1.739\times 10^{-13}$ | 0.12%

Across all three coordinates, among the standard activation functions, ReLU,
Swish, and Elliot give the best results. AdaptoSwelliGauss consistently
demonstrates substantially superior performance compared to all of these,
highlighting its robustness and effectiveness in enhancing the accuracy and
predictive capabilities of the neural network across different dimensions.

###  4.2 Results On ICDAB

When we apply collision detection as described in Section 3.3.1. we detect 262
collisions. Here the value of “R” is $0.5$. Next, we apply the original (or
standard) collision avoidance as initially described in Section 3.3.2 (i.e.,
one where infinite trajectory manipulation is allowed), and the algorithm gets
stuck in a loop.

Thus, further, we apply our modified collision avoidance algorithm (as given
at the end of Section 3.3.2) along with batching (from Section 3.3.3). This
integration leads to substantial improvement in both components.

First, the application of the modified collision avoidance (i.e., up to ten
trajectory manipulations allowed) leads to convergence of the algorithm,
eventually resulting in only 41 possible collisions. Batching brings these
collisions down to zero. Here, the safe radius taken is 0.5.

Second, results for batching integrated with the modified collision avoidance
are given in Table 8. As evident from this table, the number of batches
required is reduced from 7 to 5, while the maximum number of UAVs per batch
increased from 38 to 315.

Table 8: Result before and after applying ICDAB. Metric |  Before Collision Avoidance |  After Collision Avoidance
---|---|---
Number of Batches |  7 |  5
Maximum number of UAVs per Batch |  38 |  315

Next, we show the importance of carefully calibrating the safe radius in our
ICDAB algorithm. As shown in Table 9, increasing the safe radius initially
results in a decrease in the number of colliding UAVs, decrease in number of
batches, and increase in the maximum number of UAVs per batch, achieving
optimal results at a safe radius of 2.3. At this radius, the number of
colliding UAVs is reduced to 33, the number of batches is minimized to 4, and
the maximum number of UAVs per batch increases to 396. However, beyond this
optimal point, further increases in the safe radius lead to a reverse trend,
where both the number of colliding UAVs and the number of batches begin to
increase again, while the maximum number of UAVs per batch decreases. These
results are subject to the characteristics and dynamics of the specific
dataset under consideration, and different datasets may yield different
optimal safe radius values. However, there is a scientific reason for this
observed trend.

Table 9: ICDAB Outcomes with Different Safe Radius Values. Safe Radius |  Number of Collision After Avoidance |  Number of Batches |  Max Number of UAVs per Batch
---|---|---|---
0.5 |  47 |  5 |  315
0.7 |  46 |  6 |  321
1.9 |  39 |  7 |  326
2.1 |  35 |  4 |  378
2.3 |  33 |  4 |  396
2.5 |  42 |  6 |  335
2.7 |  61 |  8 |  305
2.9 |  65 |  10 |  278

This is because of unintended consequences of over-adjusting UAV trajectories
at larger safe radius (see Figure 6). As in the given figure, when the
trajectory of UAV1 is significantly altered to avoid UAV2, it may
inadvertently collide with UAV3, which was previously not on a collision
course with UAV1. This has a cascading effect on all the UAVs.

Figure 6: A: ICDAB with small safe radius, B: ICDAB with large safe radius.

##  5 Conclusion

In this paper, we focus on the development of an intelligent framework for
predicting and optimizing the trajectory of a fleet of UAVs. Traditional
methods have limitations in accurately predicting paths as well as efficiently
avoiding collisions for large fleets of UAVs. We address these challenges
here.

In our research, we first conduct a comprehensive comparative analysis by
applying various activation functions to a FFNN with a single hidden layer.

Second is the introduction of a novel activation function called
AdaptoSwelliGauss. This activation function substantially outperforms commonly
used counterparts in terms of trajectory accuracy.

Third, we improve existing methods for collision detection and avoidance.
Detection is straightforward while avoidance is challenging. We can avoid
collision between UAVs by either changing their trjaectories or sending them
in batches. Each of which has its drawbacks. We uniquely combine those
technique leading to improved performance.

Future work involves improving the underlying mathematical optimisation Ahuja
et al. (2008); exploring Convolutional Neural Networks (CNNs) for enhanced
trajectory accuracy Li et al. (2021); integrating advanced sensors like LiDAR
for real-time collision detection Wei et al. (2018); using approximate
computing in neural networks Gupta et al. (2020); Ullah et al. (2020);
leveraging multi-agent reinforcement learning for collaborative decision-
making Canese et al. (2021); exploiting implicit relation between different
drone trajectories Kim et al. (2005); and conducting real-world validation
studies to ensure regulatory compliance and operational efficiency in
autonomous UAV operations.

## References

  * Ahuja et al. (2008) Ahuja, K., Watson, L.T., Billups, S.C., 2008.  Probability-one homotopy maps for mixed complementarity problems.  Computational Optimization and Applications 41, 363 – 375.
  * Canese et al. (2021) Canese, L., Cardarilli, G.C., Di Nunzio, L., Fazzolari, R., Giardino, D., Re, M., Spanò, S., 2021.  Multi-agent reinforcement learning: A review of challenges and applications.  Applied Sciences 11, 4948\.
  * Chicco et al. (2021) Chicco, D., Warrens, M.J., Jurman, G., 2021.  The coefficient of determination R-squared is more informative than SMAPE, MAE, MAPE, MSE and RMSE in regression analysis evaluation.  PeerJ Computer Science 7:e623.
  * Elmkaiel and Serebrenny (2019) Elmkaiel, G., Serebrenny, V., 2019\.  Collision avoidance algorithm for a quadcopters swarm, in: AIP Conference Proceedings, AIP Publishing. p. 190006.
  * Fabra et al. (2020) Fabra, F., Wubben, J., Calafate, C.T., Cano, J.C., Manzoni, P., 2020.  Efficient and coordinated vertical takeoff of UAV swarms, in: 2020 IEEE 91st Vehicular Technology Conference (VTC2020-Spring), IEEE. pp. 1–5.
  * Guo et al. (2021) Guo, J., Liang, C., Wang, K., Sang, B., Wu, Y., 2021\.  Three-dimensional autonomous obstacle avoidance algorithm for UAV based on circular arc trajectory.  International journal of aerospace engineering 8819618\.
  * Gupta et al. (2020) Gupta, S., Ullah, S., Ahuja, K., Tiwari, A., Kumar, A., 2020.  ALigN: A highly accurate adaptive layerwise Log_2_Lead quantization of pretrained neural networks.  IEEE Access 8, 118899\.
  * Han (2019) Han, J., 2019.  An efficient approach to 3D path planning.  Information Sciences 478, 318–330.
  * Hernández et al. (2021) Hernández, D., Cecília, J.M., Calafate, C.T., Cano, J.C., Manzoni, P., 2021.  The Kuhn-Munkres algorithm for efficient vertical takeoff of UAV swarms, in: 2021 IEEE 93rd Vehicular Technology Conference (VTC2021-Spring), IEEE. pp. 1–5.
  * Huang et al. (2023) Huang, S., Zhang, H., Huang, Z., 2023.  E2CoPre: Energy efficient and cooperative collision avoidance for UAV swarms with trajectory prediction.  arXiv preprint arXiv:2303.06510 .
  * Jeong et al. (2021) Jeong, S., You, K., Seok, D., 2021.  Hazardous flight region prediction for a small UAV operated in an urban area using a deep neural network.  Aerospace Science and Technology 118, 107060.
  * Jiang et al. (2022) Jiang, B., Li, B., Zhou, W., Lo, L.Y., Chen, C.K., Wen, C.Y., 2022.  Neural network based model predictive control for a quadrotor UAV.  Aerospace 9, 460\.
  * Kim et al. (2005) Kim, S., Murthy, U., Ahuja, K., Vasile, S., Fox, E.A., 2005.  Effectiveness of implicit rating data on characterizing users in complex information systems, in: Rauber, A., Christodoulakis, S., Tjoa, A.M.e. (Eds.), Research and Advanced Technology for Digital Libraries (ECDL 2005), Lecture Notes in Computer Science. Springer. volume 3652, pp. 186 – 194.
  * Kreinovich et al. (2014) Kreinovich, V., Nguyen, H.T., Ouncharoen, R., 2014.  How to estimate forecasting quality: A system-motivated derivation of symmetric mean absolute percentage error SMAPE and other similar characteristics.  Departmental Technical Reports (CS) 865, 1–12.
  * Lai (2020) Lai, R., 2020.  A machine learning approach to trajectory planning for UAV.  M.S. Thesis, Rensselaer Polytechnic Institute.
  * Li et al. (2021) Li, Z., Liu, F., Yang, W., Peng, S., Zhou, J., 2021\.  A survey of convolutional neural networks: analysis, applications, and prospects.  IEEE transactions on neural networks and learning systems 33, 6999–7019.
  * Lin and Saripalli (2017) Lin, Y., Saripalli, S., 2017\.  Sampling-based path planning for UAV collision avoidance.  IEEE Transactions on Intelligent Transportation Systems 18, 3179–3192.
  * Ourari et al. (2022) Ourari, R., Cui, K., Elshamanhory, A., Koeppl, H., 2022\.  Nearest-neighbor-based collision avoidance for quadrotors via reinforcement learning, in: 2022 International Conference on Robotics and Automation (ICRA), IEEE. pp. 293–300.
  * Qiu and Duan (2020) Qiu, H., Duan, H., 2020.  A multi-objective pigeon-inspired optimization approach to UAV distributed flocking among obstacles.  Information Sciences 509, 515–529.
  * Sarkar et al. (2020) Sarkar, S., Totaro, M.W., Kumar, A., 2020.  An intelligent framework for prediction of a UAV’s flight time, in: 2020 16th International Conference on Distributed Computing in Sensor Systems (DCOSS), IEEE. pp. 328–332.
  * Sastre et al. (2022a) Sastre, C., Wubben, J., Calafate, C.T., Cano, J.C., Manzoni, P., 2022a.  Collision-free swarm take-off based on trajectory analysis and UAV grouping, in: 2022 IEEE 23rd International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), IEEE. pp. 477–482.
  * Sastre et al. (2022b) Sastre, C., Wubben, J., Calafate, C.T., Cano, J.C., Manzoni, P., 2022b.  Safe and efficient take-off of VTOL UAV swarms.  Electronics 11, 1128\.
  * Ullah et al. (2020) Ullah, S., Gupta, S., Ahuja, K., Tiwari, A., Kumar, A., 2020.  L2L: A highly accurate Log_2_Lead quantization of pretrained neural networks, in: 2020 Design, Automation & Test in Europe Conference & Exhibition (DATE), IEEE. pp. 979–982.
  * Wan et al. (2019) Wan, Y., Tang, J., Lao, S., 2019.  Distributed conflict-detection and resolution algorithm for UAV swarms based on consensus algorithm and strategy coordination.  IEEE Access 7, 100552–100566.
  * Wei et al. (2018) Wei, P., Cagle, L., Reza, T., Ball, J., Gafford, J., 2018\.  LiDAR and camera detection fusion in a real-time industrial multi-sensor collision avoidance system.  Electronics 7, 84\.
  * Wubben et al. (2023) Wubben, J., Hernández, D., Cecilia, J.M., Imberón, B., Calafate, C.T., Cano, J.C., Manzoni, P., Toh, C.K., 2023\.  Assignment and take-off approaches for large-scale autonomous UAV swarms.  IEEE Transactions on Intelligent Transportation Systems 24, 4836–4847.
  * Xiao et al. (2019) Xiao, K., Zhao, J., He, Y., Yu, S., 2019.  Trajectory prediction of UAV in smart city using recurrent neural networks, in: ICC 2019-2019 IEEE International Conference on Communications, IEEE. pp. 1–6.
  * Xu et al. (2024) Xu, X., Xie, C., Luo, Z., Zhang, C., Zhang, T., 2024\.  A multi-objective evolutionary algorithm based on dimension exploration and discrepancy evolution for UAV path planning problem.  Information Sciences 657, 119977\.
  * Xue (2017) Xue, M., 2017.  UAV trajectory modeling using neural networks, in: 17th AIAA Aviation Technology, Integration, and Operations Conference, ARC. p. 3072\.