Fixed queries array: A fast and economical data structure for proximity searching

Pivot-based algorithms are effective tools for proximity searching in metri c spaces. They allow trading space overhead for number of distance evaluati ons performed at query time. With additional search structures (that pose e xtra space overhead) they can also reduce the amount of side computations. We introduce a new data structure, the Fixed Queries Array (FQA), whose nov elties are (1) it permits sublinear extra CPU time without any extra data s tructure; (2) it permits trading number of pivots for their precision so as to make better use of the available memory. We show experimentally that th e FQA is an efficient tool to search in metric spaces and that it compares favorably against other state of the art approaches. Its simplicity convert s it into a simple yet effective tool for practitioners seeking for a black -box method to plug in their applications.