Show simple item record

dc.contributor.author
Biswas, Amartya S.
dc.contributor.author
Dory, Michal
dc.contributor.author
Ghaffari, Mohsen
dc.contributor.author
Mitrović, Slobodan
dc.contributor.author
Nazari, Yasamin
dc.date.accessioned
2021-08-02T11:11:06Z
dc.date.available
2021-07-18T02:37:25Z
dc.date.available
2021-08-02T11:11:06Z
dc.date.issued
2021-07
dc.identifier.isbn
978-1-4503-8070-6
en_US
dc.identifier.other
10.1145/3409964.3461784
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/495630
dc.description.abstract
Over the past decade, there has been increasing interest in distributed/parallel algorithms for processing large-scale graphs. By now, we have quite fast algorithms - -usually sublogarithmic-time and often poly(łogłog n)-time, or even faster - -for a number of fundamental graph problems in the massively parallel computation (MPC) model. This model is a widely-adopted theoretical abstraction of MapReduce style settings, where a number of machines communicate in an all-to-all manner to process large-scale data. Contributing to this line of work on MPC graph algorithms, we present poly(łog k) ϵ poly(łogłog n) round MPC algorithms for computing O(k^1+o(1) )-spanners in the strongly sublinear regime of local memory. To the best of our knowledge, these are the first sublogarithmic-time MPC algorithms for spanner construction. As primary applications of our spanners, we get two important implications, as follows: -For the MPC setting, we get an O(łog^2łog n)-round algorithm for O(łog^1+o(1) n) approximation of all pairs shortest paths (APSP) in the near-linear regime of local memory. To the best of our knowledge, this is the first sublogarithmic-time MPC algorithm for distance approximations. -Our result above also extends to the Congested Clique model of distributed computing, with the same round complexity and approximation guarantee. This gives the first sub-logarithmic algorithm for approximating APSP in weighted graphs in the Congested Clique model.
en_US
dc.language.iso
en
en_US
dc.publisher
Association for Computing Machinery
en_US
dc.subject
Spanners
en_US
dc.subject
Shortest paths
en_US
dc.subject
Massively parallel computation
en_US
dc.title
Massively parallel algorithms for distance approximation and spanners
en_US
dc.type
Conference Paper
dc.date.published
2021-07-06
ethz.book.title
Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '21)
en_US
ethz.pages.start
118
en_US
ethz.pages.end
128
en_US
ethz.event
33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2001)
en_US
ethz.event.location
Online
en_US
ethz.event.date
July 6-8, 2021
en_US
ethz.grant
Distributed Algorithms for Global Graph Problems
en_US
ethz.grant
Distributed and Massively Parallel Graph Algorithms
en_US
ethz.identifier.scopus
ethz.publication.place
New York, NY
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03457 - Welzl, Emo / Welzl, Emo::09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03457 - Welzl, Emo / Welzl, Emo::09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)
ethz.grant.agreementno
184735
ethz.grant.agreementno
853109
ethz.grant.fundername
SNF
ethz.grant.fundername
EC
ethz.grant.funderDoi
10.13039/501100001711
ethz.grant.funderDoi
10.13039/501100000780
ethz.grant.program
H2020
ethz.grant.program
Projekte MINT
ethz.date.deposited
2021-07-18T02:37:28Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2021-08-02T11:11:12Z
ethz.rosetta.lastUpdated
2022-03-29T10:52:11Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Massively%20parallel%20algorithms%20for%20distance%20approximation%20and%20spanners&rft.date=2021-07&rft.spage=118&rft.epage=128&rft.au=Biswas,%20Amartya%20S.&Dory,%20Michal&Ghaffari,%20Mohsen&Mitrovi%C4%87,%20Slobodan&Nazari,%20Yasamin&rft.isbn=978-1-4503-8070-6&rft.genre=proceeding&rft_id=info:doi/10.1145/3409964.3461784&rft.btitle=Proceedings%20of%20the%2033rd%20ACM%20Symposium%20on%20Parallelism%20in%20Algorithms%20and%20Architectures%20(SPAA%20'21)
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record