Entity resolution is the task of identifying equivalent real-world entities across diferent sources. We found that standard methods based on unsupervised learning are slow during the resolution step. Thus, we propose an alternative approach with mock labels. Mock labels are sets of strings that ideally represent real-world entities. Using a running example, we show how to create mock labels from the training data and use them in the resolution step to match real-world entities eficiently. We applied this approach in the SIGMOD 2020 Programming Contest and achieved significantly faster execution times in the resolution step compared to other top ranked teams. Since all the top ranked teams had the same F-measure, the execution speed of the resolution step was decisive.
• Information systems → Entity resolution.
Entity resolution is a problem that occurs in data integration, data
cleansing, web search, and e-commerce search scenarios [
There are basically two types of entity resolution, namely Pair-wise Entity Resolution, and Group-Wise Entity Resolution.
Definition 1.1 (Pair-wise Entity Resolution). Given a set of objects , the output is a set of pairs {(, ) | , ∈ , and refer to the same real-world entity}.
Definition 1.2 (Group-wise Entity Resolution). Given a set of objects , the output is a family of sets { | all objects in refer to the same real-world entity} where ∩ = ∅if ≠ .
Pairwise Entity Resolution approaches often use similarity or
distance functions for determining whether two objects refer to the
same real-world entity. Group-wise Entity Resolution approaches
additionally use clustering techniques for assigning an object to a
group or cluster. The results of these two types of entity resolution
are not always consistent [
The challenge of the SIGMOD 2020 Programming Contest was to design an entity resolution system for cameras. The input data consisted of about 30,000 e-commerce websites. Each website was provided as a JSON formatted file that specified a real-world product ofer. Not every website contained a single valid camera. Camera accessories such as bags or zoom lenses, TVs, and entire camera bundles were also part of the dataset. Also, the product descriptions in the JSON files were inconsistent (varying attribute names, diferent semantics and syntax). Only the page title attribute was always present. See Figure 1 for an example of a JSON formatted website that represents a specific camera. { } "<page title>": "Canon PowerShot SX 500IS | eBay", "brand": "Canon", "manufacturer warranty": "No", "megapixels": "16.0 MP", "model": "SX500IS", "optical zoom": "30x"
The task was to find as many identical camera pairs as possible
among all e-commerce websites (Pair-wise Entity Resolution). A
valid submission consisted of a CSV file containing only the
matching camera pairs found during the resolution step. The Submissions
were ranked based on the F-measure [
The rest of this paper is organized as follows. Throughout the paper we use a running example. In Section 2 we describe the training step of our approach. We show that by preprocessing the training data and using additional information about synonymous camera names from the web, it is possible to create mock camera labels that roughly represent the real-world camera entities. In Section 3 we describe our resolution step, that is, how we match the contents of the JSON ifles with the generated mock labels. To speed up the execution time, we use sorted integer sets for the mock labels and the realworld camera descriptions. Furthermore, we give recommendations on how to speed up the cleansing of input data. In Section 4 we evaluate our solution. Finally, in Section 5 we conclude this paper with a discussion of the features and limitations of our approach. 2
Our approach is based on a concept we call mock labels. We call them mock labels because they are not real identifiers, but only sets of semi-automatically generated keywords. They may or may not represent a real-world entity. For the sake of simplicity, we also refer to mock labels in the text as labels. For creating mock camera labels, we use clean websites from the training data which give rise to about 950 labels. These labels are simply extracted from the corresponding page titles by using stop words. We also use information about synonymous camera names from Wikipedia which creates another 50 labels. Additionally, we combine the attributes brand and model from provided eBay websites to create roughly another 1800 labels. In Figure 2 we summarize our approach by constructing mock camera labels for the running example. 3
In the training step described in the previous section we generated mock camera labels. In this section we describe the resolution step of our implementation, that is, how we match these labels with textual descriptions of real-world cameras. Our resolution step is subdivided into four parts: • First, we convert the mock camera labels to an eficient internal representation (Section 3.1). • Second, we create simplified mock labels that allow us to match even incomplete camera descriptions (Section 3.2). • Third, we extract camera descriptions from the JSON files and preprocess them eficiently (Section 3.3). • Finally, we match the camera mock labels with the extracted camera descriptions (Section 3.4). 3.1
Internally, we represent a mock label as a sorted integer set. Representing mock labels as sorted sequences of integers enables us to Input 1. clean page titles (stop words: -, kit, /) Canon IXUS 750 - . . . - Canon Europe Canon EOS 7D kit . . . - ShopMania Canon EOS 7D Mark II / . . . - Australia Canon EOS 7D Mark III / . . . - Australia 2. synonymous camera names (Wikipedia) canon ixus 75 == canon powershot sd750 3. brand + model attributes (eBay websites) "brand": "Nikon", "model": "D7000" Output labels.txt canon eos 7d canon eos 7d mark ii canon eos 7d mark iii canon powershot sd750, canon ixus 75 nikon d7000 compute matchings in Section 3.4 with real-world camera descriptions faster than it would be possible using only strings. In Figure 3 we convert the mock labels from Figure 2 to sorted integer sets. ID camera label 0 canon eos 7d 1 canon eos 7d mark ii 2 canon eos 7d mark iii 3 canon powershot sd750 3 canon ixus 75 4 nikon d7000 It is not always possible to create a match with a camera label because some tokens may be missing in real-world camera descriptions. We consider tokens that do not represent the camera brand and alphanumeric model information as non-critical for the resolution step. Therefore, we create a second set of camera labels without these specific tokens (see Figure 4). We use the simplified camera labels in cases where the original camera labels fail to create a match. ID simpli ed camera label 0 canon eos 7d 1 canon eos 7d mark ii 2 canon eos 7d mark iii 3 canon powershot sd750 removed tokens: eos, powershot
Reading the input data from SSD and cleansing takes up a
considerable part of the overall running time of the resolution step. The
following findings are important to speed up preprocessing of the
input data:
• Reading many small files concurrently, with multiple threads
(compared to a single thread), takes advantage of the internal
parallelism of SSDs and thus leads to higher throughput [
To achieve fast preprocessing of the input data, we use 16 threads to read the JSON files from SSD and clean the page titles. We perform string operations in-place with C library functions, and hardcode our regex expressions. The result of our preprocessing step are sorted integer sets that represent the page titles (see Figure 5).
After converting the page titles into sorted integer sets, we try to assign unique camera IDs to them. First, we try to match labels from the original camera labels with the page title. If we do not find a match, we try to match the simplified labels with the page title. We consider labels as matches if all the corresponding keywords are also part of the title. If we can match more than one label with the title, then we remove all labels that are subsets of other labels. This allows us, for example, to distinguish between the cameras canon eos 7d and canon eos 7d mark ii, because the first camera description json json json json . . .
json 1. extract page titles from json files a New Canon Camera EOS 7-D for sale b 10 month old Cannon 7d (Mark II) digital camera, good condition c digi cam Nixon d-7000 Full-HD-Video, 16 Mega-pixel d digital Camera Power-shot SD-750IS from Canon 3x Zoom (IXUS 75) e Camera bundle Canon EOS 7d Mark II and Mark III for $840
2. clean page titles (in-place, hardcoded regex expressions) a new canon camera eos 7d for sale b 10 month old canon 7d mark ii digital camera good condition c digi cam nikon d7000 fullhdvideo 16 megapixel d digital camera powershot sd750 from canon 3x zoom ixus 75 e camera bundle canon eos 7d mark ii and mark iii for 840
3. convert cleaned page titles to sorted integer sets a 0, 1, 2 b 0, 2, 3, 4 c 10, 11 d 0, 6, 7, 8, 9 e 0, 1, 2, 3, 4, 5 is a subset of the second. If the remaining labels have the same camera ID, then we can clearly assign a camera ID to a page title. Figure 6 shows our approach for assigning unique camera IDs to page titles for the running example.
To avoid iterating over all camera labels when searching for matches with the page title, we store all camera labels in a sorted vector. We iterate only over relevant ranges in the vector. To look up the relevant ranges, we index the initial keywords of the labels. For even faster matching of camera labels with the page title, we recommend storing the camera labels in a sorted trie data structure, as shown in Figure 7. Finding all labels that match a page title, is then a matter of traversing the trie and comparing integer tokens. In real-world camera descriptions it can happen that the tokens of a label are scattered in the page title. The following traversing strategy finds these scattered labels in the page title: If there is no successor in a trie node for the current token in the page title, then ignore the token and continue with the next token in the page title. camera labels
simplified camera labels 2
Our approach is related to Group-wise Entity Resolution. In the training step we semi-automatically construct mock labels that can be understood as centroids of clusters. Ideally, each label represents one real-world entity. In the contest solution we have also labels that represent several real-world entities, or no real-world entity at all. In the resolution step we try to assign each real-world camera description to one cluster with set operations on sorted integer sets. After assigning all camera descriptions to clusters, we compute the Cartesian product of the cameras in each cluster and store the unique pairs of identical cameras in a CSV file.
The quality of the results of our resolution step depends mainly on the labels generated in the training step. With the 2800 semiautomatically generated mock labels we achieved on the hidden evaluation dataset an F-measure of 0.97. To achieve an F-measure of 0.99, we manually added about 200 contest specific labels to the semi-automatically generated ones. We extracted these additional labels by inspecting page titles that did not match with any semiautomatically generated labels. Since all five best placed teams reached an F-measure of 0.99, the running time of the resolution step was decisive. We were chosen as the overall winner. Table 1 shows also the running times of the resolution step of the five best placed teams. 5
In this paper we presented our entity resolution approach, that we submitted in the SIGMOD 2020 Programming Contest. Our approach is based on mock labels that we generate in a training step and a fast matching algorithm that computes set intersections on sorted integer sets in the resolution step. Our matching algorithm knows nothing about the actual labels. The creation of labels in the training step and the matching of camera descriptions with the labels in the resolution step are decoupled. In contrast, rule-based approaches, in which the rules for clustering are hardcoded into the source code, are rigid and must be written from scratch for new entity resolution tasks. But, there are also limitations of our approach. For the matching we use set operations on integer tokens. One integer token represents one word. If entities can only be distinguished by word order, then our approach needs to be adapted. By allowing n-grams as tokens in the labels and not just individual words, it is possible to integrate word order semantics into our approach. Syntactic variations in the data can also be challenging in our resolution step. In the contest we solved this problem by preprocessing the input data by hardcoded regex expressions and in-place string operations. A more general approach would be to use distance metrics for deciding which tokens are present in realworld descriptions. Still, the biggest challenge remains, namely to generate representative labels from the data. If the training data is unstructured or incomplete, it may be impossible to extract representative labels for the resolution step. In the Programming Contest, the training data was fairly well-structured and complete, that is, the generation of mock labels was mainly a semi-automatic extraction task. This again shows that it is important to look at the data ifrst before deciding on an approach.
This work has been supported by the German Research Foundation (DFG) grant GI-711/5-1 within the Priority Program 1736 Algorithms for Big Data.