Implementing iterative algorithms with SPARQL

Abstract

The SPARQL declarative query language includes innovative capabilities to match subgraph patterns within a semantic graph database, providing a powerful base upon which to implement complex graph algorithms for very large data. Iterative algorithms are useful in a wide variety of domains, in particular in the data-mining and machine-learning domains relevant to graph analytics. In this paper we describe a general mechanism for implementing iterative algorithms via SPARQL queries, illustrate that mechanism with implementation of three algorithms (peer-pressure clustering, graph di↵usion, and label propagation) that are valuable for graph analytics, and observe the strengths and weaknesses of this approach. We find that writing iterative algorithms in this style is straightforward to implement, with scalability to very large data and good performance.