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: receiving a set of data points from an external source, the set of data points comprising at least one of a collection of digital images, video sequences, or both; partitioning the data points into subsets to identify nearest-neighboring data points for each data point, wherein the partitioning the data points further comprises recursively dividing the data points into subsets; 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.