This disclosure describes techniques for searching for similar images to an image query by using an approximate k-Nearest Neighbor (k-NN) graph. The approximate k-NN graph is constructed from data points partitioned into subsets to further identify nearest-neighboring data points for each data point. The data points may connect with the nearest-neighboring data points in a subset to form an approximate neighborhood subgraph. These subgraphs from all the subsets are combined together to form a base approximate k-NN graph. Then by performing more random hierarchical partition, more base approximate k-NN graphs are formed, and further combined together to create an approximate k-NN graph. The approximate k-NN graph expands into other neighborhoods and identifies the best k-NN data points. The approximate k-NN graph retrieves the best NN data points, based at least in part on the retrieved best k-NN data points representing images being similar in appearance to the image query.