One of the greatest challenges facing computations on data crawled from the Web is the (in)ability to scale to such large quantities of data. While some computations are less challenged by this than others, inference on the Semantic Web is certainly limited in this regard. Parallelism has been employed to scale inference to larger datasets, but evaluations of recent works have fallen back on common parallel computing metrics that do not apply to this specific scalability challenge. In this position paper, the name data scaling is given to this scalability challenge, and the metric growth efficiency is defined.
One of the greatest challenges facing computations on data crawled from the Web is the (in)ability to scale to such large quantities of data. Parallelism is often employed to scale computation to larger datasets while keeping execution time reasonable. However, traditional parallel computing metrics focus on one of two forms of scaling: strong scaling or weak scaling. The goal of strong scaling is to reduce execution time for a fixed problem by adding processors. The goal of weak scaling is to keep execution time constant by adding processors to accommodate additional workload (not necessarily proportional to amount of data). In contrast to these notions of scaling, a new notion of scalability – data scaling – is introduced herein, and it is concerned with keeping execution time constant by adding processors to accommodate more data.
The ideas presented in this position paper are preliminary in nature, still requiring formal development. The specific intent of this paper, though, is to instigate a paradigm shift in the way scalability evaluations of parallel inference (and possibly other problems) on large, RDF datasets are performed.
In section 2, the need for data scaling is motivated. In section 3, common
scalability metrics are shown to be unfit for measuring data scalability, and a
new data scaling metric – growth efficiency – is defined. Discussion about, and
a retroactive example of, evaluating a system with growth efficiency is given in
section 4, and conclusion is given in section 5.
This work subscribes to the following statement by Hitzler and van Harmelen:
“Concerning scalability, reasoning systems have made major leaps in the recent
past . . . . However, it remains an open question when (and if1) these approaches
will scale to the size of the web, . . . ” [
Perhaps these assumptions are debatable, but for the intents and purposes of this paper, they are considered axiomatic. Additionally, although inference motivates this work, the definitions and their application are not specific to any particular class of problems.
To support definitions throughout this paper, a simplistic, intentionally nonspecific computational model is assumed. A (terminating) parallel computation is performed on some dataset, in some amount of time, utilizing some number of processors. This is sufficient for the following discussion.
Indeed, progress has been made for specific forms of reasoning on large
datasets. At the very least, varying degrees of RDFS and OWL inference have
been achieved on real-world datasets containing around a billion RDF triples [
Evaluations of recently studied, parallel inference approaches [
Data scaling is concerned with the change in execution time of a parallel computation as processors are added to accommodate larger datasets. Data scaling is arguably the central scalability issue for parallel computations on the Web, and it is distinct from strong scaling and weak scaling as illustrated through metrics in the following section. 3
This section contains a brief review of fundamental metrics often used for
measuring scalability (in some sense) of parallel systems. These are defined herein in
an atypical way in order to relate the metrics to dataset size, thus highlighting
their insufficiency for measuring data scalability. Then a new metric for data
scaling is introduced. To aide this discussion, the following definition is needed.
1 “Since the web keeps growing, they may never scale, even if they become much more
efficient.” Footnote in quote from [
Relative speedup and metrics based on it are the scalability metrics reported
by nearly every recent work [
Definition 2. Let D be a growing dataset, and fix k to some positive integer. Let T1 be the execution time for one processor with dataset D(k), and let TP be the execution time for P processors with dataset D(k). Then the relative speedup is defined as SP = T1/TP .
Clearly, relative speedup (the most common strong scaling metric) gives no direct
indication of data scaling since the dataset is fixed. As an alternative, one may
resort to (empirical) scaled speedup [
Unlike with relative speedup, in scaled speedup, the dataset size changes with the number of processors. However, processors are added not to accommodate more data but rather to keep execution time constant.
Therefore, these metrics (and those metrics derived from them) are unsuited for measuring data scalability, and a new metric is needed.
Definition 4. Let D be a growing dataset, and fix k to some positive integer. Let T1 be the execution time for one processor with dataset D(k), and let TP be the execution time for P processors with dataset D(P · k). Then growth efficiency is defined as GP = T1/TP .
Growth efficiency directly aligns with the notion of data scaling. The idea is that the size of the input dataset should grow linearly with the number of processors, as captured in the definition. Thus, processors are added to accommodate more data. Growth efficiency is more comparable to efficiency EP = SP /P or scaled efficiency EP = SP /P in that it is a value between zero and one2 (inclusively). 4
Performance evaluations using growth efficiency are fairly intuitive, but there are some important details, particularly when the evaluation is meant to compare systems. 2 That is, in theory. Although undetermined at present, there may exist some conditions in practice that allow for growth efficiency to be greater than one. This would be akin to superlinear speedup in which efficiency can be greater than one.
Points x, y in scatter plots should be such that x is the dataset size and y is the growth efficiency. Using notation from definition 4, the points are P · k, GP for some k and various P . This brings up the issue of what k should be. k is the amount of data for a single processor, and as such, it is referred to herein as the processor capacity. Processor capacity can be defined in numerous ways. One possibility is availability of space (e.g., RAM, disk); another possibility is the maximum amount of data a single processor can handle without exceeding a specific upper bound on execution time. Regardless, an evaluation should include discussion and justification of how processor capacity is determined.
It is often the case that evaluations of different systems are performed independently of each other, and some meaningful comparison is retroactively sought. Thus, consideration must be given to potential differences in choice of growing dataset and notion of processor capacity. That is, evaluations are comparable only in as much as the parameters of the evaluations are comparable.
Growing datasets should be similar, if not the same. Meeting this requirement is straightforward with synthetic datasets, but more difficult with realworld datasets. Unless it is obvious, an evaluation should make clear the method by which the dataset was linearly “grown” with number of processors. It is conceivable that the order of adding data can vary the change of execution time, for example, in the context of inference with negation as failure.
Notions of processor capacity should be similar, although it is not necessary that they be exactly the same. For example, two evaluations using different notions of space-bounded, processor capacity are likely to still be comparable strictly in the context of data scaling.
Although more thorough discussion is warranted, an example, retroactive
evaluation illustrating the differences of strong scaling and data scaling would
likely be a better use of the remaining space, given the limitation on paper length.
Some of the results from parallel, RDFS inference in [
This example is intended to illustrate how growth efficiency differs from efficiency EP = SP /P in the strong scaling sense. Therefore, the two are plotted below over number of processors. (Recall that it was stated that the x-axis should be dataset size for growth efficiency, but such an x-axis is nonsensical for efficiency.)
Table 1b and figure 1b show the same metrics for only the inference portion of the computation. The inference portion of the computation is embarrassingly parallel, so there is no interprocess communication or contention. Clearly, the inference portion of the computation is very scalable – at least for LUBM data – in both the strong and data scaling senses. This indicates that the inference portion of the computation will likely scale to very large datasets without significantly impacting execution time, although the same cannot be said for the overall computation. 0.1 1 1 Traditional scalability metrics from parallel computing fail to address the specific scalability challenge faced by parallel computations on data crawled from the Web, that is, the ability to handle large, growing datasets. A notion of data scaling has been defined that is concerned with how execution time is affected as data grows, increasing the number of processors linearly with dataset size. A new metric, growth efficiency, has been introduced for evaluating data scalability of parallel computations. Focus has been on inference over RDF data crawled from the Semantic Web.
Acknowledgements. Much thanks to Jacopo Urbani and David Mizell for their constructive feedback in revising this paper.