Shortest paths in less than a millisecond
2012
We consider the problem of answering point-to-point shortest path queries on massive social networks. The goal is to answer queries within tens of milliseconds while minimizing the memory requirements. We present a technique that achieves this goal for an extremely large fraction of path queries by exploiting the structure of the social networks. Using evaluations on real-world datasets, we argue that our technique offers a unique trade-off between latency, memory and accuracy. For instance, for the LiveJournal social network (roughly 5 million nodes and 69 million edges), our technique can answer 99.9 of the queries in less than a millisecond. In comparison to storing all pair shortest paths, our technique requires at least 550x less memory; the average query time is roughly 365 microseconds --- 430x faster than the state-of-the-art shortest path algorithm. Furthermore, the relative performance of our technique improves with the size (and density) of the network. For the Orkut social network (3 million nodes and 220 million edges), for instance, our technique is roughly 2588x faster than the state-of-the-art algorithm for computing shortest paths.
Keywords:
- Machine learning
- Artificial intelligence
- Yen's algorithm
- Canadian traveller problem
- Euclidean shortest path
- Computer science
- K shortest path routing
- Shortest Path Faster Algorithm
- Average path length
- Shortest job next
- Distributed computing
- Constrained Shortest Path First
- Shortest path problem
- Algorithm
- Theoretical computer science
- Mathematics
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
16
References
9
Citations
NaN
KQI