In this paper, a novel technique to speed-up a nonlocal means (NLM) filter is proposed. In the original NLM filter, most of its computational time is spent on finding distances for all the patches in the search window. Here, we build a dictionary in which patches with similar photometric structures are clustered together. Dictionary is built only once with high resolution images belonging to different scenes. Since the dictionary is well organized in terms of indexing its entries, it is used to search similar patches very quickly for efficient NLM denoising. We achieve a substantial reduction in computational cost compared with the original NLM method, especially when the search window of NLM is large, without much affecting the PSNR. Second, we show that by building a dictionary for edge patches as opposed to intensity patches, it is possible to reduce the dictionary size; thus, further improving the computational speed and memory requirement. The proposed method preclassifies similar patches with the same distance measure as used by NLM method. The proposed algorithm is shown to outperform other prefiltering based fast NLM algorithms computationally as well as qualitatively.