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

The Semantic Web is a concept for extending the World Wide Web with semantic information in a way that computers are able to ”understand” it. A technical realization for that is provided by the Resource Description Framework (RDF). Thereby the information is stored uniquely in the form of triples (subject, predicate, object). Such data can be queried using the SPARQL Protocol And RDF Query Language (SPARQL). There are a number of native and relational-based indexing schemes for RDF. A read-optimized schema is depicted by Hexastore, whereat for all six triple permutations a separate index is created. Rdfbox is a tool for querying and storing RDF data. It extends the Hexastore indexing paradigm with update/write support by relying on B+Trees as the main physical index storage. SPARQL 1.1 brought the GRAPH clause that allows for querying the source of RDF data. The goal of this thesis is to extend Rdfbox with support of that GRAPH clause.

The Semantic Web is growing at a fast pace and single machines can reach the limits of their capabilities when trying to manage RDF data sets that contain billions of triples. In order to tackle this problem, this thesis extends Rdfbox, a Hexastore-based semantic database management system, with support for distributed index backends, a parallelised query execution engine and a distributed index loader. Evaluations show that the distributed index loader outperforms previous approaches and that the improved query execution engine is performance-critical with distributed and indices. But limits to the efficiency of distributed indices in Rdfbox are discovered that may require fundamental changes in the approach to query resolution in order to achieve a significant performance increase.

Event scheduling is a group decision-making process in which social dynamics influence people’s choices and the overall outcome. As a result, scheduling is not simply a matter of finding a mutually agreeable time, but a process that is shaped by social norms and values, which can highly vary between countries. To investigate the influence of national culture on people’s scheduling behavior we analyzed more than 1.5 million Doodle date/time polls from 211 countries. We found strong correlations between characteristics of national culture and several behavioral phenomena, such as that poll participants from collectivist countries respond earlier, agree to fewer options but find more consensus than predominantly individualist societies. Our study provides empirical evidence of behavioral differences in group decision-making and time perception with implications for cross-cultural collaborative work.

null

Computer systems still struggle with tasks such as categorizing photos, translating phrases or verifying collected data. Crowdsourcing platforms like Amazon’s Mechanical Turk are the ideal place to solve such challenging assignments by using the collective power of human beings, which are willing to work for a small amount of money. However, not every individual pro- vides perfect answers – some of them try to maximize their income by cheating, while others may misunderstood the task or do not have sufficient skills to solve it properly. In order to hold a certain level of quality, it is necessary to apply some sort of quality assurance mechanisms. This thesis will compare two such mechanisms by applying them on three different use cases and finally presents results about the performance in terms of quality, time and costs.

Rdfbox is a native triple store and implements the Hexastore indexing concept. Hexastore permutes RDF triple elements (subject, predicate, object) to build six indexes. Rdfbox takes this indexing scheme and maps it to key-value storage. Prior to this work, it used the Tokyo Cabinet key-value store as its indexing backend. This work extends it with Kyoto Cabinet, LevelDB and Redis backends and enables to easily exchange them, even on a per-index level. Further, Rdfbox's triple loading is analyzed, improved and adapted to the added backends. The backends' performance is then compared and analyzed with synthetic and real-world data sets and queries.

null

This volume contains the papers presented at the 1st International Workshop on ”Crowdsourcing the Semantic Web” that was held in conjunction with the 12th International Semantic Web Conference (ISWC 2013), 21-25 October 2013, in Sydney, Australia. This interactive workshop takes stock of the emergent work and chart the research agenda with interactive sessions to brainstorm ideas and potential applications of collective intelligence to solving AI hard semantic web problems.

null

TripleRush is a parallel in-memory triple store designed to address the need for efficient graph stores that answer queries over large-scale graph data fast. To that end it leverages a novel, graph-based architecture. Specifically, TripleRush is built on our parallel and distributed graph processing framework Signal/Collect. The index structure is represented as a graph where each index vertex corresponds to a triple pattern. Partially matched queries are routed in parallel along different paths of this index structure. We show experimentally that TripleRush takes about a third of the time to answer queries compared to the fastest of three state-of-the-art triple stores, when measuring time as the geometric mean of all queries for two common benchmarks.

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 inter-machine communication. 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 find 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.