Similarity Searching in Large Disk-Based Networks

A computer program product comprising a tangible computer readable recordable storage medium including computer useable program code for determining a shortest path in a disk-based network, the computer program product including:

• computer useable program code for creating a compressed representation of an underlying network graph, wherein creating a compressed representation of an underlying disk resident network graph, wherein creating a compressed representation of an 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;
• computer useable program code for 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
• computer useable program code for 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.

A system for determining a shortest path in a disk-based network, comprising:

• a memory;
• and
• at least one processor coupled to the memory and operative to:
• create a compressed representation of an underlying disk resident network graph, wherein creating a compressed representation of an 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;
• associate 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
• perform 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.