Optimisation de DBSCAN pour neo4j en Cypher/Python

Question

Bonjour, J'ai essayé d'implémenter l'algorithme DBSCAN pour Neo4j, mais je suis confronté à de sérieux goulots d'étranglement. Je vais décrire la mise en œuvre puis demander de l'aide.

J'ai discrétisé les valeurs epsilon possibles et mis des comptes du nombre de voisins sous chaque discrétisation dans chaque nœud afin de pouvoir récupérer tous les nœuds de base dans une requête.

START a = node(*) 
WHERE a.rel<cutoff threshold>! >= {minp} 
RETURN a 

Cette partie est rapide, la partie qui n'est pas rapide est le suivi requête:

START a = node({i}) 
SET a.label<cutoff threshold>_<minpoints> = {clust} 
WITH a 
MATCH a -[:'|'.join(<valid distance relations>)]- (x) 
WHERE not(has(x.label<cutoff threshold>_<minpoints>)) 
WITH x 
SET x.label<cutoff threshold>_<minpoints>={clust} 
RETURN x 

Je prends alors un nœud de base pour démarrer à partir, et aussi longtemps que il y a encore noyau voisins de noeud, exécutez la requête ci-dessus pour étiqueter leurs voisins. Je pense que le problème est que mon graphique a des niveaux très différents de sparsité - à partir de seulement une faible similitude, il est presque entièrement connecté, avec ~ 50M relations entre ~ 10k nœuds, alors qu'à forte similitude, il y en a aussi peu que ~ 20k relations entre ~ 10k nœuds (ou moins). Peu importe quoi, c'est toujours très lent. Quelle est la meilleure façon pour moi de gérer cela? Est-ce indexer sur le type de relation et le noeud de départ? Je n'ai pas été capable de trouver des ressources sur ce problème, et étonnamment il n'y a pas déjà une implémentation car il s'agit d'un algorithme graphique assez standard. Je pourrais utiliser scikit.learn mais alors je serais limité aux matricies de distance en mémoire seulement :(

Answer 1

Quelle version de neo4j avez-vous essayé avec? Jusqu'à ce que la performance de 1.8 n'ait pas été un objectif de conception de chiffrement (plutôt la langue) Jetez un oeil à un instantané récent (1.9-SNAP).

Assurez-vous également que votre jeu de données hot n'est pas simplement chargé à partir du disque (sinon vous mesurez le disque-io) de sorte que votre memory mapped settings et aussi le tas JVM est assez grand.

Vous pouvez également consulter le cache GCR de Neo4j enterprise qui a une empreinte mémoire plus petite.

Quelle est la cardinalité de count(x) dans votre requête? Si c'est trop petit, vous avez trop de petites transactions en cours. Selon si votre exécution python embedded ou REST utiliser un plus grand tx-scope ou REST-batch-operations

Vous utilisez déjà des paramètres ce qui est génial. Quelle est la variabilité de vos rel-types?

Une chance de partager votre ensemble de données/générateur et le code avec nous (Neo4j) pour les tests de performance de notre côté?

Answer 2

Il y a des implémentations de DBSCAN autour de cette indexation d'utilisation. L'approche que vous devrez peut-être précalculer est en fait une version clairsemée de votre graphique, avec seulement les arêtes qui sont dans le seuil epsilon

Ce que je voudrais souligner, c'est que vous avez apparemment des densités différentes votre ensemble de données, vous pouvez donc utiliser OPTICS, qui est une variante de DBSCAN qui supprime le paramètre epsilon (et qui n'a pas besoin de distinguer les nœuds "core", car chaque nœud est un nœud de base pour un certain epsilon) N'utilisez pas la version Weka (ou la version python inspirée de weka) qui flotte autour). Ils sont à moitié OPTIQUE et à moitié DBSCAN.

Lorsque vous avez des tas modifiables triés efficaces disponibles, OPTICS peut être assez rapide.