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
DOI: 10.1109/IPDPS.2016.45
Zitationen: 5
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2016
Sprache Englisch
Identifikator ISBN: 978-1-5090-2140-6
KITopen-ID: 1000068027
Erschienen in 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), Chicago, IL, USA, 23–27 May 2016
Verlag Institute of Electrical and Electronics Engineers (IEEE)
Seiten 659–668
Schlagwörter frequent elements, sampling, selection, sum aggregation, priority queue
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page