How to use Hierarchical clustering with similarity matrix using the 20 nearest neighbors

Hi, I have an infrared image with size N = 770*990 = 762300 pixels, when I want to clustering it by applying Hierarchical clustering it get out of memory because i must construct the similarity matrix with size N x N.

I have learned somewhere that we can take only k-nearest neighbors from each pixel (function 'knnsearch' in matlab) in the image and then apply the Hierarchical clustering algorithm to the similarity matrix with size [N x k]. My question is how to process with Hierarchical clustering if we have only the similarity matrix with the distance between pixel and k-neighbors instead of the whole distance between pixels.

 Thanks in advance