Access Time Oracle for Planar Graphs

doi:10.1109/TKDE.2016.2547382

2016-08-01

PRE

DOI：10.1109/TKDE.2016.2547382

原文链接

原文求助

摘要

En 中文

The study of urban networks reveals that the accessibility of important city objects for the vehicle traffic and pedestrians is significantly correlated to the popularity, micro-criminality, micro-economic vitality, and social liveability of the city, and is always the chief factor in regulating the growth and expansion of the city. The accessibility between different components of an urban structure are frequently measured along the streets and routes considered as edges of a planar graph, while the traffic ultimate destination points and street junctions are treated as vertices. For estimation of the accessibility of destination vertex j from vertex i through urban networks, in particular, the random walks are used to calculate the expected distance a random walker starting from i makes before j is visited (known as access time). The state-of-the-art of access time computation is costly in large planar graphs since it involves matrix operation over entire graph. The time complexity is O(n(2.376)) where n is the number of vertices in the planar graph. To enable efficient access time query answering in large planar graphs, this work proposes the first access time oracle which is based on the proposed access time decomposition and reconstruction scheme. The oracle is a hierarchical data structure with deliberate design on the relationships between different hierarchical levels. The storage requirement of the proposed oracle is O(n(4/3)log log n) and the access time query response time is O(n(2/3)). The extensive tests on a number of large real-world road networks (with up to about 2 million vertices) have verified the superiority of the proposed oracle.

Keyword:

Access time

planar graph

random walk

oracle