Approximate Shortest Distance/Path

Jieming Zhu (Jamie)
The Chinese University of Hong Kong


Point-to-point distance query in graphs is a fundamental primitive in many applications. Although querying shortest paths or shortest distances between pairwise vertices has been well studied in last decades, traditional algorithms cannot be applied to today’s real-world massive social networks since The massive size of the modern social networks and the online nature of distance queries make it infeasible to apply the classical algorithms online. It is also space inefficient to precompute all the shortest distances and store them explicitly on disk, as the space requirement is quadratic in the number of nodes in the graph.



Note: This is an archive of reference papers in approximate shortest distance/path. The copyrights are retained by the corresponding authors and publishers. For authors of these listed papers, if you don't like your paper to be involved in this archive, please feel free to contact me.

© 2013 Jamie Zhu
Last updated: Mar. 7, 2013