PSPeter Sanders

Peter Sanders

*This is an algorithmically generated author record based on publicly available information.

Peter Sanders has a total of 10 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    n-Level Graph Partitioning

    by Vitaly Osipov, Peter Sanders

    We present a multi-level graph partitioning algorithm based on the extreme idea to contract only a single edge on each level of the hierarchy. This obviates the need for a matching algorithm and promises very good partitioning quality since there are very few changes between two levels. Using an efficient data structure and new flexible ways to break local search improvements early, we obtain an algorithm that scales to large inputs and produces the best known partitioning results for many inputs. For example, in Walshaw's well known benchmark tables we achieve 155 improvements dominating the entries for large graphs.

  • Open Access

    GPU sample sort

    by Nikolaj Leischner, Vitaly Osipov, Peter Sanders

    In this paper, we present the design of a sample sort algorithm for manycore GPUs. Despite being one of the most efficient comparison-based sorting algorithms for distributed memory architectures its performance on GPUs was previously unknown. For uniformly distributed keys our sample sort is at least 25% and on average 68% faster than the best comparison-based sorting algorithm, GPU Thrust merge sort, and on average more than 2 times faster than GPU quicksort. Moreover, for 64-bit integer keys it is at least 63% and on average 2 times faster than the highly optimized GPU Thrust radix sort that directly manipulates the binary representation of keys. Our implementation is robust to different distributions and entropy levels of keys and scales almost linearly with the input size. These results indicate that multi-way techniques in general and sample sort in particular achieve substantially better performance than two-way merge sort and quicksort.

  • Open Access

    Fast Detour Computation for Ride Sharing

    by Robert Geisberger, Dennis Luxen, Sabine Neubauer, Peter Sanders, Lars Volker

    Todays ride sharing services still mimic a better billboard. They list the offers and allow to search for the source and target city, sometimes enriched with radial search. So finding a connection between big cities is quite easy. These places are on a list of designated origin and distination points. But when you want to go from a small town to another small town, even when they are next to a freeway, you run into problems. You can't find offers that would or could pass by the town easily with little or no detour. We solve this interesting problem by presenting a fast algorithm that computes the offers with the smallest detours w.r.t. a request. Our experiments show that the problem is efficiently solvable in times suitable for a web service implementation. For realistic database size we achieve lookup times of about 5ms and a matching rate of 90% instead of just 70% for the simple matching algorithms used today.

  • Open Access

    Towards Optimal Range Medians

    by Beat Gfeller, Peter Sanders

    We consider the following problem: given an unsorted array of $n$ elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which uses O(n) space and needs $O(n\log k + k\log n)$ time to answer the first $k$ queries. This improves previous algorithms by a logarithmic factor and matches a lower bound for $k=O(n)$. Since the algorithm decomposes the range of element values rather than the array, it has natural generalizations to higher dimensional problems -- it reduces a range median query to a logarithmic number of range counting queries.

  • Space Efficient Hash Tables with Worst Case Constant Access Time

    by Dimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul Spirakis