Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions

Matthew J Liu, Wei Hang Zheng, Vidhan Purohit +4

Grid-based approaches to approximate nearest neighbor (ANN) search have been absent from modern scaling analyses. We present a systematic characterization of a multiprobe grid algo…