Improving Distributed Similarity Join In Metric Space With Error-bounded Sampling

Abstract

Given two sets of objects, metric similarity join finds all similar pairs of objects according to a particular distance function in metric space. There is an increasing demand to provide a scalable similarity join framework which can support efficient query and analytical services in the era of Big Data. The existing distributed metric similarity join algorithms adopt random sampling techniques to produce pivots and utilize holistic partitioning methods based on the generated pivots to partition data, which results in data skew problem since both the generated pivots and the partition strategies have no quality guarantees. To address the limitation, we propose SP-Join, an end-to-end framework to support distributed similarity join in metric space based on the MapReduce paradigm, which (i) employs an estimation-based stratified sampling method to produce pivots with quality guarantees for any sample size, and (ii) devises an effective cost model as the guideline to split the whole dat

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keywu2019improving

Related papers

• Lsf-join: Locality Sensitive Filtering For Distributed All-pairs Set Similarity Under Skew (2020)6.34
• Unconventional Application Of K-means For Distributed Approximate Similarity Search (2022)5.84
• Massively-parallel Similarity Join, Edge-isoperimetry, And Distance Correlations On The Hypercube (2016)2.26
• Dynamic Enumeration Of Similarity Joins (2021)0.00
• Indexing Metric Spaces For Exact Similarity Search (2020)10.85
• Preference-driven Similarity Join (2017)2.26
• Xling: A Learned Filter Framework For Accelerating High-dimensional Approximate Similarity Join (2024)0.00
• Similarity Join And Similarity Self-join Size Estimation In A Streaming Environment (2018)6.34