Ecole d'ingénieur et centre de recherche en Sciences du numérique

Building k-nn graphs from large text data

Debatty, Thibault; Michiardi, Pietro; Thonnard, Olivier; Mees, Wim

BIGDATA 2014, IEEE International Conference on Big Data, 27-30 October 2014, Washington DC, USA

In this paper we present our new design of NNCTPH, a scalable algorithm to build an approximate k-NN graph from large text datasets. The algorithm uses a modified version of Context Triggered Piecewise Hashing to bin the input data into buckets, and uses NN-Descent, a versatile graph-buildingalgorithm, inside each bucket. We use datasets consisting of the subject of spam emails to experimentally test the influence of the different parameters of the algorithm on the number of computed similarities, on processing time, and on the quality of the final graph. We also compare the algorithm with a sequential and a MapReduce implementation of NN-Descent. For our datasets, the algorithm proved to be up to ten times faster than NN-Descent, for the same quality of produced graph. Moreover, the speedup increased with the size of the dataset, making NNCTPH a sensible choice for very largetext datasets.

Document Doi Hal Bibtex

Titre:Building k-nn graphs from large text data
Département:Data Science
Eurecom ref:4462
Copyright: © 2014 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+4462, doi = {}, year = {2014}, title = {{B}uilding k-nn graphs from large text data}, author = {{D}ebatty, {T}hibault and {M}ichiardi, {P}ietro and {T}honnard, {O}livier and {M}ees, {W}im}, booktitle = {{BIGDATA} 2014, {IEEE} {I}nternational {C}onference on {B}ig {D}ata, 27-30 {O}ctober 2014, {W}ashington {DC}, {USA}}, address = {{W}ashington , {\'{E}}{TATS}-{UNIS}}, month = {10}, url = {} }
Voir aussi: