On the optimality of the hash-coding type nearest neighbour search algorithm

The algorithmic problem of nearest neighbour search and the earlier proposed hash-coding algorithm (Elias algorithm) are considered. The problem of optimality characterization depending on the geometrical structure of blocks of the algorithm in a balanced hash-coding scheme is considered. As a supportive technique for this the structure of consecutive neighbourhood layers to the subsets of binary cube is considered. Using the known properties of isoperimetric sets it is proved that the algorithm is optimal when mentioned blocks are isoperimetric sets.