Contributions published at Dynamic and Distributed Information Systems (Abraham Bernstein)

Our ability to process large amounts of data and the size and number of data sets are growing at an incredible pace. This development presents us with the opportunity to build systems that perform complex analyses of increasingly dense networks of data. These opportunities include computing recommendations, analysing social networks, finding patterns in transaction networks, scheduling tasks, or inferencing probabilistic models. Many of these tasks involve processing data that has a natural graph representation. Whilst the opportunities are there in the form of access to processing resources and data sets, the way we write software has largely not caught up. Many use MapReduce for scalable processing, but this abstraction has shortcomings with regard to processing graph structured data, especially with iterative and asynchronous processing. This thesis introduces the SIGNAL/COLLECT programming model and framework for efficient parallel and distributed large-scale graph processing. We show that this abstraction captures the essence of many algorithms on graphs in a concise and elegant way. Beyond that, we also show implementations of two complex systems built on SIGNAL/COLLECT: The first system is TripleRush, a distributed in-memory triple store with a novel architecture. The second system is foxPSL, a distributed proba- bilistic inferencing system. Our evaluations show that the SIGNAL/COLLECT framework can efficiently execute simple graph algorithms such as PageRank and that the two complex systems also have competitive performance relative to the respective state-of-the-art. For this reason we believe that SIGNAL/COLLECT is more generally suitable for designing scalable dynamic and complex systems that process large networks of data.

As more aspects of our daily lives are being computerized, ever larger amounts of data are being produced at ever greater speeds. In this data lies great value, and we need technologies that enable us to extract this value. This thesis is concerned with one type of technology that allows us to do this: Distributed Stream Processing Systems (DSPS) are systems consisting of many computers that jointly process, and hence extract value from, large amounts of data at high speeds. This dissertation consists of three research projects that investigate two aspects of DSPS: In two projects, different approaches to increase the efficiency of DSPS were studied and in one project, the value of increased efficiency in stream processing was evaluated. All of these projects have been conducted on real computer systems and they are all of quantitative nature. In the first study, a graph partitioning algorithm was leveraged to schedule the workload within a DSPS. This reduced the communication load between hosts, while maintaining or increasing the throughput of the system. The second study was concerned with the auto-configuration of DSPS. We used a probabilistic black-box optimization strategy called Bayesian Optimization to increase throughput performance of DSPSs through configuration. In the third study, we investigated the value of increased efficiency of a DSPS. This was done by building a DSPS based entity ranking system and by evaluating the effect of timely data processing on the quality of the generated rankings.

Querying the ever-growing Web of Data poses a significant challenge in today’s Semantic Web. The complete lack of any centralised control leads to potentially arbitrary data distribution, high variability of latency between hosts participating in query answering, and, in the extreme, even the (sudden) unavailability of some hosts during query execution. In this thesis we address the question of how to efficiently query the Web of Data while taking into account its scale, diversity and unreliable and uncontrollable nature. We begin by first introducing Avalanche, a federated SPARQL engine which: 1) makes no assumptions about RDF data distribution to SPARQL endpoints, 2) is adaptive to changing network conditions, i.e, can adapt to slow network connections or endpoint unavailability, 3) retrieves up-to-date results from SPARQL endpoints, and 4) is flexible by making limiting assumptions about the structure of participating triple stores. Tailored to address the semantic heterogeneity derived from the Web of Data’s rich and broad semantic diversity, coupled with its characteristic lack of guarantees, Avalanche employs a fragmented query planning approach, under a concurrent and parallel execution model. By fragmented execution, we refer to the fact that the original SPARQL query is rewritten as the union of all fragments which comprise it. A query fragment is defined as the conjunction of all query triple patterns, where a triple pattern can be resolved by only one endpoint. As the Web of Data continues to grow, we postulate that so is the likelihood that large numbers of endpoints will index data, sharing the same vocabularies, thus forming semantically homogenous partitions of the Semantic Web. Focusing on this scenario and in order to address some of Avalanche’s limitations, we introduce x-Avalanche an extension of our original system. Here, we add support for disjunctions by using a distributed union operator capable of scaling to hundreds or thousands of endpoints. Furthermore, we enhance the distributed state management with: a) remote caches aimed to reduce the high latency typical of SPARQL endpoints, b) multicast parallel bind-joins exploiting the SPARQL 1.1 VALUES clause, and c) proxy based execution of x-Avalanche operators. Finally, in x-Avalanche, we introduce a novel and parallel-friendly optimisation paradigm designed not only to offer an optimal tradeoff between total query execution time and fast first results, but also to consider an extended planning space unexplored so far, thus taking the fragmented execution model first introduced in Avalanche to its logical conclusion. Combined, x-Avalanche’s enhancements and optimisations can lead to dramatic performance improvements over top performing state of the art federated SPARQL engines. To conclude, our results show that on average x-Avalanche can be more than one order of magnitude faster when executing SPARQL queries.

Our goal with this research manifesto is to define a roadmap to guide the evolution of the new research field that is emerging at the intersection between crowdsourcing and the Semantic Web. We analyze the confluence of these two disciplines by exploring their relationship. First, we focus on how the application of crowdsourcing techniques can enhance the machine-driven execution of Semantic Web tasks. Second, we look at the ways in which machine-processable semantics can benefit the design and management of crowdsourcing projects. As a result, we are able to describe a list of successful or promising scenarios for both perspectives, identify scientific and technological challenges, and compile a set of recommendations to realize these scenarios effectively. This research manifesto is an outcome of the Dagstuhl Seminar 14282: Crowdsourcing and the Semantic Web.

In this paper, we describe foxPSL, a fast, optimized and extended implementation of Probabilistic Soft Logic (PSL) based on the distributed graph processing framework Signal/Collect. PSL is one of the leading formalism of statistical relational learning, a recently developed field of machine learning that aims at representing both uncertainty and rich relational structures, usually by combining logical representations with probabilistic graphical models. PSL can be seen as both a probabilistic logic and a template language for hinge-loss Markov Random Fields, a type of continuous Markov Random fields (MRF) in which Maximum a Posteriori inference is very efficient, since it can be formulated as a constrained convex minimization problem, as opposed to a discrete optimization problem for standard MRFs. From the logical perspective, a key feature of PSL is the capability to represent soft truth values, allowing the expression of complex domain knowledge, like degrees of truth, in parallel with uncertainty. foxPSL supports the full PSL pipeline from problem definition to a distributed solver that implements the Alternating Direction Method of Multipliers (ADMM) consensus optimization. It provides a Domain Specific Language that extends standard PSL with a class system and existential quantifiers, allowing for efficient grounding. Moreover, it implements a series of configurable optimizations, like optimized grounding of constraints and lazy inference, that improve grounding and inference time. We perform an extensive evaluation, comparing the performance of foxPSL to a state-of-the-art implementation of ADMM consensus optimization in GraphLab, and show an improvement in both inference time and solution quality. Moreover, we evaluate the impact of the optimizations on the execution time and discuss the trade-offs related to each optimization.

The Semantic Web - a web of data formed by interlinked RDF data - has seen a steady increase in size. Triple stores are data management systems for RDF data and offer support for the SPARQL Protocol and RDF Query Language (SPARQL). With SPARQL, RDF data can be retrieved which satisfy user-defined criteria. TripleRush is such a triple store, using a graph-based architecture to efficiently answer SPARQL queries. This thesis discusses the implementation of SPARQL filter support in TripleRush. We discuss how the filters are represented after they have been parsed and describe how they are checked during query execution.

In recent years the rising popularity of outsourcing work to crowds has led to increasing importance to find an effective assignment of suitable workers with tasks. Even though attempts have been made in related areas such as expertise identification most crowdsocuring jobs today are assigned without any predefined policy. Whilst some have investigated assigning jobs based on availability or experience no dominant method has been identified so far. We propose an assignment of tasks to crowd-workers based on their cognitive capability, by conducting a set of cognitive tests and comparing them with performance on typical crowdtasks. Moreover, we examine different setups to predict task performance where a) cognitive abilities, b) performance on previous crowdtasks, or c) both of them, are partially known. Preliminary results show that cognition-based task assignment leads to an improvement in task performance prediction and may pave the way to more intelligent crowd-worker recruitment.

The Semantic Web and Linked Data open huge possibilities for the integration of knowledge from different domains. In the spatial domain, there are already approaches like linkedgeodata.org and GeoSPARQL, which integrate spatial data with georeferenced entities. These projects operate on vector data like polygons. In this explorative work, we discuss the differences between the integration of vector and raster data into the Semantic Web. Further we find, discuss and implement a method for linking raster data to georeferenced entities in the SPARQL query language. We show how geographic operations on raster data can be described in RDF and how we can load raster files from remote servers by implementing service calls using the WMS protocol. We evaluate our approach by measuring and comparing the execution time of different queries in different configurations and find that the largest bottleneck of Linked Raster Data queries is the remote endpoint and that we should fetch as few results from the remote endpoint as possible to reduce the query execution time. At the end of this thesis, we conclude that we achieved our goals defined at the beginning, altough we had to find some workarounds because of the SPARQL engine we used.

The Signal/Collect framework, developed at the University of Zurich is an approach to face the challenge of handling and passing information in large graphs. Its main power lies in its ability to work distributed on multiple machines. The main goal of this thesis is to implement Social Network Analysis measures on the Signal/Collect framework. The focus lies on centrality measures and network properties. These measures reveal what parts of a network have influence on the whole network or try to find communities. The implemented solution is an extension of an existing graph tool with a plugin where all these Social Network Analysis measures can be executed. Furthermore, a more advanced method called “Label Propagation” was implemented which is a way to detect communities in a network and makes it possible to see how these communities change over time. The implemented functionalities were evaluated on a cluster of computers for correctness of the results as well as for computation time.

We study graph vertex ranking algorithms for use in collaborative filtering-based recommender systems. In this paper we evaluate the performance of previously presented ranking algorithms in an off-line study with four different positive-only feedback datasets. Besides measuring the power to predict future user behavior (accuracy), we also consider four non-accuracy performance dimensions: intra-list diversity, item space or catalog coverage, personalization, and novelty/surprisal. We found that most recommendation lists of vertex ranking algorithms are dominated by high popularity items and give lower accuracy, coverage, personalization, and novelty/surprisal scores than lists from nearest-neighbor or latent factor model-based recommenders. By applying a parametrized popularity-penalizing recommendation list re-ranking procedure to random walk vertex transition probability-based ranking algorithms (i.e., P3 and P5 [Cooper et al., 2014]) we observed a positive impact on coverage, personalization and novelty/surprisal. For small degrees of popularity penalization the recommender’s accuracy improved or remained constant and reached in most experiments levels comparable to the state-of-the-art non-graph-based recommenders. The re-ranking procedure reduces the dominance of high popularity items in the recommendation list and allows to optimize the trade-off between accuracy and non-accuracy performance dimensions.

Quality assurance in crowdsourcing markets has appeared to be an acute problem over the last years. We propose a quality control method inspired by Statistical Process Control (SPC), commonly used to control output quality in production processes and characterised by relying on time-series data. Behavioural traces of users may play a key role in evaluating the performance of work done on crowdsourcing platforms. Therefore, in our experiment we explore fifteen behavioural traces for their ability to recognise the drop in work quality. Preliminary results indicate that our method has a high potential for real-time detection and signalling a drop in work quality.

Crowdsourcing platforms like Amazon's Mechanical Turk or CrowdFlower have provided companies with new opportunities to source their work load. But while they allow the completion of massive amounts of work in parallel, the tasks performed on said websites are mainly of simple and isolated nature. The lack of coordination mechanisms has hindered the advance of crowdsourcing into application areas with more complex and interdependent working processes. This thesis provides a domain specific language for the orchestration of complex human computation processes based of the concepts of CrowdLang. We present the capabilities of our language using example implementations of a proof reading algorithm as well as an image categorization application.

Newspaper archives are some of the richest historical doc- ument collections. Their study is, however, very tedious: one needs to physically visit the archives, search through reams of old, very fragile pa- per, and manually assemble cross-references. We present Shax, a visual newspaper-archive exploration tool that takes large, historical archives as an input and allows interested parties to browse the information included in a chronological or geographic manner so as to re-discover history. We used Shax on a selection of the Neue Zu ̈rcher Zeitung (NZZ)—the longest continuously published German newspaper in Switzerland with archives going back to 1780. Specifically, we took the highly noisy OCRed text segments, extracted pertinent entities, geolocation, as well as temporal information, linked them with the Linked Open Data cloud, and built a browser-based exploration platform. This platform enables users to interactively browse the 111906 newspaper pages published from 1910 to 1920 and containing historic events such as World War I (WWI) and the Russian Revolution. Note that Shax is neither limited to this newspaper nor to this time-period or language but exemplifies the power in combining semantic technologies with an exceptional dataset.

null

The combination of the semantic web with stream data opens new possibilities for information retrieval. This thesis develops a system for processing Linked Data streams – Linked Esper. It takes TEF-SPARQL as input query, which handles both event and derived facts. The syntax of the TEF-SPARQL grammar is improved and implemented in this project. The Linked Esper compiles the input query into runnable statements of a stream engine – Esper. Aside from the local execution mode, it also offers a distributed execution mode, which enables scalable processing of large amounts of data. In local as well as in distributed execution mode, different optimization algorithms are applied which improves the overall performances as shown by the experiment results.The evaluation reveals that: first, Linked Esper can handle the most important query features of TEF-SPARQL. Second, it compiles input query to a optimized query plan and then to a distributed execution plan. The results also show that the optimized plan achieves a higher throughput. In addition, partitioning the data flow graph based on optimization algorithms as well as parallelization increases the efficiency of Linked Esper.

Visualisation of high-dimensional data by means of a low-dimensional embedding plays a key role in explorative data analysis. Classical approaches to dimensionality reduction, such as principal component analysis (PCA) and multidimensional scaling (MDS), struggle or even fail to reveal the relevant data characteristics when applied to noisy or nonlinear data structures. We present a novel approach for dimensionality reduction in combination with an automatic noise cleaning. By employing self-organising agents that are governed by the dynamics of the superparamagnetic clustering algorithm, the method is able to generate denoised low-dimensional embeddings for which the characteristics of nonlinear data structures are preserved or even emphasised. These properties are illustrated and compared to other approaches by means of toy and real-world examples.

null

TripleRush is a distributed RDF triple store that can be queried with a subset of SPARQL. The index structure of TripleRush is represented as a graph. Executing a query on TripleRush will send messages along the edges in the index graph. This leads to messages being sent between different server nodes as the index graph vertices are distributed over multiple servers. The hypothesis is, that a big part of the query execution time is due to network latency. Reducing the amount of messages traversing the network during query execution would result in improved execution times. The goal of this thesis is to improve the query execution times of a specific set of queries by analyzing how TripleRush executes them and devising optimization strategies to reduce the inter-node network traffic. These optimizations are based on query execution logs of these queries. These logs represent a sub-graph, the query graph, of the index structure. The discussed approach uses the query graph to re-distribute the relevant parts of the index structure. This optimizes the index graph in such a way that the studied set of queries will run faster due to the optimized vertex placement. The aim is to re-partition parts of the index structure to reduce inter-node edges while maintaining an even distribution for load balancing. Two approaches are proposed to re-partition and transform the query graph to produce an optimized distribution of TripleRush index vertices. The resulting datasets can be re-introduced into TripleRush with minimal modifications to TripleRush. It has been found that one of the approaches shows promise to significantly improve query execution times for the studied set of queries, while maintaining the distributed load balancing.