As provided herein, a pairwise distance between nodes in a large graph can be determined efficiently. URL-sketches are generated for respective nodes in an index by extracting labels from respective nodes, which provide a reference to a link between the nodes, aggregating the labels into sets for respective nodes, and storing the sets of labels as URL-sketches. Neighborhood-sketches are generated for the respective nodes in the index using the URL-sketches, by determining a neighborhood for a node and generating a sketch using labels that are associated with the respective neighboring nodes. A distance between two nodes is determined by computing an approximate number of paths and an approximate path length between the two nodes, using the neighborhood sketches for the two nodes.