Download as PDF, PPTX
![Locality-Sensitive Hashing (LSH) Basic Idea: Use Map Reduce to get likely matches onto the same machines “Johnathon” “Sequoia Capital, LLC” [37.773972, -122.431297] “John” “Sequoia” [37.73, -122.43] “app.example.com” “example.com”](https://image.slidesharecdn.com/er-160414221920/75/DataEngConf-SF16-Entity-Resolution-in-Data-Pipelines-Using-Spark-28-2048.jpg)
![Clique Choosing RDD[T].toLocalIterator() : Iterator[T] • Produces an iterator on the Driver that seamlessly iterates every partition](https://image.slidesharecdn.com/er-160414221920/75/DataEngConf-SF16-Entity-Resolution-in-Data-Pipelines-Using-Spark-36-2048.jpg)
Uploaded byHakka Labs
DataEngConf SF16 - Entity Resolution in Data Pipelines Using Spark
The document outlines various layers of entity resolution (ER) techniques, including naive, graphical, big data, temporal, and learned ER, illustrating their structures and challenges. It emphasizes the importance of matching entity properties and addresses issues like clique selection and locality-sensitive hashing to improve performance. Additionally, it discusses the use of supervised learning for optimizing scoring functions in ER processes.
DataEngConf SF16 - Entity Resolution in Data Pipelines Using Spark
- 1.
- 2.
- 3.
- 4. Talk Structure Layer 1:Naive ER Layer 2: Graphical ER Layer 3: Big Data ER Layer 4: Temporal ER Layer 5: Learned ER
- 5.
- 6. Entity Resolution ID NameWebsite Geo A Facebook facebook.com Menlo Park, CA B FB facebook.com CA C Joe's Cookies joescookies.com San Francisco, CA Suppose we have the following data:
- 7. Entity Resolution Suppose wehave the following data: ID Name Website Geo A Facebook facebook.com Menlo Park, CA B FB facebook.com CA C Joe's Cookies joescookies.com San Francisco, CA D Joes Cookies facebook.com San Francisco, CA
- 8. Entity Resolution Suppose wehave the following data: ID Name Website Geo A Facebook facebook.com Menlo Park, CA B FB facebook.com CA C Joe's Cookies joescookies.com San Francisco, CA D Joes Cookies facebook.com San Francisco, CA E Joes Cookies NULL New York, NY
- 9. Fundamental Concept Match entitieson the similarity of their properties
- 10.
- 11.
- 12. Problems • What aboutwhen match arity != 2 • Entities can’t duplicate across matches • O(N^2) isn’t great either
- 13.
- 14. Think Like aGraph A B EC D ID Name Website Geo A Facebook facebook.com Menlo Park, CA B FB facebook.com CA C Joe's Cookies joescookies.com San Francisco, CA D Joes Cookies facebook.com San Francisco, CA E Joes Cookies NULL New York, NY
- 15. Think Like aGraph A B EC D 150 50 -100 -100 50 50 50 50 -150-150
- 16. Think Like aGraph A B EC D 150 50 -100 -100 50 50 50 50 -150-150
- 17.
- 18. Think Like aClique A B EC D 150 50 -100 -100 50 50 50 50 -150-150 {A} {B} {C} {D} {E} {E, A} {E, B} {E, C} {E, D} {A, B} {A, C} {A, D} {B, C} {B, D} {C, D} {E, A, B} {E, A, C} {E, A, D} {E, B, C} {E, B, D} {E, C, D} {A, B, C} {A, B, D} {A, C, D} {B, C, D} {E, A, B, C} {E, A, B, D} {E, A, C, D} {E, B, C, D} {A, B, C, D} {E, A, B, C, D} possible cliques =>
- 19.
- 20.
- 21. Overlapping Cliques A B EC D AB EC D A = 0.75 B = 0.55
- 22. Overlapping Cliques An entitycan’t belong to more than one clique. When we choose a clique, we must ensure no other cliques use any of those entities
- 23.
- 24.
- 25. Recap • Given adataset of entities… • Take the powerset of those entities => every possible clique • Score all the cliques • In sorted order, choose the best cliques when no elements have been touched
- 26. ER on BiggerData
- 27. • Get potentialmatches on the same machine • Avoid using powerset(n) for large n Challenges
- 28. Locality-Sensitive Hashing (LSH) Basic Idea:Use Map Reduce to get likely matches onto the same machines “Johnathon” “Sequoia Capital, LLC” [37.773972, -122.431297] “John” “Sequoia” [37.73, -122.43] “app.example.com” “example.com”
- 29.
- 30.
- 31. Problems • What ifour entities have missing properties?
- 32. Locality-Sensitive Hashing Joe’s CookiesJoe’sCookie’s joescookies.com joescookies.com A B C “Joe Cookie” “Joe Cookie” “” LSH on “name”
- 33. Multilevel LSH • BasicIdea: Use LSH multiple times on converging cliques
- 34. Joe’s CookiesJoe’s Cookie’s joescookies.comjoescookies.com A B C “Joe Cookie” “Joe Cookie” “” LSN on “name” Joe’s Cookie’s joescookies.com joescookies.com Clique #3 Clique #2 “joescookies.com” “joescookies.com” LSN on “website” Clique #1
- 35. Clique Choosing • Wenow have all potential cliques, spread across the cluster • We now need to choose the best cliques? • Remember: But choosing one clique invalidates others • Fundamentally a Serial Algorithm!
- 36. Clique Choosing RDD[T].toLocalIterator() :Iterator[T] • Produces an iterator on the Driver that seamlessly iterates every partition
- 37.
- 38.
- 39. Challenge • We needto keep track of which entities we’ve “touched” • But using a HashSet means we will start eating a lot memory
- 40. Primer: Bloom Filters BloomFilter{ def mightContain(T obj) def put(T obj) } example: 1 MB @ 0.5% error => 130 KB
- 41. Clique Choosing w/Bloom Filters
- 42. Clique Choosing w/Bloom Filters
- 43. Recap • Challenge: Getdata to the right machine. Solution: Use Locality-Sensitive-Hashing • Challenge: Choose the best cliques. Solution: Use serial iterator and bloom-filters to keep memory low
- 44.
- 45. Temporal Entity Resolution T1 T2 MsSally Smith Mrs Sally Doe thefacebook.com facebook.com Zen Payroll Gusto
- 46. Temporal Entity Resolution A B ZenPayroll zenpayroll.com Gusto gusto.com -1000
- 47. Temporal Entity Resolution A B ZenPayroll zenpayroll.com +100 C Zen Payroll <=> Gusto zenpayroll.com <=> gusto.com Gusto gusto.com +100 -1000
- 48. Iterative Poison Pills •Basic Idea: Use ER techniques we’ve already established • Introduce “poison pills” that can break up cliques if temporal properties don’t match • Iteratively use the poison pills to match on increasingly temporally-aware entities
- 49. gusto.com (Payroll) 2016 Perform Regular ER gusto.com (Travel) 2010 gusto.com <2015 gusto.com zenpayroll.com > 2015 zenpayroll.com (Payroll) 2014 A B C D E A, C, D, E B, E Kick Out Entities That Don’t Match Temporal Requirements A, D gusto.com < 2015 B, E gusto.com > 2015 zenpayroll < 2014 C, E gusto,2016 Perform Regular ER (now with more temporal fields available) A, C, D B, C, E Temporal Poison Pills
- 50. Temporal Entity Resolution • VeryComputational Expensive • Requires Significant Tuning & Tweaking to Keep Tractable • Considered one of the Holy Grails of ER
- 51.
- 52. Recap • Gorilla inthe room: All of our scoring has been manual
- 53. Supervised Learning ER •Basic Idea: Use a training set to learn the weights in our scoring functions • Disclaimer: Only proceed with this if you have very complex scoring properties
- 54.
- 55.
- 56. More Learning Opts •Gradient Descent: What if we viewed the system as having overall “error”? We can then use Gradient Descent to find optimal solution. • Very very computationally intense
- 57.