Cellular Class Encoding Approach to Increasing Efficiency of Nearest Neighbor Searching

摘要

Nearest neighbor searching (NNS) is a common classification method, but its brute force implementation is inefficient for dimensions greater than 10. We present Cellular Class Encoding (CCE) as an alternative, full-search equivalent shown to be 1.1-1.8 times faster than BF on real-world, 14- dimensional data sets. Given a query in an indexed cell of a partitioned space, the CCE's efficiency is achieved by only performing NNS on those database elements which could not be eliminated a priori as impossible nearest neighbors of vectors residing in that cell. To ensure CCE is a viable alternative for real-world applications, we use VQ Speaker ID as a testbed application and present results.