Methods and apparatus are provided for incremental approximate nearest neighbor searching. An approximate nearest neighbor is incrementally retrieved from a data set having a plurality of objects and cells of objects in a hierarchical organization based on a query object. The present invention maintains an object priority queue to organize the objects based on a distance to the query object and a cell priority queue to organize the cells of objects based on a distance to the query object. The next approximate nearest neighbor is incrementally retrieved based on a state of one or more of the object priority queue and the cell priority queue.