{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T22:36:19Z","timestamp":1778279779584,"version":"3.51.4"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,6]]},"abstract":"\n Determining if two sets are related - that is, if they have similar values or if one set contains the other -- is an important problem with many applications in data cleaning, data integration, and information retrieval. For example, set relatedness can be a useful tool to discover whether columns from two different databases are joinable; if enough of the values in the columns match, it may make sense to join them. A common metric is to measure the relatedness of two sets by treating the elements as vertices of a bipartite graph and calculating the score of the maximum matching pairing between elements. Compared to other metrics which require exact matchings between elements, this metric uses a similarity function to compare elements between the two sets, making it robust to small dissimilarities in elements and more useful for real-world, dirty data. Unfortunately, the metric suffers from expensive computational cost, taking\n O<\/jats:italic>\n (\n n<\/jats:italic>\n 3<\/jats:sup>\n ) time, where\n n<\/jats:italic>\n is the number of elements in the sets, for\n each<\/jats:italic>\n set-to-set comparison. Thus for applications that try to search for all pairings of related sets in a brute-force manner, the runtime becomes unacceptably large.\n <\/jats:p>\n \n To address this challenge, we developed S\n ilk<\/jats:sc>\n M\n oth<\/jats:sc>\n , a system capable of rapidly discovering related set pairs in collections of sets. Internally, S\n ilk<\/jats:sc>\n M\n oth<\/jats:sc>\n creates a signature for each set, with the property that any other set which is related must match the signature. S\n ilk<\/jats:sc>\n M\n oth<\/jats:sc>\n then uses these signatures to prune the search space, so only sets that match the signatures are left as candidates. Finally, S\n ilk<\/jats:sc>\n M\n oth<\/jats:sc>\n applies the maximum matching metric on remaining candidates to verify which of these candidates are truly related sets. An important property of S\n ilk<\/jats:sc>\n M\n oth<\/jats:sc>\n is that it is guaranteed to output exactly the same related set pairings as the brute-force method, unlike approximate techniques. Thus, a contribution of this paper is the characterization of the space of signatures which enable this property. We show that selecting the optimal signature in this space is NP-complete, and based on insights from the characterization of the space, we propose two novel filters which help to prune the candidates further before verification. In addition, we introduce a simple optimization to the calculation of the maximum matching metric itself based on the triangle inequality. Compared to related approaches, S\n ilk<\/jats:sc>\n M\n oth<\/jats:sc>\n is much more general, handling a larger space of similarity functions and relatedness metrics, and is an order of magnitude more efficient on real datasets.\n <\/jats:p>","DOI":"10.14778\/3115404.3115413","type":"journal-article","created":{"date-parts":[[2017,9,7]],"date-time":"2017-09-07T13:35:53Z","timestamp":1504791353000},"page":"1082-1093","source":"Crossref","is-referenced-by-count":23,"title":["S\n ilk<\/scp>\n M\n oth<\/scp>"],"prefix":"10.14778","volume":"10","author":[{"given":"Dong","family":"Deng","sequence":"first","affiliation":[{"name":"MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Albert","family":"Kim","sequence":"additional","affiliation":[{"name":"MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samuel","family":"Madden","sequence":"additional","affiliation":[{"name":"MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Stonebraker","sequence":"additional","affiliation":[{"name":"MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807267"},{"key":"e_1_2_1_2_1","first-page":"918","volume-title":"VLDB","author":"Arasu A.","year":"2006"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398580"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242591"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276781"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872796"},{"key":"e_1_2_1_7_1","volume-title":"CIDR","author":"Deng D.","year":"2017"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593675"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095227"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/6462.6502"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2566736"},{"key":"e_1_2_1_13_1","first-page":"518","volume-title":"VLDB","author":"Gionis A.","year":"1999"},{"key":"e_1_2_1_14_1","volume-title":"PWS Publishing Co.","author":"Hochbaum D. S.","year":"1997"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497434"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989379"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2078331.2078340"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1078"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/876875.879024"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/375360.375365"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007652"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213962"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140440"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767865"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535628"},{"key":"e_1_2_1_27_1","unstructured":"Wikipedia. Hyalophora cecropia --- wikipedia the free encyclopedia 2016. {Online; accessed 25-November-2016}. Wikipedia. Hyalophora cecropia --- wikipedia the free encyclopedia 2016. {Online; accessed 25-November-2016}."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.111"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367516"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989428"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3115404.3115413","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:50:20Z","timestamp":1672221020000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3115404.3115413"}},"subtitle":["an efficient method for finding related sets with maximum matching constraints"],"short-title":[],"issued":{"date-parts":[[2017,6]]},"references-count":30,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["10.14778\/3115404.3115413"],"URL":"https:\/\/doi.org\/10.14778\/3115404.3115413","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,6]]}}}