Patent ID: 8214527

Claim:
A computer program embodied in non-transitory computer-readable memory allowing a computer to perform a path search on a weighted graph representing a plurality of network peers utilizing upper limits and lower limits of the shortest path lengths d(v,w) each found between any two network peers v and w, the program causing the computer to execute the functions of: selecting network peers as landmarks out of the plurality of network peers in the graph based upon their substantially homogeneous distribution within the graph; calculating values of the shortest path lengths d(Lv,Lw) each found between any two network peers Lv and Lw selected as the landmarks, and recording these values in memory; selecting one or a plurality of landmarks Lv adjacent to the network peer v in association with the shortest path lengths from any network peer v in the graph, calculating values of the shortest path lengths d(v,Lv) from the network peer v to the landmarks Lv, and recording these values in the memory; calculating an upper limit of d(Lv,v)+d(Lv,Lw)+d(w,Lw) for any two network peers v and w in the graph, by reading from the memory values of one or a plurality of landmarks Lv selected in association with the network peer v as well as one or plurality of landmarks Lw selected in association with the network peer w, and providing the upper limit as an upper limit of d(v,w); and calculating a lower limit of d(Lv,Lw)−d(Lv,v)−d(w,Lw) for any two network peers v and w in the graph, by reading from the memory values of one or a plurality of landmarks Lv selected in association with the network peer v as well as one or plurality of landmarks Lw selected in association with the network peer w, and providing the lower limit as a lower limit of d(v,w).