Buffer k-d Trees: Processing Massive Nearest Neighbor Queries on GPUs
Authors: Fabian Gieseke, Justin Heinermann, Cosmin Oancea, Christian Igel
ICML 2014 | Conference 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 FABIAN.GIESEKE@DIKU.DK Department of Computer Science, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen, Denmark Justin Heinermann JUSTIN.HEINERMANN@INFORMATIK.UNI-OLDENBURG.DE Department of Computing Science, University of Oldenburg, Uhlhornsweg 84, 26111 Oldenburg, Germany Cosmin Oancea COSMIN.OANCEA@DIKU.DK Department of Computer Science, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen, Denmark Christian Igel IGEL@DIKU.DK 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. |