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

In the Big Data era, data exploration and visualization systems are getting more and more important. In the last few years very large datasets have become a major research challenge and with the development of the Semantic Web an increasing amount of semantic data has been created in form of Resource Description Framework (RDF). With this Design Science thesis, a tool was created to display large amounts of semantic data in serialized N-Triples format as graphs in a web application. The Spectral Coarse Graining method was used in order to be able to produce the representation with very large amounts of data. This Bachelor thesis provides a basic understanding of the topics Semantic Web, Linked Data, RDF and Spectral Coarse Graining. It shows the results of the prototype, explains the architecture of the application, presents the frameworks and databases used, and describes the implemented features and functionalities. For the visualization of the RDF data, seven state-of-the-art, graph-based JavaScript frameworks are analyzed and evaluated using a comprehensive criteria catalog. Finally, the work provides an overview of similar visualization systems for the desktop and the web.

In the first part of this thesis, the second iteration with the platform COLDATA is presented. The goal of COLDATA is to let freelancers work on sub-tasks on a data analysis project, lead and supervised by a data scientist. With a Design Science approach, the evaluation of the first iteration is analyzed and improvements are derived, implemented and evaluated with a usabilitytest. The second part contains the technical documentation, consisting of different manuals. In the third part, the solutions of an exercise in a master's course in data analysis at the EPFL were analyzed. The central question to answer was, why the results of such data analysis tasks differ although the data and the initial questions were the same. The results are different factors, that influence explicit and implicit decisions made during the analysis.

Data stream applications are becoming increasingly popular on the web. In these applications, one query pattern is especially prominent: a join between a continuous data stream and some background data (BGD). Oftentimes, the target BGD is large, maintained externally, changing slowly, and costly to query (both in terms of time and money). Hence, practical applications usually maintain a local (cached) view of the relevant BGD. Given that these caches are not updated as the original BGD, they should be refreshed under realistic budget constraints (in terms of latency, computation time, and possibly financial cost) to avoid stale data leading to wrong answers. This paper proposes to model the join between streams and the BGD as a bipartite graph. By exploiting the graph structure, we keep the quality of results good enough without refreshing the entire cache for each evaluation. We also introduce two extensions to this method: first, we consider a continuous join between recent portions of a data stream and some BGD to focus on updates that have the longest effect. Second, we consider the future impact of a query to the BGD by proposing to delay some updates to provide fresher answers in future. By extending an existing stream processor with the proposed policies, we empirically show that we can improve result freshness by 93% over baseline algorithms such as Random Selection or Least Recently Updated.

Our society is full of rules: rules authorize us to achieve our goals by endowing us with legitimation, they provide the necessary structure to understand the chaos of conflicting indications or tell-tales of a situation, and oftentimes they legitimate our actions. But rules in society are different than logical rules suggest to be: they are not as unshakeable, continuously renegotiated, often even accepted to be wrong but still used, and used as inspiration in the situated context rather than universal truth. Based on theories about the role of technology in society, this talk will first try to convey the role of rules in social science theory. Extending these insights, it will draw on examples to illustrate how they might be transferred to computer science or artificial intelligence to derive systems that are attuned to the role of rules in social environments and adhere to social rules in the environment in which they are used.

The validity of statistics in scientific publications is crucial for accurate and reliable results. However, there are many publications, that are not acceptable in this regard. This work confronts this problem by proposing a tool that allows for the automated validation of statistics in publications, focusing mainly on statistical methods and their assumptions. The validation process is rule-based using partially crowd-sourced workers hired from the Amazon Mechanical Turk (MTurk) platform. The tool and the validation process, were successfully tested on 100 papers from the ACM Conference on Human Factors in Computing Systems (CHI) and further applied to examine the usage of statistics over the years in CHI papers.

Enterprise social networking has become an important tool to enhance communication within companies. This thesis seeks deeper knowledge about how these networks can be analysed in order to provide managers with actionable insights. We investigate data from the Yammer platform within ABB, a Swedish-Swiss high-tech engineering multinational. In the first part of the thesis, we conduct topic analysis on ABB's Yammer groups. We perform latent Dirichlet allocation (LDA) on data from ABB's website and use the resulting topics to improve the topic model built on the Yammer dataset. Our modification of LDA uses prior topics to guide the creation of new topics. We find that prior topics can help to improve the output of LDA. Furthermore, we show that topic models can be used to detect similar groups within a corporate social network. In the second part, we introduce NetDive, a web-based tool to improve group management. We present meaningful metrics, mainly based on aggregate statistics, and recommendation that support every day actions of group managers.

From the very early days of the World Wide Web, researchers identified a need to be able to understand the semantics of the information on the Web in order to enable intelligent systems to do a better job of processing the booming Web of documents. Early proposals included labeling different kinds of links to differentiate, for example, pages describing people from those describing projects, events, and so on. By the late 90’s, this effort had led to a broad area of Computer Science research that became known as the Semantic Web [Berners-Lee et al. 2001]. In the past decade and a half, the early promise of enabling software agents on the Web to talk to one another in a meaningful way inspired advances in a multitude of areas: defining languages and standards to describe and query the semantics of resources on the Web, developing tractable and efficient ways to reason with these representations and to query them efficiently, understanding patterns in describing knowledge, and defining ontologies that describe Web data to allow greater interoperability.

Many real-world tasks can be modeled as constraint optimization problems. To ensure scalability and mapping to distributed scenarios, distributed constraint optimization problems (DCOPs) have been proposed, where each variable is locally controlled by its own agent. Most practical applications prefer approximate local iterative algorithms to reach a locally optimal and sufficiently good solution fast. Most implementations presented in the literature, however, only explored small-sized problems, typically up to 100 agents/variables. We implement CUILT, a scalable mix-and-match framework for Local Iterative Approximate Best-Response Algorithms for DCOPs, using the graph processing framework SIGNAL/COLLECT, where each agent is modeled as a vertex and communication pathways are represented as edges. Choosing this abstraction allows us to exploit the generic graph-oriented distribution/optimization heuristics and makes our proposed framework scalable, configurable, as well as extensible. We found that this approach allows us to scale to problems more than 3 orders of magnitude larger than results commonly published so far, to easily combine algorithms by mixing and matching, and to run the algorithms fast, in a parallel fashion.

We study Two-Class Collaborative Filtering (TCCF) problems with positive and negative class prediction. Our goal is to distinguish between positive and negative samples by predicting positive samples at the top and negative samples at the bottom of a personalized ranking list. Based on Bayesian Personalized Ranking Matrix Factorization (BPRMF) from Rendle et al. (2012) and Logistic MF from Johnson (2014), we introduce different new models to address TCCF problems. We evaluate our models on MovieLens 100K/1M, Slashdot-Zoo and Book Crossing datasets and compare the results with an evaluation of BPRMF, Logistic MF, SGDReg (Levy and Jack, 2013) and GAUC-OPT (Song and Meyer, 2015). With our models we outperform Logistic MF, BPRMF and GAUC-OPT on either AUC, Hit-Rate@10, Precision@20 and their respective negative evaluation metrics. However all our evaluation results are surpassed by SGDReg, which excels in most evaluation metrics on the examined datasets.

Despite the increased use of digital transfers in the banking industry, cash remains an important means of payment. Automated Teller Machines (ATM) that dispense cash are costly to deploy and maintain. Very little has been done to optimize the number and placement of ATMs. This Bachelor Thesis proposes a method to optimize the ATM network based on ATM transactions rather than the usual geo-political placement strategy. The method simulates removing different ATM combinations from the network and then predicts the customer reactions to the changes. Based on the results of several iterations, it is possible to compute the optimal operation cost. The conclusions of this thesis should be interpreted with caution. Due to data protection laws and business practices, the necessary data was only partly available. However, the findings show that it is definitely possible to optimize a retail bank's ATM network based on data, without alienating their customers.

In a time with endless and easily accessible data, valuable information is hidden in the unstructured format of text. Here, an unsupervised topic model is used is detect geospatial proximity from online user text reviews. By tuning the model parameters and using different dataset, the generated topics have shown different degrees of abstraction in terms of geographical proximity. Hotels assigned to the same topics share geographical similarities. The location of the areas formed by those hotel corresponds to the topic keywords and its size is proportional to the topic weight. The combination of keywords and weight provides insight into contextual similarities.

In some auction domains, there is uncertainty regarding the final availability of the goods being auctioned off. For example, a government may auction off spectrum from its public safety network, but it may need this spectrum back in times of emergency. In such a domain, standard combinatorial auctions perform poorly because they lead to violations of individual rationality (IR), even in expectation, and to very low efficiency. In this paper, we study the design of core-selecting payment rules for such domains. Surprisingly, we show that in this new domain, there does not exist a payment rule with is guaranteed to be ex-post core-selecting. However, we show that by designing rules that are “execution-contingent,” i.e., by charging payments that are conditioned on the realization of the availability of the goods, we can reduce IR violations. We design two core-selecting rules that always satisfy IR in expectation. To study the performance of our rules we perform a computational Bayes-Nash equilibrium analysis. We show that, in equilibrium, our new rules have better incentives, higher efficiency, and a lower rate of ex-post IR violations than standard core-selecting rules.

This Bachelor thesis recapitulates existing approaches towards distributed, large-scale RDF reasoning, which are based on the MapReduce model. Specifically, the existing inference engine Cichlid will be analyzed more closes and some improvements are suggested. Following this, a graph-based approach towards RDF reasoning will be presented, along with concrete examples for implementation. In particular, this thesis includes an alternate method for applying transitive inference rules. For this, a Pregel-based algorithm computes the transitive closure of the RDF graph. Tests show the functionality of the graph-based approaches. Concrete measurements of real-world performance and comparison to existing approaches are of limited meaningfulness.

The most popular algorithm for recommender systems utilizes the collaborative filtering technique which makes only use of the user-item rating matrix. This thesis introduces two approaches which employ extra data encoded as feature vectors. One of our proposed models, MPCFs-SI, is based on a nonlinear matrix factorization model for collaborative filtering (MPCFs) and utilizes the extra data to regularize the model. The second model called MFNN is an ensemble of a matrix factorization and a neural network and uses the extra data as an input to the neural network. Our results show that MPCFs-SI outperforms the baseline recommender MPCFs on a subset of both MovieLens 100k and MovieLens 1M datasets. MFNN is inferior to the MPCFs model on our MovieLens 100k subset, however, it is at a similar performance level as MPCFs-SI on the bigger MovieLens 1M subset.

The topic of this thesis is SPARQL query approximation on RDF data. In standard database contexts, using approaches for approximating query results is common. An example of a motivation for using query approximation instead of accurate execution is that resources in the form of computing power, disk space, money, and database access can be restricted. Approximating the query results can serve as a decision basis for or against further processing of a querying strategy. The thesis analyses an approach to transfer one of three presented methods for query approximation to the Semantic Web context. The chosen algorithm uses Bloom filters to represent datasets of query conditions and additionally to join the sub results for the result approximation. The algorithm was implemented in Java code and compared to the actual query execution on the aspects of runtime and relative error of the results. The evaluation has shown that the approach is not yet sufficiently elaborated for overall positive results. With the limitations and optimization ideas that are presented, a conclusion is drawn with an outlook to future work.