{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T23:30:15Z","timestamp":1791415815576,"version":"4.3.3"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,2,1]],"date-time":"2011-02-01T00:00:00Z","timestamp":1296518400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2011,2]]},"abstract":"<jats:p>Record linkage is an important data integration task that has many practical uses for matching, merging and duplicate removal in large and diverse databases. However, quadratic scalability for the brute force approach of comparing all possible pairs of records necessitates the design of appropriate indexing or blocking techniques. The aim of these techniques is to cheaply remove candidate record pairs that are unlikely to match. We design and evaluate an efficient and highly scalable blocking approach based on suffix arrays. Our suffix grouping technique exploits the ordering used by the index to merge similar blocks at marginal extra cost, resulting in a much higher accuracy while retaining the high scalability of the base suffix array method. Efficiently grouping similar suffixes is carried out with the use of a sliding window technique. We carry out an in-depth analysis of our method and show results from experiments using real and synthetic data, which highlight the importance of using efficient indexing and blocking in real-world applications where datasets contain millions of records. We extend our disk-based methods with the capability to utilise main memory based storage to construct Bloom filters, which we have found to cause significant speedup by reducing the number of costly database queries by up to 70% in real data. We give practical implementation details and show how Bloom filters can be easily applied to Suffix Array based indexing.<\/jats:p>","DOI":"10.1145\/1921632.1921635","type":"journal-article","created":{"date-parts":[[2011,3,3]],"date-time":"2011-03-03T08:44:26Z","timestamp":1299141866000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Robust Record Linkage Blocking Using Suffix Arrays and Bloom Filters"],"prefix":"10.1145","volume":"5","author":[{"given":"Timothy","family":"de Vries","sequence":"first","affiliation":[{"name":"University of Sydney"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hui","family":"Ke","sequence":"additional","affiliation":[{"name":"University of Sydney"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjay","family":"Chawla","sequence":"additional","affiliation":[{"name":"University of Sydney"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Christen","sequence":"additional","affiliation":[{"name":"The Australian National University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the International Workshop on Challenges in Web Information Retrieval and Integration (WIRI\u201905)","author":"Aizawa A.","unstructured":"Aizawa , A. and Oyama , K . 2005. A fast linkage detection scheme for multi-source information integration . In Proceedings of the International Workshop on Challenges in Web Information Retrieval and Integration (WIRI\u201905) . 30--39. Aizawa, A. and Oyama, K. 2005. A fast linkage detection scheme for multi-source information integration. In Proceedings of the International Workshop on Challenges in Web Information Retrieval and Integration (WIRI\u201905). 30--39."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases (VLDB\u201903)","author":"Bawa M.","unstructured":"Bawa , M. , Bayardo , Jr., R. J. , and Agrawal , R . 2003. Privacy-preserving indexing of documents on the network . In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB\u201903) . VLDB Endowment, 922--933. Bawa, M., Bayardo, Jr., R. J., and Agrawal, R. 2003. Privacy-preserving indexing of documents on the network. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB\u201903). VLDB Endowment, 922--933."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the Workshop on Data Cleaning, Record Linkage and Object Consolidation (ACM SIGKDD\u201903)","author":"Baxter R.","unstructured":"Baxter , R. , Christen , P. , and Churches , T . 2003. A comparison of fast blocking methods for record linkage . In Proceedings of the Workshop on Data Cleaning, Record Linkage and Object Consolidation (ACM SIGKDD\u201903) . Baxter, R., Christen, P., and Churches, T. 2003. A comparison of fast blocking methods for record linkage. In Proceedings of the Workshop on Data Cleaning, Record Linkage and Object Consolidation (ACM SIGKDD\u201903)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Broder A. and Mitzenmacher M. 2004. Network applications of bloom filters: A survey. In Internet Mathematics. Vol. 1. 485--509. Broder A. and Mitzenmacher M. 2004. Network applications of bloom filters: A survey. In Internet Mathematics . Vol. 1. 485--509.","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904)","author":"Chazelle B.","unstructured":"Chazelle , B. , Kilian , J. , Rubinfeld , R. , and Tal , A . 2004. The bloomier filter: an efficient data structure for static support lookup tables . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904) . SIAM, Philadelphia, PA, 30--39. Chazelle, B., Kilian, J., Rubinfeld, R., and Tal, A. 2004. The bloomier filter: an efficient data structure for static support lookup tables. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904). SIAM, Philadelphia, PA, 30--39."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2006.2"},{"key":"e_1_2_1_8_1","volume-title":"Department of Computer Science","author":"Christen P.","unstructured":"Christen , P. 2007. Towards parameter-free blocking for scalable record linkage. Tech. rep. TR-CS-07-03 , Department of Computer Science , Australian National University , Canberra . Christen, P. 2007. Towards parameter-free blocking for scalable record linkage. Tech. rep. TR-CS-07-03, Department of Computer Science, Australian National University, Canberra."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1402020"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1645994"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Dunn H. L. 1946. Record linkage. In Am. J. Pub. Health. 1412--1416. Dunn H. L. 1946. Record linkage. In Am. J. Pub. Health . 1412--1416.","DOI":"10.2105\/AJPH.36.12.1412"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 18th International Conference on Data Engineering, 17--28","author":"Elfeky M.","unstructured":"Elfeky , M. , Verykios , V. , and Elmagarmid , A . 2002. Tailor: a record linkage toolbox . In Proceedings of the 18th International Conference on Data Engineering, 17--28 . Elfeky, M., Verykios, V., and Elmagarmid, A. 2002. Tailor: a record linkage toolbox. In Proceedings of the 18th International Conference on Data Engineering, 17--28."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1969.10501049"},{"key":"e_1_2_1_15_1","first-page":"316","article-title":"Computerised linking of medical records: Methodological guidelines. J Epidemi","volume":"47","author":"Gill L.","year":"1993","unstructured":"Gill , L. , Goldacre , M. , Simmons , H. , Bettley , G. , and Griffith , M. 1993 . Computerised linking of medical records: Methodological guidelines. J Epidemi . Commun. Health 47 , 4, 316 -- 319 . Gill, L., Goldacre, M., Simmons, H., Bettley, G., and Griffith, M. 1993. Computerised linking of medical records: Methodological guidelines. J Epidemi. Commun. Health 47, 4, 316--319.","journal-title":"Commun. Health"},{"key":"e_1_2_1_16_1","unstructured":"Gu L. Baxter R. Vickers D. and Rainsford C. 2003. Record linkage: Current practice and future directions. Tech. rep. CSIRO Mathematical and Information Sciences. Gu L. Baxter R. Vickers D. and Rainsford C. 2003. Record linkage: Current practice and future directions. Tech. rep. CSIRO Mathematical and Information Sciences."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009761603038"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1989.10478785"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 8th International Conference on Database Systems for Advanced Applications (DASFAA\u201903)","author":"Jin L.","unstructured":"Jin , L. , Li , C. , and Mehrotra , S . 2003. Efficient record linkage in large datasets . In Proceedings of the 8th International Conference on Database Systems for Advanced Applications (DASFAA\u201903) . 137. Jin, L., Li, C., and Mehrotra, S. 2003. Efficient record linkage in large datasets. In Proceedings of the 8th International Conference on Database Systems for Advanced Applications (DASFAA\u201903). 137."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v33:2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Marshall J. T. 1947. Canada\u2019s national vital statistics index. In Population Stud. 204--211. Marshall J. T. 1947. Canada\u2019s national vital statistics index. In Population Stud . 204--211.","DOI":"10.1080\/00324728.1947.10415531"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347123"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.803864"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/368996.369026"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1186\/1472-6947-9-41"},{"key":"e_1_2_1_26_1","volume-title":"RR2006\/02","author":"Winkler W. E.","year":"2006","unstructured":"Winkler , W. E. 2006 . Overview of record linkage and current research directions. Tech. rep . RR2006\/02 , US Bureau of the Census. Winkler, W. E. 2006. Overview of record linkage and current research directions. Tech. rep. RR2006\/02, US Bureau of the Census."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1255175.1255213"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132956.1132959"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921632.1921635","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1921632.1921635","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:08Z","timestamp":1750278368000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921632.1921635"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["10.1145\/1921632.1921635"],"URL":"https:\/\/doi.org\/10.1145\/1921632.1921635","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2]]},"assertion":[{"value":"2010-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}