Staff:Prof. Dr. Ulrich Meyer, Johann Wolfgang Goethe-Universität Frankfurt am Main |
|
Description:
Big data is often characterized by the so called 3Vs: Volume (the amount of data), Variety (different types of data), and Velocity (the speed of input/output-data). In this proposal we are particularly interested in algorithmic challenges stemming from the combination of volume and velocity in the context of resource constraints: with a focus on huge graph problems that frequently arise in various application areas we aim to consider the possibilities and limitations of dynamically processing data after input updates, i.e., building on previous solutions instead of recomputing everything from scratch. Despite parallel computation power and efficient usage of memory hierarchies, given the sheer size of the data sets to be considered, we will often be forced to give up exact computations and rather consider effective ways to trade solution quality versus computational efforts, for example using embeddings to approximate shortest paths. Actually, not only high-frequency input data rates but also the computational platform itself may contribute to an online scenario.
Resources like main memory or cache are often shared between several non-cooperating processes, thus resulting in fluctuating individual cache sizes which often cause tremendous paging delays for the processes involved. We aim to investigate both cache-robust algorithms and methods of fair cache distribution, partially based on algorithmic game theory. In all aspects to be considered we do not only strive for theoretical results but intend to follow the whole algorithm engineering development cycle including modern performance metrics like energy-consumption. The work area ranges from refining models for the utilized hardware components (e.g., concerning memory bank conflicts in GPUs or read/write asymmetriesin modern storage devices) to engineering improved algorithms and data structures and integrating them in libraries like STXXL so that other participants of the priority programme (and beyond) can use them.