DFG Priority Programme SPP 1736: Algorithms for Big Data

This project explores methods to reduce the total energy consumption using scheduling, based on speed-scalable processors where typically much less energy is consumed if the processors run slower. While jobs come with deadlines (hence slowing down is not always possible), preemption and migration of jobs open up additional optimization opportunities. The scheduling objective is to minimize the total energy consumption while taking into account all constraints. Albers et al. considered non-homogeneous settings where trade-offs between speed and energy can differ among the set of processors used [2]. The authors improve the state of the art by providing several new approaches that are conceptionally easier and hence more practical than previous solutions.

One line of research in the project deals with dynamic, approximate, and online methods in the context of parallelism and memory hierarchies. An important application area is graph algorithms (see [22] and Sect. 3 for a more detailed treatment of joint results on graph generation in parallel external memory). Another line of research in (P2) aims to use methods from Game Theory (truthful mechanisms) in order to reasonably solve memory assignment problems for concurrently running programmes in shared memory environments. This is particularly challenging if the users do not have to pay money for the RAM their executed programmes occupy: in the absence of money, selfish programmers may claim to need unreasonably large chunks of central memory for a “fast” execution of their programmes. First results in a static setting with fixed RAM chunk sizes appeared in [18], where forced waiting times are used as a currency in order to yield a truthful mechanism that returns solutions minimizing the makespan, i.e. the maximum completion time.

The research topic of this project is the design and analysis of distributed algorithms that continuously compute functions of streams of data, arising from many devices of potentially different types. Due to huge volumes and velocity, data can neither be completely stored, nor sent to a central server via a network, nor fully processed in real time. Initial results concern, among others, the communication complexity of so-called distributed aggregation problems; Mäcker et al. [20] considered the expected message complexity for the top-k Position Monitoring problem. Here, the task is to compute the IDs of the devices that observe the k largest items at every time step. They also gave an approximation variant [21].

3D+T Terabyte Image Analysis ¹ R. Mikut and P. Sanders (KIT Karlsruhe)

The data dealt with in this project stems from light-sheet fluorescence microscopy, which is frequently applied in developmental biology in order to perform long-time observations of embryonic development. An exemplary application domain is tracking of objects (e.g., cell nuclei, cytoplasm, nano particles) in microscopic images where different object classes are labelled with particular fluorescent dyes. In the project, time series of high resolution 3D images of developing zebrafish embryos yield more than 10 terabytes per embryo, which is significantly more than state-of-the-art software tools can typically handle. While striving for improved algorithms on modern hardware, it is also important to carefully test the result quality of these new approaches. To this end, the project has successfully investigated methods to create large, realistic, simulated inputs with ground truth that can be used to quantitatively assess result quality [30].

The Project is concerned with kernelization in big-data contexts. Given a concrete optimization question q, a kernelization algorithm compresses a data set A to \(A'\) such that q can still be answered from \(A'\). Ideally, the size of \(A'\) is much smaller than that of A and depends only polynomially on some structures capturing particular aspects about the optimization question (and not on the size of A). As an example, Etscheid and Mnich discussed kernelization techniques for the Max-Cut problem [14]; more details are provided in Mnich’s article on big data algorithms beyond machine learning in this special issue.

The scientific goal of the project is to devise novel methods to cluster large-scale static and dynamic online social networks. Their approach is based on skeleton structures, i.e. sparse (sub-)graphs, that represent the essential structural properties of the graphs. Besides supporting efficient clustering approaches, these skeletons are used to find patterns in online social relationships and interactions. An example concerns components of quasi-threshold graphs ² since they share features frequently found in social network communities. Communities are then detected by finding a quasi-threshold graph that is close to a given graph in terms of edge edit distance. The problem is \({{\mathcal {N}}}{{\mathcal {P}}}\)-hard and existing FPT-approaches also fail to scale on real-world data. Hence, the project introduced Quasi-Threshold Mover (QTM), the first scalable quasi-threshold editing heuristic [9]. QTM constructs an initial skeleton forest and then refines it by moving vertices to reduce the number of edits required. (P6) is also active in graph visualization and graph generation (cf. Sect. 3).

Engineering Algorithms for Partitioning Large Graphs (See footnote 1) P. Sanders, Ch. Schulz, and D. Wagner (KIT Karlsruhe)

(Hyper-)Graph partitioning is crucial in many big-data graph applications as it subdivides the problem instance into smaller (and thus more manageable) pieces with little interaction. Unfortunately, Hypergraph Partitioning is \({\mathcal {N}}{\mathcal {P}}\)-hard, and it is even \({\mathcal {N}}{\mathcal {P}}\)-hard to obtain good approximations. Therefore, in practice, multi-level heuristics are applied. Project (P7) has significantly contributed to the large body of previous work in the area; see [10] for an overview. Their recent k-way partitioning result [1] represents the state of art concerning high-quality hypergraph partitioning: it always computes better solutions and is faster than some of the competitors.

This project looks into algorithms that operate on very large networks and the dynamics that arise from the competition or the cooperation between such algorithms. An initial result concerned the exploration of an unknown undirected graph with n vertices by an agent possessing very small memory [12]. While upper and lower memory bounds of \(\Theta (\log n)\) had been shown before for this setting, the project reduced the memory requirement of the agent to \(O(\log \log n)\) for bounded-degree graphs in case the agent gets access to another \(O(\log \log n)\) indistinguishable markers, called pebbles. A pebble can be dropped or collected whenever the agent visits a vertex, leaving or removing a mark. (P8) also showed that for sub-linear agent memory, \(\Omega (\log \log n)\) pebbles are required.

Methods for the solution of static routing problems have been successfully optimized over many decades. Unfortunately, real-life applications such as evacuation planning, logistic planning, or navigation systems for road networks crucially depend on dynamic edge costs that change over time (and even depend on the solution). The standard approach to build a huge time-expanded network whose size could be exponential in the input size becomes infeasible for big-data graphs due to memory limitation. Hence, project (P9) investigate alternative methods that try to avoid this data explosion. For example, Schlöter and Skutella presented memory-efficient solutions for evacuation problems [27].

This Project focuses on the development of local methods to compute classic network analytic measures like centrality indices, network motifs (subgraphs) and clustering. Commonly, these measures are based on global properties of the graph such as the distance between all pairs of vertices or a global ranking of similar pairs of vertices or edges, thus, resulting in at least quadratic time complexity. Hence, it is difficult to scale those fundamental approaches directly to big-data graphs. Recent work in this direction concerns the identification of network motifs in the so-called fixed degree sequence model (FDSM) which refers to the set of all graphs with the same degree sequence excluding multi-edges or self-loops. Schlauch and Zweig proposed a set of equations, based on the degree sequence and a simple independence assumption, to estimate the occurrence of a set of subgraphs in the FDSM and empirically supported their findings [26]. Other parts of the research in this project have also been included in a newly published textbook [33].

Dealing with large-scale convex optimization problems, the project developed a generic optimization code generator (GENO) which is capable of providing generic, parallel and distributed convex optimization software. Discrete and combinatorial big-data optimization problems can greatly benefit from GENO as well as machine learning, data analytics and other fields of research such as network analysis. The GENO approach to generic optimization is based on an extension of the alternating direction method of multipliers by Giesen and Laue [16] and is defined by a tight coupling of a modeling language and a generic solver. The modeling language allows to specify a class of (convex) optimization problems, and the generic solver gets instantiated for the specified problem class. Comparing the code produced by GENO with state-of-the-art, hand-tuned, problem-specific implementations show that GENO is faster and delivers better results (in terms of accuracy or objective function value for non-convex problems).

This project focuses on network analysis with three combinatorial optimization tasks with numerous applications: graph clustering, graph drawing, and network flow. Some of those applications are in the biological sciences, where most data sets are massive and contain inaccuracies. Hence, an inexact, yet faster solution process with approximation algorithms and heuristics is often useful. As an example, Bergamini and Meyerhenke [5] proposed the first betweenness centrality approximation algorithms with a provable bound on the approximation error for fully dynamic networks. Another important topic dealt with in (P12) concerns algebraic solvers. In 2016, Bergamini et al. [6] developed two algorithms that accelerate the current-flow computation for one vertex or a reasonably small subset of vertices significantly. The work also provides a reimplementation of the lean algebraic multigrid solver by Livne and Brandt [19] and is integrated into the open-source network analysis software NetworKit [28], which is freely available to the public.

Protecting outsourced data in cloud storage and cloud computing scenarios and when handling big data through third parties is rather complicated, since standard cryptographic means, such as encryption, in general do not work here. This is caused by the very nature of encryption: scrambling all reasonable information, the semantics of the data are hidden and cannot be used by third parties to perform operations, and the option of decrypting the data for the operations would violate the idea of protecting the data from the service provider. Thus, project (P13) works on efficient operations on secured data, targeted as well as through the deployment of functional encryption and indistinguishable obfuscation, certification of cryptographic primitives, and new algorithmic techniques for big cryptographic data. In 2017, Esser et al. [13] proposed new algorithms with small memory consumption for the Learning Parity with Noise (LPN) problem, both classically and quantumly. By using different advanced techniques they obtained a hybrid algorithm that achieves the best currently known run time for any fixed amount of memory.

As mentioned before, in our modern digital society, we rely on encryption and signature schemes for security. However, today’s cryptographic schemes do not scale well, and thus are not suited for the increasingly large sets of data they are used on. For instance, the security guarantees currently known for RSA encryption, which is an important type of encryption scheme, degrade linearly in the number of users and cipher texts. Therefore, project (P14) aims to construct cryptographic schemes that scale well to large scenarios. Until now, several practical cryptographic schemes suitable for truly large settings have been developed by the project, such as the first authenticated key exchange protocol whose security does not degrade with an increasing number of users or sessions [3], the first identity-based encryption scheme whose security properties do not degrade in the number of ciphertexts, and the first public-key encryption scheme for large scenarios that does not require a mathematical pairing [15] (awarded the “Best Paper” at the EUROCRYPT 2016 conference). The last-mentioned scheme is solely based upon a very standard computational assumption, namely the Decisional Diffie-Hellman assumption, and is thereby efficient.

Within the predecessor priority programme on algorithm engineering (2007–2013), H. Bast and her group have developed semantic full-text search, a deep integration of full-text and ontology search. Their search engine Broccoli [4] is able to handle queries like “Astronauts who walked on the moon and who were born in 1925–1930” or “German researchers who work on algorithms” where parts of the required information is contained in ontologies, whereas other parts only occur in text documents. In (P15), they aim to scale semantic search to text sets and ontologies being about 100 times larger than in their original Broccoli engine while increasing query quality at the same time. More details can be found in their article on a quality evaluation of combined search on a knowledge base and text included in this special issue.

The world wide web, digital libraries, biological sequences like DNA, or proteins all constitute large textual data that need to be stored, structured, searched, and compressed efficiently. The amount of such data has grown much faster than the storage and computation capacities of common desktop computers, by several orders of magnitude. Data structures for texts satisfying those needs, for instance suffix arrays or inverted indexes, are called text indexes and are the basic building block of all text-based applications, including well-known services like internet search engines. Since algorithms and data structures for texts are fundamentally different from those for other kind of data, project (P16) aims to develop an own algorithmic toolbox for large texts using both shared memory and distributed memory parallelism, focusing on general-purpose text indexes related to suffix arrays due to their applicability to any text type and their extended functionality. One step towards that goal was basic research on building blocks, yielding results, such as an extensive journal paper [8] that studies practical parallel string sorting algorithms based on the most important classical sorting algorithms. Another important step was to build a prototype of a tool for implementing algorithms that process large data sets on distributed memory machines. The result, Thrill [7], is based on C++, offers a rich set of operations on distributed arrays such as map, reduce, sort, merge, and prefix-sum. It can fuse pipelines of local operations into tight loops optimized at compile time, considerably outperforming established tools such as Spark or Flink.

The development of a new drug is a complex and costly process. The identification and optimization of bioactive molecules is to a large extent supported by computer-based methods, e.g. the semi-automated classification of molecules and their functional relationships. This is a big-data problem, since the theoretical chemical space is estimated to contain around \(10^{62}\) molecules. Many approaches within rational drug design are based on the basic hypothesis that structural similar molecules also show a similar biological effect. Common similarity measures use fast but inexact chemical fingerprints, yielding a high number of false positives. By proposing the Maximum Similar Subgraph (MSS) paradigm, an extension of the \({\mathcal {N}}{\mathcal {P}}\)-complete Maximum Common Subgraph problem with allowed deviations with respect of similar bioactivity, the project (P17) introduced an exact comparison method based on searching and clustering graph representations of molecules, where atoms are the vertices and bonds between the atoms are represented by edges. In 2017, Schäfer and Mutzel presented StruClus [25], a structural clustering algorithm for large-scale datasets of small labeled graphs based on the MSS paradigm. This algorithm achieves high quality and (human) interpretable clusterings, has a runtime linear in the number of graphs and outperforms competing clustering algorithms. The project also continuously develops Scaffold Hunter [24], a flexible visual analytics framework for the analysis of chemical compound data. One application of this tool is to identify whole scaffolds that are exchangeable by similar shape. This leads to a reduced graph which allows for a more efficient MSS computation. Scaffold Hunter was initiated as a collaboration with the group of H. Waldmann (Max Planck Institute of Molecular Physiology, Dortmund).

This is a joint project between A. Srivastav from the Department of Computer Science of Kiel University, T. Reusch from GEOMAR Helmholtz Centre for Ocean Research Kiel and Ph. Rosenstiel from the Institute of Clinical and Molecular Biology University Medical Center Schleswig-Holstein, dealing with the genome assembly problem: given a high number of sequences of an unknown genome, called reads, which may contain errors, and perhaps some extra information, the task is to reconstruct the genome. The objectives of (P18) are the development of a comprehensive mathematical model for genome assembly as an optimization problem, the engineering and theoretical analysis of distributed and streaming assemblers and distributed probabilistic data structures to hold intermediate information, the engineering of an assembler based on the maximum-likelihood method, and applications to marine species investigated in the group of Th. Reusch and to the variational calling problems in the group of Ph. Rosenstiel. In 2017, Wedemeyer et al. [32] presented their read filtering algorithm Bignorm. They show how probabilistic data structures and biological parameters can be used to drastically reduce the amount of data prior to the assembly process and demonstrate its significance by the assembly of genomes of single-celled species.