Take the 2-minute tour ×

I have a collection of objects, each has a field called fingerprint which contains 20 hashes:

    title: 'The Chronicles of Narnia',
    authors: ['C.S. Lewis'],
    fingerprint: ['50e...', 'ae2...', ...]

I then have a query fingerprint of another 20 hashes. What I'd like to do is find all of the entries that share at least X hashes. In other words the intersection of the two arrays must be a certain size.

I have an old implementation of a similar system that uses MySQL. There the query looks something like this:

FROM Document d
INNER JOIN Fingerprint f
    ON d.id = f.document_id
WHERE f.whorl IN (:hashes)

Each entry in the Fingerprint table contains a Document ID and a single whorl from the fingerprint. There will be 20 entries in Fingerprint for every Document.

As I understand it what this query is doing is duplicating the Document every time a whorl matches and then grouping by the unique documents. This seems slightly wasteful but it works.

I'm trying to re-implement this system in MongoDB but I've not had much luck. I can get a list of all of entries that share at least one or all of the whorls:

at least one: db.objects.find({ fingerprint: {$in: [hashes]})
         all: db.objects.find({ fingerprint: {$all: [hashes]})

And I understand that I could scan this list in the application layer to find the matches I'm after. If I anticipate millions of objects (currently about 1.5million) then this seems like a bad idea.

I've looked at the aggregate() functionality but can't improve on what I already have:

db.objects.aggregate({$match: {fingerprint: {$in: [hashes]}}})

From here I thought I could group and filter:

                     {$group: {_id: "$_id", matches: {$sum: 1}}})

Here I was trying to replicate what the MySQL query did: for every match emit a document then count the documents. Of course here we emit a document only once no matter how many matches there are.

I then thought to $unwind the matched list but that produces 20 documents every time.

Ideally, there would be a $some operator that I could use like this:

db.objects.find(fingerprint: {$some: {from: [hashes], count: X}})

Is anything like this possible and efficient? I'd like to be able to run these queries in response to a user's search so I imagine MapReduce is out of the question?


share|improve this question
you were very close to finding the answer yourself - the key is to put $unwind first and then match, regroup and match again. –  Asya Kamsky Jan 7 '13 at 18:26
add comment

1 Answer

It's actually pretty simple to do what you want with aggregation framework. I'm sure you'll be able to refine the following to exactly what you need:

    {$unwind : "$fingerprint" },
    {$group  : {_id:"$title", numMatches: {$sum:1} },
    {$match  : {numMatches : {$gt: X} } }
share|improve this answer
add comment

Your Answer


