SPP 1736:  Algorithms for Big Data

• Subject Area: Computer Science, Systems and Electrical Engineering
• Term: from 2014 to 2023
• Website: Homepage
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 237179235

Computer systems pervade all parts of human activity and acquire, process and exchange data at a rapidly increasing pace. As a consequence, we live in a Big Data world where information is accumulating at an exponential rate and often the real problem has shifted from collecting enough data to dealing with its impetuous growth and abundance. As the speed improvement of single processing cores has basically stalled, the hardware industry keeps on increasing the number of processors/cores per board or graphics card, and also invests into improved storage technologies. This means our algorithms must become massively parallel using memory access patterns with high locality. More and more often, we will not even be able to consider all available data. These are challenges that need new algorithmic ideas. The Priority Programme wants to improve the situation by bringing together expertise from different areas. On the one hand, recent hardware developments and technological challenges need to be appropriately captured in better computational models. On the other hand, both common and problem specific algorithmic challenges due to big data are to be identified and clustered. Considering both sides, a basic toolbox of improved algorithms and data structures for big data sets is to be derived, where we do not only strive for theoretical results but intend to follow the whole algorithm engineering development cycle. Concrete algorithmic challenges include exploiting parallelism (multicores, GPUs, clouds) and memory-hierarchies (hard-disks, flash-memory, caches), dealing with large-scale dynamic data updates, processing compressed and encrypted data, approximation and online processing under resource constraints or reducing the consumption of energy by algorithmic measures. What distinguishes our initiative from most previous work is that we do not only want to tackle certain problems in isolation but aim to find solutions for several aspects at once: for example, given a concrete application challenge, how can we use massive parallelism, memory-hierarchies, specific data features and novel algorithmic techniques to yield better overall performance. Right from the start, a close interaction with various applications areas (like bioinformatics and information retrieval) will make sure that besides fundamental problems, a bunch of practically relevant questions will be tackled for the benefit of several communities.

• DFG Programme: Priority Programmes
• International Connection: Switzerland

Projects

• Algorithmic Foundation for Genome Assembly: Streaming and External Memory Techniques (Applicants Reusch, Ph.D., Thorsten ;  Rosenstiel, Ph.D., Philip Caspar ;  Srivastav, Anand )
• Algorithms for solving time-dependent routing problems with exponential output size (Applicant Skutella, Martin )
• Big-Data-DynAmO: Dynamic, Approximate, and Online Methods for Big Data (Applicant Meyer, Ulrich )
• Competitive Exploration of Large Networks (Applicant Klimm, Max )
• Coordination Funds (Applicant Meyer, Ulrich )
• DisDaS: Distributed Data Streams in Dynamic Environments (Applicant Meyer auf der Heide, Friedhelm )
• Efficient Semantic Search on Big Data (Applicant Bast, Hannah )
• ENES: Energy-Efficient Scheduling (Applicant Albers, Susanne )
• FINCA: Fast Inexact Combinatorial and Algebraic Solvers for Massive Networks (Applicant Meyerhenke, Henning )
• GraBaDrug: Graph-Based Methods for Rational Drug Design (Applicants Koch, Oliver ;  Mutzel, Petra )
• MASS-TEXT: Massive Text Indices (Applicant Fischer, Johannes Christian )
• Phase Transitions and Mean-Field Approaches for the efficient computation of expected properties of the Fixed Degree Sequence Model (Applicant Zweig, Katharina A. )
• Scalable Cryptography (Applicant Kiltz, Eike )
• Scaling Up Generic Optimization (Applicant Giesen, Joachim )
• SecOBig: Security-Preserving Operations on Big Data (Applicants Fischlin, Marc ;  May, Alexander )
• Skeleton-based Clustering in Big and Streaming Social Networks (Applicants Brandes, Ulrik ;  Wagner, Dorothea )

• Spokesperson: Professor Dr.-Ing. Ulrich Meyer