Efficient duplicate node finding in neo4j

Question

A feature request for the next Neo4j version: Neo4j already supports indices that keep properties in a sorted order, allowing fast lookups. Eg. for a person's first name, one might have an index that looks like:

Alice Bob Carol Dave Emily (....)

so one can look up "Dave" with binary search (O(log n)) instead of linear scanning (O(n)).

However, one can also use an index to efficiently find duplicates (nodes which have the same value for some property). Eg., if one wants a list of every group of "person" nodes sharing the same first name, what Neo4j 2.3 seems to do (via EXPLAIN in Cypher) is run a comparison of each node's first name against every other first name, which is O(N^2). Eg. this query:

EXPLAIN MATCH (a:person) WITH a MATCH (b:person) WHERE a.name = b.name RETURN a, b LIMIT 5

shows a CartesianProduct step followed by a Filter step. But with an index on first names, one can do a linear scan over a list like:

Alice Alice Alice Bob Carol Carol Dave Emily Frank Frank Frank (....)

comparing item #1 to #2, #2 to #3, and so on, to build an ordered list of all the duplicates in O(n) time per scan. Neo4j doesn't seem to support that, but it would be very useful for my application, so I'd like to put in a request.

Brian Underwood Brian Underwood · Accepted Answer · 2015-12-29T04:38:36

I have a couple of suggestions for what you might try, but if you find them insufficient (and nobody else has any better ideas), I would suggest submitting new feature ideas to the Neo4j GitHub issues list.

So I was wondering if maybe Neo4j considers properties special. If you have an index on a label/property (which you can create with CREATE INDEX ON :person(name)), then comparing a property with a string should be pretty efficient. I tried passing the name through as just a variable and it seems to have fewer DB hits in my small test DB:

MATCH (a:person)
WITH a, a.name AS name
MATCH (b:person)
WHERE name = b.name
RETURN a, b LIMIT 5

That seems to give me fewer DB hits when I PROFILE it.

Another way to go about it, since you're talking about the same set of objects, is to group the nodes by name and then pull out the pairs for each group. Like so:

MATCH (a:person)
WITH a.name AS name, collect(a) AS people
UNWIND people AS a
UNWIND people AS b
WITH name, a, b
WHERE a <> b
RETURN a, b LIMIT 50

Here we collect up an array for each unique name (we could also lower/upper if we wanted to be case-insensitive) and then UNWIND twice to get a cartesian product of the array. Since we're working on a group-by-group basis, this should be much faster than comparing every node to every other node.

Efficient duplicate node finding in neo4j

1 Answers