Entity resolution or object matching describes the assignment of di erent objects to each other that describe the same object of the real world. It is used in a variety of technical systems, e.g. systems that fuse di erent data sources. Blocking is used in this context as an approach to reduce the total amount of comparisons by grouping similar objects in the same cluster and dissimilar objects in di erent clusters. As a result only the objects of the same clusters have to be compared to each other. To deal with noise, for instance spelling errors, that can result from di erent heterogeneous data sources, various blocking approaches exist that may add or remove redundancy to the data. In this paper we propose a system that utilizes a derivative of the standard blocking technique to compute correspondences between objects as starting points for a graph matching process. The blocking technique, which usually relies on identity of blocking keys derived from attributes, is modi ed to cope with heterogenous source data with few attributes suitable for matching. A common criticism of standard blocking is low e ciency, since the block sizes are unbalanced with regard to the number of contained entities. We take precautions to keep the e ciency high by reducing the size and amount of large partitions.
H.4 [Information Systems Applications]: Miscellaneous
Merging two di erent relational databases is a di cult task. There are well known research approaches in the area of information integration where mappings between relational schemas are the groundwork before relational schemas can be matched and later fused. Whereas relational databases have to compute expensive joins over relations to gather data that are related, the graph data model is predestined to directly store relational data and process them object-wise. While we have to perform complex operations in relational systems to get the join partners of a speci c tuple, in the graph data model we just have to query the adjacent edges and nodes of a speci c node. Now if we want to use graphs to match entities, we do need some starting points, since testing all possibilities is infeasible.
As an origin we have two relational databases, Discogs1
and Musicbrainz2, which collect and maintain music
metadata from web communities, that we want to fuse into one
database. Both databases are both structurally and
syntactically heterogenous. To overcome this heterogeneity, we have
de ned an integrated schema and have transformed both
databases into this schema. There are, however, actually very
few attributes in the data that are suitable for an
attributebased matching process. For example, the position of a track
on a release or the genre of a release are by no means
suitable: Genres occur frequently and possess only a small
number of distinct values, i.e., a low entropy. And track positions
are not comparable; two tracks are not more similar if the
di erence of the positions is low. Additionally these data
are a icted by noise in the form of spelling mistakes and
modi cations by internal processes. No matter how a later
object matching is implemented, as the focus of the later
object matching could be shifted from attribute-based to
relational similarities[
During initial tests we have looked at di erent solutions
to perform the blocking process directly on the database
system that holds our data. [
To deal with this problem, we have decided to modify the
standard blocking technique, rst presented by Fellegi and
Sunter [
This paper is structured as follows. In the next subsection we provide a brief overview of the various classes of blocking techniques. In section 2 we outline the steps of our envisioned process that takes two input data sources and computes starting points for a graph matching process. We explain our new blocking technique and outline the di erences to the standard blocking and explain our modi cations. Furthermore, we describe the block matching which calculates the correspondences. We show which steps we take to handle noise in the data sources and how we compute block pairs that might be similar and have to be checked in a subsequent graph-matching process; that later process is not part of this paper. In section 3 we describe our experiences with the blocking process. Finally in section 4 we present the conclusions and future work.
Blocking has been introduced as an important preparation
of matching by, e.g., Christen [
The other class, methods manipulating redundancy, i.e.
methods that may decrease or increase the redundancy, can
roughly be separated into three categories of negative
redundancy, neutral redundancy and positive redundancy. An
example for negative redundancy is canopy clustering [
Our proposed method at rst behaves like a redundancypositive method since similar (i.e. candidate) entity pairs may appear in multiple block correspondences, but nally it delivers a redundancy-free blocking since duplicate entity pairs are ltered after the block building process.
As described earlier, we want to compute possible correspondences between nodes of two di erent graphs to initialise a graph-matching process. To achieve this goal we have developed a process that takes data from two sources in the form s1: (id, string), s2: (id, string) that is su cient to describe an entity. In our prototype, that currently works with music metadata, we use the name of artists (together with their local identi er) to approximately identify real world objects in our data sources. Other attributes of artists are not given, but rich contexts of related tracks, labels, releases, etc.
These input data need to be preprocessed since they are a icted by noise, be it human mistakes like spelling errors which result in transposed characters, omitted strings or modi cations by internal processes of the systems 3 that handle the metadata. The string content from an incoming record is split apart at blanks into tokens and the tokens are then processed by applying a stop word list and regular expressions.
Input
Preprocess (Stopwords, RegExp)
Block Building Block Matching
Partition Creation
Pair Filtering
Output
To reduce the number of comparisons needed to compute possible correspondences between both datasets, we use the standard blocking technique. We work with either of two di erent strategies to create blocks from the preprocessed input data. The split-at-blank -approach leaves the tokens apart, which potentially leads to more than one block per entity. Alternatively blanks are eliminated by the merge-atblank -approach, so that the incoming tokens are merged; with this strategy only one block per entity will be created. Of course, created blocks will collect further entities with the same split/merged tokens.
Then we have to match blocks of entities from our two sources. To avoid missing matches due to noise we do not use an exact matching to compute correspondences between blocks. Instead blocks with same or similar labels shall be matched by applying a string similarity measure on the labels of all block pairs. Thus we can additionally apply a 3By system we mean internal rules inside a processing system that a ect the data as they are fed into the information system, processed and stored. variable threshold that can be set appropriately to t the noise of the data sources.
The resulting matches from the block matching are then used to create partitions. Each match is used to build a partition, which clusters the identi ers of similar block labels together according to the computed block matches. Each match is used to build such a partition by carrying two lists that contain the identi ers participating in the block matching.
To reduce redundancy and thus increase e ciency, we apply a pair ltering after the block matching process. If we consider the strategy that splits the entity string at blanks into multiple tokens, it is obvious that an entity can be contained in multiple blocks. Since this applies to both data sources, it is clear that the same entity can participate in more than one candidate pair.
The resulting output is a set of partitions that contain all correspondence pairs of entities that we want to use as starting points for the later graph-matching process. There we will decide which entity pairs really match, in our application mainly by utilizing relational similarities. To save space pairs are implicitly stored; they can be reconstructed by building the local cartesian product between two stored identi er lists, while discarded pairs are stored in a blacklist.
The whole process is depicted in gure 1 and the components of the process are further described in the following. 2.1
The proposed blocking technique bases on the method
presented by Papadakis at al. [
1: a day to remember 2: green day (2) 3: fiddler´s green
In our approach the incoming entities, which consist of
a unique identi er and a string, are initially preprocessed
before being handled by the block building process in order
to reduce the quantity of noise in the data. Opposite to [
As previously described, the strings are rst separated into tokens using blanks as delimiters. A domain-speci c stop word list with common expressions (e.g. the, a or { in the music domain { dj ) is applied and afterwards a set of regular expressions is used to eliminate disturbing su xes like (1), (3), ?. Consequently some tokens will be removed after this step.
In gure 3 (left) the result of the preprocessing can be seen. For the rst entity the stop words a and to have been removed. The entities 2 and 3 were modi ed by regular expressions, removing the numerical su x '(2)' and the apostrophe from entity 3.
day green fiddlers remember day green dayremember
greenday fiddlersgreen
In gure 3 the result of both string handling strategies are depicted. On the left side, the remaining tokens are unchanged for the blocking step. The bene t of this approach is that big mistakes can be compensated as we may get a match by other blocks that contain the same entity. On the other hand this may lead to a large number of blocks; entities which consist of more than one token and spelling mistakes will increase the count even further. Additionally, this approach does not cover cases when blanks were omitted and tokens were mistakenly concatenated in the source data. With the second strategy all tokens of one entity will be collapsed to just one string, which results in just one block. While we are able to handle mistakenly concatenated strings big mistakes cannot be compensated by other blocks but only by signi cantly reducing the required similarity threshold to assume a match.
The result of the block building is shown in gure 4. The rst strategy places the entities 1 and 2 in the same block for the token day and the entities 2 and 3 in the same block for the token green. For the desired matching of two data sources it is not required that similar objects of the same source are actually placed in the same block, since a deduplication is usually presumed beforehand.
Each block has a label that indicates the token it originated from and a list of identi ers from entities that contain the token. These labels are used in the block matching, but are irrelevant after the block matching is performed. 2.2
After the block building we have to apply a matching between the block sets of both data sources to compute the possible correspondences between entities from both data sources. Since the sources are di erent we have to handle syntactical heterogeneity, in other words noise. Therefore we must not use exact matching to determine correspondences between blocks from both sources. Because the block labels are stored as strings, we use the Jaro-Winkler string similarity to measure the similarity of block labels, and we need a threshold to determine whether two blocks represent possible entity correspondences or not.
To compute the matching, we have to compare the block labels of both block sets. Comparing them to each other is computationally very expensive, so we choose to sort the blocking labels in alphabetical order and apply a sliding window approach to reduce the number of comparisons. We hereby rely on the assumption that spelling mistakes are more likely to appear in the end part of a word. Then a spelling error will not much a ect the sorting position.
Let us assume that the block building has been applied on datasets similar to gure 2, using the split at blank -strategy. The built blocks for both data sources are depicted in gure 5. Arrows represent the correspondences between the blocks. The blocks on the left side have resulted from the following artist names: 1) A Day To Remebmer, 2) Green Day and 3) Fiddler's Green; we have noise in the form of two transposed characters in the token remebmer (b $ m). On the right side, the blocks are built from the artist names 5) The O spring, 3) Grene Day, 7) A Day To Remember and 2) Fideler's Green; here we have more noise.
remebmer: {1}
If we take the example in gure 5 and assume exact matching, two block matches (day and green) are considered which would cover a few entity match candidates, like 1 7 (A Day To Remebmer, A Day to Remember ) or 2 3 (Green Day, Grene Day).
In contrast, gure 6 depicts the results for a non-exact matching of the block labels, using the Jaro-Winkler distance; similarities with a threshold of 0:9 or above are considered a block match. With this approach we get an entity match candidate for the artist Fiddler's Green, as both tokens have matching partners on each side ( ddlers and
As can be seen in gure 7, the partitions are built according to the block matchings from gure 6. Partition 3, e.g. emerges from the matching of the blocks labeled green and grene. The identi ers are taken from the blocks and added to the identi er lists of the partition. Please note that we do not actually store all pairs to save space; instead we carry two lists along, each containing the identi ers from one source and reconstruct the pairs later.
Additionally two inverse indexes are created alongside creating the partitions ( gure 8). The index on each source tells delers, green and grene). With a threshold of 0:9, the artist The O spring does not match with anything, as there is no tting partner in the left side. Arguably this can change if we would lower the threshold strongly. In this example though, the threshold is low enough to discover all reasonable matchings, but high enough to avoid unreasonable matches. 2.3
For further computation, we utilize the existing block correspondences as partitions for our later entity matching. Thus we can load the data from all entities that are contained in both blocks in one in-memory step. The partitions consist of two separate lists that each contains the identi ers that are stored in a block. As aforementioned, each partition also will have a blacklist introduced in the next subsection. partition 2 partition 3 partition 1 s1-ids 1 s2-ids
7 blacklist
∅ partition 4 s1-ids 3 s2-ids
2 blacklist ∅ s1-ids 1 2 s2-ids 3 7 blacklist ¬(1 , 7) partition 5 s1-ids 3 s2-ids
2 blacklist ¬(3 , 2) s1-ids 2 3 s2-ids
3 blacklist ¬(2 , 3) 1 : p1; p2 2 : p2; p3 3 : p3; p4; p5 for each identi er in which partitions it is contained. These indexes will be used in the next step, the pair ltering. 2.4
Once the partitions are built, we apply a lter to eliminate redundant pairs across the generated partitions. To achieve this, we utilize the inverse indexes that were created in the partition building step and a temporary blacklist, to avoid testing pairs for duplicates more than once. For each partition, we reconstruct all possible pairs using the cartesian product. For each pair, if it is not already contained in the blacklist, we compose two sets by gathering the occurrences in partitions by looking up the inverse indexes. Next, we calculate the intersection of both sets, i.e., all partitions that contain the current pair. We will add the pair to the temporary blacklist and add the pair to the blacklists of all partitions but the rst.
The blacklist is later used when the pairs have to be reconstructed using the in-memory cartesian product; blacklisted pairs will be rejected during the reconstruction process.
We can see that three duplicate pairs exist across all ve partitions: the pair (1; 7) exists in partitions 1 and 2 and the pair (2; 3) exists in partitions 2 and 3 and the pair (3; 2) exists in partitions 4 and 5. Accordingly the pair (1; 7) is added to the blacklist of partition 2, the pair (2; 3) is added to the blacklist of partition 3 and the pair (3; 2) is added to the blacklist of partition 5. Thereby partition 5 is empty and can consequently be removed.
The partitions, as depicted in gure 7, represent the output of our process and contain the correspondences that we use to initialise a matching process across two graphs representing our data source.
The blocking technique presented was successfully applied
in a project at our institute, namely in the master thesis of
Kroll [
In our experiments we examined the e ectiveness of our pair ltering approach. Table 1 and 2 show the results for both implemented strategies. The aim of these experiments was to investigate the bene t of pair ltering concerning the amount of detected duplicates. For measurement we counted the number of pairs immediately before and after applying the duplicate ltering. All experiments where conducted on a 3.4 GHZ quad-core CPU with 32 Gigabytes of main memory running Linux 4.15 (Debian) and using Java 8u162. sim In table 1 the results for pair ltering utilizing the split-atblank strategy with various similarities are depicted. With a decreasing similarity threshold we can see that the number of pairs to test increases; yet the amount of duplicates is initially small and does not grow jointly with the number of pairs to be tested for possible duplicates.
When applying the merge-at-blank strategy it is obvious that the number of pairs to test is dramatically lower than with the split-at-blank strategy. Then we can see that the required runtimes for pair ltering are signi cantly lower than the corresponding runtimes for the split-at-blank strategy, due to the lower pair count. With regards to the amount of duplicates detected by the pair ltering, the results for the merge-at-blank strategy in table 2 are similarly underwhelming. In this case, pair ltering yields less than one percent reduction concerning the total amount of pairs.
sim Obviously the chosen attributes, the artist names, of the selected datasets have a high entropy, thus the e ect of a post-processing that applies a pair ltering step to eliminate duplicate pairs is ine ective, as the e ort spent for the postprocessing bears no proportion to the savings. Especially for the split-at-blank strategy the increasing runtime with a lowered similarity threshold gets disproportionate. 4.
In this paper we have presented a new blocking method as part of a process that allows the computation of starting points for the initialisation of a graph matching process. We took steps to adapt the standard blocking technique to datasets that have few attributes that are suitable for a matching. We also addressed the disadvantages of standard blocking by introducing stop word lists and regular expressions to reduce the size and amount of overly large blocks.
Kroll[
Additional steps have to be taken for the evaluation of two core elements of our block matching step, the e ect of the used similarity function and the optimal size of the sliding window. Concerning the result quality we want to explore our blocking technique with alternatives to the Jaro-Winkler distance and varying sizes of the sliding window and their rami cations on the quality. 5.