Applications of Succinct Graph Structures and Distance Oracles
"Explore the world of distance oracles and compact data structures for fast and efficient distance query processing in graphs. Learn about key complexity measures, history of distance oracles, space lower bounds, and 3-approximate distance oracles."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Succinct Graph Structures and Their Applications Spring 2020 Class 3: Distance Oracles
Distance Oracles Compact data structure that can quickly estimate distances in a given graph Input graph Distance query: ?,? Preprocessing ? ?,? ?_?(?,?) DO Goal: Compute fast a succinct DO that answers distance queries fast and small stretch
Distance Oracles Key complexity measures: space, query time and stretch ? ? (2? 1) spanner ? ? Thorup-Zwick Oracles Distance Matrix Space: ?1+1/? Query time: ? ??+?/? Stretch: 2? 1 Space: ?(??1+1/?) Query time: ? ? Stretch: 2? 1 Space: ?2 Query time: ? 1 Stretch: 1 Stretch ? of oracle ?: ?,? ???,? ???,? ? ?? ?,?
History of DO Stretch Query Time Space ? ?1/? ? ?1+1/? Awerbuch, Berger, Cowen and Peleg, 93 64? ? ?1/? ? ?(1) ?(log?) ?(1) ? ?1+1/? ? ??+?/? ? ?1+1/? ? ?1+1/? ? ?1+1/? Cohen, 93 2? + ? ?? ? 128? 2? 1 2? 1 Thorup-Zwick 01 Mendel-Naor 06 Wulff-Nilsen 12 Chechik 15
Space Lower Bound Thm: Every (2? 1) approximate DO for ?-vertex graph requires* (?1+1/?) space. * Under the girth conjecture Girth Conj.: ? with (?1+1/?) edges and girth 2? + 2. Claim: Every subgraphs ?1,?2 ? must have distinct DOs There are 2|? ? |distinct oracles, thus requiring (|? ? |)
Claim: Every subgraphs ?1,?2 ? must have distinct DOs By contradiction: ?1 ?2 ? such that ?1= ?2 ??: 2? 1 oracle for ?? ?,? ?1 ?2: ?1 is a (2? 1) DO for ?1 1 ??1?,? 2? 1 ?2 is a (2? 1) DO for ?2 2? ??2(?,?) ??2?,?
3-Approx. Distance Oracles Space: ? n3/2Query time: ? 1 Preprocessing algorithm: ? ??????(?,?) , ? = 1/ ? For each vertex ?: ? ? closest vertex to ? is ? ? ?0? = {? ? ? ???,? < ??(?,? ? )} Store in hash-table distances between ? and every vertex in ?0? ?
3-Approx. Distance Oracles Space: ? n3/2 Query time: ? 1 Query algorithm ?,? If ? ? ? ?: output ??(?,?) Else: ? ?,? = ???,? ? ? + ?(? ? ,?) ?(?) ?(?) 2 ? ? ?
Space: = ? ?1/2log ? w.h.p Preprocessing algorithm: ? ??????(?,?) , ? = ?log ?/ ? For each vertex ?: Claim: ?0? ? ? ??1/2log ? closest vertices to ? ? ? closest vertex to ? is ? ?0? = {? ? ? ???,? < ??(?,?(?)} ? ? ? w.h.p. ? ? ?(?) QED Store in hash-table distances between ? and every vertex in ?0? ? ?
(2? 1) Approximate Oracle Space: ? n1+1/? Query time: ? ? Preprocessing algorithm: ? = ?0 ?1 ?? 1 where ?? ?????? ?? 1 ,? 1/? Pivot ??? closest vertex to ? in ??, ? ?,? {0, ,? 1} Bunch ??? { ? ?? ??+1 ? ?,? < ?(?,??+1? )} ,? {0, ,? 2} ?? 1? = ?? 1 Store in hash-table distances between ? and every vertex in ? ? = ???(?)
Bunches A0= A1= A2= p2(v) v p1(v) ??? { ? ?? ??+1 ? ?,? < ?(?,??+1? )} *Slide taken from Uri Zwick presentation 11
Space Argument: = ?(?1/?log?) w.h.p. Claim: ??? Recall: ??? { ? ?? ??+1 ???,? < ??+1? } and ??+1 ?????? ?? ,? 1/? ??? ?1/?log?closest neighbors of ? in ?? ??+1 ??? w.h.p ??? ??(?) ? ?? ??+1 Total space: ?(??1+1/?)
Intuition for Query Alg ??? { ? ?? ??+1 ???,? < ??+1? } , ? ? = ???(?) Obs. 1: ??? ? ? for every ? {0,1, ,? 1} Obs. 2: ?? ?? ?(?)for every ?,? Goal: Find min ? such that either ??? ?(?) or ??? ?(?) ?2? ?1? ? ?
(2? 1) Approximate Oracle Query Algorithm ?,? ?2? ? ?0? For ? = 1 to ? do: If ? ?(?): // ? = ?? 1v ?1? return ? ?,? = ???,? + ??(?,?) ? ? Else: ? ??? swap ?,? Since ?? 1? ? ? , alg. always outputs a value
Stretch Argument Query Algorithm ?,? ? ?0? For ? = 1 to ? do: Iteration ?:??,??,??= ?? 1(??) If ? ?(?): // ? = ?? 1v return ? ?,? = ???,? + ??(?,?) Else: ? ??? swap ?,? Claim: ????,?? ? 1 ????,?? for every ? ? (when alg. terminates) By induction: ??= ?? 1(??) ?? 1= ?? 2(?? 1) Base: ? = 1,?1= ?0(?) Assume up to ? 1 and consider iteration ?. ??= ?? 1 ??= ?? 1
Stretch Argument Query Algorithm ?,? ? ?0? For ? = 1 to ? do: Iteration ?:??,??,??= ?? 1(??) If ? ?(?): // ? = ?? 1v return ? ?,? = ???,? + ??(?,?) Else: ? ??? swap ?,? Claim: ????,?? ? 1 ????,?? for every ? ? (when alg. terminates) ?? ???? ,?? ? 1 ???? ,?? ???? ,?? ? ???? ,?? ? ?,? = ???? ,?? +???? ,?? 2? 1 ??(?,?) ?? ??
