Patent ID: 8582554
Filing Date: 2013-11-12
Classification: H04L

Abstract:
1. A method for determining a shortest path in a disk-based network, wherein the method comprises: creating a compressed representation of an underlying disk resident network graph, wherein creating the compressed representation of the underlying disk resident network graph comprises determining one or more dense regions in the disk resident graph and compacting the one or more dense regions into one or more compressed nodes; associating one or more node penalties with the one or more compressed nodes, wherein the one or more node penalties reflect a distance of a sub-path within a compressed node; and performing a query on the underlying disk resident network graph using the compressed representation and one or more node penalties to determine a shortest path in the disk-based network to reduce the number of accesses to a physical disk, wherein determining the shortest path comprises performing a disk-based nearest neighbor search and performing a selective expansion to determine one or more nearest neighbor distances, wherein said selective expansion uses one or more node penalties and a list of nodes with sorted probabilistic distances.