Em-K Indexing for Approximate Query Matching in Large-scale ER

Many real-world data collections are low in quality because of errors (e.g., typographical errors or phonetic misspellings), incomplete or missing data, incompatible formats for recording database fields (e.g., dates, addresses), and temporal inconsistencies. Integrating or querying multiple data sources to identify records that belong to the same real-world entity is a challenging task in the presence of such data. This task is often referred to as the entity resolution (ER) problem and appears in many database applications when identifying duplicates, cleansing data, or improving data quality.

ER has been studied for years. However, the issues of efficiently handling large-scale data remain an open research problem (Liang et al., 2014). Typical ER algorithms have a quadratic running time, which is computationally prohibitive for large-scale data collections. This performance bottleneck occurs due to the detail-level pairwise comparison step of the ER process.

Consider the motivating example of linking medical records where one entity can have many entries over several years. A public health case study could involve hundreds of thousands of entities with millions of records. Quadratic ER among the records will require trillions of pairwise comparisons in this application, which is computationally infeasible.

Indexing techniques address this problem by grouping similar records into blocks. Usually, groups of similar records within or between datasets are smaller than the total number of records. Hence, many comparisons will be among the non-matching records when applying pairwise comparisons using a brute-force ER algorithm. Indexing techniques aim to reduce the potential number of comparisons by reducing the comparisons between those non-matches (Christen, 2012b). Therefore, indexing-based ER solutions run much faster than brute-force ER solutions (Kim and Lee, 2010).

However, most existing indexing methods still have quadratic time complexity and are too slow to deal with very large-scale data collections. Also, some non-scaling ER algorithms tend to generate a large number of blocks and a large number of candidate records in each block for large-scale scenarios (Christen, 2012b).

Traditional ER solutions often process databases offline in batch mode, and no further action is required once a pair of matches are determined. However, many organisations are moving online where they have to provide their services through prompt responses. Hence, many newer, real-world scenarios require real-time query processing against large-scale databases. Some of the applications demand entity query matching against large-scale reference databases within a short time. We refer to this as the query matching problem in ER. In such configurations, traditional ER solutions become less efficient or unusable.

In order to motivate the problem context and illustrate the usefulness of the approach presented in this paper, we provide the following real-world example. The application is in criminal investigations, where law enforcement officers need to query a database to identify potential suspects. Suspects usually lie to police investigators about their true identities, e.g., names, birth dates, or addresses (Chen et al., 2004). Hence, finding an exact match for falsified data against the real identity recorded in a law enforcement computer system is problematic. Detecting deceptive identities is a time-consuming activity that involves large amounts of manual information processing in real-life scenarios (Wang et al., 2004). Therefore efficient ER solutions that support real-time and approximate query matching against existing datasets can be invaluable.

Toward the challenge of real-time approximate query matching, we present an indexing technique that reduces the number of pairwise comparisons needed in the ER. The proposed indexing method transforms a set of records into a set of vectors in a metric-space, specifically a lower-dimensional Euclidean space using multidimensional scaling. These vectors have two main attractive attributes in the context. First, comparisons between vectors in a metric-space are much cheaper than string comparisons. Second, these vectors support efficient indexing data structures. We utilise these properties to propose an indexing approach that classifies similar vectors in a low-dimensional Euclidean space. We call our method Em-K indexing, as our method operates by embedding data in a K-dimensional space.

Exact query matching is easy against a reference database as we can search based on lexicographical order using an efficient data structure, e.g., binary trees. However, exact query matching is impossible with many real-world databases due to various data quality issues, and approximate query matching is the common approach (Christen, 2012a). The proposed indexing method address the problem of real-time and approximate query matching. We will be mainly using the term query matching instead of approximate query matching in this paper.

Our main objective is to develop a fast indexing method for query matching. We want our method to be efficient for large-scale data and robust to errors in the data. The proposed method searches for a block of records in the reference database as a set of potential matches to the querying record. Hence we avoid comparing the query against all the records in the referencing database. However, the search is done in the Euclidean space using a Kd-tree data structure where each record in the reference database and a query record become a vector in this space.

Given the block size is $B$, we search for this number of nearest neighbours for the query point by traversing the Kd-tree nodes that store the reference database. The search has a $O(B\log N)$ complexity, given $N$ is the number of records in the reference database. The method embeds query records in a pre-mapped Euclidean space to search against the reference data points. We propose an out-of-sample embedding that uses a fraction of the original data (defined as landmarks in Section 5) for query record embedding. For $L$ landmarks, the embedding requires $O(L^{2})$ operations, and we can choose $L$ such that $L\ll N$.

In this paper, we explore the use of metric-space indexing for efficient and approximate query matching. In particular, our contributions are,

• •

  We formulate the query matching and deduplication problems in ER to provide metric-space base solutions. First, we propose an indexing approach based on landmarks as a motivating example to explore the basic building blocks needed for query matching.

• •

  We propose a landmarks based indexing technique for query matching to provide a quick and accurate block of potential matches. Our method can process a stream of queries against a large-scale data set within a short time. By doing so, we obtain as many of the matching records as possible where the processing time of a single query takes a sub-second time. The technique is robust to noisy data that contains errors and allow efficient approximate query matching.

To describe the problem succinctly, we first describe relevant definitions and some key concepts. The definitions of relevant concepts here follow those in (Simonini et al., 2018; Papadakis et al., 2020).

In this section, we formulate our problem using the concepts and the definitions presented in the previous section. The proposed Em-K indexing method functions as a preprocessing approach for a more detailed query-matching ER. We use deduplication as a motivating example that explains the basic building blocks to the query matching problem. Thus we defined the following two problems:

We also consider the deduplication problem here, primarily as an explanatory model. We defined deduplication in Section 2.2 under dirty ER. In the following, we define the indexing for deduplication.

Traditional indexing techniques split the database into non-overlapping blocks, only comparing the records within any block (McCallum et al., 2000; Christen, 2012b; Papadakis et al., 2020; Jaro, 1989; Draisbach and Naumann, 2011). Blocks of similar pairs are determined by building an indexing structure that takes a set of records as input and classifies them according to some criteria. Usually, this criterion is based on matching a blocking key consisting of a single or several attribute values of records (Christen, 2012b). Our method uses blocking values to create blocks of records that transform blocking into a k-nearest neighbour (k-NN) search. We combine the spatial joins with block building to convert blocking values to a similarity preserving Euclidean space. The result is overlapping blocks of records.

The proposed method requires mapping blocking values into multidimensional vectors. Since many comparisons in ER are between strings of characters, we focus on entity attributes that contain string values here. Unlike the similarity between string values, the similarity between numerical values is easy to compute using $L^{p}$ norms in a metric-space (Kim and Lee, 2010). Hence, we used this property of the metric-space to propose a scalable indexing technique for query matching.

If we assume strings as elements of a complicated high-dimensional space, the distance between two different strings is typically large. However, misspelled strings tend to be located near correctly spelled strings (Mazeika and Böhlen, 2006). The embedding of a string database into a metric-space needs to preserve these two properties. Thus, coordinates for blocking values are determined in a Euclidean space such that the associated Euclidean distances approximate the dissimilarities between the original blocking values.

The general problem of assigning coordinates in this manner is one of embedding a metric or non-metric-space into a Euclidean space (Tang and Crovella, 2003). Suppose $R$ is a collection of objects, $\delta$ measures the distances between $R$ objects, $X$ represents the coordinates matrix for the $R$ objects in the Euclidean space, and $d$ measures the distances between coordinates.

Embedding of a metric or non-metric-space $(R,\delta)$ into a Euclidean space $(X,d)$ is a mapping $\phi:R\to X$. In this paper $(R,\delta)$ will always be a finite space (i.e., $R$ is a finite set) and $(X,d)$ will always be a Euclidean space.

A commonly used technique for embedding a set of distances (or dissimilarities) into a Euclidean space is multidimensional scaling (MDS) (Kruskal, 1964). We applied MDS because we can adapt it to achieve good time efficiency and distance preserve capability for large-scale data with a small amount of extra effort.

Among the variants of MDS, we use least-squares multidimensional scaling (LSMDS) for the embedding since it gave the best results compared to other variations such as classical scaling (Herath et al., 2021). We can map a set of blocking values to a lower-dimensional Euclidean space by applying LSMDS such that the distances between vectors preserve the dissimilarities between them. This embedding leaves similar blocking values closer in the Euclidean space allowing efficient, geometric-based indexing.

LSMDS initially maps each item in the non-metric or metric-space to a $K$-dimensional point. Then minimises the discrepancy between the actual dissimilarities and the estimated distances in the $K$-dimensional space by optimisation (Groenen and Velden, 2016). This discrepancy is measured using raw stress ($\sigma_{raw}$) given by the relative error where ${\delta_{ij}}$ is the dissimilarity between the two objects and ${d_{ij}}$ is the Euclidean distance between their estimated points.

Possible weights for each pair of points are denoted by $w_{ij}$. Weights are useful in handling missing values and the default values are $w_{ij}=0$, if $\delta_{ij}$ is missing and $w_{ij}=1$, otherwise (Groenen and Velden, 2016). We do not apply weights in this work, hence, $w_{ij}=1$ always. We prefer the normalized stress ($\sigma$) in our experiments since it is popular and theoretically justified. The normalized stress ($\sigma$) is obtained by $\sigma=\sqrt{\sigma_{raw}(\mathbf{X})/\delta_{ij}^{2}}.$

However, traditional MDS algorithms such as LSMDS require extensive preprocessing and usually are computationally expensive, thus not appropriate for large scale applications. The two main drawbacks are,

• •

  MDS requires $O(N^{2})$ time, where $N$ is the number of items. Thus, it is impractical for large $N$.

• •

  In an out-of-sample setting or a query-by-example setting, a query item has to be mapped to a point in the pre-mapped Euclidean space. Given LSMDS algorithm is $O(N^{2})$, an incremental algorithm to search/add a new item in the database would be $O(N)$. Hence a query search would be similar to sequential scanning of a database (Faloutsos and Lin, 1995).

Among the proposed methods of scalable MDS, we are interested in using an out-of-sample embedding approach as a scaling method for LSMDS. We have two main purposes:

1. (1)

   To embed large-scale reference databases.

2. (2)

   To embed previously unseen data to a pre-mapped Euclidean space.

Suppose we have a configuration of $N$ points in a $K$-dimensional Euclidean space obtained by applying LSMDS to a set of $N$ objects. Let $Q$ be out-of-sample objects, with measured pairwise dissimilarities from each of the original $N$ objects. The out-of-sample embedding problem is to embed the new $Q$ objects into the pre-mapped $K$-dimensional Euclidean space.

Our out-of-sample embedding approach uses the stochastic gradient descent algorithm to minimise the following objective function for numerical optimisation. The out-of-sample embedding of a new object $y$ is obtained by minimising the following objective function,

The out-of-sample embedding approach becomes inefficient for large-scale data by comparing each new point with all the existing points. We scale our out-of-sample embedding solution to accommodate large-scale data by only considering a fraction of the pre-mapped Euclidean space. The initially selected subset of pre-mapped data is usually known as landmarks. Landmarks or anchors have been used with out-of-sample extensions to scale MDS and other embedding techniques (Silva and Tenenbaum, 2002; Tang and Crovella, 2003). We discuss the characteristics of a good set of landmarks and landmarks selection methods in Section 5.

Once the Euclidean space consists of all the data required, we then formulate our indexing method to generate blocks that group close-by vectors in the Euclidean space.

MDS maps high dimensional data (in the original space) into a Euclidean space (vector space). The rationale for performing such a mapping is to approximate the distances between objects in an original space in Euclidean space. Searching for similar points in Euclidean space is less expensive and quick since we can use efficient data structures such as Kd-trees. We use Kd-trees and k-NN search to find similar vectors in the Euclidean space.

In general, k-NN search refers to finding the closest elements for a query $q$ within a given set of points $N$, as measured by some distance function ${d}(N,q)$ (Kumar et al., 2008). The distance function $d$ is a metric, e.g., $L^{p}$ norm, which satisfies the non-negativity, identity, symmetry, and triangle inequality properties (Chatfield and Collins, 1981; Loo, 2014). We use Euclidean distances $d_{E}$( where $p=2$) in our calculations. Here we are interested in finding the k-NNs ($k$ nearest neighbours) where k may be moderately large.

An index is a data structure that reduces the number of distance evaluations needed at query time. An efficient and scalable indexing method can facilitate accurate and efficient k-NN search that supports large-scale datasets. We can apply several k-NN search methods for indexing arbitrary metric spaces; for more details, refer to the surveys (Hjaltason and Samet, 2003; Chávez et al., 2001). Distance-based indexing methods use distance computations to build the index. Once the index is created, these can often perform similarity queries with a significantly lower number of distance computations than a sequential scan of the entire dataset (Hjaltason and Samet, 2003).

The decision of which indexing structure to apply depends on several factors, including query type, data type, complexity and the application. Among many data structures, we choose Kd-trees for the k-NN search. It is considered one of the best data structures for indexing multidimensional spaces and is designed for efficient k-NN search (Adly, 2009).

Kd-trees organise $K$-dimensional vectors of numeric data. Each internal node of the tree represents a branching decision in terms of a single attribute’s value, called a split value (Talbert and Fisher, 2000). These internal nodes generate a splitting hyperplane that divides the space into subspaces using this split value, usually the median value along the splitting dimension. We will use the median when constructing the Kd-tree for the data in our experiments. Building a Kd-tree (with the number of dimensions $K$ fixed, and dataset size $N$) has $O(N\log N)$ complexity (Arya et al., 1998). For more details on Kd-trees and k-NN search implementations, refer to (Arya et al., 1998).

The k-NN search algorithm aims to find a node in the tree closest to a given input vector. Searching a Kd-tree for $k$ nearest neighbours is $O(k\log N)$, which is the key to fast indexing. It uses tree properties to quickly eliminate large portions of the search space (Adly, 2009).

We evaluated the two proposed Em-K indexing methods under various settings (e.g., different dimensions, varying block sizes and datasets, and error rates). Two main questions to study in the experiments are: (1) Are these proposed methods robust over various settings? (2) Does Em-K indexing achieve high accuracy and good scalability?

All algorithms are implemented in R and executed on a desktop with Intel Core 5 Quad 2.3GHz, 16GB RAM, and MacOS Big Sur.

The Em-K indexing methods embed a set of strings in a metric-space, particularly a lower-dimensional Euclidean space. There is a trade-off between the dimension and the accuracy of the embedding. Higher dimensions allow the embedding to be more accurate. However, it does not scale well for large datasets. In our experiments, we only selected two blocking variables for embedding and indexing. We can also use other blocking variables, such as addresses and gender. As a result, the dimension of the Euclidean space needs to extend accordingly to facilitate those.

The most costly part of the method is the amount of time to embed queries, which increases linearly with the number of landmarks. However, this approach is easily parallelizable since each query is processed separately. We can tune the parameters for a fast, less accurate query matching or a slow, more accurate method depending on the application.

Our method is designed to solve approximate query matching rather than exact query matching. It means we expect the queries to contain errors in their attribute values. We could easily perform an exact search based on lexicographical order considering the query and the reference dataset using a data structure such as a binary tree to find exact matches as a pre-filter for our method.

Our indexing method for query matching uses distance computations to embed the reference database in the Euclidean space. This embedding is a slow process that requires a minimum of $O(L^{2})$ operations where $L$ is the number of landmarks. We consider this as the training phase, which only needs to be performed once. However, with the Kd-tree built, we can perform similarity queries with significantly fewer distance computations than a sequential scan of the entire dataset.

In some applications, large-scale reference databases grow with time. Hence the new entities need to be added incrementally. For example, some applications would require the addition of queries that have no matching records in the reference database already. To facilitate those, we need to extend the Kd-tree accordingly without repeating the embedding process that creates the initial tree. However, growing a Kd-tree can be a heuristic procedure where the tree could become unbalanced. Therefore, we can explore alternative tree structures such as R-tree that are robust against dynamic data.

Indexing techniques are recognized as a crucial component for improving the efficiency and the scalability of the ER solutions. There exist a variety of indexing techniques which are also known as blocking or filtering. Papadakis et al. (Papadakis et al., 2020) and Christen et al. (Christen, 2012b) presented surveys that include well-known indexing methods such as standard blocking, suffix array, q-gram blocking, sorted-neighbourhood, canopy clustering, and string-map based methods. We only survey a few closely related works since many of these existing methods are orthogonal to the focus of this paper.

Canopy clustering uses cheap comparison metrics to group similar records into overlapping canopies and creates blocks from records that share a common-canopy (McCallum et al., 2000). The method depends on global threshold values, and that reduces its flexibility. It also uses similarity measures such as TF-IDF and Cosine distance that can be computationally expensive (Christen, 2012b).

Mapping-based indexing methods map records to objects in a Euclidean space, preserving the original distances between them. Jin et al. (Li et al., 2006) proposed the Stringmap algorithm that maps records into a similarity preserving Euclidean space (with dimension between 15-20). Similar pairs are determined by building an R-tree. Stringmap has linear complexity, but it requires tuning several parameters. Moreover, the performance of such approaches tends to decrease with more than 20 dimensions. In contrast, our method operates in much smaller dimensions.

The Double Embedding scheme (Adly, 2009) uses two-dimensions, $K$ and $K^{\prime}$ for embedding records such that $K^{\prime}<K$. Similarity joins are performed in the metric-space using a Kd-tree and nearest-neighbour search to find candidate matches. The method is faster than the Stringmap algorithm. However, it attempts to keep the embedding contractive by increasing the distance computations and is not suitable for large-scale data.

Another metric-space indexing technique utilised an M-tree to produce complete and efficient ER results. The cost of the method and the quality of the results have remained similar to existing indexing techniques (Akgün et al., 2018). However, it does not scale for large-scale data since it has a single step that combines the indexing, comparison, and classification steps.

In summary, the existing mapping-based indexing techniques have two components. The first is to map the records into a metric-space. The second is to perform similarity joins in the metric-space using a tree-like indexing structure.

These methods were developed offline by applying a mapping technique to map all the records into a multidimensional metric-space. The spatial mapping of records acts as a filtering step before the actual record matching. Hence, the focus is on matching similar records without grouping them into blocks. However, none of them handles new records by reusing the properties of an existing multidimensional metric-space. Therefore, query matching is not achievable. In this paper, similar ideas are significantly extended to accommodate the benefits of the Euclidean space for efficient query matching.

Indexing techniques reduce the pairwise comparisons in ER solutions. Many existing mapping-based indexing techniques work in offline mode with fixed-size databases. Hence, these techniques are not suitable for applications that require real-time query matching, especially if it involves big, fast, or streaming data. Our method investigated the query matching problem in ER by using spatial mapping of records into a Euclidean space. We aimed to develop an indexing approach for a fast query process within a short time, returning as many as potential matches. The proposed method proved fast running time as well as scalability along with the data size. The use of vectors in the Euclidean space that represent records allowed fast query matching with comparable accuracy. Many directions are ahead for future work. First, we plan to extend the Em-K indexing method to be parallel. Second, the current Em-K indexing can be extended to other forms of ER problems, such as querying against a dynamic database or iterative ER (Kim and Lee, 2010).