Home | english  | Impressum | Sitemap | KIT

Communication Efficient Algorithms for Top-k Selection Problems

Communication Efficient Algorithms for Top-k Selection Problems
Tagung:

IPDPS'16

Links:Links_bearbeiten
Tagungsort:

Chicago

Datum:

23.-27.05.2016

Autoren:

Lorenz Hübschle-Schneider und Peter Sanders

Abstract

  We present scalable parallel algorithms with sublinear per-processor communication volume and low latency for several fundamental problems related to finding the most relevant elements in a set, for various notions of relevance: We begin with the classical selection problem with unsorted input. We present generalizations with sorted inputs, dynamic content (bulk-parallel priority queues), and multiple criteria. Then we move on to finding frequent objects and top-k sum aggregation.