Metric Tree for blocking

[fgregg]

@cjdd3b, interested in collaborating on using metric trees for blocking in dedupe?

[cjdd3b]

Hey! Sorry, got super behind on e-mail these last couple weeks. Sure, I'm
in! I'm definitely no expert in metric trees, but I'm excited to learn
more. What's the next step?

On Wed, Mar 5, 2014 at 9:23 PM, Forest Gregg [email protected]:

@cjdd3b https://github.com/cjdd3b, interested in collaborating on using
metric trees for blocking in dedupe?

Reply to this email directly or view it on GitHubhttps://github.com//issues/210
.

[fgregg]

The basic idea is to make canopies http://en.wikipedia.org/wiki/Canopy_clustering_algorithm start by looking at this paper.

Then the next step is to write code that creates a metric tree object where this object has a 'within' method that returns the record ids of records that are within some distance from a target string.

> data = {1: "foo",
              2: "bar",
              3: "baz"}
> tree = MetricTree(data)
> record_ids = tree.within('baz', threshold = 2)
> print record_ids
[2,3]

[cjdd3b]

Cool. I'm off work this week, so I'll see if I can find some time to give
that a look. In the mean time, some of the best implemented work on metric
trees I've found is this totally obscure library by Jochen Spieker:
http://well-adjusted.de/~jrspieker/mspace/. Code is extremely well
documented too.

On Mon, Mar 10, 2014 at 5:18 PM, Forest Gregg [email protected]:

The basic idea is to make canopies
http://en.wikipedia.org/wiki/Canopy_clustering_algorithm start by looking
at this paper.

Then the next step is to write code that creates a metric tree object
where this object has a 'within' method that returns the record ids of
records that are within some distance from a target string.

data = {1: "foo",
2: "bar",
3: "baz"}
tree = MetricTree(data)
record_ids = tree.within('baz', threshold = 2)
print record_ids
[2,3]

Reply to this email directly or view it on GitHubhttps://github.com//issues/210#issuecomment-37235591
.

[fgregg]

Cool! Some other references for future use:

http://code.google.com/p/bpbio/source/browse/trunk/seqfind/seqfind.pyx
https://sites.google.com/site/rrettesite/moman/
http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata

[fgregg]

Let's setup github repos for these.

Also relevant http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html

[fgregg]

moman repo here: https://github.com/datamade/moman

[fgregg]

@cjdd3b, I finally got around to refactoring blocking. The next step for this would be to an Index class that had the same public methods as TfIdfIndex: https://github.com/datamade/dedupe/blob/master/dedupe/tfidf.py

• index
• search
• unindex (this could wait)
• canopy (this could wait)

[fgregg]

Starting to rough it out here: https://github.com/datamade/moman/blob/master/example.py

CC @cjdd3b

[fgregg]

Working on this here: #352

[fgregg]

Got it working pretty well for small sized data, but fine-night just is too slow and takes too much memory for larger sets. This could be an implementation issue, but I don't know of another, better, implementation of Levenshtein distance trees. I'll keep an eye on universal-automata/liblevenshtein#9