Complete Coverage for Approximate String Matching in Record Linkage Using Bit Vectors

Research in social history is increasingly influenced by the availability of digitized sources. Tools have to be developed to access these sources in an efficient way. This paper describes a tool that performs family reconstruction using record linkage: linking historical civil certificates based on record similarity. Most current approaches in record linkage apply heuristics to limit the amount of similarity computations at the expense of linking coverage. The current paper describes a binary tree based indexing approach that provides complete coverage within practical time bounds. The indexing scheme is constructed using a simulated annealing algorithm to optimize indexing efficiency. A comparison to other methods using heuristics and complete coverage is provided. The method is developed for Levenshtein edit distance, however an extension to other similarity measures is feasible. As an example, extension to Jaro distance is discussed.