Outline Motivation problem formulation o Partition-based framework o Improving Substring Selection Improving g the e verification ● Experiment ● Conclusion 20/2021 PassJoin a VLDB2012
Outline Motivation & Problem Formulation Partition-based Framework Improving Substring Selection Improving the Verification Experiment Conclusion 1/29/2021 PassJoin @ VLDB2012 11
Our Filter condition Give threshold=l hilton huston 12
hilton huston Our Filter Condition 12 1 Give threshold τ=1
Our Filter condition Give threshold=l hilton huston Minimum edit operations is 2 Prune!
hilton huston Our Filter Condition 13 1 Give threshold τ=1 Minimum # edit operations is 2 Prune!
Our Filter condition Threshold t Split r to t +1 disjoint segments ° String r ° String s s Is there any substring of s matching a segment of r Yes No <r s> is a candidate We prune <r,s> 14
Our Filter Condition Threshold τ String r String s Is there any substring of s matching a segment of r ? <r, s> is a candidate We prune <r, s> Yes No 14 Split r to τ +1 disjoint segments
How to partition? Give threshold=l hilton Match huston Candidate
hilton huston How to partition? 15 Give threshold τ=1 Candidate! Match