The visualization of large graphs accelerated by the parallel nearest neighbors algorithm

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F16%3A86099107" target="_blank" >RIV/61989100:27240/16:86099107 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/61989100:27740/16:86099107

Výsledek na webu

<a href="http://dx.doi.org/10.1109/BigMM.2016.73" target="_blank" >http://dx.doi.org/10.1109/BigMM.2016.73</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/BigMM.2016.73" target="_blank" >10.1109/BigMM.2016.73</a>

Jazyk výsledku

angličtina

Název v původním jazyce

The visualization of large graphs accelerated by the parallel nearest neighbors algorithm

Popis výsledku v původním jazyce

The search of k-nearest neighbors (K-NN) is a very common task. The K-NN is utilized in many algorithms and scientific areas like clustering, classification, machine learning, N-body simulation, triangulation, image processing and/or video processing. However, the naive implementation of the K-NN is very slow. There are many novel algorithms for the K-NN search, but they are usually based on the hierarchical clustering. The parallelization of those algorithms is a little bit tricky task. This paper primarily presents a novel parallel method for searching the k-nearest neighbors. An appropriate clustering of a sparse space based on the regular grid and the parallel search of the K-NN using the precomputed clusters are introduced. The whole method is designed for the parallel GPU computation and it is implemented on the CUDA architecture. The presented K-NN is utilized to speed up a force-directed graph layout algorithm, which can visually demonstrate the suitability of found neighbors, because they affect the layout quality. The graphs are widely used in social network analysis, computer networks or large information systems like photographic databases or multimedia databases to visualize relationships between elements. The achieved results and performance tests are presented as well. (C) 2016 IEEE.

Název v anglickém jazyce

The visualization of large graphs accelerated by the parallel nearest neighbors algorithm

Popis výsledku anglicky

The search of k-nearest neighbors (K-NN) is a very common task. The K-NN is utilized in many algorithms and scientific areas like clustering, classification, machine learning, N-body simulation, triangulation, image processing and/or video processing. However, the naive implementation of the K-NN is very slow. There are many novel algorithms for the K-NN search, but they are usually based on the hierarchical clustering. The parallelization of those algorithms is a little bit tricky task. This paper primarily presents a novel parallel method for searching the k-nearest neighbors. An appropriate clustering of a sparse space based on the regular grid and the parallel search of the K-NN using the precomputed clusters are introduced. The whole method is designed for the parallel GPU computation and it is implemented on the CUDA architecture. The presented K-NN is utilized to speed up a force-directed graph layout algorithm, which can visually demonstrate the suitability of found neighbors, because they affect the layout quality. The graphs are widely used in social network analysis, computer networks or large information systems like photographic databases or multimedia databases to visualize relationships between elements. The achieved results and performance tests are presented as well. (C) 2016 IEEE.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/LQ1602" target="_blank" >LQ1602: IT4Innovations excellence in science</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

The Second IEEE International Conference on Multimedia Big Data : April 20-22, 2015, Taipei, Taiwan

ISBN

978-1-5090-2178-9

ISSN

—

e-ISSN

—

Počet stran výsledku

8

Strana od-do

9-16

Název nakladatele

IEEE

Místo vydání

New York

Místo konání akce

Tchaj-pej

Datum konání akce

20. 4. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000389610000002