DI ENS, ENS, CNRS, PSL University & Inria,
Franceyann.ramusat@ens.frhttps://orcid.org/0000-0002-7181-8331 Université
Paris-Saclay, LISN, CNRS,
Francesilviu.maniu@lisn.upsaclay.frhttps://orcid.org/0000-0002-8623-1533 DI
ENS, ENS, CNRS, PSL University & Inria & IUF,
Francepierre@senellart.comhttps://orcid.org/0000-0002-7909-5369 Yann Ramusat,
Silviu Maniu, and Pierre Senellart <ccs2012> <concept>
<concept_id>10002951.10002952.10002953.10010820.10003623</concept_id>
<concept_desc>Information systems Data provenance</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10003752.10010070.10010111.10003623</concept_id>
<concept_desc>Theory of computation Data provenance</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>
[500]Information systems Data provenance [500]Theory of computation Data
provenance This work has been funded by the French government under management
of Agence Nationale de la Recherche as part of the “Investissements d’avenir”
program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute).

# A Practical Dynamic Programming Approach to Datalog Provenance Computation

Yann Ramusat  Silviu Maniu  Pierre Senellart

###### Abstract

We establish a translation between a formalism for dynamic programming over
hypergraphs and the computation of semiring-based provenance for Datalog
programs. The benefit of this translation is a new method for computing
provenance for a specific class of semirings. Theoretical and practical
optimizations lead to an efficient implementation using Soufflé, a state-of-
the-art Datalog interpreter. Experimental results on real-world data suggest
this approach to be efficient in practical contexts, even competing with our
previous dedicated solutions for computing provenance in annotated graph
databases. The cost overhead compared to plain Datalog evaluation is fairly
moderate in many cases of interest.

###### keywords:

Datalog, provenance, semiring, graph databases, dynamic programming

##  1 Introduction

A notion of provenance for Datalog queries was introduced by Green,
Karvounarakis, and Tannen [green_provenance_2007]. It is based on the
algebraic structure of semirings to encode additional meta-information about
query results and extends the notion of semiring provenance of the positive
fragment of the relational algebra, also introduced in
[green_provenance_2007]. The full provenance of a Datalog program (i.e., the
provenance associated to each derived tuple) is expressed as a system of
equations over an _$\omega$ -continuous_ semiring.

Beyond this initial definition, some research has proposed other
representation frameworks to improve the computation of Datalog provenance.
Circuits [deutch_circuits_2014] have been proposed to obtain a compact
representation of the provenance. Derivation-tree analysis
[esparza_solving_2011] focuses on the natural mapping between systems of
equations over $\omega$-continuous semirings and context-free grammars. These
techniques rely on additional properties of the semiring, thus being limited
to some specific applications; in particular, some semiring properties such as
_absorptivity_ serve as a basis for optimization in both scenarios.

The present work addresses two major challenges related to the computation of
semiring-based provenance of Datalog programs.

On the first hand, much of the knowledge around the theory and applications of
using semirings to capture some meta-information about a computation (i.e.,
_provenance_ in database speak) is spread across different fields of computer
sciences. Among other areas, semirings have been successfully used in
linguistic structure prediction [smith_linguistic_2011], dynamic programming
[huang_advanced_2008], constraint programming [bistarelli_semiring-
based_1997], and variations of the shortest-distance problem in graphs
[Mohri:2002:SFA:639508.639512]. The structure of semirings is also at the
heart of the study of formal languages [rozenberg_handbook_1997,
Kuich:1985:SAL:576931], weighted automata [droste_handbook_2009], graph theory
and graph algorithms [minoux:hal-01304880], and computational algebra
[parallel]. The algebraic path problem [general] provides a common viewpoint
for a large variety of problems involving semirings. Because of the widespread
use of semirings in different areas, and rather unfortunately, it is common to
find different names used for similar properties (e.g., $0$-closed semirings
are also called absorptive, bounded, simple, $0$-stable, etc.). Even more
concerning, the term “semiring” itself is replaced by similar names in some
works (e.g. by “dioids” or “algèbre de chemin” [RO_1975__9_1_77_0]); in some
cases, the semiring structure could have been used to model the problem, but
was not acknowledged at the time [knuth_generalization_1977]. We believe it is
necessary to spend some effort establishing links between multiple
representation frameworks of what is essentially semiring provenance to
benefit from a wide range of techniques proposed in various domains of
computer science. This would obviate the pitfall of designing algorithms and
developing techniques in the jargon of a given field, whereas some key ideas
may have already been investigated under similar algebraic frameworks, but by
other research communities.

On the other hand, to the best of the knowledge of the authors, the bulk of
the scientific literature about provenance for Datalog programs is mostly
concerned with, either, formalization and extensions
[DBLP:journals/corr/abs-2105-14435] to the theoretical framework behind
semiring-based provenance, with the objective to reach a massive number of
application domains, or elegantly leveraging quite abstract tools such as
circuits [deutch_circuits_2014] or Newton convergence [esparza_solving_2011]
to optimize computations. Those works rarely go all the way to the
implementation level, apart from some “proofs of concept”
[10.1007/978-3-319-08846-4_1], raising the question of the applicability to
real-world data.

A work of note that does come with an implementation is [7113407,
Deutch2018EfficientPT], concerned about the computation of a relevant subset
of provenance information through selection criteria based on tree patterns
and the ranking of rules and facts, when the computation of the full
provenance (how-provenance) is unfeasible in practice.

Our contributions can be organized into four parts.

  1. 1.

We first establish a correspondence between dynamic programming over
hypergraphs (as introduced in [huang_advanced_2008] under the name of weighted
hypergraphs) and the proof-theoretic definition of the provenance for Datalog
programs. We provide both-way translations and characterize for which class of
semirings the best-weight derivation in the hypergraph corresponds to the
provenance of the initial Datalog program.

  2. 2.

The translation we thus introduced permits us to obtain a version of Knuth’s
generalization of Dijkstra’s algorithm [knuth_generalization_1977] to the
_grammar problem_ , adapted to the case of Datalog provenance computation. In
the special setting where all hyperedges are of arity 1, we obtain the
classical notion of semiring-based provenance for graph databases
[ramusat:hal-01850510]. In the general setting, the algorithm steadily
generalizes to Datalog the adapted Dijkstra’s algorithm we presented in
[ramusat:hal-01850510], under the same assumptions on the properties of the
underlying semiring.

  3. 3.

Such algorithm is unlikely to be efficient as-is in practical contexts. The
main issue is closely related to the inefficiency of basic Datalog evaluation:
many computations of facts (provenance values) have already been deduced,
leading to redundant computations. We show that the semi-naïve evaluation
strategy for Datalog is also applicable in our setting. An added advantage is
that it greatly facilitates the extension of existing Datalog solvers to
compute provenance annotations. We implement our strategy extending Soufflé
[10.1007/978-3-319-41540-6_23], a state-of-the-art Datalog solver. We apply
our solution to process rich graph queries (translated into Datalog programs)
on several real-world and synthetic graph datasets, as well as to Datalog
programs used in previous works [Deutch2018EfficientPT]. The performance of
the implementation competes with dedicated solutions specific to graph
databases [ramusat:hal-03140067].

  4. 4.

The link we established with the framework of weighted hypergraphs, and hence,
with the grammar problem, opens up new opportunities and challenges for
semiring-based provenance for Datalog programs. We thus carefully discuss
selected topics and problems that can now understood as closely linked to the
provenance framework [green_provenance_2007].

We start by introducing in Section 2 basic concepts on semirings and we recall
the definition of provenance for Datalog programs. We formulate and prove in
Section 3 the correspondence between weighted hypergraphs and semiring-based
provenance for Datalog programs. In Section 4, we present the adapted version
of Knuth’s algorithm for the grammar problem and discuss theoretical aspects
of its optimization. We then dive into the practical aspects of its
implementation using Soufflé, and present in Section 5 experimental results
witnessing the efficiency of our approach for practical scenarios. We finally
discuss, in Section 6 and Section 7, respectively opportunities raised by our
translation and related work. For space reasons, proofs and some auxiliary
material are deported to an appendix.

##  2 Background

In the following, we recall basic concepts of semiring theory underlying the
optimization techniques we provide in this paper. For more background on the
theory and applications of semirings, examples of relevant semirings, as well
as references to the literature on advanced notions of semiring theory, see
our previous work [ramusat:hal-03140067]. We follow the definitions in
[ramusat:hal-03140067] and highlight notions that occur under different names
depending on the application domain.

######  Definition 2.1 (Semiring).

A _semiring_ is an algebraic structure $(S,\oplus,\otimes,\bar{0},\bar{1})$
where $S$ is some set, $\oplus$ and $\otimes$ are binary operators over $S$,
and $\bar{0}$ and $\bar{1}$ are elements of $S$, satisfying the following
axioms:

  * •

$(S,\oplus,\bar{0})$ is a _commutative monoid_ : $(a\oplus b)\oplus
c=a\oplus(b\oplus c)$, $a\oplus b=b\oplus a$, $a\oplus\bar{0}=\bar{0}\oplus
a=a$;

  * •

$(S,\otimes,\bar{1})$ is a _monoid_ : $(a\otimes b)\otimes c=a\otimes(b\otimes
c)$, $\bar{1}\otimes a=a\otimes\bar{1}=a$;

  * •

$\otimes$ distributes over $\oplus$: $a\otimes(b\oplus c)=(a\otimes
b)\oplus(a\otimes c)$;

  * •

$\bar{0}$ is an annihilator for $\otimes$: $\bar{0}\otimes
a=a\otimes\bar{0}=\bar{0}$.

A semiring is _commutative_ if for all $a,b\in S$, $a\otimes b=b\otimes a$. A
semiring is _idempotent_ if for all $a\in S$, $a\oplus a=a$. For an idempotent
semiring we can introduce the _natural order_ defined by $a\leqslant b$ iff
$a\oplus b=a$.111There are unfortunately two definitions of natural order
commonly found in the literature; we use here that found in
[Mohri:2002:SFA:639508.639512, huang_advanced_2008] which matches the standard
order on the tropical semiring; other works [rozenberg_handbook_1997,
green_provenance_2007, ramusat:hal-03140067] define it as the reverse order.
Our choice obviously has some impacts: in particular, when defining Datalog
provenance, we need greatest fixpoints in lieu of the least fixpoints used in
[rozenberg_handbook_1997, green_provenance_2007]. Note that this order is
compatible with the two binary operations of the semiring: for all $a,b,c\in
S$, $a\leqslant b$ implies $a\oplus c\leqslant b\oplus c$ and $a\otimes
c\leqslant b\otimes c$. This is also called the _monotonicity_ property.

An important property is that of _k-closedness_
[Mohri:2002:SFA:639508.639512], i.e., a semiring is $k$-closed if: $\forall
a\in S,\leavevmode\nobreak\
\bigoplus_{i=0}^{k+1}a^{i}=\bigoplus_{i=0}^{k}a^{i}.$ Here, by $a^{i}$ we
denote the repeated application of the $\otimes$ operation $i$ times, i.e.,
$a^{i}=\underbrace{a\otimes a\otimes\dots\otimes a}_{i}$. 0-closed semirings
(i.e., those in which $\forall a\in S,\bar{1}\oplus a=\bar{1}$) have also been
called _absorptive_ , _bounded_ , or _simple_ depending on the literature.
Note that any $0$-closed semiring is idempotent (indeed, $a\oplus
a=a\otimes(\bar{1}\oplus\bar{1})=a\otimes\bar{1}=a$) and therefore admits a
natural order.

Huang [huang_advanced_2008] introduces the notion of _superiority_ of a
semiring $S$ with respect to a partial order $\leqslant$, defined by: $\forall
a,b\in S\>a\leqslant a\otimes b,\>b\leqslant a\otimes b$. The natural order
satisfies this notion for $0$-closed semirings:

######  Lemma 2.2.

lem:superiority Let $S$ be an idempotent semiring and $\leqslant$ the natural
order over $S$. Then $S$ is _superior_ with respect to $\leqslant$ if and only
if $S$ is $0$-closed.

######  Proof 2.3.

First assume $S$ superior with respect to $\leqslant$. Then for any $a$,
$\bar{1}\leqslant\bar{1}\otimes a=a$, which means that $\bar{1}+a=\bar{1}$,
i.e., $S$ is $0$-closed.

Now assume $S$ $0$-closed. Since $a\oplus
a\\!\otimes\\!b=a\otimes(\bar{1}\oplus b)=a$, we have: $a\leqslant a\otimes
b$, and similarly for $b\leqslant a\otimes b$. Thus $S$ is superior with
respect to $\leqslant$.

An easier way of understanding natural order in 0-closed semirings is to note
that for any idempotent semiring $S$, $\bar{0}$ is the greatest element
($\forall a\in S$, $a\oplus 0=a\leqslant\bar{0}$) while, if the semiring is
also 0-closed (i.e., _bounded_), $\bar{1}$ is the smallest ($\forall a\in S$,
$\bar{1}\oplus a=\bar{1}\geqslant a$). Thus a bounded semiring $S$ verifies
$\bar{1}\leqslant a\leqslant\bar{0}$ for all $a\in S$.

######  Definition 2.4 ($\omega$-Continuous semiring).

A semiring $(S,\oplus,\otimes,\bar{0},\bar{1})$ is _$\omega$ -continuous_ if

  1. 1.

$(S,\geqslant)$ is a _$\omega$ -complete_ partial order, i.e., the infimum
$\mathop{\mathsf{inf}}\limits_{i\in\mathbb{N}}\>a_{i}$ of any infinite chain
$a_{0}\geqslant a_{1}\geqslant\dots$ exists in $S$.

  2. 2.

both addition and multiplication are _$\omega$ -continuous_ in both arguments,
i.e., for all $a\in S$ and infinite chain $a_{0}\geqslant
a_{1}\geqslant\dots$,
$(a\oplus\mathop{\mathsf{inf}}\limits_{i\in\mathbb{N}}a_{i})=\mathop{\mathsf{inf}}\limits_{i\in\mathbb{N}}(a\oplus
a_{i})$,
$(a\otimes\mathop{\mathsf{inf}}\limits_{i\in\mathbb{N}}a_{i})=\mathop{\mathsf{inf}}\limits_{i\in\mathbb{N}}(a\otimes
a_{i})$, $(\mathop{\mathsf{inf}}\limits_{i\in\mathbb{N}}a_{i})\otimes
a=\mathop{\mathsf{inf}}\limits_{i\in\mathbb{N}}(a_{i}\otimes a)$.

In such semirings we can define countable sums:
$\bigoplus\limits_{n\in\mathbb{N}}a_{n}=\underset{m\in\mathbb{N}}{\mathsf{inf}}\bigoplus\limits_{i=0}^{m}a_{i}$.

A _system of fixpoint equations_ over an $\omega$-continuous semiring $S$ is a
finite set of equations:
$X_{1}=f_{1}(X_{1},X_{2},\dots,X_{n}),\dots,X_{n}=f_{n}(X_{1},X_{2},\dots,X_{n}),$
where $X_{1},\dots,X_{n}$ are variables and $f_{1},\dots f_{n}$ are
polynomials with coefficients in $S$. We extend the notion of natural order
from semiring elements to tuples of semiring elements by simply considering
the product order. We then have the following on solutions of a system of
equations over an $\omega$-continuous semiring:

######  Theorem 2.5 (Theorem 3.1 of [rozenberg_handbook_1997]).

Every system of fixpoint equations $\mathbf{X}=f(\mathbf{X})$ over a
commutative $\omega$-continuous semiring has a greatest solution
$\mathsf{gfp}(f)$ w.r.t. $\leqslant$, and $\mathsf{gfp}(f)$ is equal to the
infimum of the Kleene sequence:
$\mathsf{gfp}(f)=\mathop{\mathsf{inf}}\limits_{m\in\mathbb{N}}f^{m}(\mathbf{\bar{0}}).$

We now recall some basics about the Datalog query language and refer to
[DBLP:books/aw/AbiteboulHV95] for more details. A Datalog rule is of the form
$R(\vec{x})\;\textsf{:-}\;R_{1}(\vec{x_{1}}),\>\dots,\>R_{n}(\vec{x_{n}})$
with $R$’s representing relations of a given arity and the $\vec{x}$’s tuples
of variables of corresponding arities. Variables occurring on the left-hand
side, the head of the rule, are required to occur in at least one of the atoms
on the right-hand side, the body of the rule. A Datalog program is a finite
set of Datalog rules. We call fact a rule with an empty body and variables
replaced by constants. We divide relations into _extensional_ ones (which can
only occur as head of a fact, or in rule bodies) and _intensional_ ones (which
may occur as heads of a non-fact rule). The set of extensional facts is called
the _extensional database_ ($\mathsf{EDB}$). We distinguish one particular
relation occurring in the head of a rule, the _output predicate_ of the
Datalog program. We refer to [DBLP:books/aw/AbiteboulHV95] for the semantics
of such a program and the notion of _derivation tree_.

There are two ways of defining the _provenance_ of a Datalog program $q$ with
output predicate $G$ over an $\omega$-continuous semiring. We can first base
this definition on the proof-theoretic definition of standard Datalog:

######  Definition 2.6 (Proof-theoretic definition for Datalog provenance
[green_provenance_2007]).

Let $(S,\oplus,\otimes,\bar{0},\bar{1})$ be a commutative $\omega$-continuous
semiring and $q$ a Datalog program with output predicate $S$ and such that all
extensional facts $R(t^{\prime})$ are annotated with an element of $S$,
denoted as $\mathop{\mathsf{prov}}_{R}^{q}(t^{\prime})$. Then the _provenance_
of $G(t)$ for $q$, where $G(t)$ is in the output of $q$, is defined as:

$\mathsf{prov}_{G}^{q}(t)=\bigoplus\limits_{\tau\>\textup{yields}\>t}\left(\bigotimes\limits_{t^{\prime}\in\>\textup{leaves}(\tau)}\mathsf{prov}_{R}^{q}(t^{\prime})\right).$

The first sum ranges over all the derivation trees of the fact $t$ (see Figure
1 for examples of derivation trees), the second sum ranges over all leaves of
the tree (extensional facts). This definition describes how the provenance
propagates across the deduction process given an initial assignment of
provenance weights to the extensional relations of $q$,
$\mathsf{prov}_{R}^{q}$.

path(Paris, London) 3edge(Paris, London) 3dummy$r_{1}$

path(Paris, London) 1path(Paris, Lille) 1edge(Paris, Lille)
1$r_{1}$edge(Lille, London) 0$r_{2}$

edge(Paris, London) :- $\displaystyle 3$ edge(Paris, Lille) :- $\displaystyle
1$ edge(Lille, London) :- $\displaystyle 0$ path(x, y) :- edge(x, y)
$\displaystyle\quad r_{1}$ path(x, y) :- path(x, z), edge(z, y)
$\displaystyle\quad r_{2}$

Figure 1: Derivation trees along their weights for the fact path(Paris,
London) using the transitive closure Datalog program over the tropical
semiring with an $\mathsf{EDB}$ containing $3$ facts

######  Example 2.7.

The _tropical semiring_ is $(\mathbb{R}^{+}\cup\\{\infty\\},\min,+,\infty,0)$.
We show in Figure 1 an example Datalog program (right) with tropical semiring
annotations on extensional facts, as well as the (only) two derivation trees
of the fact path(Paris, London) along their weight. This witnesses that the
provenance of path(Paris, London) is $\min(1,3)=1$.

Since some tuples can have infinitely many derivations, the Datalog semantics
given above cannot be used as an algorithm. As pointed out in
[green_provenance_2007] it is possible instead to use a fixpoint-theoretic
definition of the provenance of a Datalog query $q$: introduce a fresh
variable for every possible _intensional_ tuple (i.e., every possible _ground
atom_), and produce for this variable an equation that reflects the _immediate
consequence operator_ $T_{q}$ – _extensional_ facts appearing as their
semiring annotations in these equations. This yields a system of fixpoint
equation $f_{q}$. The provenance of $G(t)$ for $q$ is now simply the value of
the variable corresponding to $G(t)$ in $\mathsf{gfp}(f_{q})$.

The fixpoint-theoretic definition directly yields an algorithm, albeit a very
inefficient one because of the need of generating a rule for every intensional
tuple. In this paper, we investigate more efficient algorithms, for specific
types of semirings.

##  3 Datalog provenance and dynamic programming over hypergraphs

We now show how to convert a Datalog program into a weighted hypergraph (as
introduced in [huang_advanced_2008]) and characterize the semirings where the
best-weight derivation in the hypergraph corresponds to the provenance for the
initial Datalog program, mimicking the proof-theoretic definition. We first
recall basic definitions and notation related to hypergraphs.

######  Definition 3.8 (Weighted hypergraph [huang_advanced_2008]).

Given a semiring $S$, a _weighted hypergraph_ on $S$ is a pair $H=\langle
V,E\rangle$, where $V$ is a finite set of vertices and $E$ is a finite set of
hyperedges, where each element $e\in E$ is a triple $e=\langle
h(e),\mathrm{T}(e),f_{e}\rangle$ with $h(e)\in V$ its _head_ vertex,
$\mathrm{T}(e)\in V$ an ordered list of _tail_ vertices and $f_{e}$ a _weight
function_ from $S^{|\mathrm{T}(e)|}$ to $S$.

We note $|e|=|\mathrm{T}(e)|$ the arity of a hyperedge. If $|e|=0$, we say $e$
is nullary and then $f_{e}()$ is a constant, an element of the semiring; we
assume there exists at most one nullary edge for a given vertex. In that case,
$v=h(e)$ is called a _source vertex_ and we note $f_{e}()$ as $f_{v}$. The
arity of a hypergraph is the maximum arity of any hyperedge.

The backward-star $\mathrm{BS}(v)$ of a vertex $v$ is the set of incoming
hyperedges $\\{e\in E\mid h(e)=v\\}$. The _graph projection_ of a hypergraph
$H=\langle V,E\rangle$ is a directed graph $G=(V,E^{\prime})$ where
$E^{\prime}=\\{(u,v)\mid\exists e\in\mathrm{BS}(v),u\in\mathrm{T}(e)\\}$. A
hypergraph $H$ is acyclic if its graph projection $G$ is acyclic; then a
topological ordering of $H$ is an ordering of $V$ that is a topological
ordering of $G$.

With these definitions in place, we can encode a Datalog program with semiring
annotations as a weighted hypergraph in a straightforward manner:

######  Definition 3.9 (Hypergraph representation of a Datalog program).

Given a Datalog program $q$ as a set of rules $\\{q_{1},\cdots,q_{n}\\}$ and
the semiring $S$ used for annotations, we define the _weighted hypergraph
representation of $q$_ as $H_{q}=\langle V_{q},E_{q}\rangle$ with $V_{q}$
being all ground atoms and, for each instantiation of a rule
$t(\vec{x})\leftarrow r_{1}(\vec{x_{1}}),\dots,r_{n}(\vec{x_{n}})$, a
corresponding edge $\langle
t(\vec{x}),(r_{1}(\vec{x_{1}}),\dots,r_{n}(\vec{x_{n}})),\otimes\rangle$. For
a fact $R(\vec{x})\in\mathsf{EDB}(q)$ we add a nullary edge $e$ with
$h(e)=R(\vec{x})$ and $f_{e}=\mathsf{prov}_{R}^{q}(\vec{x})$.

The notion of derivations is the hypergraph counterpart to paths in graph. We
recall the definition of derivations and we define it in a way that is
reminiscent of Datalog-related notions.

######  Definition 3.10 (Derivation in hypergraph [huang_advanced_2008]).

We recursively define a _derivation_ $D$ of a vertex $v$ in a hypergraph $H$
(as a pair formed of a hyperedge and a list of derivations), its size $|D|$ (a
natural integer) and its weight $w(D)$ (a semiring element) as follows:

  * •

If $e\in\mathrm{BS}(v)$ with $|e|=0$, then $D=\langle e,\langle\rangle\rangle$
is a derivation of $v$, $|D|=1$, and $w(D)=f_{e}()$.

  * •

If $e\in\mathrm{BS}(v)$ with $|e|\geqslant 0$, $D_{i}$ is a derivation of
$T_{i}(e)$ for $i=1\dots|e|$, then $D=\langle e,\langle D_{1}\cdots
D_{|e|}\rangle\rangle$ is a derivation of $v$,
$|D|=1+\sum_{i=1}^{|e|}|D_{i}|$, $w(D)=f_{e}(w(D_{1}),\dots,w(D_{|e|}))$.

We note $\mathcal{D}_{H}(v)$ the set of derivations of $v$ in $H$.

When modeling Datalog provenance in a semiring $S$ as weighted hypergraphs on
$S$, all non-source weight functions are bound to the $\otimes$ operation of
the semiring. Note that, if $S$ is idempotent, the natural order on $S$
induces an ordering on derivations: $D\leqslant D^{\prime}$ if $w(D)\leqslant
w(D^{\prime})$.

We now show that in this formalism, the Datalog provenance of an output
predicate can be understood as the best-weight for the corresponding vertex in
the hypergraph.

######  Definition 3.11 (Best-weight [huang_advanced_2008]).

The _best-weight_ $\delta_{H}(v)$ of a vertex $v$ of a hypergraph $H$ on a
semiring $(S,\oplus,\otimes,\bar{0},\bar{1})$ is the weight of the best
derivation of $v$:

$\delta_{H}(v)=\left\\{\begin{array}[]{ll}f_{v}&\mbox{if v is a source
vertex;}\\\
\bigoplus_{D\in\mathcal{D}_{H}(v)}w(D)&\mbox{otherwise.}\end{array}\right.$

The best-weight generally requires additional properties of either the
hypergraph or the semiring to be well-defined. Acyclicity for the hypergraph
is a sufficient condition. Existence of an infinitary summation operator in
the semiring extending $\oplus$, guaranteed in $\omega$-continuous semirings,
is also a sufficient condition. To guarantee semantics compatible with the
intuitive meaning of provenance, a more restrictive sufficient condition is
for the semiring to be a $c$-complete star-semiring [krob_monoides_1987], see
[ramusat:hal-03140067] for details.

We can now show that Datalog provenance can be computed through the formalism
of weighted hypergraphs. Let us start with a lemma exhibiting a one-to-one
mapping between derivations in the hypergraph and proofs in Datalog.

######  Lemma 3.12.

lemma:mult For any Datalog query $q$ and grounding of an atom $v$ of $q$,
there is a bijection between $\mathcal{D}_{H{q}}(v)$ and
$\\{\tau\mid\tau\mbox{ yields }v\\}$.

######  Proof 3.13.

By definition of $H_{q}$ each instantiation of a rule corresponds to a unique
hyperedge. Then, we can inductively construct for a given derivation $D$ its
associated (unique) Datalog proof tree $\tau_{D}$:

  * •

If $|D|=1$, then $v$ is a source vertex and thus an extensional tuple, we get
the empty proof.

  * •

If $|D|\geqslant 1$, then there exists $e\in\mathrm{BS}(v)$ where
$|e|\geqslant 0$ and $D_{i}$ a derivation of $T_{i}(e)$ for $1\leqslant
i\leqslant|e|$, where $D=\langle e,D_{1}\cdots D_{|e|}\rangle$. By definition,
this hyperedge corresponds to the grounding of a rule $t(\vec{x})\leftarrow
r_{1}(\vec{x_{1}}),\dots,r_{n}(\vec{x_{n}})$. By induction, for $1\leqslant
i\leqslant|e|$, $\tau_{D_{i}}$ is the corresponding proof of the derivation
$D_{i}$. Then by composition we obtain $\tau_{D}$ the proof for $D$.

We then show that the weight of each derivation of a tuple is equal to the
corresponding proof tree weight in Datalog.

######  Lemma 3.14.

lemma:sum For any Datalog query $q$ and grounding of an atom $v$ of $q$, for
any derivation $D$ of $v$ in $H_{q}$
$w(D)=\bigotimes\limits_{t^{\prime}\in\>leaves(\tau_{D})}\mathsf{prov}_{R}^{q}(t^{\prime})$
where $\tau_{D}$ is the proof tree corresponding to $D$ in the bijection given
by Lemma LABEL:lemma:mult.

######  Proof 3.15.

By induction on the size of the derivation $D$:

  * •

If $|D|=1$ then, there exists a nullary edge $e\in E_{q}$ with $h(e)=v$ and
$w(D)=f_{v}=\mathsf{prov}_{R}^{q}(r(\vec{x}))=\prod\limits_{t^{\prime}\in\>leaves(\tau_{D})}\mathsf{prov}_{R}^{q}(t^{\prime})$.

  * •

If $|D|\geqslant 1$ then there exists $e\in E_{q}$ and $D$ is of the form
$\langle e,D_{1}\cdots D_{|e|}\rangle$ with $D_{i}$ a derivation of $T_{i}(e)$
for $1\leqslant i\leqslant|e|$. We have
$w(D)=f_{e}(w(D_{1}),\dots,w(D_{|e|}))$ and by definition of $f_{e}=\otimes$
and by IHP
$w(D)=\bigotimes\limits_{t^{\prime}\in\>leaves(\tau_{D})}\mathsf{prov}_{R}^{q}(t^{\prime})$.

Finally, we obtain:

######  Theorem 3.16.

th:eq Let $t$ be a tuple of a Datalog program $q$ with output predicate $G$
and $H_{q}$ its hypergraph representation, then
$\mathsf{prov}_{G}^{q}(t)=\delta_{H_{q}}(G(t))$.

######  Proof 3.17.

$\begin{array}[]{cclcl}\delta_{H_{q}}(t)&=&\bigoplus\limits_{D\in\mathcal{D}_{H_{q}}(G(t))}w(D)&&\mbox{and
by Lemma\leavevmode\nobreak\ \ref{lemma:sum},}\\\
&=&\bigoplus\limits_{D\in\mathcal{D}_{H_{q}}(G(t))}\left(\bigotimes\limits_{t^{\prime}\in\>leaves(\tau_{D})}\mathsf{prov}_{R}^{q}(t^{\prime})\right)&&\mbox{and
by Lemma\leavevmode\nobreak\ \ref{lemma:mult},}\\\
&=&\bigoplus\limits_{\tau\>\mathit{yields}\>t}\left(\bigotimes\limits_{t^{\prime}\in\>leaves(\tau)}\mathsf{prov}_{R}^{q}(t^{\prime})\right)&=&\mathsf{prov}_{T}^{q}(t)\end{array}$

##  4 Best-first method

Knuth [knuth_generalization_1977] generalized the Dijkstra algorithm to what
he calls the _grammar problem_ (i.e., finding the best-weight derivation from
a given non-terminal, where each terminal has a specific weight and each rule
comes with an associated weight function). This has been identified as
corresponding to the search problem in a monotonic superior hypergraph – for
each $e\in H$, $f_{e}$ is monotone and superior in each argument (see Table 3
in [huang_advanced_2008]). We showed in Lemma LABEL:lem:superiority that
superiority corresponds to $0$-closedness in semirings with natural orders.
The definition of the grammar problem assumes a total order on weights as the
weights are real numbers. In the special case where all hyperedges are of
arity 1 (and all weight functions bound to $\otimes$), we obtain the classical
notion of semiring-based provenance for graph databases
[ramusat:hal-01850510]. Thus, Knuth’s algorithm can be seen as a
generalization to hypergraphs (and therefore, by the results of the previous
section, to Datalog provenance computation) of the modified Dijkstra algorithm
we presented in [ramusat:hal-01850510], working on _$0$ -closed totally-
ordered semirings_, which are generalizations of the tropical semiring.

### Optimized version of Best-first method

In the original paper of Knuth [knuth_generalization_1977], the question of
efficient construction of the set of candidate facts for the extraction of the
minimal-valued fact is not dealt with. A lot of redundant work may be carried
out if the implementation is not carefully designed.

In the following, we show how to obtain a ready-to-be-implemented version
incorporating ideas from the semi-naïve evaluation of Datalog programs. Semi-
naïve evaluation of Datalog, as described in [DBLP:books/aw/AbiteboulHV95,
Chapter 13] introduces a number of ideas aiming at improving the efficiency of
the naïve Datalog evaluation method; we show how to leverage these tricks in
our setting.

The naïve evaluation of a Datalog program $q$ processes iteratively, applying
at each step the consequence operator $\mathrm{T}_{q}$. Many redundant
derivations are computed, leading to practical inefficiency. The _semi-naïve_
evaluation addresses this problem by considering only facts derived using at
least one new fact found at the previous step. Note, however, whereas many new
facts can be found at one step of the semi-naïve evaluation, only one is to be
added by the Best-first method to respect the $\leqslant$-minimality ordering
of added facts.

Algorithm 1 Basic semi-naïve version of Best-first method for Datalog
provenance

1:Datalog query $q$, $\mathsf{EDB}$ $D$ with provenance indications over a
$0$-closed totally-ordered semiring $S$.

2:full Datalog provenance for the $\mathsf{IDB}$ of $q$.

3:function Relax($r_{0}(\vec{x_{0}})$, $S$)

4: for each instantiation of a rule $r(\vec{x})\leavevmode\nobreak\
\leftarrow\leavevmode\nobreak\
r_{1}(\vec{x_{1}}),\dots,r_{m}(\vec{x_{m}}),\cdots,r_{n}(\vec{x_{n}})$ where
$r_{i}(\vec{x_{i}})\in D\cup S\cup\\{r_{0}(\vec{x_{0}})\\}$, $1\leqslant i<m$,
$r_{m}(\vec{x_{m}})=r_{0}(\vec{x_{0}})$ and $r_{i}(\vec{x_{i}})\in D\cup S$,
$m<i\leqslant n$ do

5: $\nu(r(\vec{x}))\quad\oplus\\!\\!=\bigotimes\limits_{1\leqslant i\leqslant
n}r_{i}(\vec{x_{i}})$

6:

7:$I\leftarrow\emptyset$

8:Let $\nu$ be the function that maps all facts of $D$ to their annotation in
$S$ and all potential facts of the intensional schema of $q$ to $\bar{0}$

9:for each intensional atom $r(\vec{x})\,\notin\\!I$ do

10: $\nu(r(\vec{x}))\quad\oplus\\!\\!=\bigotimes\limits_{1\leqslant i\leqslant
n}r_{i}(\vec{x_{i}})$ for each instantiation of a rule
$r(\vec{x})\leavevmode\nobreak\ \leftarrow\leavevmode\nobreak\
r_{1}(\vec{x_{1}}),\dots,r_{n}(\vec{x_{n}})$ with $r_{i}(\vec{x_{i}})\in D$

11:while $\mbox{min}_{\nu\setminus I}\>r(\vec{x})\neq\bar{0}$ do

12: Add such minimal $r(\vec{x})$ to $I$

13: Relax($r(\vec{x})$, $I\setminus r(\vec{x})$)

14:return $\nu$

This algorithm starts by initializing the priority queue with $\mathsf{IDB}$
facts that are derivable from $\mathsf{EDB}$ facts. Then, at each step, the
minimum valued-fact is added, and only derivations using this new fact are
computed to update the value of the facts in $I$. This algorithm stops
whether: 1. the maximal value is reached for a candidate fact, 2. the list is
empty - the minimal value of the list is by default the maximal value of the
semiring.

######  Theorem 4.18.

Algorithm 1 computes the full Datalog provenance for $0$-closed totally-
ordered semirings.

######  Proof 4.19.

We show the algorithm verifies the following invariant: whenever a tuple is
added to $I$ in Line 12, it has optimal value. This implies that $I$ is
populated in increasing order: each new derivation computed in the
$\textsc{Relax}($) procedure only updates the priority queues with values
greater than the value of the tuple relaxed (by superiority of $\otimes$).

Suppose by contradiction that some output tuples are not correctly labeled and
take such a minimal tuple $\nu=r(\vec{x})$. At the moment where $\nu$ is
extracted with value $n$ let us consider an optimal derivation path of $\nu$
that leads to the optimum value $opt<n$. By superiority each tuple occurring
in the tail of the rule has value less than $opt$. Thus a tuple occurring in
the tail is either wrong-valued or not present in $I$ at the moment where
$\nu$ is found. In both cases and because tuples are added to $I$ in
increasing order we obtain a new minimal tuple incorrectly labeled by the
algorithm, contradicting the hypothesis.

The structure of the Datalog program can be analysed to provide clues about
the predicates to focus on. Following [DBLP:books/aw/AbiteboulHV95], we
introduce the notion of precedence graph $G_{P}$ of a Datalog program $P$. The
nodes are the $\mathsf{IDB}$ predicates and the edges are pairs of
$\mathsf{IDB}$ predicates $(R,R^{\prime})$ where $R^{\prime}$ occurs at the
head of a rule of $P$ with $R$ belonging to the tail. $P$ is a recursive
program if $G_{P}$ has a directed cycle. Two predicates $R$ and $R^{\prime}$
are mutually recursive if $R=R^{\prime}$ or $R$ and $R^{\prime}$ participate
in the same cycle of $G_{P}$. This defines equivalence classes. Putting it
together, we obtain as Algorithm 2 out final algorithm.

Algorithm 2 Semi-naïve version of Best-first method for Datalog provenance

1:$q$ a Datalog query with provenance indication over a $0$-closed totally-
ordered semiring $S$.

2:full Datalog provenance for the $\mathsf{IDB}$ of $q$.

3:Compute the equivalence classes of $q$

4:for each equivalence class in a topological order do

5: Apply Algorithm 1 over $\mathsf{IDB}$ predicates in the equivalence class

6: considering previous equivalence classes as $\mathsf{EDB}$ predicates

7:return $\nu$

### Generalization to distributive lattices

In [ramusat:hal-03140067], we outlined a new algorithm, based on the Dijkstra
algorithm and solving the single-source provenance in graph databases with
provenance indications over $0$-closed multiplicatively idempotent semirings
(equivalents to distributive lattices). This new method stems from a tentative
to bridge the strong complexity gap for computing the provenance in the case
of a semiring not $0$-closed and totally ordered. A similar gap also appears
when we consider provenance over Datalog queries (see Section 7). Thus, we
show how to apply this method for computing provenance for Datalog queries
over distributive lattices.

We provide a brief review of the key ideas presented in
[ramusat:hal-03140067]. Any element of a distributive lattice is decomposable
into a product of join-irreducible elements of the lattice, and there exists
an embedding of the distributive lattice into a chain decomposition of its
join-irreducible elements. This ensures we can 1) work on a totally ordered
environment and apply algorithms that require total ordering over the
elements, 2) independently compute partial provenance annotations for each
dimension to form the final provenance annotation. Given $m$ the number of
dimensions in the decomposition, our solution (described in Algorithm 3)
performs $m$ launches of the Best-first method and thus, roughly has a cost
increased by a factor $m$.

Algorithm 3 Generalized Best-first method for Datalog provenance

1:$q$ a Datalog query with provenance indication over a $0$-closed
multiplicatively idempotent semiring $S$.

2:full Datalog provenance for the $\mathsf{IDB}$ of $q$.

3:for each $\mathsf{EDB}$ fact $R(\vec{x})$ do

4: Decompose($R(\vec{x})$)

5:for each dimension $i$ do

6: $\nu_{i}\leftarrow\textsc{Best-first}(q,i)$

7:return Recompose($\nu_{1},\ldots,\nu_{n})$

Algorithm 4 Input Datalog program computing the transitive closure (Soufflé
syntax)

1:.decl edge(s:number, t:number[, @prov:semiring value])

2:.input edge

3:.decl path(s:number, t:number[, @prov:semiring value])

4:.output path

5:path(x, y) :- edge(x, y).

6:path(x, y) :- path(x, z), edge(z, y).

Algorithm 5 Corresponding Soufflé RAM program for Algorithm 4

1:if $\neg($edge $=\emptyset)$ then

2: for t0 in edge do

3: add (t0.0, t0.1) in path

4: add (t0.0, t0.1) in $\delta$path

5:loop

6: if $\neg(\delta$path = $\emptyset)\wedge\neg($edge $=\emptyset)$ then

7: for t0 in $\delta$path do

8: for t1 in edge on index t1.0 = t0.1 do

9: if $\neg($t0.0, t0.1) $\in$ path then

10: add (t0.0, t0.1) in path’

11: if path’ = $\emptyset$ then

12: exit

13: for t0 in path’ do

14: add (t0.0, t0.1) in path

15: swap $\delta$path with path’

16: clear path

Algorithm 6 Modification of RAM program of Algorithm 5 to implement Best-first
strategy

1:if $\neg($edge $=\emptyset)$ then

2: for t0 in edge do

3: update (t0.0, t0.1, t0.prov) in path

4: for t0 in path do

5: add (t0.0, t0.1, t0.prov) in $\delta$path

6:loop

7: if $\neg(\delta$path = $\emptyset)\wedge\neg($edge $=\emptyset)$ then

8: for t0 in $\delta$path do

9: for t1 in edge on index t1.0 = t0.1 do

10: if $\neg($t0.0, t1.1, $\bot$) $\in$ path then

11: update (t0.0, t0.1, t0.prov $\otimes$ t1.prov) in pq

12: clear $\delta$path

13: if pq is empty then

14: exit

15: add pq.top() in pq.top().relation and in pq.top().$\delta$relation

##  5 Implementation and experiments

In numerous application domains, Datalog is used as a _domain specific
language_ (DSL) to express logical specifications for static program analysis.
A formal specification, written as a declarative Datalog program is usually
translated into an efficient imperative implementation by a synthesizer. This
process simplifies the development of program analysis compared to hand-
crafted solutions (highly optimized C++ applications specialized in enforcing
a fixed set of specifications). Soufflé [10.1007/978-3-319-41540-6_23,
10.1145/2892208.2892226] has been introduced to provide efficient synthesis of
Datalog specifications to executable C++ programs, competing with state-of-
the-art handcrafted code for program analysis. The inner workings of Soufflé
were of interest to our work; the algorithm implementations are similar to the
evaluation strategy followed by the Best-first method we introduced here. We
present a brief overview of the architecture of Soufflé and discuss how we
extended it.

### Architecture and implementation

Following what is described in [10.1007/978-3-319-41540-6_23], an input
datalog program $q$ goes through a staged specialization hierarchy. After
parsing, the first stage of Soufflé specializes the semi-naïve evaluation
strategy applied to $q$, yielding a relational algebra machine program (RAM).
Such a program consists in basic relational algebra operations enriched with
I/O operators and fix-point computations. As a final step, the RAM program is
finally either interpreted or compiled into an executable. For this work, we
have only used the interpreter. Our code was inserted in two different stages
of Soufflé: a new translation strategy from the parsed program to the RAM
program, a priority queue, replacing the code in charge of adding at run-time
the tuples to the relations.

We showcase the result of our translation strategy in Algorithms 4, 5, and 6
for a Datalog query computing the transitive closure of a graph; this program
is given in Algorithm 4 in its Soufflé syntax. Algorithm 5 presents the
corresponding Soufflé RAM program resulting from applying the semi-naïve
evaluation strategy and Algorithm 6 our modification to the RAM program to
provide provenance annotation via the Best-first strategy and use the priority
queue pq for provenance computation. The $\bot$ notation corresponds to a
wildcard. Importantly, modifying directly at the RAM level of Soufflé allows
us to benefit of all implemented optimizations.

Rome99USPowerGridYeastStif$0.1$$1$$10$$100$$1\,000$$10\,000$$100\,000$time
(s)SouffléNodeElimination-IdNodeElimination-DegreeSoufflé-prov

Figure 2: Comparison between algorithms for all-pairs shortest-distances
(Tropical). Values greater than 100 000 s are timeouts.

Rome99USPowerGridYeastStif$0.001$$0.01$$0.1$$1$time
(s)BFSSouffléDijkstraMohriSoufflé-prov

Figure 3: Comparison between algorithms for single-source shortest-distances
(Tropical).

0.0 M0.5 M1.0 M1.5 M2.0 M2.5 M3.0 M$0$$1$$2$$3$$4$Output DB sizetime
(s)Soufflé-provSoufflé

ra(v, w, x, y, z) :- p(v), p(w), p(x), p(y), p(z). rb(v, w, x, y, z) :- p(v),
p(w), p(x), p(y), p(z). q(v) :- r(v, w, x, y, z). r(v, w, x, y, z) :- ra(v, w,
x, y, z), rb(v, w, x, y, z). q(z) :- r(v, w, x, y, z).

Figure 4: Comparison between Soufflé and Soufflé-prov (IRIS)

0 K5 K10 K15 K20 K25 K30 K$10^{-2}$$10^{-1}$$10^{0}$$10^{1}$Output DB sizetime
(s)Soufflé-provSoufflé

hc(x,y) :- hasChild(x, y). imt(x,y) :- isMarriedTo(x, y). hc(x,y) :- imt(z,x),
imt(z, y). hc(x,y) :- imt(x,z), imt(z, y). imt(x, y) :- imt(y, x). imt(x, y)
:- hc(x, z), hc(y, z).

Figure 5: Comparison between Soufflé and Soufflé-prov (AMIE)

### Experiments

Our implementation was tested on an Intel Xeon E5-2650 computer with 176 GB of
RAM. The source code is freely available on
Github222https://github.com/yannramusat/souffle-prov.

The initial motivation for this work stems from a key observation we outlined
in the conclusion of [ramusat:hal-03140067], where we pointed out the
similarity between Datalog and the classes of semirings and their optimized
provenance algorithms discussed in that work, focused on graph provenance
algorithms. To translate this graph setting into Datalog, the graph structure
has been encoded into an $\mathsf{EDB}$ with one binary predicate _edge_
encoding the edges, and with edge notations depending on the provenance
semiring we chose. We run the _transitive closure_ Datalog program outlined in
Algorithm 4. Full information on the graph datasets used can be found in
[ramusat:hal-03140067]. We provide, in Figure 5, a comparison between the
best-first method introduced here (Soufflé-prov), the plain Soufflé without
provenance computation, and a previous provenance-based algorithm
[ramusat:hal-03140067] computing all-pairs shortest-distances over graph
databases (the NodeElimination algorithm, with a choice of node to eliminate
based on its id or its degree), in the tropical semiring. Similarly, in Figure
5, we compare with previous solutions for single-source shortest-distances, in
the same semiring, in particular the adaptation of Dijkstra algorithm of
[ramusat:hal-03140067], and, for comparison purposes, a Bfs algorithm that
does not compute provenance. The main focus of this work was to provide an
effective Datalog based solution for all-pairs provenance in graph databases.
For the all-pairs problem, depending on the dataset, (see, e.g., Yeast),
Soufflé-Prov is significantly faster than the previous best known algorithm,
NodeElimination. Unsurprisingly, BFS and Dijkstra perform respectively better
than Soufflé and Soufflé-prov in the single-source context. What favors both
graph algorithms strongly is the fact that they reduce redundant computation:
the algorithms abort whenever the target vertex has been reached. Soufflé-prov
performs between $1$ and $2$ orders of magnitude faster than Mohri
[Mohri:2002:SFA:639508.639512] – an algorithm designed for single-source
provenance on $k$-closed semirings. This fact highlights the potential of
adapting the best-first method to also handle $k$-closed semirings.

We now turn to evaluating the overhead induced by adding provenance
computations to Datalog via Soufflé. This appears fairly modest in the
experiments of Figures 5, 5. We further consider two datasets that go beyond
the setting of graph databases: a non-recursive query over synthetic data
(IRIS [7113407], obtained from the authors of that paper) in Figure 5 and a
program over a knowledge base (AMIE [amie], available
online333https://bitbucket.org/amirgilad/selp/src/Journal/) populated with
real-world data and automatic rules in Figure 5. The evaluation was made by
varying the output database size. In IRIS, the overhead induced is a modest
constant factor of approximately $4$ times the original cost. This is not the
case for AMIE, where the overhead tends to increase with the size of the
answer. We conjecture this is due to the lack of native support for tuple
updates in Soufflé (in Datalog, the fixed-point operator is inflationary);
this leads to inefficiency in updating provenance values associated to each
tuple.

##  6 Reverse translations and opportunities

Our focus so far in this study was to express Datalog programs into
hypergraphs. We now consider the opposite direction: given a weighted
hypergraph $H$ with all its weight functions derived from a semiring $S$ via
its $\otimes$ operator we aim to design an equivalent Datalog program which
computes the provenance on the given semiring. We propose two translations – a
straightforward one and one with a fixed program, to benefit of the low data
complexity of Datalog.

######  Definition 6.20 (Weighted hypergraph to Datalog program).

Given an hypergraph $H=\langle V,E\rangle$ of maximal hyperedge arity $n$, we
define a Datalog query $q_{H}$ with extensional predicates $E_{n}$ of arity
$n+1$ for $0\leqslant i\leqslant n$ and an unary intensional predicate $R$.
For each $1\leqslant i\leqslant n$, we add a single rule of the form:
$R(x)\leftarrow E_{i+1}(x,x_{1},\dots,x_{n}),R(x_{1}),\dots,R(x_{n})$,
degenerating into $R(x)\leftarrow E_{1}(x)$ for $i=0$. For each $e\in E$ of
arity $n\geqslant 1$, we populate $E_{n+1}$ with
$E_{n+1}(h(e),{\mathrm{T}(e)})$ having provenance value $\bar{1}$. Source
vertices (i.e., heads of nullary edges) may have an initial constant value
$s\in S$. For each $e\in E$ of arity $0$ we tag $E_{1}(h(e))$ with the
provenance value $f_{e}$.

We then have:

######  Theorem 6.21.

th:eq_rev Let $v$ be a vertex of a weighted hypergraph $H$ with all weight
functions derived from the $\otimes$ operation of a semiring $S$ and $q_{H}$
its translation into a Datalog query, then
$\delta_{H}(v)=\mathsf{prov}_{R}^{q_{H}}(v)$.

######  Proof 6.22 (Proof of Theorem LABEL:th:eq_rev).

$\begin{array}[]{cclcl}\delta_{H}(t)&=&\bigoplus\limits_{D\in\mathcal{D}_{H}(v)}w(D)&&\mbox{and
by Lemma\leavevmode\nobreak\ \ref{lemma:sum_rev},}\\\
&=&\bigoplus\limits_{D\in\mathcal{D}_{H}(v)}\left(\bigotimes\limits_{t^{\prime}\in\>leaves(\tau_{D})}\mathsf{prov}_{E_{1},\dots,E_{n+1}}^{q_{H}}(t^{\prime})\right)&&\mbox{and
by Lemma\leavevmode\nobreak\ \ref{lemma:mult_rev},}\\\
&=&\bigoplus\limits_{\tau\>\mathit{yields}\>t}\left(\bigotimes\limits_{t^{\prime}\in\>leaves(\tau)}\mathsf{prov}_{E_{1},\dots,E_{n+1}}^{q_{H}}(t^{\prime})\right)&=&\mathsf{prov}_{R}^{q_{H}}(t)\end{array}$

Let us know consider the case of programs where we have a fixed schema and
arity:

######  Definition 6.23 (Weighted hypergraph to Datalog program with fixed
schema).

Given an hypergraph $H=\langle V,E\rangle$ let us consider the following
Datalog program $q_{H_{f}}$ over unary predicates $R$ and $\mathit{Nullary}$,
binary predicates $E$, $N$ and $\mathit{First}$ and ternary predicate
$\mathit{Next}$:

$\displaystyle R(x)$ $\displaystyle\leftarrow E(x,e),H(e)$ $\displaystyle
H(e)$ $\displaystyle\leftarrow\mathit{First}(e,x),R(x),N(e,x)$ $\displaystyle
N(e,x)$ $\displaystyle\leftarrow\mathit{Next}(e,x,y),R(y),N(e,y)$
$\displaystyle\leftarrow\mathit{Nullary}(e)$
$\displaystyle\leftarrow\mathit{End}(e,x)$

For each $e\in E$ of arity $n\geqslant 1$, we populate $E$ with $E(h(e),e)$
with provenance value $\bar{1}$. Let $x_{1},\dots,x_{n}$ be the elements of
${\mathrm{T}(e)})$, we populate First with $\textit{First}(e,x_{1})$,
$\mathit{Next}$ with $\mathit{Next}(e,x_{i},y_{i+1})$ for $1\leqslant
i\leqslant n-1$ and $End$ with $\mathit{End}(e,x_{n})$; all have provenance
value $\bar{1}$.

Source vertices (heads of nullary edges) may have an initial constant value
$s\in S$, then for each $e\in E$ of arity $0$ we tag $E(h(e),e)$ with the
provenance value $f_{e}$ and $\mathit{Nullary}(e)$ with provenance value
$\bar{1}$.

The reasoning follows a similar flow:

######  Theorem 6.24.

th:eq_fixed_rev Let $v$ be a vertex of a weighted hypergraph $H$ with all
weight functions derived from the $\otimes$ operation of a semiring $S$ and
$q_{H_{f}}$ its translation into a Datalog query with fixed schema, then
$\delta_{H_{f}}(v)=\mathsf{prov}_{R}^{q_{H_{f}}}(v)$.

######  Proof 6.25 (Proof of Theorem LABEL:th:eq_fixed_rev).

We note
$\text{EDB}=\\{E,\mathit{Nullary},\mathit{First},\mathit{Next},\mathit{End}\\}$.

$\begin{array}[]{cclcl}\delta_{H_{f}}(t)&=&\bigoplus\limits_{D\in\mathcal{D}_{H_{f}}(v)}w(D)&&\mbox{and
by Lemma\leavevmode\nobreak\ \ref{lemma:sum_fixed_rev},}\\\
&=&\bigoplus\limits_{D\in\mathcal{D}_{H_{f}}(v)}\left(\bigotimes\limits_{t^{\prime}\in\>\mathit{leaves}(\tau_{D})}\mathsf{prov}_{\text{EDB}}^{q_{H_{f}}}(t^{\prime})\right)&&\mbox{and
by Lemma\leavevmode\nobreak\ \ref{lemma:mult_fixed_rev},}\\\
&=&\bigoplus\limits_{\tau\>\mathit{yields}\>t}\left(\bigotimes\limits_{t^{\prime}\in\>\mathit{leaves}(\tau)}\mathsf{prov}_{\text{EDB}}^{q_{H_{f}}}(t^{\prime})\right)&=&\mathsf{prov}_{R}^{q_{H_{f}}}(t)\end{array}$

### Case study: AND/OR graphs

Section 4.3 of [huang_advanced_2008] showcases some formalisms in which
equivalent hypergraphs can be constructed in the dynamic programming framework
proposed in their work. One advantage is that we can directly benefit from
these translations in our Datalog provenance framework. However, there are
some issues with these translations, as we now discuss.

One example formalism that can be easily translated to our setting are the
AND/OR graphs, a special case of graphs – e.g., used in scheduling tasks – in
which nodes can express two types of restrictions: AND restrictions (in which
tasks have to executed sequentially) and OR restrictions (in which tasks can
be overlapping). These two operations, not unlike the $\otimes$ and $\oplus$
operations on semirings, suggest our translation strategy is readily usable.
Indeed, by our translation, vertices of the hypergraph would represent OR
vertices and the hyperedges correspond to the AND vertices. This translation
does not add any other restriction to the shape of the AND/OR graph. AND and
OR vertices can have multiples outgoing edges and the AND/OR graph is not
necessarily bipartite. However, not all applications in which AND/OR graphs
are useful can be used with semiring operations. For instance, scheduling
using AND/OR graphs [fast-pathfinding-and-or, scheduling-and-or-prec-
constraints] requires three operations (min, max and $+$) instead of the two
allowed using semirings.

Another crucial issue, not obvious at first glance, is that when expressing
these graphs into our Datalog framework the semantics can change. As explained
in [scheduling-and-or-prec-constraints], zero-edge cycles express mutual
events (occurring in groups, with no causal relations): either they all occur
together or none of them do. In a deductive system, where semantics is given
by a least fixed-point, they are believed to not occur at all. The semantics
of Datalog provenance or derivation trees cannot express this situation: in
Datalog there would be no finite proof of a set of given facts. However,
adding all of these facts to the solution would not break the deductive rules;
simply they do not belong to the least fixed-point.

##  7 Related work

There are two major notions of provenance for information systems currently in
use in the literature, each focusing on different usages. The first notion can
be broadly categorized as “informational”: the provenance encapsulates
information about the deductive process leading to a specific result.
Declarative debugging is one application of this concept. Analysis of
provenance information in an interactive manner simplifies the user’s burden
of identifying which part of the rule specification is responsible for a
faulty derivation. Soufflé contains its own integrated debugging system, based
on a provenance-based evaluation strategy [10.1145/3379446].

In the current study we consider a “computational” notion of provenance, where
operations (and queries) over provenance values are permitted. In this case,
the underlying properties of the semiring are important for optimized
algorithms. For instance, absorptivity is an ubiquitous property in the
literature allowing efficient algorithms for provenance evaluation. This
applies not only for Datalog programs, but also for e.g., regular path queries
over (semiring)-annotated graph databases [ramusat:hal-03140067].

With respect to Datalog provenance, it has been shown in
[deutch_circuits_2014] that, for a Datalog program having $n$ candidate
$\mathsf{IDB}$ tuples, a circuit for representing Datalog provenance in the
semiring $\textbf{Sorp}(X)$ (the most general absorptive semiring) only needs
$n+1$ layers. For binary relations, e.g., representing the edge relation of a
graph, this construction is at least quadratic in the number of vertices, thus
not practically applicable for the graphs we analyzed in our experiments.
Similarly, in [esparza_solving_2011], absorptive semirings (i.e., $0$-closed
semirings) have the property that derivation trees of size $\geqslant n$ are
“pumpable” (they do not contribute to the final result). A concrete
implementation [10.1007/978-3-319-08846-4_1] computes the provenance for
commutative and idempotent semirings using $n$ Newton iterations.

Fairly recently, [DBLP:journals/corr/abs-2105-14435] introduced POPS
(Partially Ordered, Pre-Semiring), a structure decoupling the order on which
the fixed-point is computed from the semiring structure. Complex and recursive
computations over vectors, matrices, tensors are now expressible using this
framework. The study also generalized the semi-naïve method from plain Datalog
evaluation to idempotent semirings (aka dioids). In comparison, our method is
restricted to semirings that are totally ordered (a subclass of distributive
dioids444Distributive dioids are POPS structures over a distributive lattice
being the natural order of the dioid.), leveraging the invariant that once a
fact is first labeled with a provenance value, we are certain it is the
correct one.

In cases where keeping the full provenance of a program (_how_ -provenance) is
still prohibitively large, [Deutch2018EfficientPT, 7113407] propose to select
only a relevant subset of such trees using selection criteria based on tree
patterns and ranking over rules and facts occurring in the derivation. First,
given a Datalog program $P$ and a pattern $q$, an offline instrumentation is
performed, leading to an instrumented program $P_{q}$. Then, given any
database $D$, an efficient algorithm can be used to retrieve only the top-$k$
best derivation trees for $P_{q}(D)$. The top-$1$ algorithm of the study is
closely related to our solution, but does not mention the use of a priority
queue nor does it take into account the optimization provided by the semi-
naïve evaluation strategy we describe in Section 4.

Our solution can be seen as a hybrid of the ideas introduced in
[DBLP:journals/corr/abs-2105-14435] and [Deutch2018EfficientPT]. We generalize
the semi-naïve evaluation to a specific class of semirings in order to achieve
a more efficient algorithm, one that can be used in practical real-world
scenarios.

##  8 Conclusion

In this work, we developed a novel method for Datalog provenance computation
based on the link between dynamic programming over hypergraphs and the proof
structure of provenance of Datalog programs. We introduced Knuth’s algorithm
for computing the provenance, and optimized it for practical use. We showed
its feasibility by providing an implementation on top of Soufflé and tested it
on several graph databases and Datalog programs.

As a continuation of this work, we aim to establish a taxonomy of recent
algorithms for provenance computation of Datalog programs (e.g.
[DBLP:journals/corr/abs-2105-14435]), i.e., classify them by their data
complexity and the class of semiring usable in each algorithm – with a focus
on $k$-closed semirings. The objective is to provide a meaningful comparison
with the already established taxonomy for semiring provenance in graph
databases [ramusat:hal-03140067]. Another direction of interest would be to
investigate a “fix” to the problems raised by Datalog provenance in AND/OR
graphs (see Section 6). Finally, in a more practical direction, it might be
feasible to implement the semi-naïve evaluation for Datalog${}^{\text{o}}$
over distributive dioids (Algorithm 1 in [DBLP:journals/corr/abs-2105-14435])
using Soufflé. Most of the inner workings can easily be adapted to do so, but
extending the current data structures storing facts (B-Trie, B-Tree) to allow
updates may be a challenge.

## References

  * [1] Kamal Abdali.  Parallel computations in *-semirings.  In Klaus G. Fischer, Philippe Loustaunau, Jay Shapiro, Edward L.Green, and Daniel Farkas, editors, Computational Algebra, chapter 1. Marcel Dekker, Inc., 1994.
  * [2] Serge Abiteboul, Richard Hull, and Victor Vianu.  Foundations of Databases.  Addison-Wesley, 1995.
  * [3] Stefano Bistarelli, Ugo Montanari, and Francesca Rossi.  Semiring-based constraint satisfaction and optimization.  Journal of the ACM, 44(2):201–236, March 1997.  doi:10.1145/256303.256306.
  * [4] Daniel Deutch, Amir Gilad, and Yuval Moskovitch.  selP: selective tracking and presentation of data provenance.  In 2015 IEEE 31st International Conference on Data Engineering, pages 1484–1487, 2015.  doi:10.1109/ICDE.2015.7113407.
  * [5] Daniel Deutch, Amir Gilad, and Yuval Moskovitch.  Efficient provenance tracking for datalog using top-k queries.  The VLDB Journal, 27:245–269, 2018.
  * [6] Daniel Deutch, Tova Milo, Sudeepa Roy, and Val Tannen.  Circuits for Datalog Provenance.  In ICDT, pages 201–212, 2014.
  * [7] Yefim Dinitz, Paz Carmi, Shahar Golan, Omri Liba, and Guy Rozenwald.  An $O(|V||E|)$ algorithm for scheduling with and/or precedence constraints.  In Haifa Workshop on Interdisciplinary Applications of Graphs, Combinatorics and Algorithms, 2011.
  * [8] Manfred Droste, Werner Kuich, and Heiko Vogler.  Handbook of Weighted Automata.  Springer Publishing Company, Incorporated, 1st edition, 2009.
  * [9] Javier Esparza and Michael Luttenberger.  Solving fixed-point equations by derivation tree analysis.  In International Conference on Algebra and Coalgebra in Computer Science, pages 19–35. Springer, 2011.
  * [10] Javier Esparza, Michael Luttenberger, and Maximilian Schlund.  Fpsolve: A generic solver for fixpoint equations over semirings.  In Markus Holzer and Martin Kutrib, editors, Implementation and Application of Automata, pages 1–15, Cham, 2014. Springer International Publishing.
  * [11] Luis Galárraga, Christina Teflioudi, Katja Hose, and Fabian Suchanek.  Amie: Association rule mining under incomplete evidence in ontological knowledge bases.  In WWW, pages 413–422, 2013.  doi:10.1145/2488388.2488425.
  * [12] M. Gondran.  Algèbre linéaire et cheminement dans un graphe.  RAIRO - Operations Research - Recherche Opérationnelle, 9(V1):77–99, 1975.
  * [13] Todd J. Green, Grigoris Karvounarakis, and Val Tannen.  Provenance semirings.  In PODS, 2007.  doi:10.1145/1265530.1265535.
  * [14] Liang Huang.  Advanced dynamic programming in semiring and hypergraph frameworks.  In Coling 2008: Advanced Dynamic Programming in Computational Linguistics: Theory, Algorithms and Applications, pages 1–18, 2008.
  * [15] Herbert Jordan, Bernhard Scholz, and Pavle Subotić.  Soufflé: On synthesis of program analyzers.  In Swarat Chaudhuri and Azadeh Farzan, editors, Computer Aided Verification, pages 422–430, Cham, 2016. Springer International Publishing.
  * [16] Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu, and Yisu Remy Wang.  Convergence of datalog over (pre-) semirings.  CoRR, abs/2105.14435, 2021.  arXiv:2105.14435.
  * [17] Donald E. Knuth.  A generalization of Dijkstra’s algorithm.  Information Processing Letters, 6(1), 1977.  doi:10.1016/0020-0190(77)90002-3.
  * [18] Daniel Krob.  Monoides et semi-anneaux complets.  In Semigroup Forum, volume 36, pages 323–339. Springer, 1987\.
  * [19] Werner Kuich.  Semirings and formal power series: Their relevance to formal languages and automata.  In Handbook of Formal Languages, volume 1, chapter 9, pages 609–677. Springer, 1997.
  * [20] Werner Kuich and Arto Salomaa.  Semirings, Automata and Languages.  Springer-Verlag, Berlin, Heidelberg, 1985.
  * [21] Adelson-Velsky M, Alexander Gelbukh, and Eugene Levner.  On fast path-finding algorithms in and-or graphs.  Mathematical Problems in Engineering, 8, 2002.  doi:10.1080/10241230306728.
  * [22] Michel Minoux and Michel Gondran.  Graphs, Dioids and Semirings. New Models and Algorithms, volume 41 of Operations Research/Computer Science Interfaces Series.  Springer, 2008.  doi:10.1007/978-0-387-75450-5.
  * [23] Mehryar Mohri.  Semiring frameworks and algorithms for shortest-distance problems.  J. Autom. Lang. Comb., 7(3):321–350, January 2002.
  * [24] Yann Ramusat, Silviu Maniu, and Pierre Senellart.  Semiring provenance over graph databases.  In 10th USENIX Workshop on the Theory and Practice of Provenance (TaPP 2018), London, United Kingdom, July 2018.  URL: https://hal.inria.fr/hal-01850510.
  * [25] Yann Ramusat, Silviu Maniu, and Pierre Senellart.  Provenance-based algorithms for rich queries over graph databases.  In EDBT 2021 - 24th International Conference on Extending Database Technology, Nicosia / Virtual, Cyprus, March 2021.
  * [26] Günter Rote.  Path problems in graphs.  Computing Supplementum, 7, 1999.  doi:10.1007/978-3-7091-9076-0_9.
  * [27] Bernhard Scholz, Herbert Jordan, Pavle Subotić, and Till Westmann.  On fast large-scale program analysis in datalog.  In Proceedings of the 25th International Conference on Compiler Construction, CC 2016, page 196–206, New York, NY, USA, 2016. Association for Computing Machinery.  doi:10.1145/2892208.2892226.
  * [28] Noah A. Smith.  Linguistic Structure Prediction.  Synthesis Lectures on Human Language Technologies, 4(2):1–274, May 2011.  doi:10.2200/S00361ED1V01Y201105HLT013.
  * [29] David Zhao, Pavle Subotić, and Bernhard Scholz.  Debugging large-scale datalog: A scalable provenance evaluation strategy.  ACM Trans. Program. Lang. Syst., 42(2), April 2020.  doi:10.1145/3379446.


# YOWO-Plus: An Incremental Improvement

Jianhua Yang<EMAIL_ADDRESS>State Key Laboratory of Robotics and
System, Harbin Institute of Technology, Harbin 150001, China

###### Abstract

In this technical report, we would like to introduce our updates to YOWO, a
real-time method for spatio-temporal action detection. We make a bunch of
little design changes to make it better. For network structure, we use the
same ones of official implemented YOWO, including 3D-ResNext-101 and YOLOv2,
but we use a better pretrained weight of our reimplemented YOLOv2, which is
better than the official YOLOv2. We also optimize the label assignment used in
YOWO. To accurately detection action instances, we deploy GIoU loss for box
regression. After our incremental improvement, YOWO achieves 84.9% frame mAP
and 50.5% video mAP on the UCF101-24, significantly higher than the official
YOWO. On the AVA, our optimized YOWO achieves 20.6% frame mAP with 16 frames,
also exceeding the official YOWO. With 32 frames, our YOWO achieves 21.6 frame
mAP with 25 FPS on an RTX 3090 GPU. We name the optimized YOWO as YOWO-Plus.
Moreover, we replace the 3D-ResNext-101 with the efficient 3D-ShuffleNet-v2 to
design a lightweight action detector, YOWO-Nano. YOWO-Nano achieves 81.0 %
frame mAP and 49.7% video frame mAP with over 90 FPS on the UCF101-24. It also
achieves 18.4 % frame mAP with about 90 FPS on the AVA. As far as we know,
YOWO-Nano is the fastest state-of-the-art action detector. Our code is
available on https://github.com/yjh0410/PyTorch_YOWO.

###### keywords:

Spatio-temporal action detection , You Only Watch Once , real-time action
detector

##  1 Introduction

Spatio-temporal action detection (STAD) is a fundamental and important
challenge in video understanding. It aims to detect action instances in the
current input frame. It has been widely applied, such as video
surveillance(Clapés et al., 2018) and somatosensory game(Yan et al., 2019).

Recently, I have taken an interest in STAD, so I’m going to reimplement a
popular model to get familiar with this task. Since YOWO(Köpüklü et al., 2019)
is simple and efficient, I decided to reproduce it. To my surprise, I found
that my reimplemented YOWO performs better. So, after reimplementing, I
released my code, and I’m writing this technical report to tell you what
improvements we make to YOWO, how we do it, and what performance we achieve.

##  2 Our improvement

In this technical report, we are dealing with a real-time action detector,
YOWO(Köpüklü et al., 2019). It consists of a 3D backbone and a 2D backbone.
YOWO designs a CFAM (channel fusion & attention module) to fuse 2D spatio-
temporal features and 3D spatio-temporal features. After that, it uses a
convolutional layer to make the prediction. The whole pipeline of YOWO is
shown in Fig.1. YOWO claims that it is the fastest state-of-the-art method in
spatio-temporal action detection. However, we think there is still large room
for improvement. We optimize YOWO from three aspects: backbone, label
assignment, and loss function.

Figure 1: Overview of YOWO.

###  2.1 Better backbone

YOWO deploys two backbones to process the input video clip. The 2D backbone
only processes the current frame a.k.a keyframe to extract spatial features,
while the 3D backbone processes the whole video clip to extract spatio-
temporal features. For the 3D backbone, YOWO uses the 3D-ResNext-101(Kopuklu
et al., 2019) which is pretrained on the Kinetics dataset(Carreira and
Zisserman, 2017). Since it is time-consuming to train a 3D CNN on the
Kinetics, we keep the pretrained weight of 3D-ResNext-101. For the 2D
backbone, we use a better COCO pretrained weight of our reimplemented
YOLOv2111https://github.com/yjh0410/PyTorch_YOLOv2, which achieves 27% mAP
with input $416\times 416$ on the COCO, significantly better than official
YOLOv2(Redmon and Farhadi, 2017). Other structure keeps the same as YOWO.

###  2.2 Better label assignment

YOWO takes advantage of YOLOv2 to process the keyframe and uses the same label
assignment as YOLOv2. Given a groundtruth, YOWO first calculates the grid cell
coordinate $\left(grid_{x},grid_{y}\right)$ as shown in Eq.(1),

$grid_{x}=\lfloor\frac{c_{x}}{s}\rfloor,\ \
grid_{y}=\lfloor\frac{c_{y}}{s}\rfloor$ (1)

where $\left(c_{x},c_{y}\right)$ is the center point of the groundtruth, and
$s$ is the output stride of the YOLOv2. Then YOWO calculates the IoU of the 5
predicted bounding boxes here. Only the predicted box with the highest IoU is
used to calculate the confidence loss, classification loss, and box regression
loss.

Different from the YOWO, we calculate the IoU of the 5 anchor boxes, not the
predicted boxes, and then we assign the anchor boxes with IoU higher than 0.5
to the groundtruth. Therefore, a groundtruth might be assigned with multiple
positive samples.

###  2.3 Better loss function

We define loss function as follows:

$\displaystyle L=$
$\displaystyle\lambda_{act}\sum_{i=0}^{S^{2}}\sum_{j=0}^{B}I_{ij}^{act}\left(C_{i}-\hat{C}_{i}\right)^{2}+\lambda_{noact}\sum_{i=0}^{S^{2}}\sum_{j=0}^{B}I_{ij}^{noact}\left(C_{i}-\hat{C}_{i}\right)^{2}$
(2)
$\displaystyle+\lambda_{cls}\sum_{i=0}^{S^{2}}\sum_{j=0}^{B}I_{ij}^{act}FocalLoss\left(p_{i},\hat{p}_{i}\right)$
$\displaystyle+\lambda_{coord}\sum_{i=0}^{S^{2}}\sum_{j=0}^{B}I_{ij}^{act}GIoU\left(b_{i},\hat{b}_{i}\right)$

where $\lambda_{act}=5.0$, $\lambda_{noact}=1.0$, $\lambda_{cls}=1.0$ and
$\lambda_{coord}$. $I_{ij}^{act}$ and $I_{ij}^{noact}$ are the indicator
functions. We use the same confidence loss and classification loss as YOWO
does except for the box regression loss. For box regression, we use the GIoU
loss(Rezatofighi et al., 2019) rather than the smooth L1 loss(Ren et al.,
2015) used in YOWO. During the training phase, the loss is normalized by the
batch size.

###  2.4 YOWO-Nano

To design a lightweight action detector, we replace the 3D-ResNext-101 with
3D-ShuffleNet-v2(Kopuklu et al., 2019). Other configurations are the same as
those of YOWO-Plus. We name this very efficient detector as YOWO-Nano.

##  3 Experiments

###  3.1 Datasets

UCF101-24(Soomro et al., 2012). UCF101-24 contains 3,207 untrimmed videos for
24 sports classes and provides corresponding spatio-temporal annotations.
There may be multiple action instances per frame. Following YOWO(Köpüklü et
al., 2019), we train and evaluate YOWO-Plus on the first split.

AVAGu et al. (2018). AVA is a large-scale benchmark for spatial-temporal
action detection. It contains 430 15-minute video clips with 80 atomic visual
actions (AVA). It provides annotations at 1 Hz in space and time, and precise
spatio-temporal annotations with possibly multiple annotations for each
person. Therefore, this benchmark is very challenging. Following YOWO, we
train YOWO-Plus on the train split and evaluate YOWO-Plus on the most-frequent
60 action classes of the AVA dataset. We report evaluation results on the AVA
v2.2.

###  3.2 Implementation details

For training, we use AdamW optimizer with an initial learning rate 0.0001 and
weight decay 0.0005. On the UCF101-24, we train YOWO-Plus for 5 epochs and
decay the learning rate by a factor of 10 at 1, 2, 3, and 4 epoch,
respectively. On the AVA, we train YOWO-Plus for 10 epochs and decay the
learning rate by a factor of 10 at 3, 4, 5, and 6 epoch, respectively. Unless
otherwise specified, the size of the input frame is reshaped to $224\times
224$.

Table 1: Comparison with YOWO on the UCF101-24. FPS si measured on a GPU RTX
3090. K is the length of the video clip.

Method | K | FPS | F-mAP (%) | V-mAP (%) | FLOPs | Params
---|---|---|---|---|---|---
YOWO | 16 | 34 | 80.4 | 48.8 | 43.7 B | 121.4 M
YOWO+LFB | - | - | 87.3 | 53.1 | - | -
YOWO-Plus | 16 | 35 | 84.9 | 50.5 | 43.7 B | 121.4 M
YOWO-Nano | 16 | 91 | 81.0 | 49.7 | 6.0 B | 72.7 M

Table 2: Comparison with YOWO on the AVA. FPS si measured on a GPU RTX 3090.

Method | K | FPS | mAP
---|---|---|---
YOWO | 16 | 31 | 17.9
YOWO | 32 | 23 | 19.1
YOWO+LFB | - | - | 20.2
YOWO-Plus | 16 | 33 | 20.6
YOWO-Plus | 32 | 25 | 21.6
YOWO-Nano | 16 | 91 | 18.4
YOWO-Nano | 16 | 90 | 19.5

###  3.3 Comparison with YOWO

UCF101-24. Table.1 summarizes the results on the UCF101-24. From the table,
YOWO-Plus achieves better performance than YOWO (84.9% frame mAP v.s. 80.4 %
frame mAP). Only equipped with long-term feature bank (LFB)(Wu et al., 2019),
YOWO can surpass YOWO-Plus. However, YOWO equipped with the LFB is no longer a
causal model because it uses the future information for inference, so it can
only run offline. Moreover, equipped with 3D-ShuffleNet-v2, YOWO-Nano achieves
better a trade-off between performance and detection speed, exceeding YOWO
with the higher mAP and much fewer FLOPs. YOWO-Nano can run at 91 FPS,
satisfying the real-time detection requirements.

AVA. Table.2 summarizes the results on the AVA. Both YOWO-Plus and YOWO-Nano
surpass YOWO with stronger performance and faster detection speed,
demonstrating the effectiveness of our improvements.

Although plenty of ablation experiments should be made to prove the
effectiveness of our improvements, it is too much time-consuming. I could only
finish the design of YOWO-Plus and YOWO-Nano in my spare time. I just want to
honestly share some of the improvements I’ve made to YOWO, not to publish a
paper. So, I think that this technical report can be ended here. If you are
interested in YOWO-Plus and YOWO-Nano, please try our code in GitHub and star
it. I hope you will enjoy it. If you have any questions, feel free to email me
or leave an issue on github.

##  4 Acknowledgment

Big thanks to YOWO222https://github.com/wei-tim/YOWO for designing such an
excellent action detector and releasing their code.

## References

  * Carreira and Zisserman (2017) Carreira, J., Zisserman, A., 2017\.  Quo vadis, action recognition? a new model and the kinetics dataset, in: proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6299–6308.
  * Clapés et al. (2018) Clapés, A., Pardo, À., Pujol Vila, O., Escalera, S., 2018\.  Action detection fusing multiple kinects and a wimu: An application to in-home assistive technology for the elderly.  Machine Vision and Applications 29, 765–788.
  * Gu et al. (2018) Gu, C., Sun, C., Ross, D.A., Vondrick, C., Pantofaru, C., Li, Y., Vijayanarasimhan, S., Toderici, G., Ricco, S., Sukthankar, R., et al., 2018.  Ava: A video dataset of spatio-temporally localized atomic visual actions, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6047–6056.
  * Kopuklu et al. (2019) Kopuklu, O., Kose, N., Gunduz, A., Rigoll, G., 2019\.  Resource efficient 3d convolutional neural networks, in: Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops, pp. 0–0.
  * Köpüklü et al. (2019) Köpüklü, O., Wei, X., Rigoll, G., 2019.  You only watch once: A unified cnn architecture for real-time spatiotemporal action localization.  arXiv preprint arXiv:1911.06644 .
  * Redmon and Farhadi (2017) Redmon, J., Farhadi, A., 2017\.  Yolo9000: better, faster, stronger, in: Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7263–7271.
  * Ren et al. (2015) Ren, S., He, K., Girshick, R., Sun, J., 2015.  Faster r-cnn: Towards real-time object detection with region proposal networks.  Advances in neural information processing systems 28\.
  * Rezatofighi et al. (2019) Rezatofighi, H., Tsoi, N., Gwak, J., Sadeghian, A., Reid, I., Savarese, S., 2019\.  Generalized intersection over union: A metric and a loss for bounding box regression, in: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 658–666.
  * Soomro et al. (2012) Soomro, K., Zamir, A.R., Shah, M., 2012.  Ucf101: A dataset of 101 human actions classes from videos in the wild.  arXiv preprint arXiv:1212.0402 .
  * Wu et al. (2019) Wu, C.Y., Feichtenhofer, C., Fan, H., He, K., Krahenbuhl, P., Girshick, R., 2019\.  Long-term feature banks for detailed video understanding, in: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 284–293.
  * Yan et al. (2019) Yan, C., Tu, Y., Wang, X., Zhang, Y., Hao, X., Zhang, Y., Dai, Q., 2019.  Stat: Spatial-temporal attention mechanism for video captioning.  IEEE transactions on multimedia 22, 229–241.