Proximity searching is the problem of retrieving,from agiven data base,those objects closest to aquery.To avoid exhaustive searching, data structures called indexes are builton the data base prior to serving queries.The curse of dimensionality is awell-known problem for indexes: in spaces with sufficiently concentrated distance histograms,no index out performs anexhaustive scan of the data base.