In order to cope with the ever-increasing data volume, distributed stream processing systems have been proposed. To ensure scalability most distributed systems partition the data and distribute the workload among multiple machines. This approach does, however, raise the question how the data and the workload should be partitioned and distributed. A uniform scheduling strategy|a uniform distribution of computation load among available machines|typically used by stream processing systems, disregards network-load as one of the major bottlenecks for throughput resulting in an immense load in terms of intermachine communication. In this paper we propose a graph-partitioning based approach for workload scheduling within stream processing systems. We implemented a distributed triple-stream processing engine on top of the Storm realtime computation framework and evaluate its communication behavior using two real-world datasets. We show that the application of graph partitioning algorithms can decrease inter-machine communication substantially (by 40% to 99%) whilst maintaining an even workload distribution, even using very limited data statistics. We also nd that processing RDF data as single triples at a time rather than graph fragments (containing multiple triples), may decrease throughput indicating the usefulness of semantics.
In today's connected world, data is produced in ever-increasing volume, velocity,
variety, and veracity [
To cope with increasing demands distributed stream processing systems have been proposed, which usually ensure scalability by partitioning the data and distributing the processing thereof to multiple machines. Note that deciding how to partition the data and distribute the associated processing is a non-trivial task and can have dire consequences on performance.
Distributed processes communicate with each other by sending messages containing partial results of the overall processing task. Processes on di erent machines communicate over the network and the resulting network load limits scalability in two ways: First, network tra c is several orders of magnitude slower than in-machine communication.1 Second, the bandwidth of each machine limits the amount it can possibly communicate to processes residing on other machines. As a consequence, nding a good distribution strategy for distributed stream processing is crucial to ensure scalability. Note that the variety and potential schemalessness of linked data further aggravates the problem as a Semantic Flow Processing (SFP) systems (1) cannot rely on the schema for data partitioning and distribution and (2) the triple-nature (rather than the reliance on n-tuples or relations) of the underlying data model potentially further subdivides the smallest unit of data increasing the number of possible partitioning (and hence, distributions).
As distributed stream processing becomes more important in many areas of business and science, researchers have proposed various ways to schedule workload in such systems. Interestingly, we found no previous work that employs existing graph partitioning algorithms to the problem of workload scheduling.
In this paper, we propose the use of graph partitioning algorithms to optimize the assignment of tasks to machines : we regard the data- ow within an SFP system as a graph, where the edges' weight represents the required bandwidth for information passing and the vertices' weight represents the computational load required to process incoming messages. Speci cally, we operationalize the edge weights as the number of messages sent from one process to another, based on the two assumptions: rst, that messages are approximately the same size, and second the computational load to be proportional to the number of messages received by a processing vertex, assuming further that all messages need the same time to be processed on all tasks. We then use a graph partitioning algorithm to optimize the distribution of processes to machines whilst addressing two possibly
http://www.cs.cornell.edu/projects/ladis2009/talks/dean-keynote-ladis2009.pdf for more details. opposing goals: we try to minimize costly network messages whilst distributing computation load as evenly as possible.
To evaluate our distribution approach we implemented an SFP system on top of the Storm realtime computation framework.2 Our implementation allows compiling certain SPARQL queries, modi ed for stream processing, to a Storm topology. To enable parallelization of the processing functions the data ows in the topology are partitioned using appropriate hash functions. Next we empirically determine the weight of the nodes and edges, partition the graph, and \schedule" the processes accordingly on machines. In our evaluation using two real-world datasets we show that our graph-partitioning strategy can decrease inter-machine communication substantially (by 40% to 99%) whilst maintaining an even workload distribution, even using very limited data statistics.
The remainder of this paper is structured as follows: next we succinctly summarize the most relevant related literature (Section 2) before introducing the details of our approach (Section 3). This is followed by a description of our experiments (Section 4), a discussion of the results in the light of its limitations (Section 5), and an exploration of the implications and future work (Section 6). 2
This study relates to (distributed) Information Flow Processing (IFP)3,
Semantic Flow Processing (SFP) [
Information Flow Processing: The eld of IFP is vast and a survey is beyond
the scope of this paper [
Aurora [
features. A distributed version was implemented using Apache S4 platform;4 yet
with no particular scheduling strategy [
EP-SPARQL [
CQELS [
SPARQLStream[
INSTANS [
Workload Scheduling: Earlier work on scheduling in stream processing
concentrated on operator scheduling in wide area networks [
SODA [
Pietzbuch et al. [
Xia et al. [
Aniello et al. [
In this section we provide the technical foundations for our study. These include a brief introduction to the data- and processing models employed. Next, we introduce the three concepts of data partitioning, scheduling, and load balancing and how they a ect the performance of a distributed system, before presenting a formal problem description. We then show, how the multi-constraint optimization problem of scheduling can be solved using a graph partitioning algorithm, before we, nally, introduce the system we built to test our hypothesis. 3.1
Data- and Processing Model
A linked data stream processing system essentially continuously ingests large
volumes of temporally annotated RDF triples and emits the results again as data
stream. Such systems usually implement a version of the SPARQL algebra that
has been modi ed for processing dynamic data. In our case, we focus on a subset
of those de ned in the queries of the SRBench benchmark [
Scheduling, Data Partitioning, and Load Balancing In order to scale the system horizontally (i.e., executing its parts on multiple processing units concurrently) we may replicate parts (or the whole) of the query's topology and execute clones of the operators in parallel. We refer to these clones as tasks or task instances. Hence, each operator will be instantiated as a nite number of n tasks (where n 1). These task instances, and thus the workload of the system, can then be distributed across several machines in a compute cluster. We refer to the assignment of tasks to machines as scheduling. Figure 1 shows an example operator topology and one possible schedule distributing tasks to two servers of a compute cluster. As there are now multiple instances of each operator of the topology the data needs to be partitioned in accordance to the operator's needs. For stateless operators, such as lters or binders, it does not matter which variable bindings they receive for processing. For stateful operators, in contrast, such as aggregators or joins, the system needs to provide some guarantees about Topology
Server 1 g Bg n i p u o r g Bo g n i p u o r g Bb tg1 to1 tb2 tb1
Server 2 tg2
tg3 to2 tb3 what data gets delivered to which task instance. To this end, a topology con guration contains grouping strategies (or information about the data partitioning function) on the edges between operator nodes (see also Figure 1 on left).
In this study we assume the number of messages sent between the machines as the key performance indicator (KPI). This is seems to be a prudent choice, as the network can become a bottleneck of a distributed system that needs to scale horizontally. We acknowledge that our choice has limitations and therefore provide a discussion in Section 5.
Given these de nitions the goal of our approach is to nd a schedule (i.e., assignment of tasks to machines) for a given topology that minimizes the total number of data messages transferred over the network, whilst maintaining an even workload distribution across machines in terms of CPU cycles.
To achieve this goal we partition the data into logical units. We then regroup these using graph-partitioning which provides us with an optimization procedure to minimize the number of messages sent between machines. As a result, we propose the following hypothesis: Combining data partitioning between tasks with a scheduler that employs graph partitioning to assign the resulting task instances outperforms a uniform distribution of data and tasks to machines.
Our hypothesis assumes that di erent distribution strategies signi cantly inuence the number of messages sent between the machines. Most stream processing platforms attempt to uniformly distribute compute loads possibly incurring high network tra c. Approaches like Borealis schedule the processors according to the structure of the query, where every operator is is assigned to one machine. This approach has an upper limit in parallelization equal to the number of operators and may incur high network tra c between to machines containing active operators. Instead we propose to parallelize the operators and minimize network tra c allowing for more exibility for distributing the workload. Most importantly, we propose that the scheduling strategy should optimize the amount of data sent between machines. 3.3
Formal Problem Description In principle, a linked data stream processing system can be conceived as a query graph QSF P =< Op; M C >, where Op is a nite set of operators opi (i.e., Op = [iI=1opi) and each opi executes one or more algebra operations. The ow of information between the operators is established by a set of edges mc 2 M C (message channels) that denote a ow of messages (time-stamped variable bindings [ts]) between the operators (opi).
Since we want to enable parallelism and distribution each operator is instantiated in parallel as a nite number of tasks Topi = [jJ=i1ti;j , where Ji denotes the degree of parallelism of opi. We refer to the set of all tasks as
I I Ji
T = [i=1Topi = [i=1[j=1ti;j
Furthermore, each message channel mc 2 M C is instantiated via a nite set of channels cij 2 C that connect the tasks ti; tj 2 T . Speci cally, connected tasks send messages, i.e., time-stamped variable bindings [ts] to each other.
Thus for each query graph QSF P there exists a parallelized Task Graph T G =< T; CT >, where in addition to the mapping of each task to exactly one operator (as speci ed above) each channel c 2 C maps to exactly one mc and each mc has at least one c to ensure connectivity. Hence, to ensure a correct mapping we require that 8opa; opb; mcopa;opb : 9ta;j ; tb;j ; cta;j;tb;j , where (i) mcopa;opb is a message channel that connects opa and opb, and (ii) cta;j;tb;j connects the corresponding tasks. In addition, we require that 8ta;j ; tb;j ; cta;j;tb;j : 9exactly oneopa; opb; mcopa;opb to ensure the one-to-n mapping of operators and message channels to tasks and channels.
Graph Partitioning A partitioning divides a set into pairwise disjoint sets. In our case we want to partition the vertices of a graph G = (V; E) with a nite set of vertices V and a nite set of edges E V V . A partitioning P = fP1; : : : ; PK g for V separates the set of vertices such that { it covers the whole set of vertices: SK
k=1 Pk = V and { the partitions Pk are pairwise disjoint: TK k=1 Pk = ; In addition, we denote (i) a partitioning function by part : V ! P that assigns every vertex v1; : : : vl the partition Pk 2 P it belongs to, (ii) a cost function by cost(P ) 2 R, which denotes some kind of cost associated with the partitioning that is subject to optimization, and (iii) a load imbalance factor stdv(P ) that ensures that the workload of the tasks is evenly distributed over the machines.
We can easily map our problem of minimizing the number of messages that are sent between machines to a graph partitioning problem with a speci c cost function. First, we de ne the graph to be partitioned as the Task Graph T G. A partitioning of T G maps each task to exactly one machine.
Second, in our case the cost function to minimize is the number of messages sent between machines. We operationalize the cost function for the network trafc as cost(P ) = PK k=1 cost(Pk). Each cost(Pk) denotes the cost of transmitting messages, i.e. the bindings, across the network to a task situated in partition Pk. Hence, we increment the cost for cost(Pk) by one, i a message is being sent from task t1 to t2 and the two tasks are not in the same partition, i.e. part(t1) 6= part(t2) and t2 2 Pk.
Third, when optimizing the costs for the partitions we add the constraint that the partitions shall be balanced with respect to the computational load. We approximate the computation load for a partition by counting the number of messages that are sent over a channel for which task t is the receiving task: load(Pk) = Pcta;tb 2C count(m) i part(tb) = Pk, where m 2 M is a message sent over channel cta;tb . Note that we count all incoming messages for each task, regardless of wether they had to be transferred over the network or not, as they have to be processed and hence consume computation power in both cases.
In order to make optimal use of the available resources, a balanced load distribution is desirable. The standard deviation stdv(P ) of the load for all partitions shall hence not exceed a certain threshold C:
C < stdv(P ) = s Pp2P ( load(P )
K
K
load(p))2
All graph partitioning in this paper were computed using the METIS algorithms
for graph partitioning [
KATTS In order to test our hypothesis we built a research prototype of a distributed linked data stream processing engine called KATTS .5 In order to keep the programming overhead minimal, we chose to build our system on top of the Storm realtime computation framework.6 While our current prototype is built using Storm it is important to note, that our ndings are not only valid in the context of Storm, but for any system that uses partitioned data streams.
A Storm application is a graph, consisting of compute nodes that are connected by edges. Edges are con gured using a partitioning function or grouping strategy. Using the abstractions of Storm we implemented a set of stream operators, a con guration environment, and a monitoring suite. Topologies can be speci ed using XML and will output the sending behavior of the topolgy: the communication graph. In addition to input operators that read time annotated n-triple les and an output operator, the current set of supported operators contains an aggregation operator (min, max, avg), a lter operator, a bind operator, and a temporal join operator. Every incoming edge of each consuming operator can be con gured with a grouping strategy. If no grouping strategy is con gured local or shu e grouping will be used.7 We always used the eld grouping strategy, which partitions the data based on the value of a tuple eld (i.e., the value 5 KATTS is a recursive acronym for Katts is A Triple Torrent Sieve. The code will be made accessible at https://github.com/uzh/katts upon publication of the paper. 6 http://storm-project.net 7 https://github.com/nathanmarz/storm/wiki/Concepts#stream-groupings of a variable). For partitioning Storm uses the hashCode() method of the eld value, which in our case is an object of type java.lang.String.8 In addition to the con guration parameters of the particular node implementation, each node of the topolgy can be con gured with a value that de nes its degree of parallelism, which is the number of task instances that should be created for this operator.
The monitoring suite has two main components: (1) a data collection facility, which records communication behvaior, and (2) a runtime monitoring component that keeps track of the number of input sources the system is receiving data from. When all sources have been fully processed, the data aggregation process will be executed and the topology as well as the Storm cluster will be halted. 4
In this section we evaluate if our proposed strategy is indeed better in terms of network load whilst maintaining a comparable host load when compared to a baseline strategy of trying to attain a uniform distribution of load. To that end we rst present the experimental setup and then present the results. 4.1
Experimental Setup
Datasets We evaluated our system using two example queries that are built
around a real world streaming use case: SRBench [
SRBench is an RDF/SPARQL streaming benchmark consisting of weather
observations about hurricanes and blizzards in the USA during the years 2001 and
2009 and contains 17 queries on LinkedSensorData,9 which originated from the
MesoWest project of the University of Utah.10 Given that our approach only
implements joins, simple aggregates, and triple-pattern matching, we restricted
ourselves to Q3, which searches for weather stations observing hurricane-like
condition. These are de ned as \a sustained wind (for more than 3 hours) of at
least 33 m/s or 74 mph." Without the pre x declaration a C-SPARQL [
oomm oowwll :: orebssuerlvt edProperty w[eoamthoewr:l W:filnodaStpVeae dlu e; ? value ] .
GgROUP BY ? s e n s o r HAVING ( MIN(? value ) >= "74"^^ xsd : f l o a t ) 8 http://docs.oracle.com/javase/6/docs/api/java/lang/String.html#hashCode() 9 http://wiki.knoesis.org/index.php/LinkedSensorData 10 http://mesowest.utah.edu/index.html 11 We employ a minimum aggregate rather than the average value used in http://www.w3.org/wiki/SRBench, as we think the word "sustained" means that the wind speed has to be "at least" 74 miles per hour and not "on average". We also use a step size of 1 hour instead of 10 minutes. SRB Q3: OpenGov: The resulting topology has four processes depicted in Fig.2: First, the reader node (R) reads the incoming stream and scans it for the triple patterns contained in the where-clause. Second, the matched bindings are then sent to the aggregator node (A), which creates the minimum aggregate over the temporal window of three hours and a step size of one hour. Third, the output of the aggregator is then sent to the lter node (F), which lters all occurrences that are smaller than 74 mph and sends all remaining instances to the output node (O). Finally, the output node writes the occurrences into a le on disk.
OpenGov Dataset: To complement the regular setup of SRBench, which consists mostly of weather station measurements, we gathered a second data set, which combines data on public spending in the US with stock ticker data.12 We devised a query that would highlight (publicly traded) companies, that double their stock price within 20 days and are/were awarded a government contract in the same time-frame. This query requires the system to scan two sources, aggregate/ lter values, and nally join certain events that may have a causal relation to each using a temporal condition. The C-SPARQL representation of the query, for example, looks as follows: REGISTER QUERY PublicSpendingStock AS FSREOLMECSTTRfEA?Mco<mwparndys.ncarmspe/?t aicgkenecry. tnradmf >e ?[RcAoNnGtEr a2c0t DidAY?SmTiEnP p1riDcAeY?] max price ? f a c t o r g FROM STREAM <usaspending . org / c o n t r a c t s . trdf > [RANGE 20 DAY STEP 1 DAY] WHERE f GRA?Pt Hic<k werrdisd. cwrscp:P/Rt Cic k e r ?. ttri dckf>e rfp r i c e ; wc :COMNAM ?company name ; wc :TICKER ? t i c k e r s y m b o l . g U?NcIoOnNt rGaRcAtPHid<uuss a:sapgeenndc yinidg . org / c o n t r a c t s . tnradmf>e f;
? agency us : obligatedamount ? contract amount ; us : vendorname ?company name .
gg
AGGREGATE f (? min price , MIN, f? t i c k e r pp rr ii cc ee gg)) gg
ABGINGDREG(?ATmEaxf p(r?icmeax/ p?rmicien, pMrAicXe, Af?S t ?icf kacetro r )
FILTER(? f a c t o r > 2)
The resulting topology (Fig.2) rst aggregates (A) the ticker-sourced (T) data to
compute the minimum and maximum over a time window of 20 days. It computes
the ratio between these numbers (B), and then lters those solutions where that
ratio is smaller than or equal to two (F). The remaining company tickers are
then joined (J13) with the ones that where awarded government contracts (C).
The joined tuples are then sent to the output node (O).
12 http://www.usaspending.gov, https://wrds-web.wharton.upenn.edu/wrds
13 We use a hash join with eviction rules for the temporal constraints.
Evaluation Criteria In accordance with the
Properties-Challenges-KPIsStress-tests (PCKS) paradigm for for benchmarking SFP systems [
Second, to test our hypothesis we needed to partition the resulting communication graph based on the network load of each channel. Since the channel loads are not known before running the query we chose two experimental scenarios. In the rst scenario we assume an oracle optimizer that would know the number of messages that would ow along every channel. This scenario allows to establish a hypothetical upper bound of quality that our method could attain, if it were to have an oracle. In a second scenario we assumed a learning optimizer that rst observes channel statistics for a brief period of time and then partitions the graph accordingly. To that end we sliced the SRBench data into daily and the OpenGov data into monthly slices. We then measured the the performance of our approach based on learning during the preceding one to three time-slices, essentially providing a adaptively learning system.
Third, to partition the graph we employed METIS [
On the right we nd the results for the OpenGov dataset. This evaluation is
not quite as clear-cut, as the join operation requires a signi cant redistribution of
messages. The results here are quite interesting. First, we nd that our approach
14 As we we ran our experiments on machines with more than 12 cores, we were able
to achieve better capacity utilization by using more than 12 tasks per node.
15 We used v5.0.2 with default partitioning (kway) and default load imbalance of 1.03.
clearly outperforms the uniform distribution strategy by a factor of two to three.
Second, it is interesting to observe that even longer learning periods, using two
(Prev.2) and even three previous time slices (Prev.3), do not necessarily improve
the overall performance - maybe due to over- tting or concept drift [
For the sake of brevity we only show data for three time-slices of each evaluation in Table 1: on the left side again the results for the embarrassingly parallel SRBench query, which shows a reduction in network usage by over 99%. The right side of the table is more interesting as it exhibits the gain of our approach in a non-trivial case. Even for the OpenGov query, workload distribution using a graph partitioning approach yields savings of network bandwidth of over 40%. Balancing Computation Load Next to keeping the bandwidth usage to a minimum, a distributed system must also make good use of the available computational power. For this reason we analyzed how many messages were processed by all tasks on each host for the two queries. Figure 4 shows the results of this
OpenGov , 2001
Uniform Oracle Prev.1 Slice Uniform Oracle Prev.1 1 1 1 0.7% 0.0% 0.0% 0.0% Feb 69,5% 0.7% Mar 69,8% 0.0% Apr 69,8% 29.0% 36.0% 32.1% 30.1% 37.7% 32.1% evaluation: The load distribution resulting from the graph partitioned task assignment only di ers slightly from the one found by uniform task distribution (average relative standard deviation [RSD] OpenGov : 7:04% for partitioning vs. 5:27% for uniform baseline; SRBench: 3:74% for partitioning vs. 2:68% for uniform baseline).
The In uence of Data Partitioning The results above are very encouraging. One of the major limitations of our measurements, however, is that we assumed that the data came partitioned into meaningful groups. Whilst this assumption is often true in practice (the input from weather stations comes as grouped messages from one station, data about one stock usually arrives from one source, etc.). But in some worst-case scenarios the data might be mixed (even if a total random intermixing is unlikely). To investigate the robustness of our procedure against this assumption we ran our approach under two di erent partitioning regimes: rst, we made sure to partition the data along a di erent hash function that chosen by our system (which relies on the Storm hash partitioning) and second, we ensured employing the same partitioning. The results of this sensitivity analysis are shown in Figure 5 for the SRBench query, which graphs a Sankey chart of the inter-task communication under both conditions, where the width of the lines corresponds to the number of messages. As the gure clearly shows the mixed hashing setting requires to reshu e all data from the readers to the processing nodes, while the equally partitioning setting provides a clean stream setting. As a consequence, we can expect that badly pre-partitioned data would not exhibit as good results as the ones we exhibited above. 5
The results shown in the section above show that using a graph partitioning algorithm to schedule tasks instances on machines does indeed reduce the messages sent over the network whilst only having a slightly less even load distribution. The rst part of the nding could be seen as almost tautological: it could be understood as showing that graph-partitioning using a well-establish algorithm is better than a partitioning that ignores network tra c but \only" focuses on load distribution. We believe, however, that there are subtle considerations that are less than obvious.
First, the critical element is to realize that the operators can be parallelized with an adequate data partitioning approach not to \just" use graph partitioning. It is the interplay of the two partitionings that enables the graph partitioning to nd a good schedule: inadequate data partition can lead to highly suboptimal schedules as the results about the in uence of data partitioning show. Second, the principle of nding the smallest possible partition given the desired degree of parallelism (see also Section 3.2) seems important. How important needs to be investigated. Whilst the idea seems simple its details are intricate and required careful analysis|a task that we will have to continue in the future by further exploring the interactions between data and graph partitioning and devise an automated model for optimizing it.
One somewhat surprising outcome of our analysis is that the overall e ciency of the system heavily depends not only on the consistent use of the same partitioning function, but also on the compatibility of the values over which the data is being partitioned. Using incompatible data partioning functions can result in very poor performance as seen in section 4.2. If a topology contains operators that partition over incompatible elds such as in the OpenGov query, graph partitioning is still useful, but much less e ective as when working with compatible elds. It is this observation which contains an interesting insight: linked data stream processors should work with graph fragments rather than triples. \Naturally" occuring graph fragments often contain interdependent graph elements. If one pulls these fragments apart due to some partitioning function one might have to gather them in a later join. Hence, it seems prudent to favor an approach that leaves these fragment together if a later join is foreseeable.
Our current analysis is based on some underlying assumptions. First, we
assumed that some network statistics are available at the onset. Whilst this may
not always be given, our ndings shows that even a small amount of statistics
seem to produce adequate schedules. Hence, it seems straightforward to start
with an uniform distribution and then apply an incremental graph partitioning
approach [
Second, we assumed that the processing load (both CPU and RAM) is proportional to the number of messages received (i.e., constant operator complexity). Whilst this assumption is de nitely true for some operators (e.g., computing the average) others may require more computational e ort. We intend to address this issue in future work.
Third, we assumed that the query topology was given. Obviously, queries could be translated to various topologies; each of which would require its own schedule. Hence, it would make sense to combine our approach with a query optimizer { a task beyond the scope of this paper.
Also, our current evaluation has some limitations. First, it is limited to two datasets and queries. Whilst the queries seem representative of many settings we have seen we intend to signi cantly extend our evaluation in the future in terms of number of datasets and queries. Second, all our evaluations were run on a cluster with 12 machines, 1GB ethernet, and 24 cores each. Obviously, we will have to extend our evaluation to investigate the interactions between number of machines and cores available and the degree of parallelism \granted." Third, we will have to run throughput-analyses in real-world setups in addition to our current network analysis adding number of messages ingested per second as KPI. 6
In this study we investigated whether and how scheduling the tasks of Distributed Semantic Flow Processing (DSFP) systems bene ts from applying graph partitioning. We implemented our approach on the Katts DSFP engine and evaluated it using a query of the SRBench benchmark and a usecase inspired by the open government movement with regards to network load. The results show that using a graph partitioning algorithm to schedule task instances on machines does indeed reduce the number of messages sent over the network. We also found that this only leads to a slightly less even load distribution.
The critical element for optimizing the scheduling using graph partitioning is an adequate data partitioning for parallelizing the operators. Future work will investigate whether the principle of nding the smallest possible data partition given the desired degree of parallelism is as important as our experiments indicate.
Our study's most important shortcomings are its limitation to two datasets and queries and the xed setup of the distributed system. For the rst we intend to systematically extend our evaluation in the future in terms of number of datasets and queries. For the latter, is it the interactions between number of machines and cores available and the degree of parallelism that require further research. Especially the impact of such interactions on throughput in terms of messages ingested per second is of interest here.
We are con dent that our ndings help making DSFP systems more scalable and ultimately enable reactive systems that are capable of processing billions of triples or graph fragments per second with a negligible delay. It is our rm belief that the key to addressing these challenges needs to and will have to be revealed from the data itself.
Acknowledgements We would like to thank Thomas Hunziker, who wrote the rst prototype of the KATTS system during his master's thesis in our group.