# Neuromorphic quadratic programming for efficient and scalable model
predictive control

Ashish Rao Mangalore*, Gabriel Andres Fonseca Guerra, Sumedh R. Risbud,
Philipp Stratmann, Andreas Wild * Corresponding author
A. R. Mangalore is presently with the School of Computation, Information, and
Technology, Technische Universität München and Neuromorphic Computing Lab,
Intel Labs. G. A. F. Fonseca, S. R. Risbud, P. Stratmann, and A. Wild are with
the Neuromorphic Computing Lab, Intel Labs. E-mail: {ashish.rao.mangalore,
gabriel.fonseca.guerra, sumedh.risbud, philipp.stratmann,
<EMAIL_ADDRESS>
###### Abstract

Applications in robotics or other size-, weight- and power-constrained
autonomous systems at the edge often require real-time and low-energy
solutions to large optimization problems. Event-based and memory-integrated
neuromorphic architectures promise to solve such optimization problems with
superior energy efficiency and performance compared to conventional von
Neumann architectures. Here, we present a method to solve convex continuous
optimization problems with quadratic cost functions and linear constraints on
Intel’s scalable neuromorphic research chip Loihi 2. When applied to model
predictive control (MPC) problems for the quadruped robotic platform ANYmal,
this method achieves over two orders of magnitude reduction in combined
energy-delay product compared to the state-of-the-art solver, OSQP, on (edge)
CPUs and GPUs with solution times under ten milliseconds for various problem
sizes. These results demonstrate the benefit of non-von-Neumann architectures
for robotic control applications.

###### Index Terms:

quadratic programming, neuromorphic hardware, spiking neural networks, model
predictive control, convex optimization

##  I Introduction

Figure 1: A class of convex optimization problems, namely, quadratic programs,
are part of the model predictive control loop of the ANYmal. In this article,
we explore running different sizes of these programs on Loihi 2, a
neuromorphic research platform developed by Intel Labs and see how they
compare against conventional compute architectures in terms of performance and
energy consumption. We show how the common motifs underlying many algorithms
(such as gradient descent, primal-dual or operator splitting methods) to solve
convex constrained optimization problems are framed as the dynamics of event-
based recurrent neural networks whose steady-states represent the solutions to
the problems. The resulting network topology enables the implementation of
diverse first-order algorithms for efficiently solving convex QP and LP
problems on neuromorphic hardware.

Convex quadratic programming (QP) has been a topic of substantial research
since the 1950s. The goal of this class of problems is to optimize a quadratic
cost function subject to linear constraints. The convex nature of the problems
ensures that iterative updates of the variables along the gradient of the cost
function are guaranteed to converge to the optimal solution. Convex QP
optimization problems are particularly attractive for edge applications like
robotic model predictive control (MPC), in which a smooth closed-loop
interaction with the environment requires solving the problems within
millisecond latency [1]. In such embedded applications, energy consumption is
also critical for long battery life. As control systems incorporate more
degrees of freedom, the underlying optimization problems grow in terms of the
number of variables and require more complex cost and constraint functions.
Solving increasingly more difficult optimization problems drives the search
for more efficient and scalable approaches beyond conventional CPUs or GPUs.

Brain-inspired neuromorphic architectures have demonstrated significant
performance and energy gains over conventional architectures for a range of
optimization problems with superior scalability up to hundred of thousands of
problem variables [2]. Neuromorphic architectures derive their advantage over
conventional architectures from the integration of memory with compute units
to minimize data movement, massive fine-grained parallelism, a streamlined set
of supported operations, as well as architectural optimizations enabling
sparse, event-based computation and communication only when necessary. As a
result and similar to biological brains, these novel architectures have the
potential to solve extremely complicated computational problems at low power
and short response times on the order of Watt and millisecond, respectively.

Among the algorithms that excel on neuromorphic architectures are solvers for
constraint satisfaction problems [3], quadratic unconstrained binary
optimization (QUBO) [4], and different optimization problems on graphs [5].
The development of the spiking locally competitive algorithm, LCA, [6, 7] — to
solve LASSO with neuromorphic hardware — was the first approach to solve
unconstrained convex QPs as a spiking neural network with wide ranging
applications such as in sparse coding or signal processing. Nonetheless, the
problem of solving general convex optimization with constraints on
neuromorphic hardware remained unaddressed.

In this article, we discuss a framework to solve general convex QPs on
neuromorphic hardware and demonstrate the implementation of a QP solver that
leverages the event-based, memory-integrated, fine-granular parallel
architecture of the Intel Loihi 2 research chip [8] using the Lava open-source
framework111https://lava-nc.org/. We further, highlight its efficacy to solve
large real-world QP problems arising in the context of model predictive
control (MPC) of the ANYmal quadrupedal robot [9]. We explore the conditions
under which neuromorphic architectures are more suitable hardware substrates
to solve convex optimization problems than traditional von-Neumann-based
architectures.

Convex QP problems arising in size-, weight-, and power-constrained (SWaP)
systems are conventionally solved on CPUs, even though a few solutions have
been developed to leverage the parallel compute capabilities of GPUs, FPGAs,
or ASICs. A range of high-performance QP solvers exist for CPUs, such as
GUROBI [10], MOSEK [11] and CVXOPT [12]. Lightweight CPU solvers specifically
optimized for embedded systems include qpOASES [13], ECOS [14] and OSQP [15];
such solvers avoid any dependence on large external libraries, use only basic
operations (e.g. avoiding division), minimize the steps to solution, optimize
the code for mobile processors, and often parallelize their code.
Unfortunately, CPUs in general — and the ones in embedded systems in
particular — often do not support the degree of parallelism needed to
accelerate large optimization workloads.

While GPUs offer a high degree of parallelism for optimization algorithms [16,
17], they primarily achieve their efficiency through extremely wide data paths
and deep pipe-lining, allowing them to stream batched data from off-chip
memory to process many parallel threads. However, in the case of sparse
problems, the GPU resources are massively underutilized, rendering them
inefficient. Similar to sparse problems, the inefficiencies of using GPUs
become apparent in real-time data processing applications too (e.g., MPC),
wherein in the absence of batching (or batch-size 1) leads to inadequate usage
of pipe-lining. In addition, both CPUs and GPUs suffer from high external
memory access latencies that can hardly be hidden when solving iterative
algorithms on a millisecond timescale in closed-loop control.

Similar to neuromorphic processors, more specialized solutions for solving QPs
have been realized using FPGAs [18, 19] and ASICs [20]. While these approaches
have their merits in terms of performance or energy consumption, they require
a vastly higher development effort and may only serve a single purpose (ASICs)
compared to highly efficient and programmable neuromorphic processors like
Intel Loihi that can be applied to many other problems apart from QP.

##  II Solving QPs and LPs with distributed discrete dynamical systems

Quadratic programming refers to

minimize: $\displaystyle f(x)=\frac{1}{2}x^{T}Qx+p^{T}x\ ,$ (1) subject to:
$\displaystyle g(x)=Ax-k\leq 0\,$ (2)

where $A\in\mathbb{R}^{M\times L}$, $x\in\mathbb{R}^{L}$,
$p\in\mathbb{R}^{L}$, $k\in\mathbb{R}^{M}$ and $Q\in\mathbb{R}^{L\times L}$.
This also covers the sub-problem of linear programming (LP), wherein $Q=0$. A
quadratic program is convex when the feasible set is a convex set and $Q$ is
symmetric positive semi-definite ($Q\in S^{L}_{+}$). In the following section
(II-A), we go over an iterative strategy to solve the QP from eqs. (1) and
(2). In section II-B, we present the implementation of our neuromorphic
algorithm to solve convex QP such that it respects the constraints and
strengths of Loihi 2, as determined in previous studies[7].

###  II-A Iterative solvers for convex quadratic programs

The unconstrained QP defined by eq. (1) alone can be solved by first-order
gradient descent. The convexity of the unconstrained problem guarantees the
convergence to the global minimum:

$x_{t+1}=x_{t}-\alpha\cdot\nabla f(x)=(I-\alpha Q)x_{t}-\alpha p\ .$ (3)

The constant $\alpha>0$ determines the step size of the gradient descent.

When constraints are introduced, as defined by eq. (2), pure gradient descent
according to eq. (3) may lead to constraint violations in the course of
iterations. Mathematically, a constraint violation occurs if a hyperplane
$A_{j}x=k_{j}$ is crossed (the hyperplane is defined by the normal vector
$A_{j}$, which is the $j^{th}$ row of $A$ [21]). To avoid such violations, one
can deflect the gradient descent dynamics into the direction of the normal
vector if a constraint boundary is crossed. The dynamics are explained in fig.
2a.

To ensure that the gradient dynamics evolves in the feasible region, it is a
sufficient condition to add this correction to our dynamical system,

$\displaystyle x_{t+1}$ $\displaystyle=(I-\alpha_{t}Q)x_{t}-\alpha_{t}\cdot
p-\beta_{t}A^{T}\theta_{G}(x_{t})$ (4) $\displaystyle\theta_{G}(x_{t})$
$\displaystyle=\begin{cases}Ax_{t}-k&\text{ if }Ax_{t}>k\\\ 0&\text{
otherwise.}\end{cases}\ ,$ (5)

where $\theta_{G}(x_{t})$ denotes the relu-function indicating when $x_{t+1}$
crosses a constraint hyperplane during gradient descent. Here, the
hyperparameter $\alpha_{t}$ decays while $\beta_{t}$ grows over time as the
solver approaches the minimum of the state space.

The convergence rate can be accelerated by an additional integral term that
accumulates the deviation of the state vector outside the feasible region,
i.e., the constraint violation, similar to a proportional integral controller.
With this additional feature, one can revise the dynamics as [22],

$\displaystyle x_{t+1}$
$\displaystyle=\pi_{\mathbb{X}}(x_{t}-\alpha_{t}(Qx_{t}+p+A^{T}v_{t}))\ ,$ (6)
$\displaystyle v_{t}$
$\displaystyle=\theta_{G}(v_{t-1})(w_{t}+\beta_{t}(Ax_{t}-k))\ ,$ (7)
$\displaystyle w_{t+1}$ $\displaystyle=w_{t}+\beta_{t}(Ax_{t+1}-k)\,$ (8)

where $\pi_{\mathbb{X}}$ refers to the projection of the corrected $x_{t}$
into the feasible set $\mathbb{X}$. The hyperparameters $\alpha_{t}$ and
$\beta_{t}$ depend on the curvature of the cost function [22].

The dynamics described by Eq. (6)-(8) can be interpreted as that of a 2-layer
event-based recurrent neural network as illustrated in fig. 2b which minimizes
the cost function (1) using gradient descent. After algebraically eliminating
$w_{t}$, the variables $x_{t}$ and $v_{t}$ can be identified as state
variables of different types of neurons, while $Q$ and $A$ can be identified
as matrices representing (sparse) synaptic connections between those neurons.
Relying only on element-wise or matrix-vector arithmetic, this type of network
can be efficiently implemented on neuromorphic hardware.

Figure 2: A QP solver can be formulated as a spiking neural network. a)
represents the two-dimensional projection of a convex region defined by $Q$,
as contour lines, alongside constraint planes defined by $A$ as shaded
regions. Black arrows represent the trajectory of gradient descent until it
crosses the blue constraint plane. At that, point gradient descent is
corrected by the dark blue arrow contribution which brings the network state
back to the feasible region (final black arrow). b) The Gradient Descent block
shows the network encoding of a solver for unconstrained QP. Each black circle
represents a neuron that performs gradient descent updates, dashed lines
represent biases and arrows synapses. For constrained QP, we add the
Constraint Correction block, where colored circles are the neurons computing
constraint violations and corresponding corrections for each constraining
plane. The correcting terms are sent to the gradient descent neurons via
channels indicated as colored arrows. An integration neuron (green) tracks the
cost of the current network state. In case of PIPG, each of the $L$ gradient
descent neurons encodes one scalar entry $x^{i}_{t}$ of the variable vector
$x_{t}$. It receives input $x_{t}$ from the other gradient neurons via
synapses with multiplicative weights defined by the vector $Q_{i}$. In
addition, it receives input $v_{t}$ from the constraint neurons via synapses
of weight $A^{T}_{i}$. Its state is updated according to eq. (6) and returned
to the other gradient neurons. Each of the $M$ constraint neurons maintains
internal states $w^{j}_{t}$ and $v^{j}_{t}$. It receives the states $x_{t}$
from all gradient descent neurons via synapses with multiplicative synaptic
weights $A^{T}_{j}$. It then updates its internal states $w^{j}_{t}$ and
$v^{j}_{t}$ according to eq. (7)-(8).

###  II-B Neuromorphic hardware implementation

Neuromorphic hardware architectures are designed to efficiently execute event-
based neural networks. Example systems include SpiNNaker 1 and 2, Dynaps,
BrainScaleS 1 and 2, TrueNorth, and Loihi 1 and 2 [23]. A shared
characteristic of many of these architectures is a large number of parallel
compute units operating out of local memory, executing either fixed-function
or highly programmable neuron models. Typically, these architectures are
optimized for sparse event-based computation and communication. The use of the
Loihi 2 for solving QP problems in this study has been motivated by prior
work, showing that the Loihi 2 architecture excels at solving iterative
constraint optimization problems[7].

Figure 3: Mapping of the QP/LP solver to a neuromorphic substrate, an Intel
Loihi 2 chip is shown here. Each Loihi 2 chip supports up to 1M neurons and up
to 120M synapses depending on the model complexity, spread across 128
computing cores. Each neuron integrates synaptic-weighted input spikes from
pre-synaptic neurons, can update local state variables via micro-code
programmable operations, and can send graded spikes, i.e, integer valued
message payloads to other post-synaptic neurons. The recurrent dynamics
$x_{t+1}=h(x_{t})$, which contains gradient descent and constraint corrections
are mapped to neurons across different cores (yellow blocks) in the chip. The
network state evolves towards the minimum in the energy landscape (fig. 2a )
by exchanging spikes (bottom right zoom-in). The final solution is then post-
processed to get the solution for the orignal non-preconditioned problem which
is then used in the next stage of the ANYmal control pipeline.

#### Mapping the QP solver to Loihi 2

The QP solver corresponding to the dynamics of eq. (6)-(8) was implemented on
the second generation of the Intel Loihi research chip [8] (fig. 3). The
massively parallel chip architecture consists 128 independent asynchronous
cores that communicate with each other by exchanging up to 24-bit messages
(graded spikes) using local on-chip routers. The innards of a core are shown
in fig. 3. Ingress spikes from other cores are first buffered before passing
through the Synapse stage. This stage effectively performs a highly optimized
dense or sparse matrix vector multiplication with up to 8-bit synaptic weights
and up to 24-bit spike activation. The resulting product can be read by the
Neuron stage from the Dendritic Accumulator stage. The Neuron stage executes
stateful, parametrizable neural programs supporting basic arithmetic and bit-
wise operations on variables up to 24 bits as well as conditional logic.
Programs can also generate egress messages which are routed to other cores via
the Axon stage.

Variables $x_{t}$ and $v_{t}$ defined in Eq. (6)-(8) are encoded as 24-bit
state-variables of two different types of neurons in the chip, i.e., the
gradient descent and constraint check neurons respectively. As seen in fig. 3,
the spikes, in this case, carrying the values of states $x_{t}$ and $v_{t}$,
are multiplied with the synaptic weights, $Q$ and $A$, and $A^{T}$
respectively the results of which are fed into the gradient descent and
constraint check neurons respectively. The neuron programs then perform the
remaining arithmetic operations involved to complete the dynamics. This co-
location of memory and compute in the neuromorphic chip leads to gains in
terms of energy and time to solution for the algorithm. Note that different
types of QP solvers can be implemented by merely changing the state update
dynamics of the constraint correction or gradient descent neurons which is
possible due to Loihi 2’s programmable neurons. The updated states are only
communicated to the next neuron through synapses if necessary, in this case,
when the value is non-zero.

According to Yue et al. [22] the hyperparameters, $\alpha$ and $\beta$, need
to evolve at a certain rate for quicker convergence.This evolution, however,
makes use of general-purpose division and floating-point operations which are
not supported on Loihi 2. We emulate the evolution on Loihi 2 by halving
$\alpha$ and doubling $\beta$ at a schedule, i.e, implementing simulated
annealing for the hyperparameter $\alpha$ and geometric growth for $\beta$.
The decay by halving is achieved using a bit right-shift operation which is
the same as division by 2. The vector of values of the state variables of the
gradient descent neurons after convergence of the dynamics of the network is
the solution to the QP. Note that, in order to accelerate the convergence, QP
problems are often first preconditioned. We choose the Ruiz preconditioner
which is known to work well for block-diagonal problems like the ones we deal
with this in this article. The pre-conditioning procedure is carried out on
the host CPU in our experiments.

For QPs arising in MPC, the neuromorphic architecture of Loihi 2 already
offers advantages over conventional architectures and ANN accelerators because
of the compute and memory co-location which will be further discussed in
section III. However, first-order type algorithms like those in eq. (4)-(8)
can be made more suitable for neuromorphic hardware by employing
$\Sigma$-$\Delta$ coding which can be implemented in Loihi 2 [24] . Doing so
sparsifies the spiking activity at the cost of solution accuracy. This,in
turn, improves the time and energy to solution because of fewer
messages/spikes being moved around and, as a consequence, fewer operations in
general. However, this reduces operations within acceptable solution
degradation only when the datatypes on chip are more precise (16-/32-bit
floating-point) which is currently not the case in Loihi 2. Therefore, in this
article we focus on results obtained without employing sigma-delta coding.

#### Programming Loihi 2 with Lava

The QP solver is implemented on Loihi 2 using the open-source software
framework Lava for neuromorphic computing in the lava-optimization library. At
its core, programming in Lava is based on asynchronous processes that
communicate with each other via message-passing over channels. Lava provides a
cross-platform runtime and compiler to execute algorithms on different
backends such as CPU/GPU and Loihi 2, but is also open to extension to other
neuromorphic platforms. Lava-optimization is one of several high-level
algorithm libraries that build on top of Lava.222Lava is an open-source
software licensed under BSD 3-Clause and LGPL 2.1, and only proprietary
modules required to run code on Loihi 2 are confidential to members of Intel’s
Neuromorphic Research Community (INRC). The proprietary code required to
execute the solver with high performance on Loihi 2 can be accessed after
joining the INRC.

##  III Quadratic programming for model predictive control

###  III-A Problem definition

To demonstrate the value of our neuromorphic QP solver, we apply it to solving
the QPs arising in model predictive control in the quadrupedal robot ANYmal
[9], a state-of-the-art quadrupedal robot. At the core of an MPC iteration is
the mathematical optimization problem of minimizing the error between actual
and goal trajectories, i.e., the tracking error. The optimization is subject
to constraints, such as the limits posed by the rigid-body dynamics, joints,
actuators, and environment. As such, the optimization problem is a
computationally expensive, nonlinear (and perhaps non-convex). However, it is
typically ‘linearized-and-quadratized’ using techniques akin to Taylor series
expansion, resulting in a convex QP problem from eq. (1) and (2). MPC is a
computationally intensive control scheme that must be executed under strict
time budgets in real-time control loops. Solving the QP accounts for a major
chunk of computational time in MPC of ANYmal. The QP further increases in
complexity with larger time horizons covered by the MPC or more degrees of
freedom of the robot. In order to meet these requirements, MPC is solved on a
dedicated laptop-class CPU. Running the QP in the MPC on Loihi would be the
first step towards making computation for control more suitable for SWaP
systems.

MPC uses a mathematical model of ANYmal to predict the temporal evolution of
its state over a time horizon in the future. The prediction is based on the
optimization of a task-specific objective function and the robot’s current
measured state (its position, orientation, linear and angular momenta, and
joint angles [1]). From the predicted time-series of the control variables,
only a fraction in the beginning is used for actuating the locomotion of
ANYmal. For example, a typical MPC horizon in the control loop of ANYmal of
about 1 second is split into 100 time-steps of 10 ms each and only first 20-30
ms worth of predictions are used to issue control commands. Once the robot
moves, a new state measurement and sensory data are fed back to the model to
generate the next set of predictions, thus completing an MPC iteration.

###  III-B Neural and synaptic scaling

For an MPC horizon of $N=100$, we require $7248$ neurons connected through
$405,504$ weights at most. These resources are well within a single Loihi 2
chip’s capacity of at least 64kB of memory synaptic connections and 8kB for
neural programs per neuron core. Assuming 8-byte neurons and 1-byte weights,
we get $\sim$$1$ million neurons and $\sim$$15$ million 8-bit synapses for a
single chip with $\sim$$123$ cores. Note that the complexity of the neuron
program can lead to higher memory requirements for it. For this article, we
implemented programs that require 2 bytes per neuron resulting in 500,000
available neurons in a single chip. This is well above the requirements for
the QPs covered here.

To understand the scaling of neurons and synapses on Loihi for our QP
formulation, we first calculate the number variables and weights involved in
the QP problem for MPC. ANYmal’s locomotion is captured by the temporal
evolution of a 48 dimensional attribute vector formed by concatenating a 24
dimensional control vector (12 joint velocities and 12 contact forces) and a
24 dimensional state vector (6 base poses, 6 momenta, 12 joint angles). When
we formulate the QP problem for an MPC iteration of horizon with $N$ time-
steps, we treat all $N$ values of the attribute vector at every time-step as a
flattened vector. The causal dependence between the attribute vectors at
successive time-steps is captured in constructing the cost, $Q$, and
constraints, $A$, matrices of the QP problem from eq. (1) and (2). We need one
neuron for each decision variable and one for each constraint variable.
Therefore, the number of neurons required to map QPs of this type onto Loihi
is given by:

$n_{neurons}=(N+1)*n_{states}+N*n_{controls},$ (9)

where $n_{states}$ is the size of the state vector (24 for ANYmal) and
$n_{control}$ is the size of the control vector (24 for ANYmal). Further, the
maximum number of synapses required to map this QP onto Loihi is given by,

$\displaystyle n_{synapses}=n_{states}*(2*n_{states}+n_{controls})*N$ (10)
$\displaystyle+(n_{states}+n_{controls})^{2}*N+n_{states}^{2}.$

Figure 4:  In (a) the matrices pertaining to stage costs, $H^{(j)}$, and
dynamics ,$G^{(j)}$, of ANYmal are associated with every timestep of the MPC.
$E^{(j)}$ and $F^{(j)}$ represent the dynamics of the robot at timestep $j$.
$S^{(j)}$, $K^{(j)}$ and $T^{(j)}$ are the stage costs at timestep $j$. It is
seen in (b) how these matrices are concatenated together to form large $Q$ and
$A$ matrices for cost and constraints of the QP (Eq. 1 & 2) and respectively.
Note that the matrices in (b) are sparsely populated making these types of
problems well-suited for Loihi.

###  III-C Benchmarking procedure and dataset

The efficiency, scalability, and speed of the Loihi QP solver was benchmarked
against OSQP running on a standard CPU and an embedded CPU, and against the
CUDA-optimized version of it, cuOSQP, running on a GPU 333Loihi 2: Oheo Gulch
board running Lava v0.7.0 and Lava-Optimization v0.2.4 with an Intel Core
i7-9700K CPU host with 32GB RAM running Ubuntu 20.04.5 LTS.
OSQP: OSQP v0.6.2.post9 ran on an Intel Core i7-9700K CPU @ 3.6GHz with 32GB
DRAM running Ubuntu 20.04.5 LTS and an Nvidia Jetson Orin 6-core Arm
Cortex-A78AE v8.2 64-bit CPU 1.5MB L2 + 4MB L3 CPU with 6GB of shared RAM
running Ubuntu 20.04.6 LTS.
cuOSQP: ran on an Intel Core i7-9700K CPU @ 3.6GHz with 32GB DRAM running
Ubuntu 20.04.5 LTS with an Nvidia GeForce RTX 2070 Super GPU with 8 GB of RAM
and cuda 10.2.  Evaluation metrics were time to solution (TTS), energy to
solution (ETS) and energy-delay product (EDP) for different problem sizes.
OSQP is a CPU-based state-of-the-art solver for convex QP problems with linear
inequality constraints [15].

The dataset used in this paper consists of data from 2173 individual time-
steps of MPC of an ANYmal robot [25]. The dataset consists of the matrices
obtained after linearization and quadratization of a nonlinear objective
function and penalizes deviation from a reference trajectory as well as the
ANYmal dynamics. We tile these matrices in an appropriate manner to construct
the $Q$ matrix of the QP objective function from (1) and the $A$ matrix of the
constraints from (2). This tiling is demonstrated in fig. 4. The derivation
and explanation of this tiling has been omitted here since it’s beyond the
scope of the article. It can be seen that these matrices are mostly block-
diagonally populated and very sparse. This entails sparse matrix-vector
multiplication making a suitable candidate for Loihi 2. The vectors $p$ and
$k$ from the cost and constraints respectively are constructed by stacking the
vectors associated with the tracking cost and the dynamics in each stage of
the MPC. We investigate how well the performance of the solver scales with
problem size by varying the number of variables. In general, the problem size
is determined by the time horizon and the degrees of freedom of the robot.
Here, we choose six horizon lengths $N={5,\,50,\,75,\,100,\,150,\,175}$ time-
steps, resulting in problems with $264,\,2424,\,3624,\,4824,\,7224,\,8424$
variables, respectively. We use this as a proxy for a robot with higher
degrees of freedom. Most QPs in the dataset are similar in difficulty (similar
condition numbers). Therefore, for each horizon length, we have chosen 10
different QPs of varying difficulty that best represent all the problems in
the dataset. In summary, we have a dataset containing a total of 60
representative QP problems of 6 different sizes from the ANYmal dataset,
spanning from $\sim 250$ to $\sim 8500$ variables.

###  III-D Convergence, power and performance analysis

In the context of solving a type of QP problem, i.e, LASSO problems, on Loihi
[26, 7] Loihi-based solvers rapidly converge to approximate solutions, but
limited precision available on the chip, explained in II-B, limits the
convergence to a finite optimality gap. The same applies to Loihi 2 as well.
However, the CPU solver operates with 64-bit floating-point precision.To make
a fair comparison across all platforms, we run all solvers until they have
converged up to the same accuracy of 8% from the true solution. This accuracy
was chosen in alignment with the precision needed to make MPC robust for
various control applications [27]. For MPC applications that need higher
accuracy, we can in general increase the precision of the Loihi 2 solution.
For this, Loihi 2 could represent each 64-bit variable by allocating several
of its 24-bit states, and each 64-bit matrix weight by combining several of
its 8-bit synaptic weights. To verify that successive MPC iterations converge
stably even with limited precision, we randomly perturbed $Q$ and $A$ matrices
for each successive iteration and verified that the cost and constraint
satisfaction keep converging with warm-starting of the QP solver. This
suggests that approximate solutions are sufficient in closed-loop control
applications.

Fig. 5 demonstrates that the Loihi QP solver rapidly converges within $\sim$55
iterations on average, where a solution is considered to have converged when
the solver reaches within 8% or less of the OSQP reference solver. The solver
continues to converge further, closer to optimality, but with a slower
convergence rate. Similar to the cost, constraint satisfaction continues to
improve beyond our definition of convergence. In the subsequent performance
comparison results, we have used the fact that Loihi QP solver converges at 55
iterations, and compared its performance with that of OSQP.

Figure 5: Convergence analysis of Lava QP solver for 60 QPs in the MPC loops
of ANYmal as measured by (a) the cost eq. 1 normalized by OSQP’s optimal cost
and (b) number of constraint violations eq. 2 normalized by the L2-norm of the
final solution is shown here. Solid lines represent the mean for cost and
constraints respectively for 60 different problem sizes
$N={5,50,75,100,150,175}$ translating into 264 to 8424 QP variables as
indicated by the legend. Shaded regions represent one standard deviation from
the mean. The horizontal black lines corresponds to the optimal cost. The
inset in (a) depicts the number iterations required for different problem
sizes to reach an optimality gap of 8% with respect to OSQP.

Fig. 6a shows the time-to-solution (TTS) for the same set of QP problems of
increasing problem size. As the MPC time horizon $N$—and thus the number of QP
variables—increases, TTS increases roughly linearly for both OSQP and the
Loihi QP solver. While the OSQP solver solves small problems faster than Loihi
2 in the sub-millisecond regime, the time it takes OSQP to find the optimal
solution (black dashed line) grows rapidly beyond Loihi’s TTS. Let us
consider, approximate solutions from Loihi for usage in iterative MPC with
warm-starts. In this case, OSQP’s TTS grows less rapidly but still exceeds
Loihi towards the largest problem size. We see that the solution time for a
standard GPU is orders of magnitude higher than even a CPU for problems of
this scale for reasons mentioned in section I. For the embedded CPU, the TTS
follows the same trend as the Laptop CPU albeit even slower.

Figure 6: (a)-(c) demonstrate the advantages of the Loihi 2 based solver over
the CPU solver on a laptop-class (black) and edge-level CPU (gray) and also
over its GPU-based implementation (green) for increasing problems size on
different metrics. As seen from (d)-(f), there exists a parallelization-
solution time trade-off but a slow solver beyond a certain point, could lead
to increased EDP. Note that the speed of execution can be increased by
operating at higher voltages.

Fig. 6b shows the corresponding ETS for increasing problem complexity. ETS for
both OSQP and the Loihi QP increase with problem size as more and more cores
on Loihi are utilized. Loihi achieves a significant advantage compared to
laptop class CPUs in energy of over $200\times$ for all problem sizes. Energy
consumption of the Loihi QP solver is composed of static and dynamic energy:
$E=E_{static}+E_{dyn}$. Static energy is mostly governed by chip leakage power
on Loihi $E_{static}=P_{static}\cdot TTS\cdot c_{active}/c_{total}$ where $c$
is the number of active and total cores respectively. Measurements for this
analysis have been obtained from early silicon samples that still have highly
variable leakage characteristics leading to a high $P_{static}=1.4W$ per chip
at the lowest operating voltage and thus is less relevant for this analysis.
Dynamic energy is governed by the amount of operations within Loihi cores to
update neurons and route traffic between cores.

Further Fig. 6c shows a $520\times$ energy-delay product advantage for the
largest problem size when using Loihi 2 in place of a laptop CPU. It can be
seen in fig. 6c that the EDP curves for CPUs (embedded and laptop) closely
resemble each other. The laptop and embedded CPU thus trade TTS against ETS,
but the combined EDP is characteristic for CPUs. For a GPU, both the ETS and
EDP are orders of magnitude higher mainly.

By increasing Loihi’s operating voltage from $VDD=0.6V$ to $0.8V$, Loihi’s TTS
improves by about 47%. At the same time, dynamic energy increases by a factor
of $1.9\times$ for increasing operating voltage for a problem of 4824
variables. The total energy remains largely unchanged since the dominating
leakage energy drops with lower TTS in this example. Fig. 6d-e further
illustrate how the level of multi-core parallelism allows to trade performance
(TTS) for chip resources. As the number of neurons per core decreases and
number of cores increases proportionately, TTS improves from 17.5 ms to 2.6 ms
for a problem size of 4824 variables. The slightly less than linear decrease
in TTS results from additional multi-core synchronization and data traffic
between parallel Loihi cores. Loihi’s highly configurable nature allows users
to trade off energy consumption (ETS), speed (TTS) and chip resource
utilization, which can be useful in size-, weight- and power- (SWaP)
constrained applications to select the optimal task-specific operating point.

##  IV Conclusion

We have developed an efficient and scalable approach for solving convex
quadratic constraint optimization problems with neuromorphic chips. The
benefits of neuromorphic systems can be exploited for optimization algorithms
by interpreting the structure of many iterative optimization approaches—such
as gradient descent and primal-dual updates—as the dynamics of recurrent
neural networks. To demonstrate the benefits of this framework, we implemented
a QP solver on Intel’s Loihi 2 research chip and made it publicly available as
part of the Lava software framework. We apply it to solving QPs on a dataset
extracted from the model predictive control (MPC) pipeline of the ANYmal
quadrupedal robot. Our Loihi solver achieves similar speed as the state-of-
the-art solver OSQP on a modern CPU [28], which was the best von-Neumann-
based-candidate for comparison, for approximate solutions while consuming
about two orders of magnitude less energy. Most notably, time and energy to
solution on Loihi scale better with increasing problem complexity than OSQP on
CPU.

The performance, energy and scaling advantages on Loihi result primarily from
its massively parallel, event-based, memory-integrated hardware architecture.
Multi-core parallelism allows to quickly and independently update a large
number of variables. The hardware is further optimized for arithmetic on
sparse matrices, as present in most large real-world QP workloads [29]. Its
event-based computation and communication further eliminates redundant data
traffic routing and computation. Together, these features support scaling to
large problems sizes with less overhead than on conventional computer
architectures. In addition, the memory-integrated compute architecture
minimizes the energy and latency required to access data for algorithmic
iterations. With the observed gains in computational efficiency, interpretable
model-based controllers could see increased adoption over more opaque model-
free controllers like reinforcement learning, thus increasing the safety of
applications.

The most significant limitation of the current approach is the limited bit-
precision of state variables and synaptic connections on neuromorphic
architectures like Loihi. This can lead to lower solution optimality than
solvers on conventional floating-point architectures. Such limitations can be
circumvented by allocating multiple low-bit variables to effectively achieve
higher precision arithmetic or enabling floating-point support in future chip
generations. Nonetheless, preliminary observations in closed-loop control
simulations hint that fast approximate solutions are sufficient for iterative
scenarios like MPC with sequential warm starts. We invite robotics labs
interested in assessing the performance of our fixed-point Quadratic
Programming (QP) solver on their cyber-physical systems to become part of
Intel’s Neuromorphic Research Community (INRC). By joining INRC, labs will
gain access to the proprietary code for running the solver on Loihi 2. They
can then apply for borrowing a Loihi 2 board for closed-loop testing in their
MPC applications. Further, with floating-point support, the current gains
observed with compute-memory co-location can be bolstered by employing sigma-
delta coding which would reduce spiking activity in the chip and consequently
TTS and ETS.

In applications where faster solves are required, the massive energy advantage
of neuromorphic architectures can be traded for additional speed by executing
multiple solver instances in parallel with different initial conditions and
selecting the best and fastest solution. In general, the customizability of
neuromorphic architectures like Intel’s Loihi 2 allows to trade solution
optimality, energy, speed, and chip resource utilization seamlessly against
each other to achieve optimal operating conditions depending on the
requirements of the task.

## Acknowledgments

We would like to thank Farbod Farshidian, a former member of the Robotics
Systems Lab, ETH Zürich, for providing the data used in this article and for
his inputs on ANYmal. We appreciate the valuable feedback on the manuscript
from Prof. Alin Albu-Schäffer from the German Aerospace Center (DLR) and TU
Munich. We thank Yulia Sandamirskaya (ZHAW, Zurich) and Akshit Saradagi (Luleå
University of Technology) who participated in disucssions and also provided
some useful suggestions for our work. Sumit Shrestha Bam and Leobardo E Campos
Macias from the Neuromorphic Computing Lab, Intel Labs provided support with
Loihi and Orin platforms. We also thank all the members of the Neuromorphic
Computing Lab, Intel Labs in general for their support in developing features
for Lava and for assistance with hardware-related issues.

## References

  * [1] J.-P. Sleiman, F. Farshidian, M. V. Minniti, and M. Hutter, “A unified mpc framework for whole-body dynamic locomotion and manipulation,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 3, pp. 4688–4695, 2021.
  * [2] C. D. Schuman, S. R. Kulkarni, M. Parsa, J. P. Mitchell, P. Date, and B. Kay, “Opportunities for neuromorphic computing algorithms and applications,” _Nature Computational Science_ , vol. 2, no. 1, pp. 10–19, Jan 2022. [Online]. Available: https://doi.org/10.1038/s43588-021-00184-y
  * [3] G. A. Fonseca Guerra and S. B. Furber, “Using stochastic spiking neural networks on spinnaker to solve constraint satisfaction problems,” _Frontiers in neuroscience_ , vol. 11, p. 714, 2017.
  * [4] M. Z. Alom, B. Van Essen, A. T. Moody, D. P. Widemann, and T. M. Taha, “Quadratic unconstrained binary optimization (qubo) on neuromorphic computing system,” in _2017 International Joint Conference on Neural Networks (IJCNN)_ , 2017, pp. 3922–3929.
  * [5] S. M. Mniszewski, “Graph partitioning as quadratic unconstrained binary optimization (qubo) on spiking neuromorphic hardware,” in _Proceedings of the International Conference on Neuromorphic Systems_ , ser. ICONS ’19. New York, NY, USA: Association for Computing Machinery, 2019. [Online]. Available: https://doi.org/10.1145/3354265.3354269
  * [6] P. T. P. Tang, T.-H. Lin, and M. Davies, “Sparse coding by spiking neural networks: Convergence theory and computational results,” _arXiv preprint arXiv:1705.05475_ , 2017.
  * [7] M. Davies, A. Wild, G. Orchard, Y. Sandamirskaya, G. A. F. Guerra, P. Joshi, P. Plank, and S. R. Risbud, “Advancing neuromorphic computing with loihi: A survey of results and outlook,” _Proceedings of the IEEE_ , vol. 109, no. 5, pp. 911–934, 2021.
  * [8] G. Orchard, E. P. Frady, D. B. D. Rubin, S. Sanborn, S. B. Shrestha, F. T. Sommer, and M. Davies, “Efficient neuromorphic signal processing with loihi 2,” in _2021 IEEE Workshop on Signal Processing Systems (SiPS)_ , 2021, pp. 254–259.
  * [9] M. Hutter, C. Gehring, D. Jud, A. Lauber, C. D. Bellicoso, V. Tsounis, J. Hwangbo, K. Bodie, P. Fankhauser, M. Bloesch _et al._ , “Anymal-a highly mobile and dynamic quadrupedal robot,” in _2016 IEEE/RSJ international conference on intelligent robots and systems (IROS)_. IEEE, 2016, pp. 38–44.
  * [10] Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,” 2023. [Online]. Available: https://www.gurobi.com
  * [11] M. ApS, _The MOSEK optimization toolbox. Version 10.0._ , 2023. [Online]. Available: https://www.mosek.com/documentation/
  * [12] M. S. Andersen and J. Dahl and L. Vandenberghe, “CVXOPT: A Python package for convex optimization,” 2012. [Online]. Available: http://abel.ee.ucla.edu/cvxopt
  * [13] H. J. Ferreau, C. Kirches, A. Potschka, H. G. Bock, and M. Diehl, “qpoases: a parametric active-set algorithm for quadratic programming,” _Mathematical Programming Computation_ , vol. 6, no. 4, pp. 327–363, Dec 2014. [Online]. Available: https://doi.org/10.1007/s12532-014-0071-1
  * [14] A. Domahidi, E. Chu, and S. Boyd, “ECOS: An OSCP solver for embedded systems,” in _2013 European Control Conference (ECC)_ , 2013, pp. 3071–3076.
  * [15] B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd, “Osqp: an operator splitting solver for quadratic programs,” _Mathematical Programming Computation_ , vol. 12, no. 4, pp. 637–672, Dec 2020. [Online]. Available: https://doi.org/10.1007/s12532-020-00179-2
  * [16] L. Yu, A. Goldsmith, and S. Di Cairano, “Efficient convex optimization on gpus for embedded model predictive control,” in _Proceedings of the General Purpose GPUs_ , ser. GPGPU-10. New York, NY, USA: Association for Computing Machinery, 2017, p. 12–21. [Online]. Available: https://doi.org/10.1145/3038228.3038234
  * [17] M. Schubiger, G. Banjac, and J. Lygeros, “GPU acceleration of admm for large-scale quadratic programming,” _Journal of Parallel and Distributed Computing_ , vol. 144, pp. 55–67, 2020. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0743731520303063
  * [18] I. McInerney, G. A. Constantinides, and E. C. Kerrigan, “A survey of the implementation of linear model predictive control on fpgas,” _IFAC-PapersOnLine_ , vol. 51, no. 20, pp. 381–387, 2018, 6th IFAC Conference on Nonlinear Model Predictive Control NMPC 2018. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S2405896318327216
  * [19] S. Lucia, D. Navarro, O. Lucia, P. Zometa, and R. Findeisen, “Optimized fpga implementation of model predictive control for embedded systems using high-level synthesis tool,” _IEEE Transactions on Industrial Informatics_ , vol. 14, no. 1, pp. 137–145, 2018.
  * [20] T. Skibik and A. A. Adegbege, “An architecture for analog vlsi implementation of embedded model predictive control,” in _2018 Annual American Control Conference (ACC)_ , 2018, pp. 4676–4681.
  * [21] A. Mancoo, S. Keemink, and C. K. Machens, “Understanding spiking networks through convex optimization,” _Advances in Neural Information Processing Systems_ , vol. 33, 2020.
  * [22] Y. Yu, P. Elango, and B. Açıkmeşe, “Proportional-integral projected gradient method for model predictive control,” _IEEE Control Systems Letters_ , vol. 5, no. 6, pp. 2174–2179, 2021.
  * [23] A. Shrestha, H. Fang, Z. Mei, D. P. Rider, Q. Wu, and Q. Qiu, “A survey on neuromorphic computing: Models and hardware,” _IEEE Circuits and Systems Magazine_ , vol. 22, no. 2, pp. 6–35, 2022.
  * [24] G. Orchard, E. P. Frady, D. B. D. Rubin, S. Sanborn, S. B. Shrestha, F. T. Sommer, and M. Davies, “Efficient neuromorphic signal processing with loihi 2,” in _2021 IEEE Workshop on Signal Processing Systems (SiPS)_. IEEE, 2021, pp. 254–259.
  * [25] F. Farshidian _et al._ , “OCS2: An open source library for optimal control of switched systems,” [Online]. Available: https://github.com/leggedrobotics/ocs2.
  * [26] M. Davies, N. Srinivasa, T.-H. Lin, G. Chinya, Y. Cao, S. H. Choday, G. Dimou, P. Joshi, N. Imam, S. Jain, Y. Liao, C.-K. Lin, A. Lines, R. Liu, D. Mathaikutty, S. McCoy, A. Paul, J. Tse, G. Venkataramanan, Y.-H. Weng, A. Wild, Y. Yang, and H. Wang, “Loihi: A neuromorphic manycore processor with on-chip learning,” _IEEE Micro_ , vol. 38, no. 1, pp. 82–99, 2018.
  * [27] M. Diehl, R. Findeisen, and F. Allgöwer, “A stabilizing real-time implementation of nonlinear model predictive control,” in _Real-Time PDE-Constrained Optimization_. SIAM, 2007, pp. 25–52.
  * [28] Y. de Viragh, M. Bjelonic, C. D. Bellicoso, F. Jenelten, and M. Hutter, “Trajectory optimization for wheeled-legged quadrupedal robots using linearized zmp constraints,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 2, pp. 1633–1640, 2019.
  * [29] K. Cheshmi, D. M. Kaufman, S. Kamil, and M. M. Dehnavi, “Nasoq: Numerically accurate sparsity-oriented QP solver,” _ACM Trans. Graph._ , vol. 39, no. 4, aug 2020. [Online]. Available: https://doi.org/10.1145/3386569.3392486

##  V Biography Section

|  Ashish Rao Mangalore completed his MSc in Neuroengineering at the the
Technical University of Munich in 2022. He is currently a Doctoral Researcher
at Intel Labs, Intel Corporation, Munich, Germany, working on algorithms for
robotic control and planning with neuromorphic architectures.
---|---
|  Gabriel Andres Fonseca Guerra received the Ph.D. degree in computer science
with a focus on stochastic processes for neuromorphic hardware from The
University of Manchester, Manchester, U.K., in 2020. He is currently a
Research Scientist with Intel Labs, Intel Deutschland GmbH, Munich, Germany,
working on algorithms and architecture development.
---|---
|  Sumedh R. Risbud received the Ph.D. degree in chemical and biomolecular
engineering with a focus on theoretical fluid mechanics and microfluidics from
Johns Hopkins University, Baltimore, MD, USA, in 2013. He is currently a
Research Scientist with Intel Labs, Intel Corporation, Santa Clara, CA, USA.
His focus at the Neuromorphic Computing Lab is on algorithms and architecture
development.
---|---
|  Philipp Stratmann completed a Dr. rer. nat. in computer science at the the
Technical University of Munich and the German Aerospace Center (DLR) in 2020.
He is currently a Research Scientist with Intel Labs, Intel Corporation,
Munich, Germany, working on algorithms and architecture modeling as a member
of the Neuromorphic Computing Lab.
---|---
|  Andreas Wild received a Dr. rer. nat. degree in physics for the development
of silicon-based electron spin qubits from the Technical University of Munich,
Germany, in 2013. Since 2015, he has been a Senior Researcher with the
Neuromorphic Computing Lab, Intel Corporation, Portland, OR, USA, where he
leads algorithm development.
---|---


11institutetext: Warsaw University of Technology, Warsaw, Poland
11email<EMAIL_ADDRESS>22institutetext: Systems
Research Institute, Polish Academy of Sciences, Warsaw, Poland 22email:
<EMAIL_ADDRESS>
# RDF Stream Taxonomy: Systematizing RDF Stream Types in Research and Practice

Piotr Sowiński 1122 0000-0002-2543-9461 Paweł Szmeja 22 0000-0003-0869-3836
Maria Ganzha 1122 0000-0001-7714-4844 Marcin Paprzycki 22 0000-0002-8069-2152

###### Abstract

Over the years, RDF streaming was explored in research and practice from many
angles, resulting in a wide range of RDF stream definitions. This variety
presents a major challenge in discussing and integrating streaming solutions,
due to the lack of a common language. This work attempts to address this
critical research gap, by systematizing RDF stream types present in the
literature in a novel taxonomy. The proposed RDF Stream Taxonomy (RDF-STaX) is
embodied in an OWL 2 DL ontology that follows the FAIR principles, making it
readily applicable in practice. Extensive documentation and additional
resources are provided, to foster the adoption of the ontology. Two realized
use cases are presented, demonstrating the usefulness of the resource in
discussing research works and annotating streaming datasets. Another result of
this contribution is the novel nanopublications dataset, which serves as a
collaborative, living state-of-the-art review of RDF streaming. The aim of
RDF-STaX is to address a real need of the community for a better way to
systematize and describe RDF streams. The resource is designed to help drive
innovation in RDF streaming, by fostering scientific discussion, cooperation,
and tool interoperability.

###### Keywords:

RDF stream Taxonomy Ontology Nanopublications.

Resource type: Ontology, documentation, nanopublications dataset
License: CC BY 4.0 International
DOI: 10.5281/zenodo.10072907
URL: https://w3id.org/stax/

##  1 Introduction

Over the years, the concept of RDF streams was investigated from many angles,
resulting in streaming serializations, querying and reasoning engines,
programming frameworks, datasets, and other resources [5, 50, 58, 60]. Without
a doubt, streaming RDF solutions are in demand, and more innovation is still
needed. However, the landscape of RDF streaming terminology is fragmented,
with many dissimilar streaming task formulations and incompatible solutions.

The term “RDF stream” is used in the literature to refer to many different
concepts, ranging from theoretical models [11], to very technical ones,
focusing on the representation and practical usage [17, 45, 50]. As noted in
past research [14, 35, 49], RDF streaming systems need more standardization in
stream exchange protocols and stream task definitions. At the same time, if
the research is to solve real-world problems, the variety of the existing RDF
streaming task formulations should be embraced, not limiting oneself to one
specific type of RDF streams. However, up until now, there was very little
academic discussion about the existing RDF stream types – what stream types
are used, how they relate to each other, and which use cases are they
applicable to. This paper aims to address this critical research gap.

The main contribution of this work is the RDF Stream Taxonomy (RDF-STaX),
embodied in an OWL 2 DL ontology. This novel taxonomy systematizes the
existing RDF stream types on the basis of a broad state of the art review.
RDF-STaX aims to be a practical and useful resource for researchers and
practitioners, enabling them to semantically annotate RDF stream types in
publications, software, and streams published on the Web. To achieve this,
RDF-STaX is accompanied with extensive documentation, including usage
examples. Finally, two implemented applications of RDF-STaX are presented – a
living state-of-the-art review of RDF streaming using nanopublications, and
annotating stream types in RiverBench datasets.

##  2 Literature Review

The primary goal of this paper is to introduce a taxonomy of RDF stream types,
which naturally must be grounded in the state of the art to be relevant. As no
comprehensive review of this topic is available, here we attempt to summarize
the most significant works that use the concept of RDF streams.

The scope of this study only includes RDF streams that can be fully
represented using the RDF 1.1 W3C Recommendation [10]. This notably excludes
stream models that do not have a direct translation to RDF, such as RSP-QL
[11]. However, due to the importance of such models, they are briefly
discussed below. The reason behind this choice is that only streams fully
representable in RDF can be easily exchanged and published on the Web, while
the theoretical models have more limited applicability, e.g., only within one
specific solution (e.g., a stream reasoning engine). As shown below, this
scope choice still leaves a lot of variety to be explored.

###  2.1 Review Methodology

The review was conducted by starting from several survey papers and books that
focus on areas of research related to RDF streaming [5, 29, 39, 40, 43, 46,
53, 58, 60, 63], such as RDF data management, linked streaming data, and
stream reasoning. Besides the works mentioned in these reviews, additional
papers and software were added based on the authors’ expertise and by
searching for keywords “RDF stream” and “RDF streaming” in Google Scholar. The
review focused on works which use streams of RDF-based elements (triples,
quads, graphs, datasets), although works that do not meet this criterion are
also mentioned as needed. For many of the examined works, determining the
exact nature of the stream was not trivial, due to unclear descriptions and a
lack of standardized terminology. Therefore, not only the papers were
examined, but also the code and documentation, where available.

###  2.2 RDF Streaming Protocols

One area of research that mentions RDF streams are works focusing on streaming
protocols for transmitting RDF data. One of the earlier examples is Streaming
HDT (S-HDT) [26], which facilitates streaming RDF data in IoT devices. More
specifically, producers (IoT devices) emit a stream of compressed, unnamed RDF
graphs. RDSZ [18] is a later method that also attempts streaming compressed
RDF graphs over the network. ERI [17] is a similar approach, however, it has
several views of the RDF stream. At the highest level, ERI streams a
continuous sequence of triples that is then divided into discrete blocks (RDF
graphs). Then, on the lowest level, these graphs are decomposed into _subject-
molecules_ (graphs with a single RDF subject) that are then streamed over the
network. Therefore, ERI has three different views of the streaming problem,
with each corresponding to a different level in the protocol.

The RDF EXI communication protocol for constrained devices [28] focuses on
streaming RDF graphs. Finally, the recent Jelly protocol [50] treats RDF
streams similarly to ERI, with it streaming a sequence of RDF statements
divided into discrete elements (stream frames). The main difference is that
Jelly can also stream quad statements, making it generalizable to RDF
datasets.

###  2.3 Stream Processing and Reasoning

There is a large body of research on the topics of RDF stream reasoning and
stream processing, where a special focus is often placed on the time
annotations of stream elements. We could find one work in this category that
did not consider the temporal aspect, an early proposal for a streaming SPARQL
engine from 2007 by Groppe et al. [23]. The proposed engine executes queries
over streams of RDF triples.

Most publications in this category focus on the inner workings of
querying/reasoning engines, and adopt task formulations that are not fully
grounded in the RDF specification. The most popular such formulation is the
stream of timestamped triples [1, 3, 4, 8, 11, 13, 30, 34, 57, 63], where a
stream is a sequence of $\langle triple,timestamp\rangle$ tuples. There are
many variations of this task, with time intervals instead of timestamps [1],
multiple timestamps per triple [12, 57], and different time domains. However,
this model (and other equivalent or similar models, e.g., time-varying graphs
[14, 33, 57]) by itself is not enough to fully realize an RDF stream – this
would require encoding the time information in RDF, which is often omitted in
these works.

The lack of grounding in the RDF specification of the timestamped triple model
is a known problem [8], and solutions to it were proposed. The most prominent
formulation is the stream of timestamped named graphs, where each stream
element is a named RDF graph. The timestamp (or other metadata) of this graph
is added by making statements in the default graph about the named graph’s
name node [7, 41, 62]. This representation was possibly first proposed by
Tappolet & Bernstein in 2009 [56], and was then expanded by the W3C RSP
Community Group, which created a draft specification for the RSP Data Model
[47]. The RSP Data Model uses the aforementioned formulation to define RDF
streams, but also mentions that RSP engines may consume streams of graphs,
datasets, or named graphs and then turn them into RDF streams proper by
associating each element with a timestamp. The RSP Data Model is the most
mature and best-grounded model for representing timestamped streams, having
been drafted by the community, and even proposing the formal semantics of RDF
streams. However, it was never made into a W3C Recommendation, and the RSP
Community Group now appears to be
inactive111https://lists.w3.org/Archives/Public/public-rsp/2023Mar/0000.html.

Time-Annotated RDF (TA-RDF) [48] is an alternative RDF representation for the
timestamped stream problem (more precisely, TA-RDF has a direct translation to
RDF). It identifies each stream element as an URI node in an RDF graph. The
data relevant to that stream element is then attached to the node. This boils
down to each stream element being an RDF graph in which a single node serves
as the “point of entry”. This model is notably less flexible than the RSP Data
Model. A similar approach is used by Stream Containers [49], a framework for
publishing RDF streams on the Web. There, a stream is a sequence of unnamed
RDF graphs that are referenced by their URIs. Each URI points to a node (the
subject) within one of the graphs, and the temporal information is also
contained within this graph.

One auxiliary RDF stream definition also appears in this category. The VoCaLS
vocabulary for describing linked streams [59] defines an RDF stream as a
potentially infinite sequence of RDF graphs and/or triples. This definition is
used in practice in the RDF4J API [57], whose YASPER implementation can
consume streams of RDF graphs or RDF triples.

###  2.4 Streaming Semantic Annotation and Translation

Several systems were developed for streaming semantic annotation (lifting) and
translation. RMLStreamer [24, 45] annotates data using the RML language [15],
outputting a stream of RDF datasets. CARML [9] is a Java library that provides
generic facilities for annotating data using RML. It supports outputting a
stream of RDF quad statements (using RDF4J Rio [16]), which corresponds to a
single RDF dataset. CARML does not natively support streams of datasets, and
thus it operates on a different abstraction level than RMLStreamer. This
limitation is addressed by the Semantic Annotation enabler [55] from ASSIST-
IoT [54], which outputs a stream of RDF datasets. SPARQL-Generate [38] is an
extension of the SPARQL language, which allows for generating RDF from various
data sources. Its reference implementation222https://github.com/sparql-
generate/sparql-generate supports outputting a stream of RDF triples (using
Apache Jena RIOT [2]).

Last in this category is the Inter Platform Semantic Mediator (IPSM) [20],
which translates a stream of RDF graphs into another such stream, in real
time. Although on a logical level IPSM processes RDF graphs, it outputs a
stream of datasets, where each dataset has two named graphs – one containing
the translated RDF, and the other with metadata about the translation itself.

###  2.5 Semantic Streaming Applications

Over the years, RDF streams were employed in various real-life use cases. One
such example is DBpedia-Live [44] – a now-defunct service that published
changes to the DBpedia knowledge base in real time. Two streams were published
– deleted and added triples. In each stream, the elements were RDF graphs, in
the form of N-Triples files.

RDF streams are also commonly used in semantic sensor networks [39]. In this
context, the Graph of Things (GoT) [36] was proposed, which uses streams of
RDF graphs. Another common use case is monitoring social media activity. Here,
a survey by Keskisärkkä & Blomqvist [29] noted that RDF streams should have
RDF graphs as elements. However, they also acknowledge that RDF streams can
have RDF triples as elements. The recent proposal for a live open scientific
knowledge graph [37] uses streams of RDF graphs to monitor scientific and
social activity in real time.

###  2.6 Streaming I/O

The last broad category of RDF streaming solutions are those that process
simple sequences of RDF statements (triples or quads) for input/output (I/O)
operations. Two examples are the RDF4J Rio toolkit [16] and Apache Jena’s RIOT
[2], both of which can parse and serialize streams of statements, reading from
or writing to a Java byte stream. The two most obvious serializations for this
task are N-Triples and N-Quads, however, Jena also supports _streamed block
formats_ for Turtle and Trig, where statements are transmitted in small
batches (blocks).

###  2.7 Summary

The review uncovered a wide variety of task formulations for RDF streams. It
should be noted that most of the identified works use the same term (RDF
stream) to describe very different concepts. The review also highlighted an
important distinction between theoretical models of RDF streams (e.g.,
timestamped triples) and practical ones. This distinction was also observed
earlier in several works [5, 8, 12, 49]. Another contrasting feature is the
use of graphs or datasets as stream elements, versus triple or quad
statements. This was also noticed in earlier works focusing on the practical
aspects of implementing RDF streams [5, 29].

Worth noting is that some works have several views of the same RDF stream. For
example, ERI [17] views its RDF streams as a flow of triples, blocks (RDF
graphs), or subject-molecules (RDF subgraphs), depending on the level of
abstraction. This suggests that describing the type of an RDF stream depends
on the context in which it is considered, or, metaphorically, one’s
perspective. In fact, an N-Triples file would be considered by RDF4J’s Rio
[16] as a stream of triples, while an application like DBpedia-Live [44] or
IPSM [20] would see it as a single element in a stream of graphs.

##  3 Proposed Systematization

In what follows, we propose a set of definitions for the types of RDF streams
present in the literature and current practice. Then, Section 3.2 organizes
these definitions in the RDF Stream Taxonomy, and Section 3.3 links the
proposed stream types to the state of the art. The basis for all following
definitions is the RDF 1.1 W3C Recommendation [10], with the aim of making the
definitions readily applicable in the context of existing, RDF 1.1-compliant
software.

The model-theoric semantics of RDF streams are not considered in this work.
Instead, the proposed semi-formal definitions can be used as a universal basis
on top of which the formal semantics can be defined, as needed. This is
motivated by, firstly, the semantics of RDF streams being irrelevant for some
of the discussed application areas (e.g., streaming protocols, streaming I/O).
Secondly, only the semantics of RDF graphs are well-defined – there are no
agreed-upon formal semantics for RDF datasets [65], and there are similarly
many ways to approach this topic for RDF streams. Therefore, we leave this for
future discussion.

###  3.1 RDF Stream Definitions

We start by defining a universal, abstract RDF stream that will serve as a
common denominator for further discussion:

###### Definition 1

An RDF stream is an ordered, potentially infinite sequence of RDF stream
elements.

This definition by itself cannot be used in practice, as it does not specify
what are the RDF stream elements. Thus, we specialize this definition further:

###### Definition 2

A grouped RDF stream is an RDF stream whose elements are either RDF graphs or
RDF datasets.

###### Definition 3

A flat RDF stream is an RDF stream whose elements are statements (either RDF
triples or RDF quads).

Grouped and flat RDF streams are still abstract, however, they correspond to
an important distinction between streams of groups of statements and streams
of statements. With this, we can define the concrete types of RDF streams:

###### Definition 4

An RDF graph stream is a grouped RDF stream whose elements are unnamed
(default) RDF graphs.

In other words, an element of an RDF graph stream is a set of triples. This is
a commonly used formulation that can be further specialized:

###### Definition 5

An RDF subject graph stream is an RDF graph stream in which every element
contains an IRI node (called the subject node) that uniquely identifies the
graph in the stream. Every other node in the graph can be reached by
traversing triples, starting from the subject node.

RDF subject graph streams or similar formulations were proposed to handle
timestamped RDF streams (TA-RDF [48] and Stream Containers [49]). ERI [17]
uses a similar formulation for subject-molecules, but its subject IRIs are
unique only within one block. The proposed definition is slightly broader than
the timestamped models, while still being useful – the advantage is that the
element can be identified by an IRI, without using RDF datasets. The rest of
the element can be discovered with what can be intuitively thought of as RDF
graph connectivity.

We can then move on to streams of RDF datasets:

###### Definition 6

An RDF dataset stream is a grouped RDF stream whose elements are RDF datasets.

It should be noted here that although an RDF graph stream may seem like a
special case of an RDF dataset stream, it is not. According to RDF 1.1, an RDF
dataset is not a generalization of an RDF graph, but rather a collection of
RDF graphs. Thus, the definitions of RDF dataset streams and RDF graph streams
are not directly related in the taxonomy. It should be noted, however, that an
RDF graph stream can be trivially transformed into an RDF dataset stream.

This definition can be further restricted to one named graph per element:

###### Definition 7

An RDF named graph stream is an RDF dataset stream in which every element has
exactly one named RDF graph pair $\langle n,G\rangle$, where $G$ is an RDF
graph, and $n$ is the graph name. Apart from graph $G$, the dataset may
contain any number of triples in the default graph.

This is a simplified version of the RSP Data Model [47], without the temporal
aspect. Although we could find only one reference to this stream type in the
literature (RSP engines can consume such streams [47]), it is an intuitively
important specialization of the RDF dataset stream. Here, every element
corresponds to one named RDF graph with some optional information (metadata)
about it. As with RDF subject graph streams, this has the advantage of
identifying an element by IRI, albeit with more flexibility as to the
element’s contents.

With this, we can move on to the timestamped variant:

###### Definition 8

A timestamped named graph is an RDF dataset in which:
(1) there is exactly one named RDF graph pair $\langle n,G\rangle$, where $G$
is an RDF graph, and $n$ is the graph name;
(2) the default graph includes a timestamp triple $\langle n,p,t\rangle$,
where $p$ is a timestamp predicate that relates $t$, called the timestamp, and
the graph $G$.

###### Definition 9

A timestamped RDF named graph stream is an RDF named graph stream in which
every element is a timestamped named graph. The elements that share the same
timestamp predicate $p$ are ordered by the partial order associated with $p$.

These definitions were derived directly from the draft RSP Data Model [47].

Finally, we define concrete flat RDF stream types:

###### Definition 10

A flat RDF triple stream is a flat RDF stream whose elements are triples.

###### Definition 11

A flat RDF quad stream is a flat RDF stream whose elements are quads.

An “RDF quad” is a term that is often used by practitioners, but not defined
in the RDF 1.1 Recommendation. It is however defined in the RDF 1.2 Working
Draft [25], and thus we use the RDF 1.2 definition of quads here.

Flat RDF streams can be represented simply as N-Triples or N-Quads files,
however, contrary to RDF graphs and datasets, they have a defined order of
statements. Similarly to RDF graph and dataset streams, a triple stream is not
a subclass of a quad stream, because a triple is not a special case of a quad.
However, a trivial transformation from one to the other can be performed, by
stating explicitly that the triples belong to the default graph.

Grouped and flat RDF streams are notably interrelated, as any RDF graph stream
can be flattened into an RDF triple stream, by simply listing and
concatenating the statements in each of its elements – the same is true for
RDF dataset streams and RDF quad streams. The reverse is also possible, the
elements of a flat stream can be grouped into a grouped stream. Such
operations are in fact common in streaming applications [5, 17, 29, 50].

Finally, for all of the above definitions, their generalized variants can be
trivially derived (e.g., generalized RDF graph stream), by using generalized
triples and generalized datasets. We skip these definitions for the sake of
brevity.

###  3.2 RDF Stream Taxonomy

The proposed definitions form a taxonomical structure of task formulations
(RDF Stream Taxonomy – RDF-STaX), summarized in Figure 1. This overview allows
us to observe that each concrete RDF stream type uses one of the four element
types: graph, dataset, triple, and quad, possibly with additional restrictions
on them. In fact, these four types of elements seem to be the only conceivable
ones that can be derived from the RDF 1.1 specification. For each of them,
representing the element is a known and solved problem (RDF serializations),
and thus they can be easily used in practical applications.

Figure 1: Overview of the RDF Stream Taxonomy (RDF-STaX).

###  3.3 Correspondence to the State of the Art

Finally, we link the proposed RDF stream types to the definitions used in
state-of-the-art research and software – Table 1 presents such a summary. As
noted in Section 2.7, a single RDF stream can be viewed from multiple
perspectives, which is reflected in the table, with some items appearing more
than once. In some cases the correspondence is not ideal and there may be
insignificant differences between the definitions proposed here and those in
the literature. The short descriptions presented in the table are expanded
upon in the nanopublications dataset, as described in Section 5.1.

Stream type |  Uses
---|---
RDF graph stream |  DBpedia-Live [44], ERI (blocks) [17], GoT [36], IPSM (logical level) [20], Jelly (stream frames) [50], Keskisärkkä & Blomqvist [29], Live open scientific knowledge graphs [37], RDF EXI [28], RDSZ [18], RSP Data Model (can be consumed) [47], RSP4J YASPER (can be consumed) [57], S-HDT [26], VoCaLS [59]
RDF subject
graph stream |  ERI (subject-molecule stream, only within a block) [17], TA-RDF [48], Stream Containers [49]
RDF dataset stream |  IPSM (output) [20], Jelly (stream frames) [50], RMLStreamer [24, 45], RSP Data Model (can be consumed) [47], Semantic Annotation enabler [55]
RDF named
graph stream |  RSP Data Model (can be consumed) [47]
Timestamped RDF
named graph stream |  Linked Data Notifications for RDF streams [7], RSP Data Model [47], Tappolet & Bernstein [56], TripleWave [41], Wu et al. [62]
Flat RDF
triple stream |  Apache Jena RIOT [2], ERI (high level) [17], Groppe et al. [23], Jelly (high level) [50], Keskisärkkä & Blomqvist (mentioned) [29], RDF4J Rio [16], RSP4J YASPER (can be consumed) [57], SPARQL-Generate [38], VoCaLS [59]
Flat RDF
quad stream |  Apache Jena RIOT [2], CARML [9], Jelly (high level) [50], RDF4J Rio [16]
Table 1: RDF stream type usage in research and software, according to RDF-
STaX.

Different types of RDF streams appear to be applicable in different settings.
In the context of network streaming applications, most commonly used are
grouped RDF streams. Flat RDF streams, on the other hand, are used for
streaming I/O and internally by various applications.

##  4 RDF-STaX Ontology

To make the taxonomy readily applicable, it was modeled as an OWL 2 DL
ontology333https://w3id.org/stax/1.0.0/ontology (Figure 2). Stream types are
instances of either stax:AbstractStreamType or stax:ConcreteStreamType class,
with taxonomical relations being realized using SKOS in the OWL DL version
[27, 42]. Each stream type is accompanied by a label, formal definition, and
usage example.

Figure 2: Classes and object properties in the RDF-STaX ontology.

The ontology includes rich semantic relations between stream types. Properties
stax:canBeFlattenedInto and stax:canBeGroupedInto relate grouped and flat
stream types that can be easily converted into one another (e.g., an RDF graph
stream can be flattened into a flat RDF triple stream). The property
stax:canBeTriviallyExtendedInto is used for graph- and triple-based streams,
to indicate that they can be trivially turned into dataset- and quad-based
streams, respectively. This transformation consists of stating explicitly that
the triples are in the default graph. Object property chains are defined in
the ontology to allow reasoning on these relations, exploiting the taxonomical
relations from SKOS.

It should be stressed that RDF-STaX does not define a class for RDF streams,
but rather classes for RDF stream _types_. It also defines a class for RDF
stream type usages, which can be thought of as subjective views of how an RDF
stream is used. As described in detail in the
documentation444https://w3id.org/stax/use-it, the expected usage pattern is
for users to create instances of the stax:RdfStreamTypeUsage class to annotate
research works, software, or datasets, with each instance corresponding to a
different view or use case of the stream. This pattern was selected due to the
inherent subjectivity of determining the types of RDF streams, as discussed in
Section 2.7. Below is an example of how this pattern may be used to annotate a
DCAT [6] Dataset:

⬇

@prefix dcat: <http://www.w3.org/ns/dcat#> .

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .

@prefix stax: <https://w3id.org/stax/ontology#> .

\par_:dataset a dcat:Dataset ;

# … other properties of the dataset …

stax:hasStreamTypeUsage [

a stax:RdfStreamTypeUsage ;

stax:hasStreamType stax:datasetStream ;

rdfs:comment "The data is a sequence of RDF datasets."@en

] , [

a stax:RdfStreamTypeUsage ;

stax:hasStreamType stax:flatQuadStream ;

rdfs:comment "The data can be viewed as a flat sequence of RDF quads."@en

] .

The ontology’s documentationfootnote 3 contains a detailed description of
every class, property, and individual.

###  4.1 Availability and Sustainability

The sources of the ontology and its documentation are hosted on
GitHub555https://github.com/RDF-STaX/rdf-stax.github.io. The repository
includes continuous integration and deployment (CI/CD) scripts that
automatically validate the ontology’s profile, generate documentation, run an
OWL 2 reasoner to add more assertions, package the ontology into a number of
formats, and publish it on the website666https://w3id.org/stax. Two versions
of the ontology are published: OWL 2 DL, which can be used with reasoners; and
OWL 2 Full, which contains more metadata and alignments to other vocabularies.

The ontology uses best findability, accessibility, interoperability, and
reusability (FAIR) practices developed by the community [22], achieving 86%
score in _FOOPS!_ [21] and 4/4 stars in DBpedia Archivo [19]. All releases of
the ontology, including the OWL 2 DL and OWL 2 Full variants, are distributed
through the RDF-STaX website, under a permanent URL. The ontology is also
archived in Zenodo [51].

RDF-STaX is an open and freely-licensed project, welcoming contributions to
the ontology, its documentation, and tooling. A usage guidefootnote 4 with
several use case scenarios and examples was prepared to facilitate adoption.
To ensure long-term sustainability, a comprehensive contribution guide was
provided777https://w3id.org/stax/1.0.0/contributing, along with a public issue
tracker888https://github.com/RDF-STaX/rdf-stax.github.io/issues. The project
is entirely hosted on permanently free infrastructure, which should ensure its
long-term stability.

###  4.2 Comparison with Other Ontologies

To the best of our knowledge, there is no other ontology or vocabulary that
would model RDF stream types. As previously noted, the RDF-STaX ontology
purposefully does not define classes for RDF streams, but rather focuses on
subjective RDF stream usages. This difference makes other ontologies non-
overlapping – instead, RDF-STaX can naturally complement them. To this end,
the documentation includes examples of using RDF-STaX with these complementary
ontologies (VoCaLS, VoID, and DCAT)footnote 4. The usage pattern is to define
an RDF stream / dataset with these ontologies as usual, and add the
stax:hasStreamTypeUsage property to indicate the stream type, according to
RDF-STaX. The same pattern can be used with any future ontology for describing
streams or datasets.

The VoCaLS vocabulary for describing published RDF streams [59] defines the
RDFStream class for potentially infinite sequences of RDF graphs and/or
triples. These streams can be thus annotated as RDF graph streams or flat RDF
triple streams in RDF-STaX. The VoID vocabulary [64] describes datasets with
RDF data (not _RDF datasets_ as per RDF 1.1), which can be viewed as flat RDF
triple streams. The more general DCAT [6] describes datasets and their
distributions, which may be RDF streams.

The RDF-STaX ontology also defines four element types (RDF graphs, triples,
quads, and datasets). In this regard, we could identify only the SPARQL 1.1
Service Description vocabulary [61], which has the sd:Graph and sd:Dataset
classes for RDF graphs and datasets. These classes were aligned with the
corresponding terms in RDF-STaX, using the skos:relatedMatch property.

##  5 Applications

RDF-STaX was created with several applications in mind. Firstly, it can be
used to describe stream types used in research and software, to easily compare
different solutions and foster compatibility. Secondly, it may be employed to
semantically annotate published datasets and streams, improving their
accessibility and interoperability. Both of these use cases have already been
realized in practice.

###  5.1 Nanopublications

A nanopublication is a small unit of scientific knowledge published in RDF
[31] – it can be an opinion, a measurement, or any other assertion.
Nanopublications are a natural way to express statements about scientific
works or software due to their strong provenance mechanisms and citeability.
This fits well the pattern of subjective statements about stream types, which
is used in RDF-STaX. To make it easier to create nanopublications with the
RDF-STaX ontology, a template was prepared for Nanodash, an open
nanopublication editor [32]. The template along with the accompanying
manual999https://w3id.org/stax/1.0.0/nanopubs makes it easy to create and
publish semantic assertions such as “X uses stream type Y because Z”,
requiring the user only to fill out a simple online form.

The results from the survey conducted in this paper (as summarized in Section
3.3) were published as 32 nanopublications, including a more detailed
discussion of the usages than what could fit in the paper. The RDF-STaX
nanopublications are packaged as a single knowledge graph in a CI/CD pipeline
and published automatically on the websitefootnote 9. Anyone can contribute to
the dataset by simply publishing nanopublications with the provided template.
The dataset can serve as a living state-of-the-art review, allowing one to
easily compare and discuss works on RDF streaming, in a structured manner.

###  5.2 RiverBench

RiverBench is an open RDF streaming benchmark suite, containing heterogeneous
streaming datasets that are published using automated pipelines, following
FAIR principles [52]. RiverBench integrates with the RDF-STaX ontology,
requiring all datasets to be annotated with their stream types. Each dataset
has two stream types assigned, one for the grouped stream formulation and
another for the flat. The consistency of the annotations is checked in CI/CD
using SHACL rules and the semantic relations defined in RDF-STaX (SKOS
taxonomy properties and stax:canBeFlattenedInto). The datasets are then
organized into benchmark profiles by their stream type. The published dataset
documentation and RDF metadata based on DCAT [6] also includes the RDF stream
types.

At the time of writing, RiverBench’s 12 datasets use each stream type in RDF-
STaX, except the RDF named graph stream (but there are examples of the
timestamped variant). Detailed information about this use case along with
examples are available on the website101010https://w3id.org/stax/1.0.0/uses.

##  6 Discussion and Future Work

Although the “RDF stream” is a term that is now ubiquitous in research, it is
used to describe many different concepts. There is no universally accepted
language for describing RDF streams, which leads to a situation in which RDF
streaming solutions become hard to assess, compare, and connect together. For
example, forming a pipeline composed of a stream annotator, translator,
streaming protocol, and a reasoner currently appears to be a tough challenge,
as it is hard to determine what exactly is an RDF stream for each of these
tools.

It appears that the variety of RDF stream formulations is here to stay. Each
of the different definitions has its merits and use cases, and none of them
should be disregarded. Instead, we call to embrace the variety of RDF streams
by systematizing them in one shared taxonomy. The taxonomy with its semantic
relations (taxonomical, flattening, grouping, extending – see Section 4)
allows one to reason about stream types not only in terms of subclassing, but
also in terms of possible conversions between them. This, we hope, will be a
much needed step in the direction of making RDF stream applications more
compatible with each other.

RDF-STaX is embodied in an ontology that makes the taxonomy readily usable in
practice. The ontology does not attempt to replace any existing vocabulary for
describing streams or datasets, but rather aims to complement them. We hope
that by being non-overlapping by design and focused on a single purpose, RDF-
STaX will remain useful and relevant in the long term. The two presented use
cases, both of which were already realized in practice, are very common and
well-known to the community, making the ontology all the more relevant.

Another result of this work is the nanopublications dataset, which is a
collaborative, living state-of-the-art review of RDF streaming.
Nanopublications, in our view, are a natural way to structure intersubjective
scientific discourse. It is possible for example, to comment on other
nanopublications, confirm or disagree with them, all in a structured manner.
Here we propose to use this powerful tool for a very narrow field of science,
but its possible future applications are certainly much broader. We encourage
other researchers to contribute their perspectives to the dataset or to
comment on the existing assertions.

As for future work, the theory presented in this contribution notably does not
tackle the formal semantics of RDF streams. As with RDF datasets, it is
unlikely that there can be single, unifying semantics for streams, but
nonetheless, we see this area as worth exploring in the future. The presented
survey of RDF streaming is also not a systematic review – it only serves as a
basis for the discussion in this work. Producing a systematic review of RDF
streaming would be very valuable to the community, and we hope that the
proposed taxonomy and nanopublication tooling will make creating it easier.

##  7 Conclusion

In this work we propose the RDF Stream Taxonomy, which systematizes RDF stream
definitions found in the literature. The taxonomy uncovered the variety of RDF
streaming in research and practice, highlighting the open challenge of making
the different applications compatible with each other. The proposed RDF-STaX
ontology embodies the semantic relations between stream types in the taxonomy,
and makes the definitions readily applicable. The ontology positions itself as
complementary to existing vocabularies, and employs a flexible approach of
making subjective statements about the types of RDF streams. The ontology and
its documentation are fully open and follow best practices for FAIR developed
by the community.

The ontology was applied in two use cases – annotating research works in
nanopublications, and describing RDF stream types of streaming datasets. The
nanopublications dataset is a living state-of-the-art review that anyone can
contribute to, using the provided documentation and tooling. The second use
case highlights how RDF-STaX can be used to annotate published streaming
datasets, integrating with other vocabularies.

## References

  * [1] Anicic, D., Fodor, P., Rudolph, S., Stojanovic, N.: EP-SPARQL: a unified language for event processing and stream reasoning. In: Proceedings of the 20th international conference on World wide web. pp. 635–644 (2011)
  * [2] Apache Software Foundation: Working with RDF streams in Apache Jena (2023), https://jena.apache.org/documentation/io/streaming-io.html, accessed on May 7, 2023
  * [3] Barbieri, D.F., Braga, D., Ceri, S., Valle, E.D., Grossniklaus, M.: Querying RDF streams with C-SPARQL. ACM SIGMOD Record 39(1), 20–26 (2010)
  * [4] Bolles, A., Grawunder, M., Jacobi, J.: Streaming SPARQL–extending SPARQL to process data streams. In: The Semantic Web: Research and Applications: 5th European Semantic Web Conference, ESWC 2008, Tenerife, Canary Islands, Spain, June 1-5, 2008 Proceedings 5. pp. 448–462. Springer (2008)
  * [5] Bonte, P., Tommasini, R.: Streaming linked data: A survey on life cycle compliance. Journal of Web Semantics 77, 100785 (2023)
  * [6] Browning, D., Beltran, A.G., Perego, A., Winstanley, P., Cox, S., Albertoni, R.: Data catalog vocabulary (DCAT) - version 3. W3C working draft, W3C (Mar 2023), https://www.w3.org/TR/2023/WD-vocab-dcat-3-20230307/
  * [7] Calbimonte, J.P.: Linked data notifications for RDF streams. In: Proceedings of the Web Stream Processing workshop (WSP 2017) and the 2nd International Workshop on Ontology Modularity, Contextuality, and Evolution (WOMoCoE 2017) co-located with 16th International Semantic Web Conference (ISWC 2017). 22 October 2017 (2017)
  * [8] Calbimonte, J.P., Corcho, Ó.: Evaluating SPARQL queries over linked data streams. In: Linked Data Management, pp. 165–190. Chapman and Hall/CRC (2016)
  * [9] CARML contributors: CARML: A pretty sweet RML engine, for RDF (2023), https://github.com/carml/carml, accessed on November 2, 2023
  * [10] Cyganiak, R., Wood, D., Lanthaler, M.: RDF 1.1 concepts and abstract syntax. W3C recommendation, W3C (Feb 2014), https://www.w3.org/TR/2014/REC-rdf11-concepts-20140225/
  * [11] Dell’Aglio, D., Della Valle, E., Calbimonte, J.P., Corcho, O.: RSP-QL semantics: A unifying query model to explain heterogeneity of RDF stream processing systems. International Journal on Semantic Web and Information Systems (IJSWIS) 10(4), 17–44 (2014)
  * [12] Dell’Aglio, D., Calbimonte, J.P., Balduini, M., Corcho, O., Della Valle, E.: On correctness in RDF stream processor benchmarking. In: The Semantic Web–ISWC 2013: 12th International Semantic Web Conference, Sydney, NSW, Australia, October 21-25, 2013, Proceedings, Part II 12. pp. 326–342. Springer (2013)
  * [13] Dell’Aglio, D., Calbimonte, J.P., Della Valle, E., Corcho, O.: Towards a unified language for RDF stream query processing. In: European Semantic Web Conference. pp. 353–363. Springer (2015)
  * [14] Dell’Aglio, D., Dao-Tran, M., Calbimonte, J.P., Le Phuoc, D., Della Valle, E.: A query model to capture event pattern matching in RDF stream processing query languages. In: European Knowledge Acquisition Workshop. pp. 145–162. Springer (2016)
  * [15] Dimou, A., Vander Sande, M., Colpaert, P., Verborgh, R., Mannens, E., Van de Walle, R.: RML: A generic language for integrated RDF mappings of heterogeneous data. Ldow 1184 (2014)
  * [16] Eclipse Foundation, Inc.: Parsing and writing RDF with Rio (2023), https://rdf4j.org/documentation/programming/rio/, accessed on May 7, 2023
  * [17] Fernández, J.D., Llaves, A., Corcho, O.: Efficient RDF interchange (ERI) format for RDF data streams. In: International Semantic Web Conference. pp. 244–259. Springer (2014)
  * [18] Fernández, N., Arias, J., Sánchez, L., Fuentes-Lorenzo, D., Corcho, Ó.: RDSZ: an approach for lossless RDF stream compression. In: European Semantic Web Conference. pp. 52–67. Springer (2014)
  * [19] Frey, J., Streitmatter, D., Götz, F., Hellmann, S., Arndt, N.: DBpedia Archivo: a web-scale interface for ontology archiving under consumer-oriented aspects. In: Semantic Systems. In the Era of Knowledge Graphs: 16th International Conference on Semantic Systems, SEMANTiCS 2020, Amsterdam, The Netherlands, September 7–10, 2020, Proceedings 16. pp. 19–35. Springer International Publishing (2020)
  * [20] Ganzha, M., Paprzycki, M., Pawłowski, W., Szmeja, P., Wasielewska, K.: Streaming semantic translations. In: 2017 21st international conference on system theory, control and computing (ICSTCC). pp. 1–8. IEEE (2017)
  * [21] Garijo, D., Corcho, O., Poveda-Villalón, M.: FOOPS!: An ontology pitfall scanner for the FAIR principles. In: ISWC (Posters/Demos/Industry) (2021)
  * [22] Garijo, D., Poveda-Villalón, M.: Best practices for implementing FAIR vocabularies and ontologies on the Web. In: Applications and Practices in Ontology Design, Extraction, and Reasoning, pp. 39–54. IOS Press (2020)
  * [23] Groppe, S., Groppe, J., Kukulenz, D., Linnemann, V.: A SPARQL engine for streaming RDF data. In: 2007 Third International IEEE Conference on Signal-Image Technologies and Internet-Based System. pp. 167–174. IEEE (2007)
  * [24] Haesendonck, G., Maroy, W., Heyvaert, P., Verborgh, R., Dimou, A.: Parallel RDF generation from heterogeneous big data. In: Proceedings of the International Workshop on Semantic Big Data. pp. 1–6 (2019)
  * [25] Hartig, O., Champin, P.A., Kellogg, G.: RDF 1.2 concepts and abstract syntax. W3C working draft, W3C (Oct 2023), https://www.w3.org/TR/2023/WD-rdf12-concepts-20231013/
  * [26] Hasemann, H., Kröller, A., Pagel, M.: RDF provisioning for the Internet of Things. In: 2012 3rd IEEE International Conference on the Internet of Things. pp. 143–150. IEEE (2012)
  * [27] Jupp, S., Bechhofer, S., Stevens, R.: SKOS with OWL: Don’t be full-ish! In: OWLED. vol. 432, pp. 2009–2 (2008)
  * [28] Käbisch, S., Peintner, D., Anicic, D.: Standardized and efficient RDF encoding for constrained embedded networks. In: European Semantic Web Conference. pp. 437–452. Springer (2015)
  * [29] Keskisärkkä, R., Blomqvist, E.: Semantic complex event processing for social media monitoring–a survey. In: Proceedings of Social Media and Linked Data for Emergency Response (SMILE) Co-located with the 10th Extended Semantic Web Conference, Montpellier, France. CEUR workshop proceedings (May 2013) (2013)
  * [30] Komazec, S., Cerri, D., Fensel, D.: Sparkwave: continuous schema-enhanced pattern matching over RDF data streams. In: Proceedings of the 6th ACM International Conference on Distributed Event-Based Systems. pp. 58–68 (2012)
  * [31] Kuhn, T., Barbano, P.E., Nagy, M.L., Krauthammer, M.: Broadening the scope of nanopublications. In: The Semantic Web: Semantics and Big Data: 10th International Conference, ESWC 2013, Montpellier, France, May 26-30, 2013. Proceedings 10. pp. 487–501. Springer (2013)
  * [32] Kuhn, T., Taelman, R., Emonet, V., Antonatos, H., Soiland-Reyes, S., Dumontier, M.: Semantic micro-contributions with decentralized nanopublication services. PeerJ Computer Science 7, e387 (2021)
  * [33] Le Phuoc, D., Dao-Tran, M., Le Tuan, A., Duc, M.N., Hauswirth, M.: RDF stream processing with CQELS framework for real-time analysis. In: Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems. pp. 285–292 (2015)
  * [34] Le-Phuoc, D., Dao-Tran, M., Xavier Parreira, J., Hauswirth, M.: A native and adaptive approach for unified processing of linked streams and linked data. In: International Semantic Web Conference. pp. 370–388. Springer (2011)
  * [35] Le-Phuoc, D., Polleres, A., Hauswirth, M., Tummarello, G., Morbidoni, C.: Rapid prototyping of semantic mash-ups through semantic web pipes. In: Proceedings of the 18th international conference on World wide web. pp. 581–590 (2009)
  * [36] Le-Phuoc, D., Quoc, H.N.M., Quoc, H.N., Nhat, T.T., Hauswirth, M.: The graph of things: A step towards the live knowledge graph of connected things. Journal of Web Semantics 37, 25–35 (2016)
  * [37] Le-Tuan, A., Franzreb, C., Le Phuoc, D., Schimmler, S., Hauswirth, M.: Towards building live open scientific knowledge graphs. In: Companion Proceedings of the Web Conference 2022. pp. 443–447 (2022)
  * [38] Lefrançois, M., Zimmermann, A., Bakerally, N.: Flexible RDF generation from RDF and heterogeneous data sources with SPARQL-Generate. In: European Knowledge Acquisition Workshop. pp. 131–135. Springer (2016)
  * [39] Llanes, K.R., Casanova, M.A., Lemus, N.M.: From sensor data streams to linked streaming data: a survey of main approaches. Journal of Information and Data Management 7(2), 130–130 (2016)
  * [40] Ma, Z., Capretz, M.A., Yan, L.: Storing massive Resource Description Framework (RDF) data: a survey. The Knowledge Engineering Review 31(4), 391–413 (2016)
  * [41] Mauri, A., Calbimonte, J.P., Dell’Aglio, D., Balduini, M., Brambilla, M., Della Valle, E., Aberer, K.: TripleWave: Spreading RDF streams on the web. In: The Semantic Web–ISWC 2016: 15th International Semantic Web Conference, Kobe, Japan, October 17–21, 2016, Proceedings, Part II 15. pp. 140–149. Springer (2016)
  * [42] Miles, A., Matthews, B., Wilson, M., Brickley, D.: Skos core: simple knowledge organisation for the web. In: International conference on dublin core and metadata applications. pp. 3–10 (2005)
  * [43] Modoni, G.E., Sacco, M., Terkaj, W.: A survey of RDF store solutions. In: 2014 International Conference on Engineering, Technology and Innovation (ICE). pp. 1–7. IEEE (2014)
  * [44] Morsey, M., Lehmann, J., Auer, S., Stadler, C., Hellmann, S.: DBpedia and the live extraction of structured data from Wikipedia. Program 46(2), 157–181 (2012)
  * [45] Oo, S.M., Haesendonck, G., De Meester, B., Dimou, A.: RMLStreamer-SISO: an RDF stream generator from streaming heterogeneous data. In: International Semantic Web Conference. pp. 697–713. Springer (2022)
  * [46] Özsu, M.T.: A survey of RDF data management systems. Frontiers of Computer Science 10, 418–432 (2016)
  * [47] RDF Stream Processing Community Group: RSP data model. Draft community group report, W3C RSP Community Group, https://streamreasoning.org/RSP-QL/Abstract%20Syntax%20and%20Semantics%20Document/
  * [48] Rodrıguez, A., McGrath, R., Liu, Y., Myers, J., Urbana-Champaign, I.: Semantic management of streaming data. Proc. Semantic Sensor Networks 80, 80–95 (2009)
  * [49] Schraudner, D., Harth, A.: Stream containers for resource-oriented RDF stream processing. arXiv preprint arXiv:2202.13630 (2022)
  * [50] Sowinski, P., Wasielewska-Michniewska, K., Ganzha, M., Pawlowski, W., Szmeja, P., Paprzycki, M.: Efficient RDF streaming for the edge-cloud continuum. arXiv preprint arXiv:2207.04439 (2022), in print, presented on the IEEE 8th World Forum on Internet of Things
  * [51] Sowiński, P.: RDF-STaX/rdf-stax.github.io (Nov 2023). https://doi.org/10.5281/zenodo.10082586, https://doi.org/10.5281/zenodo.10082586
  * [52] Sowiński, P., Ganzha, M., Paprzycki, M.: RiverBench: an open RDF streaming benchmark suite. arXiv preprint arXiv:2305.06226 (2023)
  * [53] Su, X., Gilman, E., Wetz, P., Riekki, J., Zuo, Y., Leppänen, T.: Stream reasoning for the Internet of Things: Challenges and gap analysis. In: Proceedings of the 6th International Conference on Web Intelligence, Mining and Semantics. pp. 1–10 (2016)
  * [54] Szmeja, P., Fornés-Leal, A., Lacalle, I., Palau, C.E., Ganzha, M., Pawłowski, W., Paprzycki, M., Schabbink, J.: ASSIST-IoT: A modular implementation of a reference architecture for the next generation Internet of Things. Electronics 12(4), 854 (2023)
  * [55] Szmeja, P.: ASSIST-IoT semantic annotation enabler (2023), https://github.com/assist-iot/semantic_annotation, accessed on November 2, 2023
  * [56] Tappolet, J., Bernstein, A.: Applied temporal RDF: Efficient temporal querying of RDF data with SPARQL. In: European semantic web conference. pp. 308–322. Springer (2009)
  * [57] Tommasini, R., Bonte, P.: Web stream processing with RSP4J. In: Proceedings of the 15th ACM International Conference on Distributed and Event-based Systems. pp. 164–167 (2021)
  * [58] Tommasini, R., Bonte, P., Spiga, F., Della Valle, E.: Streaming Linked Data: From Vision to Practice. Springer Nature (2023)
  * [59] Tommasini, R., Sedira, Y.A., Dell’Aglio, D., Balduini, M., Ali, M.I., Le Phuoc, D., Della Valle, E., Calbimonte, J.P.: VoCaLS: Vocabulary and catalog of linked streams. In: The Semantic Web–ISWC 2018: 17th International Semantic Web Conference, Monterey, CA, USA, October 8–12, 2018, Proceedings, Part II 17. pp. 256–272. Springer (2018)
  * [60] Van Assche, D., Delva, T., Haesendonck, G., Heyvaert, P., De Meester, B., Dimou, A.: Declarative RDF graph generation from heterogeneous (semi-) structured data: A systematic literature review. Journal of Web Semantics 75, 100753 (2023)
  * [61] Williams, G.: SPARQL 1.1 service description. W3C recommendation, W3C (Mar 2013), https://www.w3.org/TR/2013/REC-sparql11-service-description-20130321/
  * [62] Wu, J., Orlandi, F., O’Sullivan, D., Dev, S.: A workflow to convert live atmospheric sensor data into linked data. In: IGARSS 2022-2022 IEEE International Geoscience and Remote Sensing Symposium. pp. 4086–4089. IEEE (2022)
  * [63] Zhang, F., Li, Z., Peng, D., Cheng, J.: RDF for temporal data management–a survey. Earth science informatics 14, 563–599 (2021)
  * [64] Zhao, J., Alexander, K., Hausenblas, M., Cyganiak, R.: Describing linked datasets with the VoID vocabulary. W3C note, W3C (Mar 2011), https://www.w3.org/TR/2011/NOTE-void-20110303/
  * [65] Zimmermann, A.: RDF 1.1: On semantics of RDF datasets. W3C note, W3C (Feb 2014), https://www.w3.org/TR/2014/NOTE-rdf11-datasets-20140225/