Efficient kNN search, or k-nearest neighbors search, is useful, among other fields, in multimedia information retrieval, data mining and pattern recognition problems. A distance function determines how similar the objects ...