September 14, 2016

Publications

Haslhofer, B., Karl, R., Filtz, E. O Bitcoin Where Art Thou? Insight into Large-Scale Transaction Graphs. SEMANTICS 2016, Leipzig. (pdf)

Bitcoin is a rising digital currency and exemplifies the growing need for systematically gathering and analyzing public transaction data sets such as the blockchain. However, the blockchain in its raw form is just a large ledger listing transfers of currency units between alphanumeric character strings, without revealing contextually relevant real-world information. In this demo, we present GraphSense, which is a solution that applies a graph-centric perspective on digital currency transactions. It allows users to explore transactions and follow the money flow, facilitates analytics by semantically enriching the transaction graph, supports path and graph pattern search, and guides analysts to anomalous data points. To deal with the growing volume and velocity of transaction data, we implemented our solution on a horizontally scalable data processing and analytics infrastructure. Given the ongoing digital transformation in financial services and technologies, we believe that our approach contributes to development of analytics solutions for digital currency ecosystems, which is relevant in fields such as financial analytics, law enforcement, or scientific research.

Filtz, E., Savenkow, V., Umbrich, J. On finding the k shortest paths in RDF data. Intelligent Exploration of Semantic Data Workshop (IESD 2016), co-located with ISWC 2016, Kobe, Japan. (pdf)

Finding relationships between entities in RDF data is in the heart of many exploration tasks. General path enumeration algorithms are typically used for computing such relationships, nding top k short-est paths being of special interest. The k shortest paths problem has been thoroughly studied for the weighted graph case, the two most pop-ular generic algorithms are due to Eppstein and to Yen. Along with the Dijkstra’s shortest path algorithm upon which they build, these two algorithms are available in most libraries and graph databases. In the RDF context, however, the graph is unlabeled but can have multi-edges, and the found paths can contain cycles, so applying the mentioned algorithms is either impossible (Yen’s) or suboptimal. It is a folklore knowledge that the traditional breadth rst search (BFS) can be easily adapted to compute the k shortest paths. However, for dense graphs and large k, both
time and memory consumption become critical. We discuss two BFS adaptations which are easy to implement and substantially boost performance when solving the k shortest paths problem.