The neighbourhood, N(h), is the number of the pairs of nodes that are within distance h. The neighbourhood function provides useful information for graphs such as the structure of XML documents, OODBs, Web graphs, telephone (caller-callee) records, citations graphs, to name a few. It is very expensive to compute the neighbourhood function exactly on large graphs. Instead, we propose an algorithm using approximation counting. Our approximation runs with any amount of available memory, providing excellent scalability to arbitrarily large graphs. By applying our approximation algorithm on large real and synthetic graphs, we find that our approximation algorithm is significantly faster and more accurate than the best prior approximation scheme. Our approximation runs over 400 times faster than the exact computation (with less than a 10% error).