Hybrid Block Balanced Searches for Nearest Neighbors

Best match search or nearest neighbor search is a technique necessary to extend the traditional exact searches to meet the needs of specific applications. Block balanced search with space partitioning was introduced by Peter Elias, allowing the best match search algorithm to be compiled in a reduced space, in a dynamic programming manner. Ronald Rivest studied optimality issues of best match search in hypercube with respect to the isoperimetric properties of partition blocks. Error correction coding theory describes all isoperimetric spherical partitions of a hypercube (Hamming and Golay codes), but best match search needs more structures for its flexibility. This partitioning problem may be interpreted in terms of integer linear programming when implementing the spectral and isoperimetric partition approaches of graphs. The Lagrangian decomposition obtains partial problems, which are individual discrete isoperimetry problems in their nature, with known solutions. Spectral and isoperimetric partitions give approximations to the solutions. This paper introduces hybrid block constructions to the problem, that are also approximate but may be obtained easily, combinatorially. Approximate partitioning of the search space results in partitioning of search set itself, which allows us to apply the hashing and dynamic programming techniques in an extended way. The work is aimed at successive stages of research where experimental confirmation of the constructions will also be given.