research
∙
08/18/2023
ShockHash: Towards Optimal-Space Minimal Perfect Hashing Beyond Brute-Force
A minimal perfect hash function (MPHF) maps a set S of n keys to the fir...
share
research
∙
05/15/2023
A Sweep-plane Algorithm for Calculating the Isolation of Mountains
One established metric to classify the significance of a mountain peak i...
research
∙
05/09/2023
Fast Many-to-Many Routing for Ridesharing with Multiple Pickup and Dropoff Locations
We introduce KaRRi, an improved algorithm for scheduling a fleet of shar...
research
∙
04/21/2023
Learned Monotone Minimal Perfect Hashing
A Monotone Minimal Perfect Hash Function (MMPHF) constructed on a set S ...
research
∙
04/18/2023
Sliding Block Hashing (Slick) – Basic Algorithmic Ideas
We present Sliding Block Hashing (Slick), a simple hash table data struc...
research
∙
03/30/2023
Scalable High-Quality Hypergraph Partitioning
Balanced hypergraph partitioning is an NP-hard problem with many applica...
research
∙
03/14/2023
Efficient Yao Graph Construction
Yao graphs are geometric spanners that connect each point of a given poi...
research
∙
03/02/2023
Distributed Deep Multilevel Graph Partitioning
We describe the engineering of the distributed-memory multilevel graph p...
research
∙
02/23/2023
Engineering Massively Parallel MST Algorithms
We develop and extensively evaluate highly scalable distributed-memory a...
research
∙
02/22/2023
Engineering a Distributed-Memory Triangle Counting Algorithm
Counting triangles in a graph and incident to each vertex is a fundament...
research
∙
12/19/2022
High Performance Construction of RecSplit Based Minimal Perfect Hash Functions
A minimal perfect hash function (MPHF) is a bijection from a set of obje...
research
∙
10/04/2022
SicHash – Small Irregular Cuckoo Tables for Perfect Hashing
A Perfect Hash Function (PHF) is a hash function that has no collisions ...
research
∙
05/26/2022
More Recent Advances in (Hyper)Graph Partitioning
In recent years, significant advances have been made in the design and e...
research
∙
05/13/2022
Scalable SAT Solving in the Cloud
Previous efforts on making Satisfiability (SAT) solving fit for high per...
research
∙
05/12/2022
Vectorized and performance-portable Quicksort
Recent works showed that implementations of Quicksort using vector CPU i...
research
∙
05/10/2022
PaCHash: Packed and Compressed Hash Tables
We introduce PaCHash, a hash table that stores its objects contiguously ...
research
∙
03/02/2022
ReStore: In-Memory REplicated STORagE for Rapid Recovery in Fault-Tolerant Algorithms
Fault-tolerant distributed applications require mechanisms to recover da...
research
∙
01/05/2022
Parallel Flow-Based Hypergraph Partitioning
We present a shared-memory parallelization of flow-based refinement, whi...
research
∙
09/04/2021
Fast Succinct Retrieval and Approximate Membership using Ribbon
A retrieval data structure for a static function f:S→{0,1}^r supports qu...
research
∙
07/03/2021
Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues
Priority queues with parallel access are an attractive data structure fo...
research
∙
06/23/2021
Weighted Random Sampling on GPUs
An alias table is a data structure that allows for efficiently drawing w...
research
∙
06/16/2021
High-Quality Hypergraph Partitioning
This paper considers the balanced hypergraph partitioning problem, which...
research
∙
05/05/2021
Deep Multilevel Graph Partitioning
Partitioning a graph into blocks of "roughly equal" weight while cutting...
research
∙
04/16/2021
Shared-Memory n-level Hypergraph Partitioning
We present a shared-memory algorithm to compute high-quality solutions t...
research
∙
11/05/2020
Fast, Exact and Scalable Dynamic Ridesharing
We study the problem of servicing a set of ride requests by dispatching ...
research
∙
10/20/2020
Scalable Shared-Memory Hypergraph Partitioning
Hypergraph partitioning is an important preprocessing step for optimizin...
research
∙
09/28/2020
Engineering In-place (Shared-memory) Sorting Algorithms
We present sorting algorithms that represent the fastest known technique...
research
∙
03/02/2020
Recent Advances in Scalable Network Generation
Random graph models are frequently used as a controllable and versatile ...
research
∙
02/18/2020
Connecting MapReduce Computations to Realistic Machine Models
We explain how the popular, highly abstract MapReduce model of parallel ...
research
∙
01/23/2020
Communication-Efficient String Sorting
There has been surprisingly little work on algorithms for sorting string...
research
∙
11/19/2019
Concurrent Expandable AMQs on the Basis of Quotient Filters
A quotient filter is a cache efficient AMQ data structure. Depending on ...
research
∙
10/24/2019
Communication-Efficient (Weighted) Reservoir Sampling
We consider communication-efficient weighted and unweighted (uniform) ra...
research
∙
07/08/2019
More Hierarchy in Route Planning Using Edge Hierarchies
A highly successful approach to route planning in networks (particularly...
research
∙
05/09/2019
Linear Work Generation of R-MAT Graphs
R-MAT is a simple, widely used recursive model for generating `complex n...
research
∙
03/01/2019
Parallel Weighted Random Sampling
Data structures for efficient sampling from a set of weighted items are ...
research
∙
02/20/2019
Load-Balancing for Parallel Delaunay Triangulations
Computing the Delaunay triangulation (DT) of a given point set in R^D is...
research
∙
08/14/2018
Hashing with Linear Probing and Referential Integrity
We describe a variant of linear probing hash tables that never moves ele...
research
∙
03/27/2018
Proving Equivalence Between Imperative and MapReduce Implementations Using Program Transformations
Distributed programs are often formulated in popular functional framewor...
research
∙
02/10/2018
Network Flow-Based Refinement for Multilevel Hypergraph Partitioning
We present a refinement framework for multilevel hypergraph partitioning...
research
∙
01/26/2018
Relational Equivalence Proofs Between Imperative and MapReduce Algorithms
MapReduce frameworks are widely used for the implementation of distribut...
research
∙
10/23/2017
Communication Efficient Checking of Big Data Operations
We propose fast probabilistic algorithms with low (i.e., sublinear in th...
research
∙
10/22/2017
Lightweight MPI Communicators with Applications to Perfectly Balanced Schizophrenic Quicksort
MPI uses the concept of communicators to connect groups of processes. It...
research
∙
10/20/2017
Communication-free Massively Distributed Graph Generation
Analyzing massive complex networks yields promising insights about our e...
research
∙
09/15/2017
Fast OLAP Query Execution in Main Memory on Large Data in a Cluster
Main memory column-stores have proven to be efficient for processing ana...
research
∙
02/06/2017
Distributed Evolutionary k-way Node Separators
Computing high quality node separators in large graphs is necessary for ...
research
∙
10/17/2016
Efficient Random Sampling - Parallel, Vectorized, Cache-Efficient, and Online
We consider the problem of sampling n numbers from the range {1,...,N} w...
research
∙
04/17/2016
Generating Semi-Synthetic Validation Benchmarks for Embryomics
Systematic validation is an essential part of algorithm development. The...
research
∙
09/02/2015
Finding Near-Optimal Independent Sets at Scale
The independent set problem is NP-hard and particularly difficult to sol...
research
∙
04/29/2015
Incorporating Road Networks into Territory Design
Given a set of basic areas, the territory design problem asks to create ...
research
∙
02/05/2015