An apparatus configured to construct one or more tree sub-graphs data structures for estimating a shortest distance between a given pair of nodes of a graph having multiple interconnected nodes, the method comprising: a processor; a memory communicatively connected to the processor, the memory configured to store the one or more tree sub-graph data structures and one or more executable instructions, which, upon execution by the processor, configure the processor to: select one or more root nodes from the multiple interconnected nodes of the graph; construct, for each of at least one of the one or more root nodes, a respective multi-level tree sub-graph data structure representing the multiple interconnected nodes of the graph characterized in that the multiple interconnected nodes of the graph are represented in a parent-child relationship in successive levels of the multi-level tree sub-graph data structure starting with each of the at least one of the one or more root nodes, wherein said nodes have respective degrees; wherein at least one level of the multi-level tree sub-graph data structure includes a plurality of parent nodes, the degree of at least one parent node in the plurality of parent nodes being higher than the degree of another parent node in the plurality of parent nodes, and, wherein the processor is further configured to construct the multi-level tree sub-graph data structure by expanding respective ones of the plurality of parent nodes of the at least one level of the tree sub-graph data structure into one or more respective child nodes in a successive level of the tree sub-graph data structure based on a descending order of the degrees of the plurality of parent nodes. a processor; a memory communicatively connected to the processor, the memory configured to store the one or more tree sub-graph data structures and one or more executable instructions, which, upon execution by the processor, configure the processor to: select one or more root nodes from the multiple interconnected nodes of the graph; construct, for each of at least one of the one or more root nodes, a respective multi-level tree sub-graph data structure representing the multiple interconnected nodes of the graph characterized in that the multiple interconnected nodes of the graph are represented in a parent-child relationship in successive levels of the multi-level tree sub-graph data structure starting with each of the at least one of the one or more root nodes, select one or more root nodes from the multiple interconnected nodes of the graph; construct, for each of at least one of the one or more root nodes, a respective multi-level tree sub-graph data structure representing the multiple interconnected nodes of the graph characterized in that the multiple interconnected nodes of the graph are represented in a parent-child relationship in successive levels of the multi-level tree sub-graph data structure starting with each of the at least one of the one or more root nodes, wherein said nodes have respective degrees; wherein at least one level of the multi-level tree sub-graph data structure includes a plurality of parent nodes, the degree of at least one parent node in the plurality of parent nodes being higher than the degree of another parent node in the plurality of parent nodes, and, wherein the processor is further configured to construct the multi-level tree sub-graph data structure by expanding respective ones of the plurality of parent nodes of the at least one level of the tree sub-graph data structure into one or more respective child nodes in a successive level of the tree sub-graph data structure based on a descending order of the degrees of the plurality of parent nodes.