IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0044000.html
   My bibliography  Save this article

GPU-FS-kNN: A Software Tool for Fast and Scalable kNN Computation Using GPUs

Author

Listed:
  • Ahmed Shamsul Arefin
  • Carlos Riveros
  • Regina Berretta
  • Pablo Moscato

Abstract

Background: The analysis of biological networks has become a major challenge due to the recent development of high-throughput techniques that are rapidly producing very large data sets. The exploding volumes of biological data are craving for extreme computational power and special computing facilities (i.e. super-computers). An inexpensive solution, such as General Purpose computation based on Graphics Processing Units (GPGPU), can be adapted to tackle this challenge, but the limitation of the device internal memory can pose a new problem of scalability. An efficient data and computational parallelism with partitioning is required to provide a fast and scalable solution to this problem. Results: We propose an efficient parallel formulation of the k-Nearest Neighbour (kNN) search problem, which is a popular method for classifying objects in several fields of research, such as pattern recognition, machine learning and bioinformatics. Being very simple and straightforward, the performance of the kNN search degrades dramatically for large data sets, since the task is computationally intensive. The proposed approach is not only fast but also scalable to large-scale instances. Based on our approach, we implemented a software tool GPU-FS-kNN (GPU-based Fast and Scalable k-Nearest Neighbour) for CUDA enabled GPUs. The basic approach is simple and adaptable to other available GPU architectures. We observed speed-ups of 50–60 times compared with CPU implementation on a well-known breast microarray study and its associated data sets. Conclusion: Our GPU-based Fast and Scalable k-Nearest Neighbour search technique (GPU-FS-kNN) provides a significant performance improvement for nearest neighbour computation in large-scale networks. Source code and the software tool is available under GNU Public License (GPL) at https://sourceforge.net/p/gpufsknn/.

Suggested Citation

  • Ahmed Shamsul Arefin & Carlos Riveros & Regina Berretta & Pablo Moscato, 2012. "GPU-FS-kNN: A Software Tool for Fast and Scalable kNN Computation Using GPUs," PLOS ONE, Public Library of Science, vol. 7(8), pages 1-13, August.
  • Handle: RePEc:plo:pone00:0044000
    DOI: 10.1371/journal.pone.0044000
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0044000
    Download Restriction: no

    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0044000&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pone.0044000?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Brito, M. R. & Chávez, E. L. & Quiroz, A. J. & Yukich, J. E., 1997. "Connectivity of the mutual k-nearest-neighbor graph in clustering and outlier detection," Statistics & Probability Letters, Elsevier, vol. 35(1), pages 33-42, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ivan Komarov & Ali Dashti & Roshan M D'Souza, 2014. "Fast k-NNG Construction with GPU-Based Quick Multi-Select," PLOS ONE, Public Library of Science, vol. 9(5), pages 1-9, May.
    2. Ali Dashti & Ivan Komarov & Roshan M D’Souza, 2013. "Efficient Computation of k-Nearest Neighbour Graphs for Large High-Dimensional Data Sets on GPU Clusters," PLOS ONE, Public Library of Science, vol. 8(9), pages 1-12, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Shemendyuk, Aleksandr & Wagner, Joël, 2024. "On the factors determining the health profiles and care needs of institutionalized elders," Insurance: Mathematics and Economics, Elsevier, vol. 114(C), pages 223-241.
    2. Nie, Chun-Xiao, 2020. "Correlation dynamics in the cryptocurrency market based on dimensionality reduction analysis," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 554(C).
    3. Nie, Chun-Xiao, 2022. "Analysis of critical events in the correlation dynamics of cryptocurrency market," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 586(C).
    4. Nie, Chun-Xiao & Song, Fu-Tie, 2023. "Stable versus fragile community structures in the correlation dynamics of Chinese industry indices," Chaos, Solitons & Fractals, Elsevier, vol. 167(C).
    5. Brito, María R. & Quiroz, Adolfo J. & Yukich, J. E., 2002. "Graph-Theoretic Procedures for Dimension Identification," Journal of Multivariate Analysis, Elsevier, vol. 81(1), pages 67-84, April.
    6. S. Camelo & M. González-Lima & A. Quiroz, 2015. "Nearest neighbors methods for support vector machines," Annals of Operations Research, Springer, vol. 235(1), pages 85-101, December.
    7. Yong-Jing Hao & Ying-Lian Gao & Mi-Xiao Hou & Ling-Yun Dai & Jin-Xing Liu, 2019. "Hypergraph Regularized Discriminative Nonnegative Matrix Factorization on Sample Classification and Co-Differentially Expressed Gene Selection," Complexity, Hindawi, vol. 2019, pages 1-12, August.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0044000. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.