| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2009-03-14 13:15 Approximate nearest neighbor search algorithm on HDD based on B+ tree. Noritaka Himei, Toshikazu Wada (Wakayama Univ.)  PRMU2008-273 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | Nearest Neighbor (NN) search plays important roles in example-based Computer Vision algorithms. Accelerating NN search in very high-dimensional space, however, has a limitation, because of curse of dimensionality. For avoiding this problem, approximate NN search algorithms have been proposed. The most popular one is ANN which is basically a kd-tree based search algorithm with a feasible error. Recently, Locality Sensitive Hashing (LSH) is getting highlighted, because of its theoretical basis providing a clear relationship between the accuracy and the computational complexity. An improved hash based search algorithm, Principal Component Hashing (PCH), has been proposed, which is faster than ANN and LSH at the same accuracy without producing any search failures. However, most NN search algorithms share the limitations that 1) start-up time is mainly consumed for loading the data onto the memory, and 2) NN search for huge data cannot be executed, because the main memory size is limited. For solving this problem, we propose an external NN search algorithm which directly finds the approximate NN data on HDD based on PCH algorithm. The basic idea is simple. By replacing the hash bins on a projection axis by a file having B+ tree structure, we can realize memory efficient PCH which works on HDD. In the experiment, we confirmed that the algorithm can perform NN search on huge database, which cannot be loaded on main memory. Also, we noticed that the search algorithm gains unexpected acceleration by the cashing mechanism of Linux operating system that frequently accessed data on HDD is kept on the memory. | |
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | high dimensional space / approximate NN search / auxiliary storage / HDD / PCH / B+tree / / | |
| Reference Info. | IEICE Tech. Rep., vol. 108, no. 484, PRMU2008-273, pp. 223-228, March 2009. | |
| Paper # | PRMU2008-273 | |
| Date of Issue | 2009-03-06 (PRMU) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | PRMU2008-273 |
|
| Conference Information | |
| Committee | PRMU |
| Conference Date | 2009-03-13 - 2009-03-14 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Tohoku Institute of Technology |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | PRMU |
| Conference Code | 2009-03-PRMU |
| Language | Japanese |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Approximate nearest neighbor search algorithm on HDD based on B+ tree. |
| Sub Title (in English) | |
| Keyword(1) | high dimensional space |
| Keyword(2) | approximate NN search |
| Keyword(3) | auxiliary storage |
| Keyword(4) | HDD |
| Keyword(5) | PCH |
| Keyword(6) | B+tree |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Noritaka Himei |
| 1st Author's Affiliation | Wakayama University (Wakayama Univ.) |
| 2nd Author's Name | Toshikazu Wada |
| 2nd Author's Affiliation | Wakayama University (Wakayama Univ.) |
| 3rd Author's Name | |
| 3rd Author's Affiliation | () |
| 4th Author's Name | |
| 4th Author's Affiliation | () |
| 5th Author's Name | |
| 5th Author's Affiliation | () |
| 6th Author's Name | |
| 6th Author's Affiliation | () |
| 7th Author's Name | |
| 7th Author's Affiliation | () |
| 8th Author's Name | |
| 8th Author's Affiliation | () |
| 9th Author's Name | |
| 9th Author's Affiliation | () |
| 10th Author's Name | |
| 10th Author's Affiliation | () |
| 11th Author's Name | |
| 11th Author's Affiliation | () |
| 12th Author's Name | |
| 12th Author's Affiliation | () |
| 13th Author's Name | |
| 13th Author's Affiliation | () |
| 14th Author's Name | |
| 14th Author's Affiliation | () |
| 15th Author's Name | |
| 15th Author's Affiliation | () |
| 16th Author's Name | |
| 16th Author's Affiliation | () |
| 17th Author's Name | |
| 17th Author's Affiliation | () |
| 18th Author's Name | |
| 18th Author's Affiliation | () |
| Speaker | Author-1 |
| Date Time | 2009-03-14 13:15:00 |
| Presentation Time | 30 minutes |
| Registration for | PRMU |
| Paper # | PRMU2008-273 |
| Volume (vol) | vol.108 |
| Number (no) | no.484 |
| Page | pp.223-228 |
| #Pages | 6 |
| Date of Issue | 2009-03-06 (PRMU) |
[Return to Top Page]