Amazon.com, Inc.
Optimal-path finding algorithm for data on storage media

Abstract:

A computing system may generate a directed graph to access data stored in multiple locations or blocks of a data storage device or system. Cost values may be determined for each of multiple paths between nodes, representing the blocks or subsets of data. In some cases, nodes having a cost value between them that is less than a threshold may be combined into a single node. A master path, linking at least two of the multiple paths, between a start node and an end node, may be generated by iteratively selecting paths with a lowest cost. The number of paths considered for determining the lowest path cost may be limited by a complexity parameter, so as to optimize the path to access the data without introducing unbeneficial computational complexity.