DocumentCode :
1791599
Title :
Building k-nn graphs from large text data
Author :
Debatty, Thibault ; Michiardi, Pietro ; Thonnard, Olivier ; Mees, Wim
Author_Institution :
R. Mil. Acad., Brussels, Belgium
fYear :
2014
fDate :
27-30 Oct. 2014
Firstpage :
573
Lastpage :
578
Abstract :
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-building algorithm, 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 large text datasets.
Keywords :
data handling; graph theory; unsolicited e-mail; MapReduce implementation; NN-Descent graph-building algorithm; NNCTPH; context triggered piecewise hashing; k-NN graphs; large text datasets; scalable algorithm; spam emails; Algorithm design and analysis; Approximation algorithms; Artificial neural networks; Buildings; Computational efficiency; Electronic mail; Measurement;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Big Data (Big Data), 2014 IEEE International Conference on
Conference_Location :
Washington, DC
Type :
conf
DOI :
10.1109/BigData.2014.7004276
Filename :
7004276
Link To Document :
بازگشت