Name
Abstract | ||
|---|---|---|
We discuss the nearest neighbor search using sketch which is a kind of locality sensitive hash (LSH). Nearest neighbor search using sketch is done in two stages. In the first stage, the top K candidates, which have close sketches to a query, are selected, where K > 1. In the second stage, the nearest object to the query from K candidates is selected by performing actual distance calculations. Conventionally, higher accurate search requires wider sketches than 32-bit. In this paper, we propose search methods using narrow 16-bit sketch, which enables efficient data management by buckets and implement a faster first stage. To keep accuracy, search using 16-bit sketch requires larger K than using 32-bit sketch. By sorting the data objects according to sketch's values, cost influence due to the increase in the number of candidates K can be reduced by improving memory locality in the second stage search. The proposed method achieves about 10 times faster search speed while maintaining accuracy. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.5220/0007377705400547 | ICPRAM: PROCEEDINGS OF THE 8TH INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION APPLICATIONS AND METHODS |
Keywords | Field | DocType |
Similarity Search, Sketch, Ball Partitioning, Hamming Distance, Dimension Reduction, Distance Lower Bound | Pattern recognition,Computer science,16-bit,Artificial intelligence,Nearest neighbor search,Sketch | Conference |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Naoya Higuchi | 1 | 0 | 1.01 |
| Yasunobu Imamura | 2 | 0 | 0.68 |
| Tetsuji Kuboyama | 3 | 140 | 29.36 |
| Kouichi Hirata | 4 | 130 | 32.04 |
| takeshi shinohara | 5 | 103 | 12.69 |