Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Entity Resolution: The most common data science challenge

docs.magniv.io

Post reply on HN
Print view View original

11–20 of 28 posts

Re: Entity Resolution: The most common data science challenge

#11

Post by staticassertion »

smeeth wrote: post #2

Danger awaits all ye who enter this tutorial and have large datasets. The tutorial is fun marketing material and all but its FAR too slow to be used on anything at scale. Please, for your sanity, don't treat this as anything other than a fun toy example. ER wants to be an an O(n^2) problem and you have to fight very hard for it not to turn into one. Most people doing this at scale are following basically the same pla…

Cool, TIL about blocking/ filtering. We do entity resolution such that if we have a "process id" (ex: 1234) in two different event logs we can determine if they're the same process (since pids get reused). We don't have to compare every process to every other process, only ones that share the same pid, which drastically reduces the data size, and then we do filtering on top of that based on other optional attributes.

When I wrote this system I didn't know what ER even was, an article like this would have helped a lot, even just the first line defining ER would have helped a lot.

Re: Entity Resolution: The most common data science challenge

#12

Post by benmanns »

smeeth wrote: post #9
pfisherman wrote: post #5

Earlier quoted context omitted.

Great advice! What is your rough guesstimate - in big O - of a general least upper bound of what you can do with ER?

Caveat: just my personal hunch. My suspicion is O(kn), where k is both constant and rather large. This would be highly reliant on an extremely good blocking algorithm. Maybe trending towards O(nlogn)? I don't know. It's really tough. The blocking algorithm for this hypothetical solution would most likely be an approximate hashing algorithm sort of resembling a bloom filter. The input data would have to be amenable to…

Thinking about this, I think you would end up with something like O(s^2*b) where s is the size of your biggest block (e.g. all the "Smith"s or company names containing "Inc." if that doesn't get removed), and b is the number of blocks. This would be at least n, so O(kn) with a big k makes some sense. If you have some way to get away with not comparing every element in a block to every other element, e.g. exact string match only I think you could get away with O(s*log(s)*b), but most of the time the matches are not going to be good enough.

Re: Entity Resolution: The most common data science challenge

#13

Post by benmanns »

What are people doing with entity resolution/record linkage? At Doximity we use it to match messy physician, hospital, and medical publication data from various sources into more coherent data sets to power profiles and research tools. Mostly with https://dedupe.io/ but with some custom tooling to handle larger (1m+ entities) datasets.

Re: Entity Resolution: The most common data science challenge

#14

Post by chrisoakman »

ropeladder wrote: post #6

Entity resolution/record linkage/deduplication is an oddly specialized domain of knowledge given that it's such a common problem. I put together a page of resources a while back if anyone is interested: https://github.com/ropeladder/record-linkage-resources

I gave a talk about Record Linking at Clojure/conj 2019: https://www.youtube.com/watch?v=rGKEOMUtJfE

I opened a PR to add it to your list

Re: Entity Resolution: The most common data science challenge

#15

Post by ropeladder »

chrisoakman wrote: post #14
ropeladder wrote: post #6

Entity resolution/record linkage/deduplication is an oddly specialized domain of knowledge given that it's such a common problem. I put together a page of resources a while back if anyone is interested: https://github.com/ropeladder/record-linkage-resources

I gave a talk about Record Linking at Clojure/conj 2019: https://www.youtube.com/watch?v=rGKEOMUtJfE I opened a PR to add it to your list

Merged! Thanks for the addition, looks like an interesting talk with some good real-world lessons.

Re: Entity Resolution: The most common data science challenge

#16

Post by fastaguy88 »

Sorry to post on at topic I know nothing about.

To me, this looks very similar to local sequence similarity search (e.g. BLAST), where there are very rapid methods that use tuple-lookup and banded alignment to quickly identify "homologs" (the same entity). The nice thing about similarity searching algorithms is that they give you a very accurate probability of whether two strings are "homologous" (belong to the same entity). Perhaps I have the scale wrong, but it is routine to look for thousands of queries (new entities) among hundreds of millions of sequences (known entities) in an hour or so (and sequences are typically an order of magnitude longer than entity names). The problem is embarrassingly parallel, and very efficient algorithms are available for entities that are usually very similar.

Re: Entity Resolution: The most common data science challenge

#17

Post by nwatson »

benmanns wrote: post #13

What are people doing with entity resolution/record linkage? At Doximity we use it to match messy physician, hospital, and medical publication data from various sources into more coherent data sets to power profiles and research tools. Mostly with https://dedupe.io/ but with some custom tooling to handle larger (1m+ entities) datasets.

Replacing sensitive entity content with pseudorandom seeded junk for subsequent training and transforms in exposed settings. Not the main use case for ER.

Re: Entity Resolution: The most common data science challenge

#18

Post by mynegation »

I remember helping my little sister who got entity resolution (people’s names and company names) homework assignment for programming class 26 years ago (she is economics major and I am CS). That was infuriating and intellectually challenging at the same time. We came up with a combination of n-grams, Levenshtein distance, and common abbreviation (think “Inc.” and “Corp.”) canonicalization. It worked reasonably well.

Re: Entity Resolution: The most common data science challenge

#19

Post by jonpon »

ropeladder wrote: post #6

Entity resolution/record linkage/deduplication is an oddly specialized domain of knowledge given that it's such a common problem. I put together a page of resources a while back if anyone is interested: https://github.com/ropeladder/record-linkage-resources

This is amazing! Thanks for sharing :)

Re: Entity Resolution: The most common data science challenge

#20

Post by jonpon »

mynegation wrote: post #18

I remember helping my little sister who got entity resolution (people’s names and company names) homework assignment for programming class 26 years ago (she is economics major and I am CS). That was infuriating and intellectually challenging at the same time. We came up with a combination of n-grams, Levenshtein distance, and common abbreviation (think “Inc.” and “Corp.”) canonicalization. It worked reasonably well.

The reason why I love this problem is because of this! I feel like there are a lot of fun ways to be creative here, but as the other comments mentioned -- to get a scalable and really good solution is extremely difficult.
Post reply on HN