Nous présentons dans ce papier un nouvel algorithme Mean-Shift utilisant les K-plus proches voisins pour la montée du gradient (NNMS : Nearest Neighbours Mean Shift). Le coût computationnel intensif de ce dernier a longtemps limité son utilisation sur des jeux de données complexes où un partitionnement en clusters non ellipsoïdaux serait bénéfique. Or, une implémentation scalable de l'algorithme ne compense pas l'augmentation du temps d'exécution en fonction de la taille du jeu de données en raison de sa complexité quadratique. Afin de pallier, ce problème nous avons introduit le "Locality Sensitive Hashing" (LSH) qui est une approximation de la recherche des K-plus proches voisins ainsi qu'une règle empirique pour le choix du K. La combinaison de ces améliorations au sein du NNMS offre l'opportunité d'un traitement pertinent aux problématiques du clustering appliquée aux données massives.