Fast and Memory Saving Instance Search with Approximate Reverse Nearest Neighbor Search Using Reverse Lookup
| Language | English |
|---|---|
| Type | Proceedings of International Conferences |
| Authors | Tomokazu Sato, Masakazu Iwamura, Kitahiro Kaneda, Koichi Kise |
| Title | Fast and Memory Saving Instance Search with Approximate Reverse Nearest Neighbor Search Using Reverse Lookup |
| Journal | Proc. Second IEEE International Conference on Multimedia Big Data (BigMM2016) |
| Pages | pp.326-333 |
| Location | Taipei, Taiwan |
| Reviewed | Reviewed |
| Presentation type | Oral |
| Date | April 2016 |
| Research fields | Nearest Neighbor Search |
| DOI | 10.1109/BigMM.2016.76 |
| Key | Sato2016 (id=1505) |
Abstract
Recently more and more videos have been shared through the websites such as youtube.com. In order to utilize them efficiently, instance search (INS) techniques which find a specific person, object and place from a video database without metadata has been desired. It is known that the BM25 scoring method is a powerful tool for the INS task. It is, however, also known that it requires a time consuming process. It has been pointed out that the time consuming process is equivalent to the bichromatic reverse nearest neighbor (BRNN) search problem and a method to approximate it has been proposed. However, the algorithm needs a huge reference table which causes large memory usage and computational complexity. In this paper, we propose a more efficient way to search BRNNs using a reverse lookup structure. An experimental result using the database of TRECVID 2012 INS task showed that the proposed method was 2.8 times faster with 10% less memory usage than the conventional method.
Export this publication
Format definition
How to write the definition
Insert a field with braces like {authors}. A part enclosed in [ ... ] is omitted entirely when any field inside it is empty. Available fields:
{authors}{authors_and}{authors_ja}{authors_ja_tight}{authors_en}{authors_en_and}{authors_tight}{first_author}{title}{title_ja}{title_en}{journal}{journal_ja}{journal_en}{book_title}{volume}{number}{series}{presen_id}{pages}{pp}{num_pages}{year}{month}{month_en}{month_short}{ym}{date}{date_ja}{date_en}{publisher}{address}{location}{review}{review_ja}{review_en}{reviewed_mark}{presen_type}{type}{type_label}{doi}{url}{key}{awards}