English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

A Nearest Neighbor Data Structure for Graphics Hardware

MPS-Authors
/persons/resource/persons83850

Cayton,  L
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;
Max Planck Institute for Biological Cybernetics, Max Planck Society;

Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Cayton, L. (2010). A Nearest Neighbor Data Structure for Graphics Hardware. In First International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures at VLDB 2010 (ADMS 2010) (pp. 9-14).


Cite as: https://hdl.handle.net/11858/00-001M-0000-0013-BE64-1
Abstract
Nearest neighbor search is a core computational task in
database systems and throughout data analysis. It is also
a major computational bottleneck, and hence an enormous
body of research has been devoted to data structures and
algorithms for accelerating the task. Recent advances in
graphics hardware provide tantalizing speedups on a variety
of tasks and suggest an alternate approach to the problem:
simply run brute force search on a massively parallel sys-
tem. In this paper we marry the approaches with a novel
data structure that can effectively make use of parallel systems such as graphics cards. The architectural complexities of graphics hardware - the high degree of parallelism, the small amount of memory relative to instruction throughput, and the single instruction, multiple data design- present significant
challenges for data structure design. Furthermore,
the brute force approach applies perfectly to graphics hardware, leading one to question whether an intelligent algorithm or data structure can even hope to outperform this
basic approach. Despite these challenges and misgivings,
we demonstrate that our data structure - termed a Random
Ball Cover - provides significant speedups over the GPU-
based brute force approach.