1. Identity statement | |
Reference Type | Conference Paper (Conference Proceedings) |
Site | sibgrapi.sid.inpe.br |
Holder Code | ibi 8JMKD3MGPEW34M/46T9EHH |
Identifier | 8JMKD3MGPBW34M/3JMNB5L |
Repository | sid.inpe.br/sibgrapi/2015/06.19.17.45 |
Last Update | 2015:06.19.17.45.06 (UTC) administrator |
Metadata Repository | sid.inpe.br/sibgrapi/2015/06.19.17.45.06 |
Metadata Last Update | 2022:06.14.00.08.05 (UTC) administrator |
DOI | 10.1109/SIBGRAPI.2015.37 |
Citation Key | MalheirosWalt:2015:SiEfAp |
Title | Simple and efficient approximate nearest neighbor search using spatial sorting |
Format | On-line |
Year | 2015 |
Access Date | 2024, Sep. 23 |
Number of Files | 1 |
Size | 875 KiB |
|
2. Context | |
Author | 1 Malheiros, Marcelo de Gomensoro 2 Walter, Marcelo |
Editor | Papa, Joćo Paulo Sander, Pedro Vieira Marroquim, Ricardo Guerra Farrell, Ryan |
e-Mail Address | mgmalheiros@gmail.com |
Conference Name | Conference on Graphics, Patterns and Images, 28 (SIBGRAPI) |
Conference Location | Salvador, BA, Brazil |
Date | 26-29 Aug. 2015 |
Publisher | IEEE Computer Society |
Publisher City | Los Alamitos |
Book Title | Proceedings |
Tertiary Type | Full Paper |
History (UTC) | 2015-06-19 17:45:06 :: mgmalheiros@gmail.com -> administrator :: 2022-06-14 00:08:05 :: administrator -> :: 2015 |
|
3. Content and structure | |
Is the master or a copy? | is the master |
Content Stage | completed |
Transferable | 1 |
Version Type | finaldraft |
Keywords | spatial sorting k-nearest neighbors parallel algorithms data structures |
Abstract | Finding the nearest neighbors of a point is a highly used operation in many graphics applications. Recently, the neighborhood grid has been proposed as a new approach for this task, focused on low-dimensional spaces. In 2D, for instance, we would organize a set of points in a matrix in such a way that their x and y coordinates are at the same time sorted along rows and columns, respectively. Then, the problem of finding closest points reduces to only examining the nearby elements around a given element in the matrix. Based on this idea, we propose and evaluate novel spatial sorting strategies for the bidimensional case, providing significant performance and precision gains over previous works. We also experimentally analyze different scenarios, to establish the robustness of searching for nearest neighbors. The experiments show that for many dense point distributions, by using some of the devised algorithms, spatial sorting beats more complex and current techniques, like k-d trees and index sorting. Our main contribution is to show that spatial sorting, albeit a still scarcely researched topic, can be turned into a competitive approximate technique for the low-dimensional k-NN problem, still being simple to implement, memory efficient, robust on common cases, and highly parallelizable. |
Arrangement 1 | urlib.net > SDLA > Fonds > SIBGRAPI 2015 > Simple and efficient... |
Arrangement 2 | urlib.net > SDLA > Fonds > Full Index > Simple and efficient... |
doc Directory Content | access |
source Directory Content | there are no files |
agreement Directory Content | |
|
4. Conditions of access and use | |
data URL | http://urlib.net/ibi/8JMKD3MGPBW34M/3JMNB5L |
zipped data URL | http://urlib.net/zip/8JMKD3MGPBW34M/3JMNB5L |
Language | en |
Target File | PID3770507.pdf |
User Group | mgmalheiros@gmail.com |
Visibility | shown |
Update Permission | not transferred |
|
5. Allied materials | |
Mirror Repository | sid.inpe.br/banon/2001/03.30.15.38.24 |
Next Higher Units | 8JMKD3MGPBW34M/3K24PF8 8JMKD3MGPEW34M/4742MCS |
Citing Item List | sid.inpe.br/sibgrapi/2015/08.03.22.49 44 sid.inpe.br/sibgrapi/2022/06.10.21.49 2 sid.inpe.br/banon/2001/03.30.15.38.24 2 |
Host Collection | sid.inpe.br/banon/2001/03.30.15.38 |
|
6. Notes | |
Empty Fields | affiliation archivingpolicy archivist area callnumber contenttype copyholder copyright creatorhistory descriptionlevel dissemination edition electronicmailaddress group isbn issn label lineage mark nextedition notes numberofvolumes orcid organization pages parameterlist parentrepositories previousedition previouslowerunit progress project readergroup readpermission resumeid rightsholder schedulinginformation secondarydate secondarykey secondarymark secondarytype serieseditor session shorttitle sponsor subject tertiarymark type url volume |
|