KIT | KIT-Bibliothek | Impressum | Datenschutz

Communication Efficient Algorithms for Top-k Selection Problems

Hübschle-Schneider, Lorenz; Sanders, Peter

Abstract (englisch):
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.

Open Access Logo


Postprint §
DOI: 10.5445/IR/1000068027
Veröffentlicht am 01.08.2018
Originalveröffentlichung
DOI: 10.1109/IPDPS.2016.45
Scopus
Zitationen: 2
Coverbild
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Jahr 2016
Sprache Englisch
Identifikator ISBN: 978-1-5090-2140-6
urn:nbn:de:swb:90-680275
KITopen-ID: 1000068027
Erschienen in 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), Chicago, IL, USA, 23–27 May 2016
Verlag IEEE, Piscataway (NJ)
Seiten 659–668
Schlagworte frequent elements, sampling, selection, sum aggregation, priority queue
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page