Efficient computation of k-Nearest Neighbour Graphs for large high-dimensional data sets on GPU clusters.
This paper presents an implementation of the brute-force exact k-Nearest Neighbor Graph (k-NNG) construction for ultra-large high-dimensional data cloud. The proposed method uses Graphics Processing Units (GPUs) and is scalable with multi-levels of parallelism (between nodes of a cluster, between di...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2013-01-01
|
| Series: | PLoS ONE |
| Online Access: | http://europepmc.org/articles/PMC3781071?pdf=render |
| _version_ | 1819070896543891456 |
|---|---|
| author | Ali Dashti Ivan Komarov Roshan M D'Souza |
| author_facet | Ali Dashti Ivan Komarov Roshan M D'Souza |
| author_sort | Ali Dashti |
| collection | DOAJ |
| description | This paper presents an implementation of the brute-force exact k-Nearest Neighbor Graph (k-NNG) construction for ultra-large high-dimensional data cloud. The proposed method uses Graphics Processing Units (GPUs) and is scalable with multi-levels of parallelism (between nodes of a cluster, between different GPUs on a single node, and within a GPU). The method is applicable to homogeneous computing clusters with a varying number of nodes and GPUs per node. We achieve a 6-fold speedup in data processing as compared with an optimized method running on a cluster of CPUs and bring a hitherto impossible [Formula: see text]-NNG generation for a dataset of twenty million images with 15 k dimensionality into the realm of practical possibility. |
| first_indexed | 2024-12-21T17:13:13Z |
| format | Article |
| id | doaj.art-2525cf0600b0491cab1832cb6643e808 |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-12-21T17:13:13Z |
| publishDate | 2013-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-2525cf0600b0491cab1832cb6643e8082022-12-21T18:56:21ZengPublic Library of Science (PLoS)PLoS ONE1932-62032013-01-0189e7411310.1371/journal.pone.0074113Efficient computation of k-Nearest Neighbour Graphs for large high-dimensional data sets on GPU clusters.Ali DashtiIvan KomarovRoshan M D'SouzaThis paper presents an implementation of the brute-force exact k-Nearest Neighbor Graph (k-NNG) construction for ultra-large high-dimensional data cloud. The proposed method uses Graphics Processing Units (GPUs) and is scalable with multi-levels of parallelism (between nodes of a cluster, between different GPUs on a single node, and within a GPU). The method is applicable to homogeneous computing clusters with a varying number of nodes and GPUs per node. We achieve a 6-fold speedup in data processing as compared with an optimized method running on a cluster of CPUs and bring a hitherto impossible [Formula: see text]-NNG generation for a dataset of twenty million images with 15 k dimensionality into the realm of practical possibility.http://europepmc.org/articles/PMC3781071?pdf=render |
| spellingShingle | Ali Dashti Ivan Komarov Roshan M D'Souza Efficient computation of k-Nearest Neighbour Graphs for large high-dimensional data sets on GPU clusters. PLoS ONE |
| title | Efficient computation of k-Nearest Neighbour Graphs for large high-dimensional data sets on GPU clusters. |
| title_full | Efficient computation of k-Nearest Neighbour Graphs for large high-dimensional data sets on GPU clusters. |
| title_fullStr | Efficient computation of k-Nearest Neighbour Graphs for large high-dimensional data sets on GPU clusters. |
| title_full_unstemmed | Efficient computation of k-Nearest Neighbour Graphs for large high-dimensional data sets on GPU clusters. |
| title_short | Efficient computation of k-Nearest Neighbour Graphs for large high-dimensional data sets on GPU clusters. |
| title_sort | efficient computation of k nearest neighbour graphs for large high dimensional data sets on gpu clusters |
| url | http://europepmc.org/articles/PMC3781071?pdf=render |
| work_keys_str_mv | AT alidashti efficientcomputationofknearestneighbourgraphsforlargehighdimensionaldatasetsongpuclusters AT ivankomarov efficientcomputationofknearestneighbourgraphsforlargehighdimensionaldatasetsongpuclusters AT roshanmdsouza efficientcomputationofknearestneighbourgraphsforlargehighdimensionaldatasetsongpuclusters |