IP Library › Granted Patent US 12,299,410
Granted Patent B2
US 12,299,410 · App. 17/853,996 · Granted May 13, 2025

String similarity based weighted min-hashing

Inventors: Allon Adir (Kiryat Tivon, IL); Ehud Aharoni (Kfar Saba, IL); Omri Soceanu (Haifa, IL); Michael Mirkin (Tivon, IL)
Assignee: International Business Machines Corporation
G06F7/02G06F16/152G06F16/313G06F16/90344G06F16/2458
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,299,410
App. No.
17/853,996
Filed
Jun 30, 2022
Granted
May 13, 2025
Kind
B2
Art Unit
2154
USPC
707/749
Abstract

A computer-implemented method for generating hash values to determine string similarity is disclosed. The computer-implemented method includes converting a first text string of a first data set into a first set of shingles. The computer-implemented method further includes determining a weight associated with each shingle in the first set of shingles based, at least in part, on a particular record field associated with a shingle. The computer-implemented method further includes generating, based on a hash function, a hash value for each shingle in the first set of shingles. The computer-implemented method further includes reducing the hash value generated for each shingle in the first set of shingles, based, at least in part on the weight associated with the shingle.

Claims (69)

1. A computer-implemented method for generating hash values to determine string similarity, the computer-implemented method comprising:

converting a first text string of a first data set into a first set of shingles;

determining a weight associated with each shingle in the first set of shingles, based, at least in part, on a particular record field associated with the shingle;

generating, based on a hash function, a hash value for each shingle in the first set of shingles;

reducing the hash value generated for each shingle in the first set of shingles, based, at least in part, on the weight associated with the shingle;

computing a hash signature value using the reduced hash value;

determining that two data records intersect according to the hash signature value; and

storing information about the intersection over a network, in a record database.

2. The computer-implemented method of claim 1 , wherein reducing the hash value generated for each shingle in the first set of shingles is further based on:

generating a first intermediate value by dividing the hash value generated for the shingle by a maximum hash value;

generating a second intermediate value by calculating 1 minus the first intermediate value raised to the weight associated with the shingle;

generating a third intermediate value by multiplying the second intermediate value by the weight associated with the shingle; and

reducing the hash value generated for the shingle based on the third intermediate value.

3. The computer-implemented method of claim 1 , wherein a reduction in the hash value generated for the shingle increases as the weight associated with the shingle increases.

4. The computer-implemented method of claim 1 , wherein a reduction in the hash value generated for the shingle decreases as the weight associated with the shingle increases.

5. The computer-implemented method of claim 1 , wherein converting the text string into the set of shingles further includes:

dividing the first text string into a set of overlapping substrings having a fixed number of consecutive characters, wherein a total number of shingles in the first set of shingles is determined by a total number of different possible combinations overlapping substrings having the fixed number of consecutive characters.

6. The computer-implemented method of claim 1 , wherein reducing the hash value of each shingle in the first set of shingles according to the weight associated with the shingle directly increases a likelihood of a shingle with a higher weight ending up with a minimum hash value.

7. The computer-implemented method of claim 1 , further comprising:

computing a hash-based signature for the shingle having a minimum hash value.

8. The computer-implemented method of claim 7 , further comprising:

determining that the first text string from the first data set and a second text string from a second data set intersect, based, at least in part, the first text string and the second text string sharing the hash-based signature.

9. The computer-implemented method of claim 8 , further comprising:

determining that the first text string from the first data set and the second text string from the second data set are a match, based, at least in part, on a similarity score associated with the first and second text strings being above a predetermined threshold.

10. The computer-implemented method of claim 9 , wherein determining that the first text string from the first data set and the second text string from the second data set are a match is further based, at least in part, on a Jaccard similarity being above a predetermined threshold.

11. A computer program product for generating hash values to determine string similarity, the

computer program product comprising one or more computer readable storage media and program

instructions stored on the one or more computer readable storage media, the program instructions

including instructions, which when executed, cause one or more computer processors to preform

functions to:

convert a first text string of a first data set into a first set of shingles;

determine a weight associated with each shingle in the first set of shingles, based, at least in part, on a particular record field associated with the shingle;

generate, based on a hash function, a hash value for each shingle in the first set of shingles;

reduce the hash value generated for each shingle in the first set of shingles, based, at least in part on the weight associated with the shingle;

compute a hash signature value using the reduced hash value;

determine that two data records intersect according to the hash signature value; and store

information about the intersection over a network, in a record database.

12. The computer program product of claim 11 , wherein the instructions to reduce the hash value generated for each shingle in the first set of shingles is further based on instructions to:

generate a first intermediate value by dividing the hash value generated for the shingle by a maximum hash value;

generate a second intermediate value by calculating 1 minus the first intermediate value raised to the weight associated with the shingle;

generate a third intermediate value by multiplying the second intermediate value by the weight associated with the shingle; and

reduce the hash value generated for the shingle based on the third intermediate value.

13. The computer program product of claim 11 , wherein a reduction in the hash value generated for the shingle increases as the weight associated with the shingle increases.

14. The computer program product of claim 11 , wherein a reduction in the hash value generated for the shingle decreases as the weight associated with the shingle increases.

15. The computer program product of claim 11 , wherein the instructions to convert the text string into the set of shingles further includes instructions to:

divide the first text string into a set of overlapping substrings having a fixed number of consecutive characters, wherein a total number of shingles in the first set of shingles is determined by a total number of different possible combinations overlapping substrings having the fixed number of consecutive characters.

16. The computer program product of claim 11 , wherein reducing the hash value of each shingle in the first set of shingles according to the weight associated with the shingle directly increases a likelihood of a shingle with a higher weight ending up with a minimum hash value.

17. The computer program product of claim 11 , further comprising instructions to:

compute a hash-based signature for the shingle having a minimum hash value; and

determine that the first text string from the first data set and a second text string from a second data set intersect, based, at least in part, the first text string and the second text string sharing the hash-based signature.

18. The computer program product of claim 17 , further comprising instructions to:

determine that the first text string from the first data set and the second text string from the second data set are a match, based, at least in part, on a similarity score associated with the first and second text strings being above a predetermined threshold.

19. A computer system for generating hash values to determine string similarity, comprising:

one or more computer processors;

one or more computer readable storage media;

computer program instructions;

the computer program instructions being stored on the one or more computer readable storage media for execution by the one or more computer processors; and

the computer program instructions including instructions to:

convert a first text string of a first data set into a first set of shingles;

determine a weight associated with each shingle in the first set of shingles, based, at least in part, on a particular record field associated with the shingle;

generate, based on a hash function, a hash value for each shingle in the first set of shingles;

reduce the hash value generated for each shingle in the first set of shingles, based, at least in part on the weight associated with the shingle;

compute a hash signature value using the reduced hash value;

determine that two data records intersect according to the hash signature value; and store information about the intersection over a network, in a record database.

20. The computer system of claim 19 , wherein the instructions to reduce the hash value generated for each shingle in the first set of shingles is further based on instructions to:

generate a first intermediate value by dividing the hash value generated for the shingle by a maximum hash value;

generate a second intermediate value by calculating 1 minus the first intermediate value raised to the weight associated with the shingle;

generate a third intermediate value by multiplying the second intermediate value by the weight associated with the shingle; and

reduce the hash value generated for the shingle based on the third intermediate value.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 30, 2022
From: ADIR, ALLON; AHARONI, EHUD; SOCEANU, OMRI; MIRKIN, MICHAEL
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 060365/0264 →
Continuity (1)
Related Publication 20240004610A1 · Jan 4, 2024
References Cited (88)
US 5200999A · Matyas · 1993 [cited by examiner]
US 6307938B1 · Matyas, Jr. · 2001 [cited by examiner]
US 7151829B2 · Condorelli · 2006 [cited by examiner]
US 7617231B2 · Moon · 2009 [cited by examiner]
US 9158925B2 · Kamara · 2015 [cited by applicant]
US 9275237B2 · De Cristofaro · 2016 [cited by applicant]
US 9686283B2 · Hunt · 2017 [cited by examiner]
US 9942032B1 · Kornaropoulos et al. · 2018 [cited by applicant]
US 9984176B2 · Ueda · 2018 [cited by examiner]
US 10341103B2 · Shaked · 2019 [cited by applicant]
US 10757101B2 · Hunt · 2020 [cited by examiner]
US 11061874B1 · Funk et al. · 2021 [cited by applicant]
US 20030198342A1 · Condorelli · 2003 [cited by examiner]
US 20060101069A1 · Bell · 2006 [cited by examiner]
US 20070130188A1 · Moon · 2007 [cited by examiner]
US 20080071852A1 · Haller · 2008 [cited by examiner]
US 20090132669A1 · Milliken · 2009 [cited by examiner]
US 20100189409A1 · Brasnett et al. · 2010 [cited by applicant]
US 20150010143A1 · Yang · 2015 [cited by examiner]
US 20150098660A1 · Ravid · 2015 [cited by examiner]
US 20160019232A1 · Lambright · 2016 [cited by applicant]
US 20160077977A1 · Narayanamurthy · 2016 [cited by applicant]
US 20160182234A1 · Ueda · 2016 [cited by examiner]
US 20170060866A1 · Rudy · 2017 [cited by examiner]
US 20170286544A1 · Hunt · 2017 [cited by examiner]
US 20180075090A1 · Knight · 2018 [cited by examiner]
US 20190354574A1 · Wick et al. · 2019 [cited by applicant]
US 20190378599A1 · Amisano et al. · 2019 [cited by applicant]
US 20210240841A1 · Nicolas · 2021 [cited by applicant]
US 20210397350A1 · Luo et al. · 2021 [cited by applicant]
US 20220004654A1 · Patel et al. · 2022 [cited by applicant]
US 20230315883A1 · Adir · 2023 [cited by examiner]
CN 105677661A · 2016 [cited by applicant]
CN 112099725A · 2020 [cited by applicant]
CN 114418014A · 2022 [cited by applicant]
EP 3201782 · 2017 [cited by examiner]
“IBM InfoSphere Optim Test Data Fabrication”, IBM, downloaded from the Internet on Apr. 12, 2022, 7 pages, <https://www.ibm.com/products/infosphere-optim-test-data-fabrication>. [cited by applicant]
Baker et al., “Privacy-Preserving Linkage of Genomic and Clinical Data Sets”, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 16, No. 4, Jul./Aug. 2019, pp. 1342-1348. [cited by applicant]
Barker et al., “Recommendation for Pair-Wise Key-Establishment Schemes Using Integer Factorization Cryptography”, Draft NIST Special Publication 800-56B, Revision 1, Mar. 2014, NIST, U.S. Department of Commerce, 132 pag… [cited by applicant]
Carter et al., “Universal Classes of Hash Functions”, Journal of Computer and System Sciences, 18, pp. 143-154 (1979). [cited by applicant]
Chen et al., “Fast Private Set Intersection from Homomorphic Encryption”, In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1243-1255, CCS '17, Association for Computing Mach… [cited by applicant]
Chen et al., “Labeled PSI from Fully Homomorphic Encryption with Malicious Security”, In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 1223-1237, CCS '18, Association for Co… [cited by applicant]
Chen et al., “Perfectly Secure and Efficient Two-Party Electronic-Health-Record Linkage”, IEEE Internet Computing, Mar.-Apr. 2018;22(2): 32-41, Published online Jan. 16, 2018, doi: 10.1109/MIC.2018.112102542. [cited by applicant]
Chen, Yanling, “Current approaches and challenges for the two-party privacy-preserving record linkage (PPRL)”, Collaborative Technologies and Data Science in Artificial Intelligence Applications pp. 108-116 (2020). [cited by applicant]
Christen et al., “Efficient Cryptanalysis of Bloom Filters for Privacy-Preserving Record Linkage”, Advances in Knowledge Discovery and Data Mining. pp. 628-640. Springer International Publishing, Cham (2017). [cited by applicant]
Christen et al., “Precise and Fast Cryptanalysis for Bloom Filter Based Privacy-Preserving Record Linkage”, IEEE Transactions on Knowledge and Data Engineering, vol. 31, No. 11, Nov. 2019, pp. 2164-2177. [cited by applicant]
Churches et al., “Blind data linkage using n-gram similarity comparisons”, In: Advances in Knowledge Discovery and Data Mining. pp. 121-126. Springer Berlin Heidelberg, Berlin, Heidelberg (2004). [cited by applicant]
Clifton et al., “Privacy-Preserving Data Integration and Sharing”, DMKD '04, Jun. 13, 2004, Paris, France, 9 pages. [cited by applicant]
Cong et al., “Labeled PSI from Homomorphic Encryption with Reduced Computation and Communication”, In: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, 27 pages, CCS '21, Associatio… [cited by applicant]
Cui et al., “A Not-So-Trival Replay Attack Against DH-PSI”, Jul. 18, 2020, Cryptology ePrint Archive, Report 2020/901 (2020), 3 pages. [cited by applicant]
Essex, Aleksander, “Secure Approximate String Matching for Privacy-preserving Record Linkage”, IEEE Transactions on Information Forensics and Security (TIFS), 14(10) 11 pages, 2019. [cited by applicant]
Franke et al., “Evaluation of Hardening Techniques for Privacy-Preserving Record Linkage”, Published in Proceedings of the 24th International Conference on Extending Database Technology (EDBT), Mar. 23-26, 2021,12 pages. [cited by applicant]
Franke et al., “Parallel Privacy-preserving Record Linkage using LSH-based Blocking”, In Proceedings of the 3rd International Conference on Internet of Things, Big Data and Security (IoTBDS 2018), pp. 195-203, DOI: 10.5… [cited by applicant]
Freeman, David, “Pairing-Based Identification Schemes”, Cryptology ePrint Archive, Report 2005/336, Received Sep. 19, 2005, 18 pages. [cited by applicant]
Gkoulalas-Divanis et al., “Modern Privacy-Preserving Record Linkage Techniques: An Overview”, IEEE Transactions on Information Forensics and Security, vol. 16, 2021, pp. 4966-4987. [cited by applicant]
He et al., “Composing Differential Privacy and Secure Computation: A case study on scaling private record linkage”, CCS'17, Oct. 30-Nov. 3, 2017, Dallas, TX, USA, pp. 1389-1406, <https://doi.org/10.1145/3133956.3134030>. [cited by applicant]
Huberman et al., “Enhancing Privacy and Trust in Electronic Communities”, In: Proceedings of the 1st ACM Conference on Electronic Commerce, 9 pages, EC '99, Association for Computing Machinery, NY, USA (1999). [cited by applicant]
Ioffe, Sergey, “Improved Consistent Sampling, Weighted Minhash and L1 Sketching”, 2010 IEEE International Conference on Data Mining, 10 pages, DOI 10.1109/ICDM.2010.80. [cited by applicant]
Karapiperis et al., “A Distributed Near-Optimal LSH-based Framework for Privacy-Preserving Record Linkage”, Computer Science and Information Systems 11(2):745-763 DOI: 10.2298/CSIS140215040K, (2014). [cited by applicant]
Kargupta et al., “Random-data perturbation techniques and privacy-preserving data mining”, Knowledge and Information Systems 7(4), 387-414 (May 2005). [cited by applicant]
Khurram et al., “SFour: A Protocol for Cryptographically Secure Record Linkage at Scale”, 2020 IEEE 36th International Conference on Data Engineering (ICDE), 12 pages, DOI 10.1109/ICDE48307.2020.00031. [cited by applicant]
Kroll et al., “Automated Cryptanalysis of Bloom Filter Encryptions of Health Records”, In Proceedings of the International Conference on Health Informatics (Healthinf-2015), pp. 5-13, DOI:10.5220/0005176000050013. [cited by applicant]
Kuzu et al., “A Constraint Satisfaction Cryptanalysis of Bloom Filters in Private Record Linkage”, PETS 2011, LNCS 6794, pp. 226-245, 2011. [cited by applicant]
Leskovec et al., “Finding Similar Items (Chapter 3)—Mining of Massive Datasets”, Published online by Cambridge University Press: Dec. 5, 2014, 4 pages. [cited by applicant]
Meadows, Catherine, “A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party”, In: 1986 IEEE Symposium on Security and Privacy. pp. 134-134 (1986). [cited by applicant]
Mullaymeri, et al., “A Two-Party Private String Matching Fuzzy Vault Scheme”, SAC '21, Mar. 22-26, 2021, Virtual Event, Republic of Korea, pp. 340-343, <https://doi.org/10.1145/3412841.3442079>. [cited by applicant]
Pinkas et al., “Faster Private Set Intersection Based on OT Extension”, USENIX, This paper is included in the Proceedings of the 23rd USENIX Security Symposium, Aug. 20-22, 2014 ⋅ San Diego, CA, 17 pages. [cited by applicant]
Rao et al., “Hybrid Private Record Linkage: Separating Differentially Private Synopses from Matching Records”, ACM Transactions on Privacy and Security, vol. 22, No. 3, Article 15. Publication date: Apr. 2019, 36 pages,… [cited by applicant]
Ravikumar et al., “A secure protocol for computing string distance metrics”, PSDM held at ICDM (2004), 7 pages. [cited by applicant]
Saleem et al., “Recent advancements in garbled computing: How far have we come towards achieving secure, efficient and reusable garbled circuits”, Journal of Network and Computer Applications, 108 (2018) pp. 1-19, <http… [cited by applicant]
Schnell et al., “Privacy-preserving record linkage using Bloom filters”, BMC Medical Informatics and Decision Making 2009, 9:41, doi: 10.1186/1472-6947-9-41, Published Aug. 25, 2009, 11 pages. [cited by applicant]
Vatsalan et al., “Privacy-Preserving Record Linkage for Big Data: Current Approaches and Research Challenges”, Chapter 7, Feb. 2017, Handbook of Big Data Technologies, DOI 10.1007/978-3-319-49340-4_25, 46 pages. [cited by applicant]
Wong et al., “Privacy-preserving similarity coefficients for binary data”, Computers and Mathematics with Applications 65, pp. 1280-1290 (2013), doi:10.1016/j.camwa.2012.02.028. [cited by applicant]
Adir et al., “Method to Privately Determine Data Intersection”, U.S. Appl. No. 17/707,099, filed Mar. 29, 2022. [cited by applicant]
List of IBM Patents or Patent Applications Treated as Related, Filed Jul. 5, 2022, 2 pages. [cited by applicant]
“Weighted MinHash”, downloaded from the Internet on Apr. 28, 2022, 2 pages, <http://ekzhu.com/datasketch/weightedminhash.html>. [cited by applicant]
Authors Disclosed Anonymously, “Privacy-preserving record linkage using local sensitive hash and private set intersection”, submitted Mar. 21, 2022 in preparation for Cloud S&P 2022, 4th Workshop on Cloud Security & Pri… [cited by applicant]
Chmielewski et al., “Fuzzy Private Matching (Extended Abstract)”, 2008 Third International Conference on Availability, Reliability and Security, Mar. 4-7, 2008, Date added to IEEE Xplore: May 23, 2008, DOI: 10.1109/ARES… [cited by applicant]
Christiani et al., “Set Similarity Search Beyond MinHash”, arXiv:1612.07710v2 [cs.DS] Apr. 18, 2017, 14 pages. [cited by applicant]
Ghosh, Supriya, “Text Similarity using K-Shingling, Minhashing and LSH (Locality Sensitive Hashing)”, Oct. 29, 2021, 27 pages, <https://towardsai.net/p/l/text-similarity-using-k-shingling-minhashing-and-Ishlocality-sens… [cited by applicant]
Hasan, Rizvi, “Large scale document similarity search with LSH and MinHash”, Mar. 19, 2020, 10 pages, <https://mrhasankthse.github.io/riz/2020/03/19/Minhash-and-LSH.html>. [cited by applicant]
Ioffe, Sergey, “Improved Consistent Sampling, Weighted Minhash and L1 Sketching”. ICDM 2010, The 10th IEEE International Conference on Data Mining, Sydney, Australia, Dec. 14-17, 2010, 10 pages. [cited by applicant]
Karapiperis et al., “Federal: A Framework for Distance-Aware Privacy-Preserving Record Linkage”, IEEE Transactions on Knowledge and Data Engineering, vol. 30, No. 2, Feb. 2018, 13 pages. [cited by applicant]
Mell et al., “The NIST Definition of Cloud Computing”, Recommendations of the National Institute of Standards and Technology, NIST Special Publication 800-145, Sep. 2011, 7 pages. [cited by applicant]
Papadakis et al., “Blocking and Filtering Techniques for Entity Resolution: A Survey”, 2020, ACM Comput. Surv. 53, 2, Article 31 (Mar. 2020), 42 pages, https://doi.org/10.1145/3377455. [cited by applicant]
Titus et al., “SIG-DB: leveraging homomorphic encryption to Securely Interrogate privately held Genomic DataBases”, provided by inventor in invention record dated Nov. 15, 2021, 38 pages, <https://arxiv.org/ftp/arxiv/pa… [cited by applicant]
Yao et al., “AMPPERE: A Universal Abstract Machine for Privacy-Preserving Entity Resolution Evaluation”, arXiv:2108.09879v2 [cs.CR] Aug. 24, 2021, CIKM '21, Nov. 1-5, 2021, Virtual Event, QLD, Australia, <https://doi.or… [cited by applicant]
IBM Appendix P., List of IBM Patents or Patent Applications Treated as Related, Dated Herewith 2 pages. [cited by applicant]