Graduate School and Research Center in Digital Sciences

Fast distributed k-nn graph update

Debatty, Thibault; Pulvirenti, Fabio; Michiardi, Pietro; Mees, Wim

BIGDATA 2016, 2016 IEEE International Conference on Big Data, December 5-8, 2016, Washington, USA

In this paper, we present an approximate algorithm that is able to quickly modify a large distributed fc-nn graph by adding or removing nodes. The algorithm produces an approximate graph that is highly similar to the graph computed using a naïve approach, although it requires the computation of far fewer similarities. To achieve this goal, it relies on a novel, distributed graph based search procedure. All these algorithms are also experimentally evaluated, using both euclidean and non-euclidean datasets.

Document Doi Hal Bibtex

Title:Fast distributed k-nn graph update
Department:Data Science
Eurecom ref:5133
Copyright: © 2016 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @inproceedings{EURECOM+5133, doi = {}, year = {2016}, title = {{F}ast distributed k-nn graph update}, author = {{D}ebatty, {T}hibault and {P}ulvirenti, {F}abio and {M}ichiardi, {P}ietro and {M}ees, {W}im}, booktitle = {{BIGDATA} 2016, 2016 {IEEE} {I}nternational {C}onference on {B}ig {D}ata, {D}ecember 5-8, 2016, {W}ashington, {USA}}, address = {{W}ashington, {UNITED} {STATES}}, month = {12}, url = {} }
See also: