On the Complexity of Sorted Neighborhood

Mayank Kejriwal, Daniel P. Miranker

Record linkage concerns identifying semantically equivalent records in databases. Blocking methods are employed to avoid the cost of full pairwise similarity comparisons on $n$ rec…