Timezone: »

Fast k-Nearest Neighbour Search via Prioritized DCI
Ke Li · Jitendra Malik

Mon Aug 07 10:30 PM -- 10:48 PM (PDT) @ C4.6 & C4.7

Most exact methods for k-nearest neighbour search suffer from the curse of dimensionality; that is, their query times exhibit exponential dependence on either the ambient or the intrinsic dimensionality. Dynamic Continuous Indexing (DCI) offers a promising way of circumventing the curse by avoiding space partitioning and achieves a query time that grows sublinearly in the intrinsic dimensionality. In this paper, we propose a variant of DCI, which we call Prioritized DCI, and show a remarkable improvement in the dependence of query time on intrinsic dimensionality. In particular, a linear increase in intrinsic dimensionality, which could mean an exponential increase in the number of points near a query, can be mostly counteracted with just a linear increase in space. We also demonstrate empirically that Prioritized DCI significantly outperforms prior methods. In particular, relative to Locality-Sensitive Hashing (LSH), Prioritized DCI reduces the number of distance evaluations by a factor of 14 to 116 and the memory consumption by a factor of 21.

Author Information

Ke Li (UC Berkeley)
Jitendra Malik (University of California at Berkeley)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors