L14pt Num[arabic] Sym[fnsymbol] [2]

$#2$

#  FlashProfile: A Framework for Synthesizing Data Profiles

Saswat Padhi  0000-0001-6865-4359 Dept. of Computer ScienceUniversity of
California – Los AngelesCA90095USA<EMAIL_ADDRESS>,  Prateek Jain
Microsoft ResearchBangaloreIndia<EMAIL_ADDRESS>,  Daniel Perelman
Microsoft CorporationRedmondWA98052USA<EMAIL_ADDRESS>,  Oleksandr
Polozov  0000-0003-3669-4262 Microsoft ResearchRedmondWA98052USA
<EMAIL_ADDRESS>,  Sumit Gulwani  Microsoft CorporationRedmondWA98052USA
<EMAIL_ADDRESS>and  Todd Millstein  Dept. of Computer ScienceUniversity
of California – Los AngelesCA90095USA<EMAIL_ADDRESS>
(2018)

###### Abstract.

We address the problem of learning a syntactic _profile_ for a collection of
strings, i.e. a set of regex-like patterns that succinctly describe the
syntactic variations in the strings. Real-world datasets, typically curated
from multiple sources, often contain data in various syntactic formats. Thus,
any data processing task is preceded by the critical step of data format
identification. However, manual inspection of data to identify the different
formats is infeasible in standard big-data scenarios.

Prior techniques are restricted to a small set of pre-defined patterns (e.g.
digits, letters, words, etc.), and provide no control over granularity of
profiles. We define syntactic profiling as a problem of clustering strings
based on _syntactic similarity_ , followed by identifying patterns that
succinctly describe each cluster. We present a technique for synthesizing such
profiles over a given language of patterns, that also allows for interactive
refinement by requesting a desired number of clusters.

Using a state-of-the-art inductive synthesis framework, PROSE, we have
implemented our technique as FlashProfile. Across $153$ tasks over $75$ large
real datasets, we observe a median profiling time of only $\sim$0.7 s.
Furthermore, we show that access to syntactic profiles may allow for more
accurate synthesis of programs, i.e. using fewer examples, in programming-by-
example (PBE) workflows such as Flash Fill.

data profiling, pattern profiles, outlier detection, hierarchical clustering,
pattern learning, program synthesis

††copyright: rightsretained††doi: 10.1145/3276520††journalyear: 2018††journal:
PACMPL††journalvolume: 2††journalnumber: OOPSLA††article:
150††publicationmonth: 11††ccs: Information systems Clustering and
classification††ccs: Information systems Summarization††ccs: Software and its
engineering Programming by example††ccs: Software and its engineering Domain
specific languages††ccs: Computing methodologies Anomaly detection

##  1\. Introduction

In modern data science, most real-life datasets lack high-quality metadata —
they are often incomplete, erroneous, and unstructured (Dong and Srivastava,
2013). This severely impedes data analysis, even for domain experts. For
instance, a merely preliminary task of _data wrangling_ (importing, cleaning,
and reshaping data) consumes 50 – 80% of the total analysis time (Lohr, 2014).
Prior studies show that high-quality metadata not only help users clean,
understand, transform, and reason over data, but also enable advanced
applications, such as compression, indexing, query optimization, and schema
matching (Abedjan et al., 2015). Traditionally, data scientists engage in
_data gazing_ (Maydanchik, 2007) — they manually inspect small samples of
data, or experiment with aggregation queries to get a bird’s-eye view of the
data. Naturally, this approach does not scale to modern large-scale datasets
(Abedjan et al., 2015).

_Data profiling_ is the process of generating small but useful metadata
(typically as a succinct summary) for the data (Abedjan et al., 2015). In this
work, we focus on syntactic profiling, i.e. learning structural patterns that
summarize the data. A syntactic profile is a disjunction of regex-like
patterns that describe all of the syntactic variations in the data. Each
pattern succinctly describes a specific variation, and is defined by a
sequence of _atomic patterns_ or _atoms_ , such as digits or letters.

While existing tools, such as Microsoft SQL Server Data Tools (SSDT)
(Microsoft, 2017c), and Ataccama One (Ataccama, 2017) allow pattern-based
profiling, they generate a single profile that cannot be customized. In
particular,  (1) they use a small predetermined set of atoms, and do not allow
users to supply custom atoms specific to their domains, and  (2) they provide
little support for controlling granularity, i.e. the number of patterns in the
profile.

We present a novel application of program synthesis techniques to addresses
these two key issues. Our implementation, FlashProfile, supports custom user-
defined atoms that may encapsulate arbitrary pattern-matching logic, and also
allows users to interactively control the granularity of generated profiles,
by providing desired bounds on the number of patterns.

#### A Motivating Example

Figure 2(a) shows a fragment of a dataset containing a set of references in
various formats, and its profiles generated by Ataccama One (in fig. 2(c)),
Microsoft SSDT (in fig. 2(c)), and our tool FlashProfile (in fig. 2(d)).
Syntactic profiles expose rare variations that are hard to notice by manual
inspection of the data, or from simple statistical properties such as
distribution of string lengths. For example, Ataccama One reveals a suspicious
pattern “W_W”, which matches less than 0.5% of the dataset. SSDT, however,
groups this together with other less frequent patterns into a “.*” pattern.
Since SSDT does not provide a way of controlling the granularity of the
profile, a user would be unable to further refine the “.*” pattern.
FlashProfile shows that this pattern actually corresponds to missing entries,
which read “not_available”.

Reference ID
---
ISBN: ␣ 1-158-23466-X
not_available
doi: ␣ 10.1016/S1387- 7003(03)00113-8
$\vdots$
PMC9473786
ISBN: ␣ 0-006-08903-1
doi: ␣ ␣
10.13039/100005795
PMC9035311
$\vdots$
PMC5079771
ISBN: ␣ 2-287-34069-6
(a) Sample data

0pt
0pt

  * $\cdot$

W_W (5)

  * $\cdot$

W: N.N/LN-N(N)N-D (11)

  * $\cdot$

W: D-N-N-L (34)

  * $\cdot$

W: N.N/N (110)

  * $\cdot$

W: D-N-N-D (267)

  * $\cdot$

WN (1024)

Classes: [L]etter, [W]ord, [D]igit, [N]umber

(b) Profile from Ataccama One

  * $\cdot$

doi: ␣ +10\\.\d\d\d\d\d/\d+ (110)

  * $\cdot$

.* (113)

  * $\cdot$

ISBN: ␣  0-\d\d\d-\d\d\d\d\d-\d (204)

  * $\cdot$

PMC\d+ (1024)

(c) Profile from Microsoft SSDT

  * $\cdot$

“not_available” (5)

  * $\cdot$

$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{doi:}''}}\;\,\textsf{\\!{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\,\textvisiblespace\,}\\!}\,^{+}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{10.1016/}''}}\;\texttt{U}\;\texttt{D}^{\,4}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\;\texttt{D}^{\,4}\;$
$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{(}''}}\;\texttt{D}^{\,2}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{)}''}}\;\texttt{D}^{\,5}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\;\texttt{D}$
(11)

  * $\cdot$

$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{ISBN:}''}}\;\,\textsf{\\!{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\,\textvisiblespace\,}\\!}\,\;\texttt{D}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\;\texttt{D}^{\,3}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\;\texttt{D}^{\,5}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color<EMAIL_ADDRESS>(34)

  * $\cdot$

$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{doi:}''}}\;\,\textsf{\\!{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\,\textvisiblespace\,}\\!}\,^{+}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{10.13039/}''}}\;\texttt{D}^{+}$
(110)

  * $\cdot$

$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{ISBN:}''}}\;\,\textsf{\\!{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\,\textvisiblespace\,}\\!}\,\;\texttt{D}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\;\texttt{D}^{\,3}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\;\texttt{D}^{\,5}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\;\texttt{D}$
(267)

  * $\cdot$

$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{PMC}''}}\;\texttt{D}^{\,7}$
(1024)

Classes: [U]ppercase, [D]igit

Superscripts indicate repetition of atoms.
Constant strings are surrounded by quotes.

(d) Default profile from FlashProfile

Figure 2. Profiles for a set of references— number of matches for each pattern
is shown on the right

The full dataset is available at
https://github.com/SaswatPadhi/FlashProfileDemo/tree/master/motivating_example.json.

For this dataset, although Ataccama One suggests a profile of the same
granularity as from FlashProfile, the patterns in the profile are too coarse
to be immediately useful. For instance, it may not be immediately obvious that
the pattern W: D-N-N-L maps to ISBNs in the dataset. FlashProfile further
qualifies the W (word) to the constant “ISBN”, and restricts the [N]umber
patterns to $\texttt{D}^{\,3}$ (short for ${\textsf{Digit}}^{\times 3}$) and
$\texttt{D}^{\,5}$, and the final [L]etter to the constant “X”.

  * $\cdot$

“not_available” (5)

  * $\cdot$

$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{doi:}''}}\;\,\textsf{\\!{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\,\textvisiblespace\,}\\!}\,^{+}\;\langle\textsf{DOI}\rangle$
(121)

  * $\cdot$

$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{ISBN:}''}}\;\,\textsf{\\!{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\,\textvisiblespace\,}\\!}\,\;\langle\textsf{ISBN10}\rangle$
(301)

  * $\cdot$

$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{PMC}''}}\;\texttt{D}^{\,7}$
(1024)

(a) Auto-suggested profile from FlashProfile

  * $\cdot$

“not_available” (5)

  * $\cdot$

$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{doi:}''}}\;\,\textsf{\\!{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\,\textvisiblespace\,}\\!}\,^{+}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{10.1016/}''}}\;\texttt{U}\;\texttt{D}^{\,4}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\;\texttt{D}^{\,4}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{(}''}}\;\texttt{D}^{\,2}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{)}''}}\;\texttt{D}^{\,5}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\;\texttt{D}$
(11)

  * $\cdot$

$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{doi:}''}}\;\,\textsf{\\!{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\,\textvisiblespace\,}\\!}\,^{+}\;\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{10.13039/}''}}\;\texttt{D}^{+}$
(110)

  * $\cdot$

$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{ISBN:}''}}\;\,\textsf{\\!{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\,\textvisiblespace\,}\\!}\,\;\langle\textsf{ISBN10}\rangle$
(301)

  * $\cdot$

$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{PMC}''}}\;\texttt{D}^{\,7}$
(1024)

(b) A refined profile on requesting 5 patterns

Figure 3. Custom atoms,1 and refinement of profiles

FlashProfile also allows users familiar with their domains to define custom
patterns, that cluster data in ways that are specific to the domain. For
example, the two patterns for “doi” in fig. 2(d) are vastly different — one
contains letters and parentheses, whereas the other contains only digits.
However, grouping them together makes the profile more readable, and helps
spot outliers differing from the expected patterns. Figure 3(a) shows a
profile suggested by FlashProfile when provided with two custom atoms:
$\langle\textsf{DOI}\rangle$ and $\langle\textsf{ISBN10}\rangle$,
$\langle\textsf{DOI}\rangle$ is defined as the regex
10.\d{4,9}/[-._;()/:A-Z0-9a-z]+.
$\langle\textsf{ISBN10}\rangle$ is defined as the regex
\d-\d{3}-\d{5}-[0-9Xx]. with appropriate costs. Users may refine the profile
to observe more specific variations within the DOIs and ISBNs. On requesting
one more pattern, FlashProfile unfolds $\langle\textsf{DOI}\rangle$, since the
DOIs are _more dissimilar_ to each other than ISBNs, and produces the profile
shown in Figure 3(b).

#### Key Challenges

A key barrier to allowing custom atoms is the large search space for the
desirable profiles. Prior tools restrict their atoms to letters and digits,
followed by simple upgrades such as sequences of digits to numbers, and
letters to words. However, this simplistic approach is not effective in the
presence of several overlapping atoms and complex pattern-matching semantics.
Moreover, a naïve exhaustive search over all profiles is prohibitively
expensive. Every substring might be generalized in multiple ways into
different atoms, and the search space grows exponentially when composing
patterns as sequences of atoms, and a profile as a disjunction of patterns.

One approach to classifying strings into matching patterns might be to
construct decision trees or random forests (Breiman, 2001) with features based
on atoms. However features are typically defined as predicates over entire
strings, whereas atoms match specific substrings and may match multiple times
within a string. Moreover, the location of an atomic match within a string
depends on the lengths of the preceding atomic matches within that string.
Therefore, this approach seems intractable since generating features based on
atoms leads to an exponential blow up.

Instead, we propose to address the challenge of learning a profile by first
_clustering_ (Xu and Wunsch II, 2005) — partitioning the dataset into
_syntactically similar_ clusters of strings and then learning a succinct
pattern describing each cluster. This approach poses two key challenges:  (1)
efficiently learning patterns for a given cluster of strings over an arbitrary
set of atomic patterns provided by the user, and  (2) defining a suitable
notion of _pattern-based similarity_ for clustering, that is aware of the
user-specified atoms  . For instance, as we show in the motivating example
(Fig. 2 and Fig. 3), the clustering must be sensitive to the presence of
$\langle\textsf{DOI}\rangle$ and $\langle\textsf{ISBN10}\rangle$ atoms.
Traditional character-based similarity measures over strings (Gomaa and Fahmy,
2013) are ineffective for imposing a clustering that is susceptible to high-
quality explanations using a given set of atoms.

#### Our Technique

We address both the aforementioned challenges by leveraging recent advances in
_inductive program synthesis_ (Gulwani et al., 2017) — an approach for
learning programs from incomplete specifications, such as input-output
examples for the desired program.

First, to address challenge (1), we present a novel domain-specific language
(DSL) for patterns, and define a specification over a given set of strings.
Our DSL provides constructs that allow users to easily augment it with new
atoms. We then give an efficient synthesis procedure for learning patterns
that are consistent with the specification, and a cost function to select
compact patterns that are not overly general, out of all patterns that are
consistent with a given cluster of strings.

Second, we observe that the cost function for patterns induces a natural
_syntactic dissimilarity measure_ over strings, which is the key to addressing
challenge (2). We consider two strings to be similar if both can be described
by a low-cost pattern. Strings requiring overly general / complex patterns are
considered dissimilar. Typical clustering algorithms require computation of
all pairwise dissimilarities (Xu and Wunsch II, 2005). However, in contrast to
standard clustering scenarios, computing dissimilarity for a pair of strings
not only gives us a numeric measure, but also a pattern for them. That this
allows for practical performance optimizations. In particular, we present a
strategy to approximate dissimilarity computations using a small set of
carefully sampled patterns.

Approximation Parameters Custom Atoms with Costs Number of Patterns Pattern
Learner + Cost Function Hierarchical Clustering ProfileDataset

Figure 4. FlashProfile’s interaction model: dashed edges denote internal
communication, and thin edges denote optional parameters to the system.

To summarize, we present a framework for syntactic profiling based on
clustering, that is parameterized by a pattern learner and a cost function.
Fig. 4 outlines our interaction model. In the default mode, users simply
provide their dataset. Additionally, they may control the performance _vs._
accuracy trade-off, define custom atoms, and provide bounds on the number of
patterns. To enable efficient refinement of profiles based on the given
bounds, we construct a _hierarchical clustering_ (Xu and Wunsch II, 2005,
Section IIB) that may be _cut_ at a suitable height to extract the desired
number of clusters.

#### Evaluation

We have implemented our technique as FlashProfile using PROSE (Microsoft,
2017d), also called FlashMeta (Polozov and Gulwani, 2015), a state-of-the-art
inductive synthesis framework. We evaluate our technique on 75 publicly-
available datasets collected from online sources. All public datasets are
available at:
https://github.com/SaswatPadhi/FlashProfileDemo/tree/master/tests. Over 153
tasks, FlashProfile achieves a median profiling time of 0.7s, 77% of which
complete in under 2s. We show a thorough analysis of our optimizations, and a
comparison with state-of-the-art tools.

#### Applications in PBE Systems

The benefits of syntactic profiles extend beyond data understanding. An
emerging technology, programming by examples (PBE) (Lieberman, 2001; Gulwani
et al., 2017), provides end users with powerful semi-automated alternatives to
manual data wrangling. For instance, they may use a tool like Flash Fill
(Gulwani, 2011), a popular PBE system for data transformations within
Microsoft Excel and Azure ML Workbench (Microsoft, 2017b, a). However, a key
challenge to the success of PBE is finding a representative set of examples
that best discriminates the desired program from a large space of possible
programs (Mayer et al., 2015). Typically users provide the desired outputs
over the first few entries, and Flash Fill then synthesizes the _simplest
generalization_ over them. However, this often results in incorrect programs,
if the first few entries are not representative of the various formats present
in the entire dataset (Mayer et al., 2015).

Instead, a syntactic profile can be used to select a representative set of
examples from syntactically dissimilar clusters. We tested 163 scenarios where
Flash Fill requires more than one input-output example to learn the desired
transformation. In 80% of them, the examples belong to different syntactic
clusters identified by FlashProfile. Moreover, we show that a _profile-guided
interaction model_ for Flash Fill, which we detail in § 6, is able to
complete 86% of these tasks requiring the _minimum_ number of examples.
Instead of the user having to select a representative set of examples, our
dissimilarity measure allows for proactively requesting the user to provide
the desired output on an entry that is _most discrepant_ with respect to those
previously provided.

In summary, we make the following major contributions:

  * ( § 2 )

We formally define syntactic profiling as a problem of clustering of strings,
followed by learning a succinct pattern for each cluster.

  * ( § 3 )

We show a hierarchical clustering technique that uses pattern learning to
measure dissimilarity of strings, and give performance optimizations that
further exploit the learned patterns.

  * ( § 4 )

We present a novel DSL for patterns, and give an efficient synthesis procedure
with a cost function for selecting desirable patterns.

  * ( § 5 )

We evaluate FlashProfile’s performance and accuracy on large real-life
datasets, and provide a detailed comparison with state-of-the-art tools.

  * ( § 6 )

We present a profile-guided interaction model for Flash Fill, and show that
data profiles may aid PBE systems by identifying a representative set of
inputs.

##  2\. Overview

Henceforth, the term _dataset_ denotes a set of strings. We formally define a
syntactic profile as:

###### Definition 2.1.

Syntactic Profile — Given a dataset $\mathcal{S}$ and a desired number $k$ of
patterns, syntactic profiling involves learning  (1) a partitioning
$\mathcal{S}_{1}\sqcup\ldots\sqcup\mathcal{S}_{k}=\mathcal{S}$, and  (2) a set
of patterns $\\{P_{1},\ldots,P_{k}\\}$, where each $P_{i}$ is an expression
that describes the strings in $\mathcal{S}_{i}$.  We call the disjunction of
these patterns $\widetilde{P}=P_{1}\vee\ldots\vee P_{k}$ a _syntactic profile_
of $\mathcal{S}$, which describes all the strings in $\mathcal{S}$.

The goal of syntactic profiling is to learn a set of patterns that summarize a
given dataset, but is neither too specific nor too general (to be practically
useful). For example, the dataset itself is a trivial overly specific profile,
whereas the regex “.*” is an overly general one. We propose a technique that
leverages the following two key subcomponents to generate and rank profiles:
We denote the universe of all strings as $\mathbb{S}$, the set of non-negative
reals as
$\mathbb{R}_{\leavevmode\resizebox{}{3.84009pt}{$\,\kern-0.70004pt\geq\\!0$}}$,
and the power set of a set $X$ as $2^{X}$.

  * •

a pattern learner $\mathcal{L}\colon 2\,^{\mathbb{S}}\to 2\,^{\mathscr{L}}$,
which generates a set of patterns over an arbitrary pattern language
$\mathscr{L}$, that are consistent with a given dataset.

  * •

a cost function
$\mathcal{C}\colon\mathscr{L}\,\times\,2\,^{\mathbb{S}}\to\mathbb{R}_{\leavevmode\resizebox{}{3.84009pt}{$\,\kern-0.70004pt\geq\\!0$}}$,
which quantifies the suitability of an arbitrary pattern (in the same language
$\mathscr{L}$) with respect to the given dataset.

Using $\mathcal{L}$ and $\mathcal{C}$, we can quantify the suitability of
clustering a set of strings together. More specifically, we can define a
minimization objective $\mathcal{O}\colon
2\,^{\mathbb{S}}\to\mathbb{R}_{\leavevmode\resizebox{}{3.84009pt}{$\,\kern-0.70004pt\geq\\!0$}}$
that indicates an aggregate cost of a cluster. We can now define an _optimal
syntactic profile_ that minimizes $\mathcal{O}$ over a given dataset
$\mathcal{S}$:

###### Definition 2.2.

Optimal Syntactic Profile — Given a dataset $\mathcal{S}$, a desired number
$k$ of patterns, and access to a pattern learner $\mathcal{L}$, a cost
function $\mathcal{C}$ for patterns, and a minimization objective
$\mathcal{O}$ for partitions, we define:  (1) the optimal partitioning
$\widetilde{\mathcal{S}}_{opt}$ as one that minimizes the objective function
$\mathcal{O}$ over all partitions, and  (2) the optimal syntactic profile
$\widetilde{P}_{opt}$ as the disjunction of the least-cost patterns describing
each partition in $\widetilde{\mathcal{S}}_{opt}$ . Formally,

$\leavevmode\resizebox{}{18.0pt}{$\displaystyle\widetilde{\mathcal{S}}_{opt}\mathrel{\overset{\mathsf{\scriptscriptstyle
def}}{=}}\operatorname*{\arg\min}_{\begin{subarray}{c}\\{\mathcal{S}_{1},\,\ldots\,,\mathcal{S}_{k}\\}\\\
\text{s.t.
}\mathcal{S}\,=\,\bigsqcup\limits_{i\,=\,1}^{k}\mathcal{S}_{i}\end{subarray}}\;\sum\limits_{i\,=\,1}^{k}\;\mathcal{O}(\mathcal{S}_{i})$}\qquad\text{and}\qquad\widetilde{P}_{opt}\mathrel{\overset{\mathsf{\scriptscriptstyle
def}}{=}}\bigvee_{\mathcal{S}_{i}\,\in\,\widetilde{\mathcal{S}}_{opt}}\operatorname*{\arg\min}_{P\,\in\,\mathcal{L}(\mathcal{S}_{i})}\;\mathcal{C}(P,\mathcal{S}_{i})$

Ideally, we would define the aggregate cost of a partition as the minimum cost
incurred by a pattern that describes it entirely. This is captured by
$\mathcal{O}(\mathcal{S}_{i})\mathrel{\overset{\mathsf{\scriptscriptstyle
def}}{=}}\min_{P\,\in\,\mathcal{L}(\mathcal{S}_{i})}\mathcal{C}(P,\mathcal{S}_{i})$.
However, with this objective, computing the optimal partitioning
$\widetilde{\mathcal{S}}_{opt}$ is intractable in general. For an arbitrary
learner $\mathcal{L}$ and cost function $\mathcal{C}$, this would require
exploring all $k$-partitionings of the dataset $\mathcal{S}$. The number of
ways to partition a set $\mathcal{S}$ into $k$ non-empty subsets is given by
Stirling numbers of the second kind (Graham et al., 1994),
$\braceVectorstack{|\mathcal{S}|k}$ . When $k\ll|\mathcal{S}|$, the asymptotic
value of  $\braceVectorstack{|\mathcal{S}|k}$ is given by
$\displaystyle\frac{k^{|\mathcal{S}|}}{k!}$ .

Instead, we use an objective that is tractable and works well in practice —
the aggregate cost of a cluster is given by the maximum cost of describing any
two strings belonging to the cluster, using the best possible pattern.
Formally, this objective is
$\widehat{\mathcal{O}}(\mathcal{S}_{i})\mathrel{\overset{\mathsf{\scriptscriptstyle
def}}{=}}\max_{x,y\,\in\,\mathcal{S}_{i}}\min_{P\,\in\,\mathcal{L}(\\{x,y\\})}\mathcal{C}(P,\\{x,y\\})$.
This objective is inspired by the _complete-linkage_ criterion (Sørensen,
1948), which is widely used in clustering applications across various domains
(Jain et al., 1999). To minimize $\widehat{\mathcal{O}}$, it suffices to only
compute the costs of describing (at most) $|\mathcal{S}|^{2}$ pairs of strings
in $\mathcal{S}$.

func
Profile⟨L,C⟩($\mathcal{S}\colon\textsf{String}[\,],m\colon\textsf{Int},M\colon\textsf{Int},\theta\colon\textsf{Real}$)

output: $\widetilde{P}$, a partitioning of $\mathcal{S}$ with the associated
patterns
for each partition, such that $m\leqslant|\>\widetilde{P}\>|\leqslant M$

$1\,\cdot$$H\leftarrow\textsc{BuildHierarchy${}_{\langle\mathcal{L},\mathcal{C}\rangle}$}(\mathcal{S},M,\theta)\quad;\quad\widetilde{P}\leftarrow\\{\\}$
$2\,\cdot$for all $X\in\textsc{{Partition}}(H,m,M)$ do $3\,\cdot$
$\langle\textsf{Pattern:}\;P,\textsf{Cost:}\;c\rangle\leftarrow\textsc{LearnBestPattern${}_{\langle\mathcal{L},\mathcal{C}\rangle}$}(X)$
$4\,\cdot$
$\widetilde{P}\leftarrow\widetilde{P}\cup\\{\langle\textsf{Data:}\;X,\textsf{Pattern:}\;P\rangle\\}$
$5\,\cdot$return $\widetilde{P}$

Figure 5. Our main profiling algorithm

We outline our main algorithm Profile in Fig. 5. It is parameterized by an
arbitrary learner $\mathcal{L}$ and cost function $\mathcal{C}$. Profile
accepts a dataset $\mathcal{S}$, the bounds $\big{[}m,M\big{]}$ for the
desired number of patterns, and a sampling factor $\theta$ that decides the
efficiency _vs._ accuracy trade-off. It returns the generated partitions
paired with the least-cost patterns describing them:
$\\{\langle\mathcal{S}_{1},P_{1}\rangle,\ldots,\langle\mathcal{S}_{k},P_{k}\rangle\\}$,
where $m\leqslant k\leqslant M$.

At a high level, we partition a dataset using the cost of patterns to induce a
syntactic dissimilarity measure over its strings. For large enough $\theta$,
we compute all $O(|\mathcal{S}|^{2})$ pairwise dissimilarities, and generate
the partitioning $\widetilde{\mathcal{S}}_{opt}$ that minimizes
$\widehat{\mathcal{O}}$. However, many large real-life datasets have a very
small number of syntactic clusters, and we notice that we can closely
approximate $\widetilde{\mathcal{S}}_{opt}$ by sampling only a few pairwise
dissimilarities. We invoke BuildHierarchy, in line 1, to construct a hierarchy
$H$ over $\mathcal{S}$ with accuracy controlled by $\theta$. The hierarchy $H$
is then _cut_ at a certain height to obtain $k$ clusters by calling Partition
in line 2 — if $m\neq M$, $k$ is heuristically decided based on the quality of
clusters obtained at various heights. Finally, using LearnBestPattern, we
learn a pattern $P$ for each cluster $X$, and add it to the profile
$\widetilde{P}$.

In the following subsections, we explain the two main components:  (1)
BuildHierarchyfor building a hierarchical clustering, and  (2)
LearnBestPatternfor pattern learning  .

###  2.1. Pattern-Specific Clustering

BuildHierarchy uses an agglomerative hierarchical clustering (AHC) (Xu and
Wunsch II, 2005, Section IIB) to construct a hierarchy (also called a
dendrogram) that depicts a nested grouping of the given collection of strings,
based on their syntactic similarity. Fig. 8 shows such a hierarchy over an
incomplete and inconsistent dataset containing years, using the default set of
atoms listed in Fig. 8. Once constructed, a hierarchy may be split at a
suitable height to extract clusters of desired granularity, which enables a
natural form of refinement — supplying a desired number of clusters. In
contrast, flat clustering methods like k-means (MacQueen et al., 1967)
generate a fixed partitioning within the same time complexity. In fig. 7(b),
we show a heuristically suggested split with 4 clusters, and a refined split
on a request for 5 clusters. A key challenge to clustering is defining an
appropriate pattern-specific measure of dissimilarity over strings, as we show
below.

###### Example 2.3.

Consider the pairs:
$p={\small\\{\,\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1817}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1813?}''}}\,\\}}$
and
$q={\small\\{\,\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1817}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1907}''}}\,\\}}$.
Selecting the pair that is syntactically _more similar_ is ambiguous, even for
humans. The answer depends on the user’s application — it may make sense to
either cluster homogeneous strings (containing only digits) together, or to
cluster strings with a longer common prefix together.

A natural way to resolve this ambiguity is to allow users to express their
application-specific preferences by providing custom atoms, and then to make
the clustering algorithm sensitive to the available atoms. Therefore we desire
a dissimilarity measure that incorporates the user-specified atoms, and yet
remains efficiently computable, since typical clustering algorithms compute
dissimilarities between all pairs of strings (Xu and Wunsch II, 2005).

#### Syntactic Dissimilarity

Our key insight is to leverage program synthesis techniques to efficiently
learn patterns describing a given set of strings, and induce a dissimilarity
measure using the learned patterns — overly general or complex patterns
indicate a high degree of syntactic dissimilarity.

In § 3.1, we formally define the dissimilarity measure $\eta$ as the minimum
cost incurred by any pattern for describing a given pair of strings, using a
specified pattern learner $\mathcal{L}$ and cost function $\mathcal{C}$. We
evaluate our measure $\eta$ in § 5.1, and demonstrate that for estimating
syntactic similarity it is superior to classical character-based measures
(Gomaa and Fahmy, 2013), and simple machine-learned models such as random
forests based on intuitive features.

Year
---
1900
1877
$\epsilon$
1860
?
1866
$\epsilon$
1893
$\vdots$
1888 ?
1872
(a) Dataset

roof/.style= parent anchor=south, child anchor=north, edge path= [edge]
(!u.parent anchor) – ([xshift=-28pt].child anchor) – ([xshift=28pt] .child
anchor) – cycle edge label; , ,  for tree= l sep-=.6em,l=0, edge path=[edge]
(!u.parent anchor) – ++(0,-4pt) -— (.child anchor)edge label;, parent
anchor=south, [$\boldsymbol{\bot}$ [$\textsf{Any}^{+}$, edge=decorate,
decoration=border, segment length=4pt, amplitude=3pt
[$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1}''}}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textsf{Any}^{+}$,
l+=10mm
[$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1}''}}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>{\textsf{Digit}}^{\times
3}$, name=years, l+=18mm
[$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{18}''}}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>{\textsf{Digit}}^{\times
2}$, l+=13mm [$\texttt{1813}\;\cdots\;\texttt{1898}$, edge
label=node[midway,above, yshift=-10pt,xshift=-14pt]$\iddots\vdots\ddots$,
roof, tier=string] ]
[$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{190}''}}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textsf{Digit}$,
l+=17mm [$\texttt{1900}\;\cdots\;\texttt{1903}$, edge label=node[midway,above,
yshift=-8pt,xshift=-14pt]$\iddots\vdots\ddots$, roof, tier=string] ] ]
[$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{18}''}}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>{\textsf{Digit}}^{\times
2}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{?}''}}$,
l+=33mm [$\texttt{1850?}\,\cdots\,\texttt{1875?}$, edge
label=node[midway,above, yshift=-8pt,xshift=-14pt]$\iddots\vdots\ddots$, roof,
tier=string] ] ] [“?”, l+=47mm [?, tier=string]] ] [Empty, l+=47mm,
edge=decorate, decoration=border, segment length=3pt, amplitude=2.25pt,
angle=-45 [$\epsilon$, tier=string]]] [line width=0.8pt,ForestGreen]
[decorate,decoration=snake, segment length=10pt, amplitude=2pt]
([shift=(-1.6,0.45)]years.north west) – ([shift=(7.25,0.45)]years.north east);
[above left = 5mm and -2mm of years] Suggested; [line width=0.8pt,NavyBlue]
[decorate,decoration=snake, segment length=6pt, amplitude=2pt]
([shift=(-1.6,-1.05)]years.north west) – ([shift=(7.25,-1.05)]years.north
east); [below left = -1.5mm and 3mm of years] Refined;

(b) A hierarchy based on default atoms from Fig. 8

Figure 7. A hierarchy with suggested and refined clusters: Leaf nodes
represent strings, and internal nodes are labelled with patterns describing
the strings below them. Atoms are concatenated using
“$\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>$”.
A dashed edge denotes the absence of a pattern that describes the strings
together.

Lower | Bin
---|---
${[a-z]}$ | ${[01]}$
Upper | Digit
${[A-Z]}$ | ${[0-9]}$
$\langle\textsf{TitleCaseWord}\rangle$ | Hex
${\textsf{Upper}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textsf{Lower}^{+}}$ | ${[a-fA-F0-9]}$
Alpha | AlphaDigit
${[a-zA-Z]}$ | ${[a-zA-Z0-9]}$
 ␣  | AlphaDigitSpace
${\textbackslash{}s}$ | ${[a-zA-Z0-9\textbackslash{}s]}$
DotDash | Punct
${[.-]}$ | ${[.,\,:\,?\,/-]}$
AlphaDash | Symb
${[a-zA-Z-]}$ | ${[-.,\,:\,?\,/@\,\\#\,\$\,\%\,\&\,\cdots]}$
AlphaSpace | Base64
${[a-zA-Z\textbackslash{}s]}$ | ${[a-zA-Z0-9+\setminus=]}$
Figure 8. Default atoms in FlashProfile, with their regex: We also allow “Any”
atom that matches any character.

Linda K. Jacobs, The Syrian Colony in New York City 1880-1900.
http://bit.ly/LJacobs

#### Adaptive Sampling and Approximation

While $\eta$ captures a high-quality syntactic dissimilarity, with it, each
pairwise dissimilarity computation requires learning and scoring of patterns,
which may be expensive for large real datasets. To allow end users to quickly
generate approximately correct profiles for large datasets, we present a two-
stage sampling technique.  (1) At the top-level, FlashProfile employs a
Sample$-$Profile$-$Filter cycle: we sample a small subset of the data, profile
it, and filter out data that is described by the profile learned so far.  (2)
While profiling each sample, our BuildHierarchy algorithm approximates some
pairwise dissimilarities using previously seen patterns.  We allow end users
to control the degree of approximations using two optional parameters.

Our key insight that, unlike typical clustering scenarios, computing
dissimilarity between a pair of strings gives us more than just a measure — we
also learn a pattern. We test this pattern on other pairs to approximate their
dissimilarity, which is typically faster than learning new patterns. Our
technique is inspired by counter-example guided inductive synthesis (CEGIS)
(Solar-Lezama et al., 2006). CEGIS was extended to sub-sampling settings by
Raychev et al. (2016), but they synthesize a single program and require the
outputs for all inputs. In contrast, we learn a disjunction of several
programs, the outputs for which over a dataset, i.e. the partitions, are
unknown a priori.

###### Example 2.4.

The pattern
$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{PMC}''}}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>{\textsf{Digit}}^{\times
7}$ learned for the string pair { “PMC2536233”, “PMC4901429” }, also describes
the string pair { “PMC4901429”, “PMC2395569” }, and may be used to accurately
estimate their dissimilarity without invoking learning again.

However this sampling needs to be performed carefully for accurate
approximations. Although the pattern
$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1}''}}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>{\textsf{Digit}}^{\times
3}$ learned for { “1901”, “1875” }, also describes { “1872”, “1875” }, there
exists another pattern
$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{187}''}}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textsf{Digit}$,
which indicates a much lower syntactic dissimilarity. We propose an adaptive
algorithm for sampling patterns based on previously observed patterns and
strings in the dataset. Our sampling and approximation algorithms are detailed
in § 3.2 and § 3.3 respectively.

###  2.2. Pattern Learning via Program Synthesis

An important aspect of our clustering-based approach to profiling, described
in § 2.1, is its generality. It is agnostic to the specific language
$\mathscr{L}$ in which patterns are expressed, as long as appropriate pattern
learner $\mathcal{L}$ and cost function $\mathcal{C}$ are provided for
$\mathscr{L}$.

func LearnBestPattern⟨L,C⟩($\mathcal{S}\colon\textsf{String}[\,]$)

output: The least-cost pattern and its cost, for $\mathcal{S}$

$1\,\cdot$$V\leftarrow\textsc{$\mathcal{L}$}(\mathcal{S})$ $2\,\cdot$if
$V=\\{\\}$ then return
$\langle\textsf{Pattern:\,}\boldsymbol{\bot},\textsf{Cost:\,}\infty\rangle$
$3\,\cdot$$P\leftarrow\operatorname*{\arg\min}_{P\,\in\,V}\
\textsc{$\mathcal{C}$}(P,\mathcal{S})$ $4\,\cdot$return
$\langle\textsf{Pattern:\,}P,\textsf{Cost:\,}\textsc{$\mathcal{C}$}(P,\mathcal{S})\rangle$

Figure 9. Learning the best pattern for a dataset

LearnBestPattern, listed in Fig. 9, first invokes $\mathcal{L}$ to learn a set
$V$ of patterns each of which describes all strings in $\mathcal{S}$. If
pattern learning fails, Pattern learning may fail, for example, if the
language $\mathscr{L}$ is too restrictive and no pattern can describe the
given strings. in line 2, we return the special pattern $\boldsymbol{\bot}$
and a very high cost $\infty$. Otherwise, we return the pattern that has the
minimum cost using $\mathcal{C}$ w.r.t. $\mathcal{S}$. LearnBestPattern is
used during clustering to compute pairwise dissimilarity and finally compute
the least-cost patterns for clusters.

A natural approach to learning patterns is _inductive program synthesis_
(Gulwani et al., 2017), which generalizes a given specification to desired
programs over a domain-specific language (DSL). We propose a rich DSL for
patterns, and present an efficient inductive synthesizer for it.

#### Language for Patterns

Our DSL $\mathscr{L}_{\textsf{FP}}$ is designed to support efficient synthesis
using existing technologies while still being able to express rich patterns
for practical applications. A pattern is an arbitrary sequence of atomic
patterns (atoms), each containing low-level logic for matching a sequence of
characters. A pattern $P\in\mathscr{L}_{\textsf{FP}}$ _describes_ a string
$s$, i.e. $P(s)=\texttt{True}$, iff the atoms in $P$ match contiguous non-
empty substrings of $s$, ultimately matching $s$ in its entirety. FlashProfile
uses a default set of atoms listed in Fig. 8, which may be augmented with new
regular expressions, constant strings, or ad hoc functions. We formally define
our language $\mathscr{L}_{\textsf{FP}}$ in § 4.1.

#### Pattern Synthesis

The inductive synthesis problem for pattern learning is: given a set of
strings $\mathcal{S}$, learn a pattern $P\in\mathscr{L}_{\textsf{FP}}$ such
that $\forall\,s\in\mathcal{S}$: $P(s)=\texttt{True}$. Our learner
$\mathcal{L}_{\textsf{FP}}$ decomposes the synthesis problem for $P$ over the
strings in $\mathcal{S}$ into synthesis problems for individual atoms in $P$
over appropriate substrings. However, a naïve approach of tokenizing each
string to (exponentially many) sequences of atoms, and computing their
intersection is simply impractical. Instead, $\mathcal{L}_{\textsf{FP}}$
computes the intersection incrementally at each atomic match, using a novel
decomposition technique.

$\mathcal{L}_{\textsf{FP}}$ is implemented using PROSE (Microsoft, 2017d;
Polozov and Gulwani, 2015), a state-of-the-art inductive synthesis framework.
PROSE requires DSL designers to define the logic for decomposing a synthesis
problem over an expression to those over its subexpressions, which it uses to
automatically generate an efficient synthesizer for their DSL. We detail our
synthesis procedure in § 4.2.

#### Cost of Patterns

Once a set of patterns has been synthesized, a variety of strategies may be
used to identify the most desirable one. Our cost function
$\mathcal{C}_{\textsf{FP}}$ is inspired by _regularization_ (Tikhonov, 1963)
techniques that are heavily used in statistical learning to construct
generalizations that do not overfit to the data. $\mathcal{C}_{\textsf{FP}}$
decides a trade-off between two opposing factors:  (1) specificity:prefer a
pattern that is not general, and  (2) simplicity:prefer a compact pattern that
is easy to interpret  .

###### Example 2.5.

The strings { “Male”, “Female” } are matched by the patterns
$\textsf{Upper}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textsf{Lower}^{+}$,
and
$\textsf{Upper}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textsf{Hex}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textsf{Lower}^{+}$.
Although the latter is more specific, it is overly complex. On the other hand,
the pattern $\textsf{Alpha}^{+}$ is simpler and easier to interpret, but is
overly general.

To this end, each atom in $\mathscr{L}_{\textsf{FP}}$ has a fixed _static
cost_ similar to fixed _regularization hyperparameters_ used in machine
learning (Bishop, 2016), and a dataset-driven _dynamic weight_. The cost of a
pattern is the weighted sum of the cost of its constituent atoms. In § 4.3,
we detail our cost function $\mathcal{C}_{\textsf{FP}}$, and provide some
guidelines on assigning costs for new atoms defined by users.

##  3\. Hierarchical Clustering

We now detail our clustering-based approach for generating syntactic profiles
and show practical optimizations for fast approximately-correct profiling. In
§ 3.1 – § 3.4, we explain these in the context of a small chunk of data
drawn from a large dataset. In § 3.5, we then discuss how profile large
datasets by generating profiles for as many chunks as necessary and combining
them.

func
BuildHierarchy⟨L,C⟩($\mathcal{S}\colon\textsf{String}[\,],M\colon\textsf{Int},\theta\colon\textsf{Real}$)

output: A hierarchical clustering over $\mathcal{S}$

$1\,\cdot$$D\leftarrow\textsc{SampleDissimilarities${}_{\langle\mathcal{L},\mathcal{C}\rangle}$}(\mathcal{S},\left\lceil\theta\,M\right\rceil)$
$2\,\cdot$$A\leftarrow\textsc{ApproxDMatrix}(\mathcal{S},D)$ $3\,\cdot$return
$AHC(\mathcal{S},A)$

Figure 10. Building an approximately-correct hierarchy

$\left\lceil x\right\rceil$ denotes the _ceiling_ of $x$, i.e. $\left\lceil
x\right\rceil=\min\;\\{m\in\mathbb{Z}\mid m\geqslant x\\}$.

Recall that our first step in Profile is to build a hierarchical clustering
over the data. The BuildHierarchy procedure, listed in Fig. 10, constructs a
hierarchy $H$ over a given dataset $\mathcal{S}$, with parameters $M$ and
$\theta$. $M$ is the maximum number of clusters in a desired profile. The
_pattern sampling factor_ $\theta$ decides the performance _vs._ accuracy
trade-off while constructing $H$.

Henceforth, we use _pair_ to denote a pair of strings. In line 1 of
BuildHierarchy, we first sample pairwise dissimilarities, i.e. the best
patterns and their costs, for a small set (based on the $\theta$ factor) of
string pairs. Specifically, out of all $O(|\mathcal{S}|^{2})$ pairs within
$\mathcal{S}$, we adaptively sample dissimilarities for only $O(\theta
M|\mathcal{S}|)$ pairs by calling SampleDissimilarities, and cache the learned
patterns in $D$. We formally define the dissimilarity measure in § 3.1, and
describe SampleDissimilarities in § 3.2. The cache $D$ is then used by
ApproxDMatrix, in line 2, to complete the dissimilarity matrix $A$ over
$\mathcal{S}$, using approximations wherever necessary. We describe these
approximations in § 3.3. Finally, a standard agglomerative hierarchical
clustering (AHC) (Xu and Wunsch II, 2005, Section IIB) is used to construct a
hierarchy over $\mathcal{S}$ using the matrix $A$.

###  3.1. Syntactic Dissimilarity

We formally define our syntactic dissimilarity measure as follows:

###### Definition 3.1.

Syntactic Dissimilarity — For a given pattern learner $\mathcal{L}$ and a cost
function $\mathcal{C}$ over an arbitrary language of patterns $\mathscr{L}$,
we define the syntactic dissimilarity between strings $x,y\in\mathbb{S}$ as
the minimum cost incurred by a pattern in $\mathscr{L}$ to describe them
together, i.e.

$\eta\,(x,y)\mathrel{\overset{\mathsf{\scriptscriptstyle
def}}{=}}\begin{cases}0&\text{if $x=y$}\\\ \infty&\text{if
$x\not=y\,\bigwedge\,V=\\{\\}$}\\\
\displaystyle\min_{P\,\in\,V}\;\mathcal{C}\big{(}P,\\{x,y\\}\big{)}&\text{otherwise}\end{cases}$

where $V=\mathcal{L}\big{(}\\{x,y\\}\big{)}\subseteq\mathscr{L}$ is the set of
patterns that describe strings $x$ and $y$, and $\infty$ denotes a high cost
for a failure to describe $x$ and $y$ together using patterns learned by
$\mathcal{L}$.

The following example shows some candidate patterns and their costs
encountered during dissimilarity computation for various pairs. The actual
numbers depend on the pattern learner and cost function used, in this case
FlashProfile’s $\mathcal{L}_{\textsf{FP}}$ and $\mathcal{C}_{\textsf{FP}}$,
which we describe in § 4. However, this example highlights the desirable
properties for a natural measure of syntactic dissimilarity.

###### Example 3.2.

For three pairs, we show the shortcomings of classical character-based
similarity measures. We compare the Levenshtein distance (LD) (Levenshtein,
1966) for these pairs against the pattern-based dissimilarity $\eta$ computed
with our default atoms from Fig. 8. On the right, we also show the least-cost
pattern, and two other randomly sampled patterns that describe the pair.

First, we compare two dates both using the same syntactic format “YYYY-MM-DD”:

(a) $\textsf{LD}=8$  _vs._ $\eta=4.96\>\Bigg{\\{}$

1990-11-23
---
2001-02-04

_4.96_ | ${\textsf{Digit}}^{\times 4}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!{\textsf{Digit}}^{\times 2}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!{\textsf{Digit}}^{\times 2}$
---|---
_179.9_ | $\textsf{Hex}^{+}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Symb}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Hex}^{+}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Hex}^{+}$
_46482_ | $\textsf{Digit}^{+}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Punct}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Any}^{+}$

Syntactically, these dates are very similar — they use the same delimiter “-”,
and have same width for the numeric parts. The best pattern found by
FlashProfile captures exactly these features. However, Levenshtein distance
for these dates is higher than the following dates which uses a different
delimiter and a different order for the numeric parts:

(b) $\textsf{LD}=5$  _vs._ $\eta=30.2\>\Bigg{\\{}$

1990-11-23
---
29/05/1923

_30.2_ | $\textsf{Digit}^{+}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Punct}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!{\textsf{Digit}}^{\times 2}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Punct}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Digit}^{+}$
---|---
_318.6_ | $\textsf{Digit}^{+}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Symb}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Digit}^{+}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Symb}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Digit}^{+}$
_55774_ | $\textsf{Digit}^{+}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Punct}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Any}^{+}$

The Levenshtein distance is again lower for the following pair containing a
date and an ISBN code:

(c) $\textsf{LD}=7$  _vs._ $\eta=23595\>\Bigg{\\{}$

1990-11-23
---
899-2119-33-X

_23595_ | $\textsf{Digit}^{+}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Digit}^{+}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Any}^{+}$
---|---
_55415_ | $\textsf{Digit}^{+}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Punct}\\!\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\\!\textsf{Any}^{+}$
_92933_ | $\textsf{Any}^{+}$

The same trend is also observed for Jaro-Winkler (Winkler, 1999), and other
measures based on edit distance (Gomaa and Fahmy, 2013). Whereas these
measures look for exact matches on characters, pattern-based measures have the
key advantage of being able to generalize substrings to atoms.

###  3.2. Adaptive Sampling of Patterns

Although $\eta$ accurately captures the syntactic dissimilarity of strings
over an arbitrary language of patterns, it requires pattern learning and
scoring for every pairwise dissimilarity computation, which is computationally
expensive. While this may not be a concern for non-realtime scenarios, such as
profiling large datasets on cloud-based datastores, we provide a tunable
parameter to end users to be able to generate approximately correct profiles
for large datasets in real time.

Besides a numeric measure of dissimilarity, computing $\eta$ over a pair also
generates a pattern that describes the pair. Since the patterns generalize
substrings to atoms, often the patterns learned for one pair also describe
many other pairs. We aim to sample a subset of patterns that are likely to be
sufficient for constructing a hierarchy accurate until $M$ levels, i.e.
$1\leqslant k\leqslant M$ clusters extracted from this hierarchy should be
identical to $k$ clusters extracted from a hierarchy constructed without
approximations. Our SampleDissimilarities algorithm, shown in Fig. 11, is
inspired by the seeding technique of k-means++ (Arthur and Vassilvitskii,
2007). Instead of computing all pairwise dissimilarities for pairs in
$\mathcal{S}\times\mathcal{S}$, we compute the dissimilarities for pairs in
$\rho\times\mathcal{S}$, where set $\rho$ is a carefully selected small set of
_seed strings_. The patterns learned during this process are likely to be
sufficient for accurately estimating the dissimilarities for the remaining
pairs.

func
SampleDissimilarities⟨L,C⟩($\mathcal{S}\colon\textsf{String}[\,],\widehat{M}\colon\textsf{Int}$)

output: A dictionary mapping $O(\widehat{M}|\mathcal{S}|)$ pairs of strings
from $\mathcal{S}$,
to the best pattern describing each pair and its cost

$1\,\cdot$$D\leftarrow\\{\\}\quad;\quad a\leftarrow\text{a random string in
}\mathcal{S}\quad;\quad\rho\leftarrow\\{a\\}$ $2\,\cdot$for $i\leftarrow 1\
\textbf{to}\ \widehat{M}$ do $3\,\cdot$ for all $b\in\mathcal{S}$ do
$4\,\cdot$
$D[a,b]\leftarrow\textsc{LearnBestPattern${}_{\langle\mathcal{L},\mathcal{C}\rangle}$}(\\{a,b\\})$
$5\,\cdot$ $\blacktriangleright$ Pick the most dissimilar string w.r.t.
strings already in $\rho$. $6\,\cdot$
$a\leftarrow\operatorname*{\arg\max}_{x\>\in\>\mathcal{S}}\;\min_{y\>\in\>\rho}\;D[y,x].\textsf{Cost}$
$7\,\cdot$ $\rho\leftarrow\rho\cup\\{a\\}$ $8\,\cdot$return $D$

Figure 11. Adaptively sampling a small set of patterns

SampleDissimilarities takes a dataset $\mathcal{S}$ and a factor
$\widehat{M}$, and it samples dissimilarities for
$O(\widehat{M}|\mathcal{S}|)$ pairs. It iteratively selects a set $\rho$
containing $\widehat{M}$ strings that are most dissimilar to each other.
Starting with a random string in $\rho$, in each iteration, at line 6, it adds
the string $x\in\mathcal{S}$ such that it is as dissimilar as possible, even
with its most-similar neighbor in $\rho$. In the end, the set $D$ only
contains dissimilarities for pairs in $\mathcal{S}\times\rho$, computed at
line 5. Recall that, $\widehat{M}$ is controlled by the pattern sampling
factor $\theta$. In line 1 of BuildHierarchy (in Fig. 10), we set
$\widehat{M}=\left\lceil\theta M\right\rceil$.

Since the user may request up to at most $M$ clusters, $\theta$ must be at
least $1.0$, so that we pick at least one seed string from each cluster to
$\rho$. Then, computing the dissimilarities with _all_ other strings in the
dataset would ensure we have a good distribution of patterns that describe
intra– and inter– cluster dissimilarities, even for the finest granularity
clustering with $M$ clusters.

###### Example 3.3.

Consider the dataset containing years in fig. 7(a). Starting with a random
string, say “1901”; the set $\rho$ of seed strings grows as shown below, with
increasing $\widehat{M}$. At each step, $NN$ (nearest neighbor) shows the new
string added to $\rho$ paired with its most similar neighbor.

  1. $\widehat{M}=2\>\;\lvert$

$NN=\langle\epsilon,\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color<EMAIL_ADDRESS>$\rho=\\{\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1901}''}},\epsilon\\}$

  2. $\widehat{M}=3\>\;\lvert$

$NN=\langle\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{?}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color<EMAIL_ADDRESS>$\rho=\\{\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{?}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1901}''}},\epsilon\\}$

  3. $\widehat{M}=4\>\;\lvert$

$NN=\langle\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1875?}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color<EMAIL_ADDRESS>$\rho=\\{\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1875?}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{?}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1901}''}},\epsilon\\}$

  4. $\widehat{M}=5\>\;\lvert$

$NN=\langle\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1817}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1875?}''}}\rangle$
$\rho=\\{\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1817}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1875?}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{?}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1901}''}},\epsilon\\}$

  5. $\widehat{M}=6\>\;\lvert$

$NN=\langle\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1898}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color<EMAIL_ADDRESS>$\rho=\\{\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1898}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1817}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1875?}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{?}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{1901}''}},\epsilon\\}$

###  3.3. Dissimilarity Approximation

Now we present our technique for completing a dissimilarity matrix over a
dataset $\mathcal{S}$, using the patterns sampled from the previous step. Note
that, for a large enough value of the pattern sampling factor, i.e.
$\displaystyle\theta\geqslant\frac{|\mathcal{S}|}{M}$ , we would sampled all
pairwise dissimilarities and no approximation would be necessary. For smaller
values of $\theta$, we use the patterns learned while computing $\eta$ over
$\rho\times\mathcal{S}$ to approximate the remaining pairwise dissimilarities
in $\mathcal{S}\times\mathcal{S}$. The key observation here is that, testing
whether a pattern describes a string is typically much faster than learning a
new pattern.

func ApproxDMatrix ⟨L,C⟩($\mathcal{S}\colon\textsf{String}[\,],\\\ \hskip
115.0ptD\colon\textsf{String}\times\textsf{String}\mapsto\textsf{Pattern}\times\textsf{Real}$)

output: A matrix $A$ of all pairwise dissimilarities over strings in
$\mathcal{S}$

$1\,\cdot$$A\leftarrow\\{\\}$ $2\,\cdot$for all $x\in\mathcal{S}$ do
$3\,\cdot$ for all $y\in\mathcal{S}$ do $4\,\cdot$ if $x=y$ then
$A[x,y]\leftarrow 0$ $5\,\cdot$ else if $\langle x,y\rangle\in D$ then
$A[x,y]\leftarrow D[x,y].\textsf{Cost}$ $6\,\cdot$ else $7\,\cdot$
$\blacktriangleright$ Select the least cost pattern that describes $x$ and
$y$. $8\,\cdot$
$V\leftarrow\big{\\{}P\bigm{\lvert}\langle\textsf{Pattern:}\,P,\textsf{Cost:\,}\,\cdot\rangle\in
D\bigwedge P(x)\bigwedge P(y)\big{\\}}$ $9\,\cdot$ if $V\neq\\{\\}$ then
$A[x,y]\leftarrow\min_{P\>\in\>V}\;\mathcal{C}\big{(}P,\\{x,y\\}\big{)}$
$10\,\cdot$ else $11\,\cdot$ $\blacktriangleright$ Compute $\eta\,(s,y)$, and
store the learned pattern. $12\,\cdot$
$D[x,y]\leftarrow\textsc{LearnBestPattern${}_{\langle\mathcal{L},\mathcal{C}\rangle}$}(\\{x,y\\})$
$13\,\cdot$ $A[x,y]\leftarrow D[x,y].\textsf{Cost}$ $14\,\cdot$return $A$

Figure 12. Approximating a complete dissimilarity matrix

The ApproxDMatrix procedure, listed in Fig. 12, uses the dictionary $D$ of
patterns from SampleDissimilarities to generate a matrix $A$ of all pairwise
dissimilarities over $\mathcal{S}$. Lines 7 and 8 show the key approximation
steps for a pair $\\{x,y\\}$. In line 7, we test the patterns in $D$, and
select a set $V$ of them containing only those which describe both $x$ and
$y$. We then compute their new costs relative to $\\{x,y\\}$, in line 8, and
select the least cost as an approximation of $\eta\,(x,y)$. If $V$ turns out
to be empty, i.e. no sampled pattern describes both $x$ and $y$, then, in line
10, we call LearnBestPattern to compute $\eta\,(x,y)$. We also add the new
pattern to $D$ for use in future approximations.

Although $\theta=1.0$ ensures that we pick a seed string from each final
cluster, in practice we use a $\theta$ that is slightly greater than $1.0$.
This allows us to sample a few more seed strings, and ensures a better
distribution of patterns in $D$ at the cost of a negligible performance
overhead. In practice, it rarely happens that no sampled pattern describes a
new pair (at line 9, Fig. 12), since seed patterns for inter-cluster string
pairs are usually overly general, as we show in the example below.

###### Example 3.4.

Consider a dataset $\mathcal{S}=\\{$“07-jun”, “aug-18”, “20-feb”, “16-jun”,
“20-jun”$\\}$. Assuming $M=2$ and $\theta=1.0$ (i.e. $\widehat{M}=2$), suppose
we start with the string “20-jun”. Then, following the SampleDissimilarities
algorithm shown in Fig. 11, we would select
$\rho={\small\\{\,\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{20-jun}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{aug-18}''}}\,\\}}$,
and would sample the following seed patterns into $D$ based on patterns
defined over our default atoms (listed in Fig. 8) and constant string
literals:

  1. (a)

$D[$“20-jun”,“07-jun”$]\mapsto$ ${\textsf{Digit}}^{\times
2}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color<EMAIL_ADDRESS>and

  2. (b)

$D[$“20-jun”,“20-feb”$]\mapsto$
$\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{20-}''}}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>{\textsf{Lower}}^{\times
3}$,

  3. (c)

$D[$“20-jun”,“16-jun”$]\mapsto$ ${\textsf{Digit}}^{\times
2}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color<EMAIL_ADDRESS>and

  4. (d)

$D[$“20-jun”,“aug-18”$]$, $D[$“aug-18”,“07-jun”$]$, $D[$“aug-18”,“20-feb”$]$,
$D[$“aug-18”,“16-jun”$]$ $\mapsto$
$\textsf{AlphaDigit}^{+}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textsf{AlphaDigit}^{+}$.

Next, we estimate
$\eta\,(\small\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{16-jun}''}},\small\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{20-feb}''}})$
using these patterns. None of _(a)_ — _(c)_ describe the pair, but _(d)_ does.
However, it is overly general compared to the least-cost pattern,
${\textsf{Digit}}^{\times
2}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{-}''}}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>{\textsf{Lower}}^{\times
3}$.

As in the case above, depending on the expressiveness of the pattern language,
for a small $\theta$ the sampled patterns may be too specific to be useful.
With a slightly higher $\theta=1.25$, i.e. $\widehat{M}=\left\lceil\theta
M\right\rceil=3$, we would also select “07-jun” as a seed string in $\rho$,
and sample the desired while computing $D[$“07-jun”,“20-feb”$]$. We evaluate
the impact of $\theta$ on performance and accuracy in § 5.2.

###  3.4. Hierarchy Construction and Splitting

func
AHC($\mathcal{S}\colon\textsf{String}[\,],A\colon\textsf{String}\times\textsf{String}\mapsto\textsf{Real}$)

output: A hierarchy over $\mathcal{S}$ using dissimilarity matrix $A$

$1\,\cdot$$H\leftarrow\big{\\{}\\{\,s\,\\}\mid s\in\mathcal{S}\big{\\}}$
$2\,\cdot$while $|\,H\,|>1$ do $3\,\cdot$ $\langle
X,Y\rangle\leftarrow\operatorname*{\arg\min}_{X,Y\in
H}\,\widehat{\eta}\,(X,Y\mid A)$ $4\,\cdot$
$H\leftarrow\big{(}H\setminus\\{X,Y\\}\big{)}\cup\big{\\{}\\{\,X,Y\,\\}\big{\\}}$
$5\,\cdot$return $H$

Figure 13. A standard algorithm for AHC

Once we have a dissimilarity matrix, we use a standard agglomerative
hierarchical clustering (AHC) (Xu and Wunsch II, 2005, Section IIB) algorithm,
as outlined in Fig. 13. Note that AHC is not parameterized by $\mathcal{L}$
and $\mathcal{C}$, since it does not involve learning or scoring of patterns
any more.

We start with each string in a singleton set (leaf nodes of the hierarchy).
Then, we iteratively join the least-dissimilar pair of sets, until we are left
with a single set (root of the hierarchy). AHC relies on a _linkage criterion_
to estimate dissimilarity of sets of strings. We use the classic complete-
linkage (also known as further-neighbor linkage) criterion (Sørensen, 1948),
which has been shown to be resistant to outliers, and yield useful hierarchies
in practical applications (Jain et al., 1999).

###### Definition 3.5.

Complete-Linkage — For a set $\mathcal{S}$ and a dissimilarity matrix $A$
defined on $\mathcal{S}$, given two arbitrarily-nested clusters $X$ and $Y$
over a subset of entities in $\mathcal{S}$, we define the dissimilarity
between their contents (the _flattened_ sets
$\overline{X},\overline{Y}\subseteq\mathcal{S}$, respectively) as:

$\widehat{\eta}\,(X,Y\mid A)\mathrel{\overset{\mathsf{\scriptscriptstyle
def}}{=}}\max_{x\in\overline{X},y\in\overline{Y}}\,A[x,y]$

Once a hierarchy has been constructed, our Profile algorithm (in Fig. 5)
invokes the Partition method (at line 2) to extract $k$ clusters within the
provided bounds $[m,M]$. If $m\not=M$, we use a heuristic based on the _elbow_
(also called _knee_) method (Halkidi et al., 2001): between the top
$m^{\text{th}}$ and the $M^{\text{th}}$ nodes, we split the hierarchy till the
knee — a node below which the average intra-cluster dissimilarity does not
vary significantly. A user may request $m=k=M$, in which case Partition simply
splits the top $k$ nodes of the hierarchy to generate $k$ clusters.

###  3.5. Profiling Large Datasets

To scale our technique to large datasets, we now describe a second round of
sampling. Recall that in SampleDissimilarities, we sample dissimilarities for
$O(\theta M|\mathcal{S}|)$ pairs. However, although $\theta M$ is very small,
$|\,\mathcal{S}\,|$ is still very large for real-life datasets. In order to
address this, we run our Profile algorithm from Fig. 5 on small chunks of the
dataset, and combine the generated profiles.

func
BigProfile⟨L,C⟩($\mathcal{S}\colon\textsf{String}[\,],m\colon\textsf{Int},M\colon\textsf{Int},\\\
\hskip 90.0pt\theta\colon\textsf{Real},\mu\colon\textsf{Real}$)

output: A profile $\widetilde{P}$ that satisfies
$m\leqslant|\>\widetilde{P}\>|\leqslant M$

$1\,\cdot$$\widetilde{P}\leftarrow\\{\\}$ $2\,\cdot$while
$|\,\mathcal{S}\,|>0$ do $3\,\cdot$
$X\leftarrow\textsc{SampleRandom}(\mathcal{S},\left\lceil\mu M\right\rceil)$
$4\,\cdot$
$\widetilde{P}^{\prime}\leftarrow\textsc{Profile${}_{\langle\mathcal{L},\mathcal{C}\rangle}$}(X,m,M,\theta)$
$5\,\cdot$
$\widetilde{P}\leftarrow\textsc{CompressProfile${}_{\langle\mathcal{L},\mathcal{C}\rangle}$}(\widetilde{P}\cup\widetilde{P}^{\prime},M)$
$6\,\cdot$
$\mathcal{S}\leftarrow\textsc{RemoveMatchingStrings}(\mathcal{S},\widetilde{P})$
$7\,\cdot$return $\widetilde{P}$

Figure 14. Profiling large datasets

We outline our BigProfile algorithm in Fig. 14. This algorithm accepts a new
_string sampling factor_ $\mu\geqslant 1$, which controls the size of chunks
profiled in each iteration, until we have profiled all the strings in
$\mathcal{S}$. In § 5.3, we evaluate the impact of $\mu$ on performance and
accuracy.

We start by selecting a random subset $X$ of size $\left\lceil\mu
M\right\rceil$ from $\mathcal{S}$ in line 3. In line 4, we obtain a profile
$\widetilde{P}^{\prime}$ of $X$, and merge it with the global profile
$\widetilde{P}$ in line 5. We repeat this loop with the remaining strings in
$\mathcal{S}$ that do not match the global profile. While merging
$\widetilde{P}$ and $\widetilde{P}^{\prime}$ in line 5, we may exceed the
maximum number of patterns $M$, and may need to _compress_ the profile.

func CompressProfile⟨L,C⟩($\widetilde{P}\colon\texttt{ref}\
\textsf{Profile},M\colon\textsf{Int}$)

output: A compressed profile $\widetilde{P}$ that satisfies
$|\>\widetilde{P}\>|\leqslant M$

$1\,\cdot$while $|\,\widetilde{P}\,|>M$ do $2\,\cdot$ $\blacktriangleright$
Compute the most similar partitions in the profile so far. $3\,\cdot$ $\langle
X,Y\rangle\leftarrow\displaystyle\operatorname*{\arg\min}_{X,Y\in\widetilde{P}}\big{[}\textsc{LearnBestPattern${}_{\langle\mathcal{L},\mathcal{C}\rangle}$}(X.\textsf{Data}\cup
Y.\textsf{Data})\big{]}.\textsf{Cost}$ $4\,\cdot$ $\blacktriangleright$ Merge
partitions $\langle X,Y\rangle$, and update $\widetilde{P}$. $5\,\cdot$
$Z\leftarrow X.\textsf{Data}\;\cup\;Y.\textsf{Data}$ $6\,\cdot$
$P\leftarrow\textsc{LearnBestPattern${}_{\langle\mathcal{L},\mathcal{C}\rangle}$}(Z).\textsf{Pattern}$
$7\,\cdot$
$\widetilde{P}\leftarrow(\widetilde{P}\setminus\\{X,Y\\})\cup\\{\,\langle\textsf{Data:}\;Z,\textsf{Pattern:}\;P\rangle\,\\}$
$8\,\cdot$return $\widetilde{P}$

Figure 15. Limiting the number of patterns in a profile

For brevity, we elide the details of SampleRandom and RemoveMatchingStrings,
which have straightforward implementations. In Fig. 15 we outline
CompressProfile. It accepts a profile $\widetilde{P}$ and shrinks it to at
most $M$ patterns. The key idea is to repeatedly merge the most similar pair
of patterns in $\widetilde{P}$. However, we cannot compute the similarity
between patterns. Instead, we estimate it using syntactic similarity of the
associated data partitions. The profile $\widetilde{P}$ must be of the same
type as returned by Profile, i.e. a set of pairs, each containing a data
partition and its pattern. In line 2, we first identify the partitions
$\langle X,Y\rangle$ which are the most similar, i.e. require the least cost
pattern for describing them together. We then merge $X$ and $Y$ to $Z$, learn
a pattern describing $Z$, and update $\widetilde{P}$ by replacing $X$ and $Y$
with $Z$ and its pattern. This process is repeated until the total number of
patterns falls to $M$.

###### Theorem 3.6 (Termination).

Over an arbitrary language $\mathscr{L}$ of patterns, assume an arbitrary
learner $\mathcal{L}\colon 2\,^{\mathbb{S}}\to 2\,^{\mathscr{L}}$ and a cost
function
$\mathcal{C}\colon\mathscr{L}\,\times\,2\,^{\mathbb{S}}\to\mathbb{R}_{\leavevmode\resizebox{}{3.84009pt}{$\,\kern-0.70004pt\geq\\!0$}}$,
such that for any finite dataset $\mathcal{S}\subset\mathbb{S}$, we have:  (1)
$\mathcal{L}(\mathcal{S})$terminates and produces a finite set of patterns,
and  (2) $\mathcal{C}(P,\mathcal{S})$terminates for all $P\in\mathscr{L}$.
Then, the BigProfile procedure (Fig. 14) terminates on any finite dataset
$\mathcal{S}\subset\mathbb{S}$, for arbitrary valid values of the optional
parameters $m$, $M$, $\theta$ and $\mu$.

###### Proof.

We note that in BigProfile, the loop within lines 2 – 6 runs for at most
$\displaystyle\frac{|\mathcal{S}|}{\left\lceil\mu M\right\rceil}$ iterations,
since at least $\left\lceil\mu M\right\rceil$ strings are removed from
$\mathcal{S}$ in each iteration. Therefore, to prove termination of
BigProfile, it is sufficient to show that Profile and CompressProfile
terminate.

First, we note that termination of LearnBestPattern immediately follows from
(1) and (2). Then, it is easy to observe that CompressProfile terminates as
well:  (1) the loop in lines 1 – 5 runs for at most $|\widetilde{P}|-M$
iterations, and  (2) LearnBestPatternis invoked $O(|\widetilde{P}|^{2})$ times
in each iteration.

The Profile procedure (Fig. 5) makes at most $O\big{(}(\mu M)^{2}\big{)}$
calls to LearnBestPattern (Fig. 9) to profile the $\left\lceil\mu
M\right\rceil$ strings sampled in to $X$ — at most $O\big{(}(\mu
M)^{2}\big{)}$ calls within BuildHierarchy (Fig. 10), and $O(M)$ calls to
learn patterns for the final partitions. Depending on $\theta$, BuildHierarchy
may make many fewer calls to LearnBestPattern. However, it makes no more than
1 such call per pair of strings in $X$, to build the dissimilarity matrix.
Therefore, Profile terminates as well. ∎

##  4\. Pattern Synthesis

We now describe the specific pattern language, leaning technique and cost
function used to instantiate our profiling technique as FlashProfile. We begin
with a brief description our pattern language in § 4.1, present our pattern
synthesizer in § 4.2, and conclude with our cost function in § 4.3.

###  4.1. The Pattern Language $\mathscr{L}_{\textsf{FP}}$

Figure 16(a) shows the formal syntax for our pattern language
$\mathscr{L}_{\textsf{FP}}$. Each pattern $P\in\mathscr{L}_{\textsf{FP}}$ is a
predicate defined on strings, i.e. a function
$P\colon\textsf{String}\rightarrow\textsf{Bool}$, which embodies a set of
constraints over strings. A pattern $P$ _describes_ a given string $s$, i.e.
$P(s)=\texttt{True}$, iff $s$ satisfies all constraints imposed by $P$.
Patterns in $\mathscr{L}_{\textsf{FP}}$ are composed of atomic patterns:

###### Definition 4.1.

Atomic Pattern (or Atom) — An atom,
$\alpha\colon\textsf{String}\rightarrow\textsf{Int}$ is a function, which
given a string $s$, returns the length of the longest prefix of $s$ that
satisfies its constraints. Atoms only match non-empty prefixes. $\alpha(s)=0$
indicates match failure of $\alpha$ on $s$.

We allow the following four kinds of atoms in $\mathscr{L}_{\textsf{FP}}$:

  1. (a)

_Constant Strings_ : A $\textsf{Const}_{s}$ atom matches only the string $s$
as the prefix of a given string. For brevity, we denote
$\textsf{Const}_{\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color<EMAIL_ADDRESS>as simply “str” throughout the text.

  2. (b)

_Regular Expressions_ : A $\textsf{RegEx}_{r}$ atom returns the length of the
longest prefix of a given string, that is matched by the regex $r$.

  3. (c)

_Character Classes_ : A $\textsf{Class}^{0}_{c}$ atom returns the length of
the longest prefix of a give string, which contains only characters from the
set $c$. A $\textsf{Class}^{z}_{c}$ atom with $z>0$ further enforces a fixed-
width constraint — the match $\textsf{Class}^{z}_{c}(s)$ fails if
$\textsf{Class}^{0}_{c}(s)$$\neq z$, otherwise it returns $z$.

  4. (d)

_Arbitrary Functions_ : A $\textsf{Funct}_{f}$ atom uses the function $f$ that
may contain arbitrary logic, to match a prefix $p$ of a given string and
returns $|p|$.

$\begin{array}[]{rccl}\textsf{\small
Pattern}&P\,[s]&:=&\texttt{$\texttt{Empty}$(}s\texttt{)}\\\
&&|&P\,[\texttt{$\texttt{SuffixAfter}$(}s,\alpha\texttt{)}]\\\\[6.0pt]
\textsf{\small Atom}&\alpha&:=&\textsf{Class}^{z}_{c}\ |\
\textsf{RegEx}_{r}\\\ &&|&\textsf{Funct}_{f}\ |\
\textsf{Const}_{s}\end{array}$

$\begin{array}[]{ccl}c&\in&\textnormal{power set of characters}\\\
f&\in&\textnormal{functions\;}\textsf{String}\rightarrow\textsf{Int}\\\
r&\in&\textnormal{regular expressions}\\\ s&\in&\textnormal{set of
strings\;}\mathbb{S}\\\ z&\in&\textnormal{non-negative integers}\end{array}$

(a) Syntax of $\mathscr{L}_{\textsf{FP}}$ patterns.

$\begin{array}[]{c}\texttt{$\texttt{Empty}$(}\epsilon\texttt{)}\ \ \Downarrow\
\ \texttt{true}\\\\[15.0pt]
\texttt{$\texttt{SuffixAfter}$(}s,\alpha\texttt{)}\ \ \Downarrow\ \
s_{1}s=s_{0}\circ s_{1}\quad\enskip\alpha(s)=|s_{0}|>0\\\\[18.0pt]
\textsf{Funct}_{f}(s)\ \ \Downarrow\ \ f(s)\\\\[13.0pt]
\textsf{Const}_{s}(s_{0})\ \ \Downarrow\ \ |s||s|>0\quad\enskip s_{0}=s\circ
s_{1}\end{array}$ $\begin{array}[]{c}\textsf{RegEx}_{r}(s)\ \ \Downarrow\ \
\max LL=\\{n\in\mathbb{N}\mid
r\;\triangleright\;s[0\,\boldsymbol{\colon}n]\\}\\\\[15.0pt]
\textsf{Class}^{0}_{c}(s)\ \ \Downarrow\ \ |s_{0}|s=s_{0}\circ
s_{1}\quad\enskip\forall x\in s_{0}\colon x\in<EMAIL_ADDRESS>}{\quad\quad\enskip s_{1}=\epsilon\vee s_{1}[0]\not\in c}\\\\[18.0pt]
\textsf{Class}^{z}_{c}(s)\ \ \Downarrow\ \ zs=s_{0}\circ
s_{1}\quad\quad\forall x\in s_{0}\colon x\in<EMAIL_ADDRESS>}{|s_{0}|=z>0\quad\enskip s_{1}=\epsilon\vee s_{1}[0]\not\in c}\end{array}$

(b) Big-step semantics for $\mathscr{L}_{\textsf{FP}}$ patterns: We use the
judgement $E\ \ \Downarrow\ \ v$ to indicate that the expression $E$ evaluates
to a value $v$.

Figure 16. Formal syntax and semantics of our DSL $\mathscr{L}_{\textsf{FP}}$
for defining syntactic patterns over strings

$a\circ b$ denotes the concatenation of strings $a$ and $b$, and
$r\;\triangleright\;x$ denotes that the regex $r$ matches the string $x$ in
its entirety.

Note that, although both constant strings and character classes may be
expressed as regular expressions, having separate terms for them has two key
benefits:

  * •

As we show in the next subsection, we can _automatically infer_ all constant
strings, and some character class atoms (namely, those having a fixed-width).
This is unlike regular expression or function atoms, which we do not infer and
they must be provided a priori.

  * •

These atoms may leverage more efficient matching logic and do not require
regular expression matching in its full generality. Constant string atoms use
equality checks for characters, and character class atoms use set membership
checks.

We list the default set of atoms provided with FlashProfile, in Fig. 8. Users
may extend this set with new atoms from any of the aforementioned kinds.

###### Example 4.2.

The atom Digit is $\textsf{Class}^{1}_{D}$ with $D=\\{0,\ldots,9\\}$. We write
$\textsf{Class}^{0}_{D}$ as $\textsf{Digit}^{+}$, and $\textsf{Class}^{n}_{D}$
as ${\textsf{Digit}}^{\times n}$ for clarity. Note that,
${\textsf{Digit}}^{\times 2}$ matches “04/23” but not “2017/04”, although
$\textsf{Digit}^{+}$ matches both, since the longest prefix matched, “2017”,
has length $4\neq 2$.

###### Definition 4.3.

Pattern — A pattern is simply a sequence of atoms. The pattern Empty denotes
an empty sequence, which only matches the empty string $\epsilon$. We use the
concatenation operator
“$\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>$”
for sequencing atoms. For $k>1$, the sequence
$\alpha_{1}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\alpha_{2}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\ldots\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\alpha_{k}$
of atoms defines a pattern that is realized by the $\mathscr{L}_{\textsf{FP}}$
expression:

${\small\texttt{$\texttt{Empty}$(}\texttt{$\texttt{SuffixAfter}$(}\cdots\texttt{$\texttt{SuffixAfter}$(}s,\alpha_{1}\texttt{)}\cdots,\alpha_{k}\texttt{)}\texttt{)}},$

which matches a string $s$, iff

$s\neq\epsilon\enskip\textstyle{\bigwedge}\enskip\forall
i\in\\{1,...,k\\}:\alpha_{i}(s_{i})>0\enskip\textstyle{\bigwedge}\enskip
s_{k+1}=\epsilon,$

where $s_{1}\mathrel{\overset{\mathsf{\scriptscriptstyle def}}{=}}s$ and
$s_{i+1}\mathrel{\overset{\mathsf{\scriptscriptstyle
def}}{=}}s_{i}[\alpha_{i}(s_{i})\,\boldsymbol{\colon}]$ is the remaining
suffix of the string $s_{i}$ after matching atom $\alpha_{i}$.

Throughout this section, we use $s[i]$ to denote the $i^{\text{th}}$ character
of $s$, and $s[i\,\boldsymbol{\colon}j]$ denotes the substring of $s$ from the
$i^{\text{th}}$ character, until the $j^{\text{th}}$. We omit $j$ to indicate
a substring extending until the end of $s$. In $\mathscr{L}_{\textsf{FP}}$,
the $\texttt{$\texttt{SuffixAfter}$(}s,\alpha\texttt{)}$ operator computes
$s[\alpha(s)\,\boldsymbol{\colon}]$, or fails with an error if $\alpha(s)=0$.
We also show the formal semantics of patterns and atoms in
$\mathscr{L}_{\textsf{FP}}$, in fig. 16(b).

Note that, we explicitly forbid atoms from matching empty substrings. This
reduces the search space by an exponential factor, since an empty string may
trivially be inserted between any two characters within a string. However,
this does not affect the expressiveness of our final profiling technique,
since a profile uses a disjunction of patterns. For instance, the strings
matching a pattern
$\alpha_{1}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>(\epsilon\;|\;\alpha_{2})\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\alpha_{3}$
can be clustered into those matching
$\alpha_{1}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\alpha_{3}$
and
$\alpha_{1}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\alpha_{2}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\alpha_{3}$.

###  4.2. Synthesis of $\mathscr{L}_{\textsf{FP}}$ Patterns

Our pattern learner $\mathcal{L}_{\textsf{FP}}$ uses inductive program
synthesis (Gulwani et al., 2017) for synthesizing patterns that describe a
given dataset $\mathcal{S}$ using a specified set of atoms $\mho$. For the
convenience of end users, we automatically _enrich_ their specified atoms by
including:  (1) all possible Const atoms, and  (2) all possible fixed-width
variants of all Class atoms specified by them.  Our learner
$\mathcal{L}_{\textsf{FP}}$ is instantiated with these enriched atoms derived
from $\mho$, denoted as $\widehat{\mho}$:

(1) $\begin{array}[]{rl}\widehat{\mho}\ \
\mathrel{\overset{\mathsf{\scriptscriptstyle def}}{=}}\ \
\mho&\cup\quad\\{{\small\textsf{Const}_{s}}\mid s\in\mathbb{S}\\}\\\\[1.0pt]
&\cup\quad\\{{\small\textsf{Class}^{z}_{c}}\mid{\small\textsf{Class}^{0}_{c}}\in\mho\;\bigwedge\;z\in\mathbb{N}\\}\end{array}$

Although $\widehat{\mho}$ is very large, as we describe below, our learner
$\mathcal{L}_{\textsf{FP}}$ efficiently explores this search space, and also
provides a completeness guarantee on patterns possible over $\widehat{\mho}$.

We build on PROSE (Microsoft, 2017d), a state-of-the-art inductive program
synthesis library, which implements the FlashMeta (Polozov and Gulwani, 2015)
framework. PROSE uses _deductive reasoning_ — reducing a problem of
synthesizing an expression to smaller synthesis problems for its
subexpressions, and provides a robust framework with efficient algorithms and
data-structures for this. Our key contribution towards
$\mathcal{L}_{\textsf{FP}}$ are efficient _witness functions_ (Polozov and
Gulwani, 2015, §5.2) that enable PROSE to carry out the deductive reasoning
over $\mathscr{L}_{\textsf{FP}}$.

An inductive program synthesis task is defined by:  (1) a _domain-specific
language_ (DSL) for the target programs, which in our case is
$\mathscr{L}_{\textsf{FP}}$, and  (2) a _specification_ (Polozov and Gulwani,
2015, §3.2) (spec) that defines a set of constraints over the output of the
desired program.  For learning patterns over a collection $\mathcal{S}$ of
strings, we define a spec $\varphi$, that simply requires a learned pattern
$P$ to describe all given strings, i.e. $\forall s\in\mathcal{S}\colon
P(s)=\texttt{True}$. We formally write this as:

$\varphi\mathrel{\overset{\mathsf{\scriptscriptstyle
def}}{=}}\bigwedge_{s\,\in\,\mathcal{S}}\;[s\rightsquigarrow\texttt{True}]$

We provide a brief overview of the deductive synthesis process here, and refer
the reader to FlashMeta (Polozov and Gulwani, 2015) for a detailed discussion.
In a deductive synthesis framework, we are required to define the logic for
reducing a spec for an expression to specs for its subexpressions. The
reduction logic for specs, called witness functions (Polozov and Gulwani,
2015, §5.2), is domain-specific, and depends on the semantics of the DSL.
Witness functions are used to recursively reduce the specs to terminal symbols
in the DSL. PROSE uses a succinct data structure (Polozov and Gulwani, 2015,
§4) to track the valid solutions to these specs at each reduction and generate
expressions that satisfy the initial spec. For $\mathscr{L}_{\textsf{FP}}$, we
describe the logic for reducing the spec $\varphi$ over the two kinds of
patterns: Empty and $P\,[\texttt{$\texttt{SuffixAfter}$(}s,\alpha\texttt{)}]$.
For brevity, we elide the pseudocode for implementing the witness functions —
their implementation is straightforward, based on the reductions we describe
below.

For $\texttt{$\texttt{Empty}$(}s\texttt{)}$ to satisfy a spec $\varphi$, i.e.
describe all strings $s\in\mathcal{S}$, each string $s$ must indeed be
$\epsilon$. No further reduction is possible since $s$ is a terminal. We
simply check, $\forall s\in\mathcal{S}\colon s=\epsilon$, and reject
$\texttt{$\texttt{Empty}$(}s\texttt{)}$ if $\mathcal{S}$ contains at least one
non-empty string.

The second kind of patterns for non-empty strings,
$P\,[\texttt{$\texttt{SuffixAfter}$(}s,\alpha\texttt{)}]$, allows for complex
patterns that are a composition of an atom $\alpha$ and a pattern $P$. The
pattern $P\,[\texttt{$\texttt{SuffixAfter}$(}s,\alpha\texttt{)}]$ contains two
unknowns:  (1) an atom $\alpha$ that matches a non-empty prefix of $s$, and
(2) a pattern $P$ that matches the remaining suffix
$s[\alpha(s)\,\boldsymbol{\colon}]$ . Again, note that this pattern must match
all strings $s\in\mathcal{S}$. Naïvely considering all possible combinations
of $\alpha$ and $P$ leads to an exponential blow up.

First we note that, for a fixed $\alpha$ the candidates for $P$ can be
generated recursively by posing a synthesis problem similar to the original
one, but over the suffix $s[\alpha(s)\,\boldsymbol{\colon}]$ instead of each
string $s$. This reduction style is called a _conditional witness function_
(Polozov and Gulwani, 2015, §5.2), and generates the following spec for $P$
assuming a fixed $\alpha$:

(2) $\varphi_{\alpha}\mathrel{\overset{\mathsf{\scriptscriptstyle
def}}{=}}\bigwedge_{s\,\in\,\mathcal{S}}\;\big{[}s[\alpha(s)\,\boldsymbol{\colon}]\rightsquigarrow\texttt{True}\big{]}$

However, naïvely creating $\varphi_{\alpha}$ for all possible values of
$\alpha$ is infeasible, since our set $\widehat{\mho}$ of atoms is unbounded.
Instead, we consider only those atoms (called _compatible atoms_) that match
some non-empty prefix for _all_ strings in $\mathcal{S}$, since ultimately our
pattern needs to describe all strings. Prior pattern-learning approaches
(Raman and Hellerstein, 2001; Singh, 2016) learn complete patterns for each
individual string, and then compute their intersection to obtain patterns
consistent with the entire dataset. In contrast, we compute the set of atoms
that are compatible with the entire dataset at each step, which allows us to
generate this intersection in an incremental manner.

###### Definition 4.4.

Compatible Atoms — Given a universe $\mho$ of atoms, we say a subset
$A\subseteq\mho$ is compatible with a dataset $\mathcal{S}$, denoted as
$A\propto\mathcal{S}$, if all atoms in $A$ match each string in $\mathcal{S}$,
i.e.

$A\propto\mathcal{S}\quad\textnormal{iff}\quad\forall\,\alpha\in
A\,\colon\;\forall\,s\in\mathcal{S}\,\colon\;\alpha(s)>0$

We say that a compatible set $A$ of atoms is _maximal_ under the given
universe $\mho$, denoted as
$A\,=\;\max^{\mho}_{\propto}[\scalebox{0.9}{$\mathcal{S}$}]$ iff
$\forall\,X\subseteq\mho\,\colon\;X\propto\mathcal{S}\Rightarrow X\subseteq
A$.

###### Example 4.5.

Consider a dataset with Canadian postal codes: $\mathcal{S}$ = { “V6E3V6”,
“V6C2S6”, “V6V1X5”, “V6X3S4” }. With $\mho=$ the default atoms (listed in Fig.
8), we obtain the enriched set $\widehat{\mho}$ using Equation 1. Then, the
maximal set of atoms compatible with $\mathcal{S}$ under $\widehat{\mho}$,
i.e. $\max^{\widehat{\mho}}_{\propto}[\scalebox{0.9}{$\mathcal{S}$}]$ contains
$18$ atoms, such as “V6”, “V”, Upper, $\textsf{Upper}^{+}$, AlphaSpace,
${\textsf{AlphaDigit}}^{\times 6}$, etc.

func
GetMaxCompatibleAtoms($\mathcal{S}\colon\textsf{String}[\,],\mho\colon\textsf{Atom}[\,]$)

output: The maximal set of atoms that are compatible with $\mathcal{S}$

$1\,\cdot$$C\leftarrow\\{\\}\ ;\ \Lambda\leftarrow\mho$ $2\,\cdot$for all
$s\in\mathcal{S}$ do $3\,\cdot$ for all $\alpha\in\Lambda$ do $4\,\cdot$
$\blacktriangleright$ Remove incompatible atoms. $5\,\cdot$ if $\alpha(s)=0$
then $\Lambda.\textsf{Remove}(\alpha)\ ;\ C.\textsf{Remove}(\alpha)$
$6\,\cdot$ else if $\alpha\in\texttt{Class}$ then $7\,\cdot$
$\blacktriangleright$ Check if character class atoms maintain a fixed width.
$8\,\cdot$ if $\alpha\not\in C$ then $C[\alpha]\leftarrow\alpha(s)$ $9\,\cdot$
else if $C[\alpha]\neq\alpha(s)$ then $C.\textsf{Remove}(\alpha)$ $10\,\cdot$
$\blacktriangleright$ Add compatible fixed-width Class atoms. $11\,\cdot$for
all $\alpha\in C$ do
$\Lambda.\textsf{Add}(\textsc{RestrictWidth}(\alpha,C[\alpha]))$ $12\,\cdot$
$\blacktriangleright$ Add compatible Const atoms.
$13\,\cdot$$L\leftarrow\textsc{LongestCommonPrefix}(\mathcal{S})$
$14\,\cdot$$\Lambda.\textsf{Add}(\textsf{Const}_{L[0\,:\,1]},\,\textsf{Const}_{L[0\,:\,2]},\,\dots,\,\textsf{Const}_{L})$
$15\,\cdot$return $\Lambda$

Figure 17. Computing the maximal set of compatible atoms

For a given universe $\mho$ of atoms and a dataset $\mathcal{S}$, we invoke
the GetMaxCompatibleAtoms method outlined in Fig. 17 to efficiently compute
the set
$\Lambda=\max^{\widehat{\mho}}_{\propto}[\scalebox{0.9}{$\mathcal{S}$}]$,
where $\widehat{\mho}$ denotes the enriched set of atoms based on $\mho$ given
by Equation 1. Starting with $\Lambda=\mho$, in line 1, we iteratively remove
atoms from $\Lambda$, that are not compatible with $\mathcal{S}$, i.e. fail to
match at least one string $s\in\mathcal{S}$, at line 4. At the same time, we
maintain a hashtable $C$, which maps each Class atom to its width at line 6.
$C$ is used to enrich $\mho$ with fixed-width versions of Class atoms that are
already specified in $\mho$. If the width of a Class atom is not constant over
all strings in $\mathcal{S}$, we remove it from our hashtable $C$, at line 7.
For each remaining Class atom $\alpha$ in $C$, we add a fixed-width variant
for $\alpha$ to $\Lambda$. In line 8, we invoke RestrictWidth to generate the
fixed-width variant for $\alpha$ with width $C[\alpha]$. Finally, we also
enrich $\Lambda$ with Const atoms — we compute the longest common prefix $L$
across all strings, and add every prefix of $L$ to $\Lambda$, at line 12. Note
that, GetMaxCompatibleAtoms does not explicitly compute the entire set
$\widehat{\mho}$ of enriched atoms, but performs simultaneous pruning and
enrichment on $\mho$ to ultimately compute their maximal compatible subset,
$\Lambda=\max^{\widehat{\mho}}_{\propto}[\scalebox{0.9}{$\mathcal{S}$}]$.

In essence, the problem of learning an expression
$P\,[\texttt{$\texttt{SuffixAfter}$(}s,\alpha\texttt{)}]$ with spec $\varphi$
is reduced to
$\big{|}\\!\max^{\widehat{\mho}}_{\propto}[\scalebox{0.9}{$\mathcal{S}$}]\big{|}$
subproblems for $P$ with specs
$\\{\varphi_{\alpha}\mid\alpha\in\max^{\widehat{\mho}}_{\propto}[\scalebox{0.9}{$\mathcal{S}$}]\\}$,
where $\varphi_{\alpha}$ is as given by Equation 2, and $\widehat{\mho}$
denotes the enriched set of atoms derived from $\mho$ by Equation 1. Note that
these subproblems are recursively reduced further, until we match all
characters in each string, and terminate with Empty. Given this reduction
logic as witness functions, PROSE performs these recursive synthesis calls
efficiently, and finally combines the atoms to candidate patterns. We conclude
this subsection with a comment on the soundness and completeness of
$\mathcal{L}_{\textsf{FP}}$.

###### Definition 4.6.

Soundness and $\mho$-Completeness — We say that a learner for
$\mathscr{L}_{\textsf{FP}}$ patterns is _sound_ if, for any dataset
$\mathcal{S}$, every learned pattern $P$ satisfies $\forall
s\in\mathcal{S}:P(s)=\texttt{True}$.

We say that a learner for $\mathscr{L}_{\textsf{FP}}$, instantiated with a
universe $\mho$ of atoms is _$\mho$ -complete_ if, for any dataset
$\mathcal{S}$, it learns every possible pattern
$P\in\mathscr{L}_{\textsf{FP}}$ over $\mho$ atoms that satisfy $\forall
s\in\mathcal{S}:P(s)=\texttt{True}$.

###### Theorem 4.7 (Soundness and $\widehat{\mho}$-Completeness of
$\mathcal{L}_{\textsf{FP}}$).

For an arbitrary set $\mho$ of user-specified atoms, FlashProfile’s pattern
learner $\mathcal{L}_{\textsf{FP}}$ is sound and $\widehat{\mho}$-complete,
where $\widehat{\mho}$ denotes the enriched set of atoms obtained by
augmenting $\mho$ with constant-string and fixed-width atoms, as per Equation
1.

###### Proof.

Soundness is guaranteed since we only compose compatible atoms.
$\widehat{\mho}$-completeness follows from the fact that we always consider
the _maximal_ compatible subset of $\widehat{\mho}$. ∎

Due to the $\widehat{\mho}$-completeness of $\mathcal{L}_{\textsf{FP}}$, once
the set $\mathcal{L}_{\textsf{FP}}(\mathcal{S})$ of patterns over
$\mathcal{S}$ has been computed, a variety of cost functions may be used to
select the most suitable pattern for $\mathcal{S}$ amongst all possible
patterns over $\widehat{\mho}$, without having to invoke pattern learning
again.

###  4.3. Cost of Patterns in $\mathscr{L}_{\textsf{FP}}$

Our cost function $\mathcal{C}_{\textsf{FP}}$ assigns a real-valued score to
each pattern $P\in\mathscr{L}_{\textsf{FP}}$ over a given dataset
$\mathcal{S}$, based on the structure of $P$ and its behavior over
$\mathcal{S}$. This cost function is used to select the most desirable pattern
that represents the dataset $\mathcal{S}$. Empty is assigned a cost of $0$
regardless of the dataset, since Empty can be the only pattern consistent with
such datasets. For a pattern
$P=\alpha_{1}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\ldots\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\alpha_{k}$,
we define the cost $\mathcal{C}_{\textsf{FP}}(P,\mathcal{S})$ with respect to
a given dataset $\mathcal{S}$ as:

$\mathcal{C}_{\textsf{FP}}(P,\mathcal{S})=\sum_{i=1}^{k}Q(\alpha_{i})\cdot
W(i,\mathcal{S}\mid P)$

$\mathcal{C}_{\textsf{FP}}$ balances the trade-off between a pattern’s
specificity and complexity. Each atom $\alpha$ in $\mathscr{L}_{\textsf{FP}}$
has a statically assigned cost $Q(\alpha)\in(0,\infty]$, based on a priori
bias for the atom. Our cost function $\mathcal{C}_{\textsf{FP}}$ computes a
sum over these static costs after applying a data-driven weight
$W(i,\mathcal{S}\mid P)\in(0,1)$:

$W(i,\mathcal{S}\mid\alpha_{1}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\ldots\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\alpha_{k})=\frac{1}{|\mathcal{S}|}\cdot\sum_{s\,\in\,\mathcal{S}}\frac{\alpha_{i}(s_{i})}{|s|},$

where $s_{1}\mathrel{\overset{\mathsf{\scriptscriptstyle def}}{=}}s$ and
$s_{i+1}\mathrel{\overset{\mathsf{\scriptscriptstyle
def}}{=}}s_{i}[\alpha_{i}(s_{i})\,\boldsymbol{\colon}]$ denotes the remaining
suffix of $s_{i}$ after matching with $\alpha_{i}$, as in Definition 4.3. This
dynamic weight is an average over the fraction of length matched by
$\alpha_{i}$ across $\mathcal{S}$. It gives a quantitative measure of how well
an atom $\alpha_{i}$ generalizes over the strings in $\mathcal{S}$. With a
sound pattern learner, an atomic match would never fail and
$W(i,\mathcal{S}\mid P)>0$ for all atoms $\alpha_{i}$.

###### Example 4.8.

Consider
$\mathcal{S}={\small\\{\,\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{Male}''}},\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{Female}''}}\,\\}}$,
that are matched by
$P_{1}=\textsf{Upper}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textsf{Lower}^{+}$,
and
$P_{2}=\textsf{Upper}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textsf{Hex}\>\,{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\mathbin{\mathchoice{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}{\vbox{\hbox{$\scriptscriptstyle\diamond$}}}}}\,\>\textsf{Lower}^{+}$.
Given FlashProfile’s static costs: $\\{\textsf{Upper}\mapsto
8.2,\;\textsf{Hex}\mapsto 26.3,\;\textsf{Lower}^{+}\mapsto 9.1\\}$, the costs
for these two patterns shown above are:

$\begin{split}\mathcal{C}_{\textsf{FP}}(P_{1},\mathcal{S})\;&=\;8.2\times\frac{\nicefrac{{1}}{{4}}+\nicefrac{{1}}{{6}}}{2}\,+\,9.1\times\frac{\nicefrac{{3}}{{4}}+\nicefrac{{5}}{{6}}}{2}\;=\;8.9\\\
\mathcal{C}_{\textsf{FP}}(P_{2},\mathcal{S})\;&=\;8.2\times\frac{\nicefrac{{1}}{{4}}+\nicefrac{{1}}{{6}}}{2}\,+\,26.3\times\frac{\nicefrac{{1}}{{4}}+\nicefrac{{1}}{{6}}}{2}\,+\,9.1\cdot\frac{\nicefrac{{2}}{{4}}+\nicefrac{{4}}{{6}}}{2}\;=\;12.5\end{split}$

$P_{1}$ is chosen as best pattern, since
$\mathcal{C}_{\textsf{FP}}(P_{1},\mathcal{S})<\mathcal{C}_{\textsf{FP}}(P_{2},\mathcal{S})$.

Note that although Hex is a more specific character class compared to Upper
and Lower, we assign it a higher static cost to avoid strings like “face”
being described as ${\textsf{Hex}}^{\times 4}$ instead of
${\textsf{Lower}}^{\times 4}$. ${\textsf{Hex}}^{\times 4}$ would be chosen
over ${\textsf{Lower}}^{\times 4}$ only if we observe some other string in the
dataset, such as “f00d”, which cannot be described using
${\textsf{Lower}}^{\times 4}$.

#### Static Cost ($Q$) for Atoms

Our learner $\mathcal{L}_{\textsf{FP}}$ automatically assigns the static cost
of a $\textsf{Const}_{s}$ atom to be proportional to  $\nicefrac{{1}}{{|s|}}$
, and the cost of a $\textsf{Class}^{z}_{c}$ atom, with width $z\geqslant 1$,
to be proportional to  $\frac{Q(\textsf{Class}^{0}_{c})}{z}$ . However, static
costs for other kinds of atoms must be provided by the user.

Static costs for our default atoms, listed in Fig. 8, were seeded with the
values based on their estimated _size_ — the number of strings the atom may
match. Then they were penalized (e.g. the Hex atom) with empirically decided
penalties to prefer patterns that are more _natural_ to users. We describe our
_quality_ measure for profiles in § 5.2, which we have used to decide the
penalties for the default atoms. In future, we plan to automate the process of
penalizing atoms by designing a learning procedure which tries various
perturbations to the seed costs to optimize profiling quality.

##  5\. Evaluation

We now present experimental evaluation of the FlashProfile tool which
implements our technique, focusing on the following key questions:

  * ( § 5.1 )

How well does our syntactic similarity measure capture similarity over real
world entities?

  * ( § 5.2 )

How accurate are the profiles? How do sampling and approximations affect their
quality?

  * ( § 5.3 )

How fast is FlashProfile, and how does its performance depend on the various
parameters?

  * ( § 5.4 )

Are the profiles natural and useful? How do they compare to those from
existing tools?

#### Implementation

We have implemented FlashProfile as a cross-platform C# library built using
Microsoft PROSE (Microsoft, 2017d). It is now publicly available as part of
the PROSE NuGet package. FlashProfile has been publicly released as the
Matching.Text module within the PROSE library. For more information, please
see: https://microsoft.github.io/prose/documentation/matching-text/intro/. All
of our experiments were performed with PROSE 2.2.0 and .NET Core 2.0.0, on an
Intel i7 3.60 GHz machine with 32 GB RAM running 64-bit Ubuntu 17.10.

Figure 18. Number and length of strings across datasets5

#### Test Datasets

We have collected $75$ datasets from public sources, All public datasets are
available at:
https://github.com/SaswatPadhi/FlashProfileDemo/tree/master/tests. spanning
various domains such as names, dates, postal codes, phone numbers, etc. Their
sizes and the distribution of string lengths is shown in Fig. 18. We sort them
into three (overlapping) groups:

  * •

Clean (25 datasets): Each of these datasets, uses a _single format_ that is
_distinct_ from other datasets. We test syntactic similarity over them —
strings from the same dataset must be labeled as similar.

  * •

Domains (63 datasets): These datasets belong to _mutually-distinct domains_
but may exhibit multiple formats. We test the quality of profiles over them —
a profile learned over fraction of a dataset should match rest of it, but
should not be too general as to also match other domains.

  * •

All (75 datasets): We test FlashProfile’s performance across all datasets.

###  5.1. Syntactic Similarity

We evaluate the applicability of our dissimilarity measure from Definition
3.1, over real-life entities. From our Clean group, we randomly pick two
datasets and select a random string from each. A good similarity measure
should recognize when the pair is drawn from the same dataset by assigning
them a lower dissimilarity value, compared to a pair from different datasets.
For example, the pair { “A. Einstein”, “I. Newton” } should have a lower
dissimilarity value than { “A. Einstein”, “03/20/1998” }. We instantiated
FlashProfile with only the default atoms listed in Fig. 8 and tested $240400$
such pairs. Fig. 19 shows a comparison of our method against two simple
baselines:  (1) a character-wise edit-distance-based similarity measure
(JarW), and  (2) a machine-learned predictor ($RF$) over intuitive syntactic
features.

For evaluation, we use the standard precision-recall (PR) (Manning et al.,
2008) measure. In our context, precision is the fraction of pairs that truly
belongs to the same dataset, out of all pairs that are labeled to be “similar”
by the predictor. Recall is the fraction of pairs retrieved by the predictor,
out of all pairs truly drawn from same datasets. By varying the threshold for
labelling a pair as “similar”, we generate a PR curve and measure the area
under the curve (AUC). A good similarity measure should exhibit high precision
and high recall, and therefore have a high AUC.

(a) Precision-Recall curves $\Delta[\texttt{len}]$
---
$\Delta[\texttt{cnt}\langle\textsf{Digit}\rangle]$
$\Delta[\texttt{cnt}\langle\textsf{Lower}\rangle]$
$\Delta[\texttt{cnt}\langle\textsf{Upper}\rangle]$
$\Delta[\texttt{cnt}\langle\;\textsf{\\!{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}\,\textvisiblespace\,}\\!}\,\rangle]$
$\Delta[\texttt{cnt}\langle\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color<EMAIL_ADDRESS>
$\Delta[\texttt{cnt}\langle\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color@gray@fill{0.36}``{,}''}}\rangle]$
$\Delta[\texttt{cnt}\langle\textnormal{{\color[rgb]{0.36,0.36,0.36}\definecolor[named]{pgfstrokecolor}{rgb}{0.36,0.36,0.36}\pgfsys@color@gray@stroke{0.36}\pgfsys@color<EMAIL_ADDRESS>
$\texttt{begin}\langle\textsf{Upper}\rangle$
$\texttt{begin}\langle\textsf{Lower}\rangle$
$\texttt{begin}\langle\textsf{Digit}\rangle$
(b) Features

_Predictor_ |  FP |  JarW |  $RF_{1}$ |  $RF_{2}$ |  $RF_{3}$
---|---|---|---|---|---
_AUC_ |  96.28% |  35.52% |  91.73% |  98.71% |  76.82%