| Information Science & Engineering |
|
|
|
|
| Indexing the bit-code and distance for fast KNN search in high-dimensional spaces |
| LIANG Jun-jie, FENG Yu-cai |
| College of Computer Science & Technology, Huazhong University of Science and Technology, Wuhan 430074, China; Faculty of Mathematics & Computer Science, Hubei University, Wuhan 430062, China |
|
|
|
Abstract Various index structures have recently been proposed to facilitate high-dimensional KNN queries, among which the techniques of approximate vector presentation and one-dimensional (1D) transformation can break the curse of dimensionality. Based on the two techniques above, a novel high-dimensional index is proposed, called Bit-code and Distance based index (BD). BD is based on a special partitioning strategy which is optimized for high-dimensional data. By the definitions of bit code and transformation function, a high-dimensional vector can be first approximately represented and then transformed into a 1D vector, the key managed by a B+-tree. A new KNN search algorithm is also proposed that exploits the bit code and distance to prune the search space more effectively. Results of extensive experiments using both synthetic and real data demonstrated that BD outperforms the existing index structures for KNN search in high-dimensional spaces.
|
|
Received: 22 August 2006
|
|
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
