Identity statement area
Reference TypeConference Paper (Conference Proceedings)
Last Update2015: (UTC)
Metadata Last Update2020: (UTC) administrator
Citation KeyMalheirosWalt:2015:SiEfAp
TitleSimple and efficient approximate nearest neighbor search using spatial sorting
Access Date2021, Dec. 04
Number of Files1
Size875 KiB
Context area
Author1 Malheiros, Marcelo de Gomensoro
2 Walter, Marcelo
EditorPapa, Joćo Paulo
Sander, Pedro Vieira
Marroquim, Ricardo Guerra
Farrell, Ryan
Conference NameConference on Graphics, Patterns and Images, 28 (SIBGRAPI)
Conference LocationSalvador
DateAug. 26-29, 2015
PublisherIEEE Computer Society
Publisher CityLos Alamitos
Book TitleProceedings
Tertiary TypeFull Paper
History (UTC)2015-06-19 17:45:06 :: -> administrator ::
2020-02-19 02:14:03 :: administrator -> :: 2015
Content and structure area
Is the master or a copy?is the master
Content Stagecompleted
Content TypeExternal Contribution
Keywordsspatial sorting
k-nearest neighbors
parallel algorithms
data structures
AbstractFinding 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. > SDLA > SIBGRAPI 2015 > Simple and efficient...
doc Directory Contentaccess
source Directory Contentthere are no files
agreement Directory Content
agreement.html 19/06/2015 14:45 0.7 KiB 
Conditions of access and use area
data URL
zipped data URL
Target FilePID3770507.pdf
Update Permissionnot transferred
Allied materials area
Next Higher Units8JMKD3MGPBW34M/3K24PF8
Notes area
Empty Fieldsaccessionnumber affiliation archivingpolicy archivist area callnumber copyholder copyright creatorhistory descriptionlevel dissemination doi edition electronicmailaddress group holdercode isbn issn label lineage mark nextedition notes numberofvolumes orcid organization pages parameterlist parentrepositories previousedition previouslowerunit progress project readergroup readpermission resumeid rightsholder secondarydate secondarykey secondarymark secondarytype serieseditor session shorttitle sponsor subject tertiarymark type url versiontype volume