1. A method implemented at least partially by a processor, the method comprising: identifying an image query; constructing an approximate k-Nearest Neighbor (k-NN) graph to retrieve images similar in appearance to the image query by: partitioning data points into subsets to identify nearest-neighboring data points for each data point; connecting each data point with the nearest-neighboring data points in a subset in which the data points represent nodes to form a subgraph; forming multiple subgraphs, which are to be combined to form a base approximate k-NN graph; creating additional base approximate k-NN graphs, which are merged to create the approximate k-NN graph; retrieving images similar in appearance to the image query by identifying best NN data points from the approximate k-NN graph.