DISTANCE QUERIES ON MASSIVE NETWORKS

摘要

Distance query techniques are provided that are robust to network structure, scale to large and massive networks, and are fast, straightforward, and efficient. A hierarchical hub labeling (HHL) technique is described to determine a distance between two nodes or vertices on a network. The HHL technique provides indexing by ordering vertices by importance, then transforming the ordering into an index, which enables fast exact shortest-path distance queries. The index may be compressed without sacrificing its correctness.

主权项

1. A method of determining a distance between two vertices, comprising:
receiving as input, at a computing device, a graph comprising a plurality of vertices; generating a plurality of labels for each vertex of the graph wherein for each vertex, each label comprises both a set of vertices referred to as hubs and the distances between the hubs in the label and the vertex; performing hierarchical hub labeling on the labels; and storing data corresponding to the vertices and labels as preprocessed graph data in storage associated with the computing device.