Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Sensitive Distance and Reachability Oracles for Large Batch Updates
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
Toyota Technol Inst, Chicago, IL USA..
2019 (English)In: 2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019), IEEE COMPUTER SOC , 2019, p. 424-435Conference paper, Published paper (Refereed)
Abstract [en]

In the sensitive distance oracle problem, there are three phases. We first preprocess a given directed graph G with n nodes and integer weights from [-W, W]. Second, given a single batch of f edge insertions and deletions, we update the data structure. Third, given a query pair of nodes (u, v), return the distance from u to v. In the easier problem called sensitive reachability oracle problem, we only ask if there exists a directed path from u to v. Our first result is a sensitive distance oracle with (O) over tilde (W n(omega+(3-omega)mu)) preprocessing time, (O) over tilde (Wn(2-mu) f(2) + Wnf(omega)) update time, and (O) over tilde (Wn(2-mu) f + Wnf(2)) query time where the parameter mu is an element of [0, 1] can be chosen. The data-structure requires O(Wn(2+mu) log n) bits of memory. This is the first algorithm that can handle f >= log n updates. Previous results (e.g. [Demetrescu et al. SICOMP'08; Bernstein and Karger SODA'08 and FOCS'09; Duan and Pettie SODA'09; Grandoni and Williams FOCS'121) can handle at most 2 updates. When 3 <= f <= log n, the only non-trivial algorithm was by [Weimann and Yuster FOCS'10]. When W = (O) over tilde (1), our algorithm simultaneously improves their preprocessing time, update time, and query time. In particular, when f = omega(1), their update and query time is Omega(n(2-o(1))), while our update and query time are truly subquadratic in n, i.e., ours is faster by a polynomial factor of n. To highlight the technique, ours is the first graph algorithm that exploits the kernel basis decomposition of polynomial matrices by [Jeannerod and Villard J.Comp'05; Zhou, Labahn and Storjohann J.Comp'151 developed in the symbolic computation community. As an easy observation from our technique, we obtain the first sensitive reachability oracle can handle f >= log n updates. Our algorithm has O(n(omega)) preprocessing time, O(f(omega)) update time, and O(f(2)) query time. This data-structure requires O(n(2) log n) bits of memory. Efficient sensitive reachability oracles were asked in [Chechik, Cohen, Fiat, and Kaplan SODA'17]. Our algorithm can handle any constant number of updates in constant time. Previous algorithms with constant update and query time can handle only at most f <= 2 updates. Otherwise, there are non-trivial results for f <= log n, though, with query time Omega(n) by adapting [Baswana, Choudhary and Roditty STOC'16].

Place, publisher, year, edition, pages
IEEE COMPUTER SOC , 2019. p. 424-435
Series
Annual IEEE Symposium on Foundations of Computer Science, ISSN 0272-5428
Keywords [en]
sensitive oracle, emergency oracle, failure, batch, reachability, distance
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-269513DOI: 10.1109/FOCS.2019.00034ISI: 000510015300025Scopus ID: 2-s2.0-85078436479ISBN: 978-1-7281-4952-3 (print)OAI: oai:DiVA.org:kth-269513DiVA, id: diva2:1412841
Conference
60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), NOV 09-12, 2019, Baltimore, MD
Note

QC 20200309

Available from: 2020-03-09 Created: 2020-03-09 Last updated: 2020-03-09Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

van den Brand, Jan

Search in DiVA

By author/editor
van den Brand, Jan
By organisation
Theoretical Computer Science, TCS
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf