Buffer k-d Trees: Processing Massive Nearest Neighbor Queries on GPUs
Authors: Fabian Gieseke, Justin Heinermann, Cosmin Oancea, Christian Igel
ICML 2014 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experiments show that we can take advantage of both the hierarchical subdivision induced by k-d trees and the huge computational resources provided by today s many-core devices. We demonstrate the potential of our approach in astronomy, where hundreds of million nearest neighbor queries have to be processed. |
| Researcher Affiliation | Academia | Fabian Gieseke EMAIL Department of Computer Science, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen, Denmark Justin Heinermann EMAIL Department of Computing Science, University of Oldenburg, Uhlhornsweg 84, 26111 Oldenburg, Germany Cosmin Oancea EMAIL Department of Computer Science, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen, Denmark Christian Igel EMAIL Department of Computer Science, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen, Denmark |
| Pseudocode | Yes | Algorithm 1 LAZYPARALLELNN, Algorithm 2 FINDLEAFBATCH, Algorithm 3 PROCESSALLBUFFERS, Algorithm 4 Leaf Nearest Neighbor |
| Open Source Code | Yes | The code is made publicly available on the authors websites. |
| Open Datasets | Yes | Current projects such as the Sloan Digital Sky Survey (SDSS) (Ahn et al., 2013) have gathered terabytes of data for hundreds of million astronomical objects. |
| Dataset Splits | No | The paper does not explicitly provide training/test/validation dataset splits. It mentions training and testing patterns but not the specific split percentages or counts for validation. |
| Hardware Specification | Yes | All experiments were conducted on a standard PC with an Intel(R) Core(TM) i7-3770 CPU at 3.40GHz (4 cores, 8 hardware threads), 16GB RAM, and a Ge Force GTX 770 GPU with 1536 shader units (4GB RAM). The operating system was Ubuntu 12.04 (64 Bit). |
| Software Dependencies | Yes | All algorithms were implemented in C and Open CL compiled using Swig with gcc-4.6.3 and -fopenmp as additional compiler option; Python was used to set up the experiments. |
| Experiment Setup | Yes | For a buffer k-d tree of height h, we fixed B = 222 h. In each iteration of Algorithm 1, M = 5B indices were fetched from input and reinsert. |