Problem: We want to find a location for the new hospital so that the maximum distance 2. Problem Defin between a residential estate and its nearest hospital is minimized a set of points on the road network with distances at vitals Suppose that we want to build a most c,, dist new hospital so that the distance between each residential estate 1, C21 dential estates C. dist to its nearest hospital is as small as possible nearest pital = s C12V2 Nearest location component(NlC) NLC of c NLC of C a set of points on the road network with distances at t c dist 1 V5 C2.dist nearest hospital=S25
2. Problem Definition S = {s1 , s2} C = {c1 , c2} hospitals residential estates v1 v2 v3 v4 v5 v6 c1 c2 s1 Suppose that we want to build a new hospital so that the distance between each residential estate to its nearest hospital is as small as possible. nearest hospital = s1 nearest hospital = s2 5 2 4 s 5 2 6 Nearest location component (NLC) NLC of c1 NLC of c2 c1 .dist c2 .dist A set of points on the road network with distances at most c1 .dist A set of points on the road network with distances at most c2 .dist Problem: We want to find a location for the new hospital so that the maximum distance between a residential estate and its nearest hospital is minimized
Outline 1 Introduction 2. Problem definition 3. Related work 4. Algorithm 5. Empirical Study 6. Conclusion
12 Outline 1. Introduction 2. Problem Definition 3. Related Work 4. Algorithm 5. Empirical Study 6. Conclusion
3. Related work Optimal location Queries with Non-Road Network Setting Optimal Location queries with Road Network Setting Best-known Method Proposed in ICDE 2011 13
3. Related Work ◼ Optimal Location Queries with Non-Road Network Setting ◼ Optimal Location Queries with Road Network Setting ◼ Best-known Method Proposed in ICDE 2011 13
3. Related work Best-known Method Proposed in ICDE 2011 It is very time-consuming For each client/server it creates a vertex in the road network It creates a larger road network It solves the optimal location query with this larger road network However, our Min Max-Alg does not need to generate this larger road network 14
3. Related Work ◼ Best-known Method Proposed in ICDE 2011 ◼ It is very time-consuming ◼ For each client/server, ◼ it creates a vertex in the road network ◼ It creates a larger road network ◼ It solves the optimal location query with this larger road network 14 However, our MinMax-Alg does not need to generate this larger road network
3. Related work Best-known Method Proposed in ICDE 2011 a Time Complexity aO(V|+S|+|(C|)2og(V+|S|+(C|) where vi is the number of vertices s is the number of servers and c is the number of clients The time complexity of our method o(vLog v+vic logIcO where y is a small number at most c (e.g. in SFy=27 but C= 300k) 15
3. Related Work ◼ Best-known Method Proposed in ICDE 2011 ◼ Time Complexity ◼ O((|V|+|S|+|C|)2 log (|V|+|S|+|C|)) where |V| is the number of vertices, |S| is the number of servers and |C| is the number of clients 15 The time complexity of our method = O(|V|log|V|+|V||C|log|C|) where is a small number at most |C| (e.g., in SF, = 27 but |C| = 300k)