proposal: fuzzy matching

1 files changed, 430 insertions, 0 deletions

diff --git a/proposals/2020_fuzzy_matching.md b/proposals/2020_fuzzy_matching.md
new file mode 100644
index 00000000..30c321e3
--- /dev/null
+++ b/proposals/2020_fuzzy_matching.md
@@ -0,0 +1,430 @@
+
+Status: planned
+
+Bibliographic Entity Fuzzy Match and Verification
+====================================================
+
+This document summarizes work so far on entity "fuzzy matching" and match
+verification, notes some specific upcoming use cases for such methods, and
+proposes new generic routines to be implemented.
+
+There are three main routines desired:
+
+**Match verification:** given two bibliographic metadata records (or two entire
+entities), confirm whether they refer to the exact same version of the entity.
+Optionally, also determine if they are not the exact same entity, but are
+variations of the same entity (eg, releases that should be grouped under a
+shared work entity). Performance is not as critical as correctness. Should be a
+pure, in-memory routine (not touch the network or external services).
+
+**Fuzzy matching:** of bibliographic metadata to entity in current/live Fatcat
+catalog. Eg, given complete or partial metadata about a paper or other entity,
+return a list of candidate matches. Emphasis on recall over precision; better
+to return false matches than missed records. This would likely hit the fatcat
+elasticsearch indexes (search.fatcat.wiki), which are continuously updated to
+be in sync with the catalog itself (API). Expected to scale to, eg, 5-10
+lookups per second and operate over up to a couple million entities during
+cleanup or merging operations. Should operate per record, on-demand, always
+up-to-date (aka, not a batch process).
+
+**Bulk fuzzy match:** a tool capable of matching hundreds or billions of raw
+metadata records against the entire fatcat catalog, resulting in candidate
+fuzzy match pairs or groupings. The two main applications are de-duplicating or
+grouping releases over the entire catalog (aka, matching the catalog against
+itself), matching billions of citations (structured partial metadata) against
+release entities, and grouping citations which fail to match to existing
+entities against each other. Likely to include a batch mode, though may also
+include an efficient per-record lookup API as well.
+
+As a terminology note, the outputs of a fuzzy match are called "candidate
+matches", and the output of match verificatino would be "confirmed match" or
+"confident match". A "self-match" is when an exact complete entity is compared
+to a set it already exists in, and matches to itself (aka, fatcat entity
+identifier is exact match). "Identifier matches" are an easy case when external
+identifiers (like DOI, ISSN, ORCID) are used for matching; note that the Fatcat
+lookup API always returns the first such match, when there may actually be
+multiple entities with the same external identifier, so this may not always be
+sufficient.
+
+
+## Container Matching
+
+Containers are a simpler case, so will discuss those first. Function signatures
+would look like:
+
+    verify_container_match(left:container, right:container) -> status:str
+    match_container_fuzzy(record:??) -> [candidate:container]
+
+Verify statuses could be:
+
+- `exact`: all metadata fields match byte-for-byte
+- `strong`: good confidence these are the same
+- `weak`: could be a match, perhaps missing enough metadata to be confident
+- `ambiguous`: not enough confidence that is or even isn't a match
+- `not-match`: confident that these are *not* the same container (TODO: better word?)
+
+Alternatively, could return a confidence floating point number, but that puts
+burdern of interpretation on external code.
+
+Fields of interest would be at least:
+
+- name
+- original name
+- aliases
+- publisher
+- abbrev
+
+Some test cases that match verification should probably handle (just making
+these up):
+
+- differences in title whitespace and capitalization
+- title of one record has ISSN appended ("PLOS One" matches "PLOS One
+  1932-6203")
+- title of one record has publisher appended ("PLOS One" matches "PLOS One
+  (Public Library of Science)")
+- record with original (non-English) name in name field matches fatcat record
+  where the non-Enlish title is in `original_title` field
+- difference of "The" doesn't matter ("Lancet" matches "The Lancet")
+- detect and reject bogus names
+
+Nice to haves:
+
+- records with only abbreviation or acroynm match (for "official" abbreviations
+  and acronyms, which may need to be recorded as alias).
+- records of full name match when the "official" title is now an acroynum (eg,
+  "British Medical Journal" matches "The BMJ")
+- optionally, detect and return `ambiguous` for a fixed list of known-ambiguous
+  names (eg, two journals with very similar titles, name or acronym along can't
+  distinguish)
+
+Can't remember if we already have aliases stored in container entity `extra`
+yet, but idea is to store "also known as" names to help with fuzzy matching.
+
+The main application of these routines would be adding container linkage to
+releases where we have a container name but no identifier (eg, an ISSN). We
+have millions of releases (many with DOIs) that have a container name but no
+linked container. We also want to import millions of papers based on GROBID
+metadata alone, where we will likely only extract a journal name, and will want
+to do lookups on that.
+
+For the particular case of containers, we'll probably want to memoize results
+(aka, cache lookups) for efficiency. Probably will also want a unified helper
+function like:
+
+    match_container(name:str, **kwargs) -> (status:str, match:Option<container>)
+
+which would handle caching (maybe this is a class/object not a function?), call
+`match_container_fuzzy()` to get candidates, call `verify_container_match()` on
+each candidate, and ensure there is only one `exact` or `strong` match. Eg, if
+there are multiple `weak` matches, should return `ambiguous` for the group
+overall.
+
+Another speculative application of these routines could be as part of chocula,
+to try and find "true" ISSNs for records where we know the ISSN is not
+registered or invalid (eg, ISSN checksum digit fails). Another would be to look
+for duplicate container/ISSNs, where there are multiple ISSNs for the same
+journal but only one has any papers actually published; in that case we would
+maybe want to mark the other container entity as a "stub".
+
+Test datasets:
+
+- in kibana/ES, filter for "`container_id` does not exist" and
+  "`container_name` exists"
+- in sandcrawler, dump `grobid` table and look in the metadata snippet, which
+  includes extracted journal info
+
+
+## Release Matching (verification and fuzzy, not bulk fuzzy)
+
+For release entities, the signature probably looks something like:
+
+    verify_release_match(left:release, right:release) -> status:str
+        how confident, based on metadata, that these are same release, or
+        should be grouped under same work?
+    exact_release_match(left:release, right:release) -> bool
+    exact_work_match(left:release, right:release) -> bool
+
+Instead of full release entities, we could use partial metadata in the form of
+a python dataclass or named tuple. If we use a struct, will need a routine to
+convert full entities to the partial struct; if we use full entities, will
+probably want a helper to construct entities from partial metadata.
+
+Don't know which fields would be needed, but guessing at least the following,
+in priority order:
+
+- if full entity: `ident` (and `work_id` for case of releases)
+- `title`
+- `authors` (at least list of surnames, possibly also raw and given names)
+- `ext_ids`
+- `release_year` (and full `release_date` if available)
+- volume, issue, pages
+- `subtitle`
+- `original_title`
+- container name (and `container_id` if available)
+- `release_type` and `release_stage` (particularly for work/release grouping
+  vs. match)
+
+For releases, the "status" output could be:
+
+- `strong` (good confidence)
+- `weak` (seems good, but maybe not enough metadata to be sure)
+- `work-strong` (good confidence that same work, but not same release)
+- `work-weak`
+- `ambiguous`
+- `not-match` (name?)
+
+Cases we should handle:
+
+- ability to filter out self-matches from fuzzy matcher. Eg, if we want to find
+  a duplicate of an existing release, should be able to filter out self-match
+  (as a kwarg?)
+- ability to filter out entire categories of matches. eg, match only to
+  published works (`release_stage`), only to papers (`release_type`), only not
+  match to longtail OA papers (`is_longtail_oa` ES flag)
+- have an in-memory stoplist for ambiguous titles (eg, "abstract", "index")
+- differences in punctuation, capitalization
+- single-character typos
+- subtitle/title matching (eg: {title: "Important Research", subtitle: "A
+  History"} should match {title: "Important Research: A History", subtitle:
+  None})
+- record with only one author, surname only should be able to match against
+  full author list. maybe a flag to indicate this case? eg, for matching some
+  citation styles where only one author is listed
+- years are +/- 1. certainly for pre-prints ("work matches"), but also
+  different databases sometimes have different semantics about whether
+  "publication date" or "submission date" or "indexed date" are used as the
+  `release_date` (which we consider the "publication date"). Maybe "weak" match
+  in this case
+- (probably a lot more i'm not thinking of)
+
+Nice to have (but harder?):
+
+- journal/container matching where one side has an abbreviation, acronym, or
+  alias of the other. does this require a network fetch? maybe cached or
+  pre-loaded? may not be important, do testing first. Note that entire
+  container entity is transcluded when doing full release entity API lookups.
+  This may be important for citation matching/verification
+
+Will probably want a helper function to check that a metadata record (or
+entity) has enough metadata and seems in-scope for matching. For example, a
+record with title of just "Abstract" should probably be blocked from any match
+attempt, because there are so many records with that metadata. On the other
+hand, if there is an external identifier (eg, DOI), could still attempt a
+direct match. Maybe something like:
+
+    can_verify_match(release:release) -> boolean
+
+Test datasets:
+
+- PDFs crawled as part of longtail OA crawls (see context below). We have both
+  fatcat release already imported, and new GROBID-extracted works. Can use
+  glutton fuzzy matching for comparison, or verify those glutton matches
+- many, many unmatched reference strings. will do separate
+
+Optionally, we could implement a glutton-compatible API with equivalent or
+better performance for doing GROBID "header consolidation". If performance is
+great, could even use it for reference conslidation at crawl/ingest time.
+
+
+## Bulk Fuzzy
+
+Current concept for this is to implement Semantic Scholar's algorithm
+(described below) in any of python, golang, or rust, to function for all these
+use-cases:
+
+- grouping releases in fatcat which are variants of the same work (or, eg,
+  publisher registered multiple DOIs for same paper by accident) into the same
+  work
+- reference matching from structured partial metadata to fatcat releases
+- grouping of unmatched references (from reference matching) as structured
+  partial metadata, with the goal of finding, eg, the "100,000 most cited
+  papers which do not have a fatcat entity", and creating fatcat entities for
+  them
+
+Optionally, we could also architect/design this tool to replace biblio-glutton
+for ingest-time "reference consolidation", by exposing a biblio-glutton
+compatible API. If this isn't possible or hard it could become a later tool
+instead. Eg, shouldn't sacrafice batch performance for this. In particular, for
+ingest-time reference matching we'd want the backing corpus to be updated
+continuously, which might be tricky or in conflict with batch-mode design.
+
+## Existing Fatcat Work
+
+### Hadoop matching pipeline
+
+In Summer 2018, the fatcat project had a wonderful volunteer, Ellen Spertus.
+Ellen implemented a batch fuzzy matching pipeline in Scala (using the Scalding
+map/reduce framework) that ran on our Hadoop cluster. We used it to "join"
+GROBID metadata from PDF files against a Crossref metadata dump.
+
+The Scala job worked by converting input metadata records into simple "bibjson"
+metadata subsets (plus keeping the original record identifiers, eg Crossref DOI
+or PDF file hash, for later import). It created a key for each record by
+normalizing the title (removing all whitespace and non-alphanumeric characters,
+lower-casing, etc; we called this a "slug"), and filtering out keys from a
+blocklist. We used the map/reduce framework to then join the two tables on
+these keys, and then filtered the output pairs with a small bit of addiitonal
+title similarity comparison logic, then dumped the list of pairs as a table to
+Hadoop, sorted by join key (slug). I can't remember if we had any other
+heuristics in the Scala code.
+
+This was followed by a second processing stage in python, which iterated over
+the full list. It grouped pairs by key, and discarded any groups that had too
+many pairs (on the assumption that the titles were too generic). It then ran
+additional quality checks (much easier/faster to implement in python) on year,
+author names (eg, checking that the number of authors matched). The output of
+this filtering was then fed into a fatcat importer which matched the PDFs to
+releases based on DOI.
+
+We got several million matches using this technique. In the end we really only
+ran this pipeline once. Hadoop (and HBase in particular) ended up being
+frustrating to work with, as jobs took hours or days to run, and many bugs
+would only appear when run against the full dataset. A particular problem that
+came up with the join approach was N^2 explosions for generic titles, where the
+number of join rows would get very large (millions of rows) for generic titles,
+even after we filtered out the top couple hundred most popular join keys.
+
+TODO: should update this section with specific algorithms and parameters used by
+reading the Scala and Python source
+
+## Longtail OA Import Filtering
+
+Not direcly related to matching, but filtering mixed-quality metadata.
+
+As part of Longtail OA preservation work, we ran a crawl of small OA journal
+websites, and then ran GROBID over the resulting PDFs to extract metadata. We
+then filtered the output metadata using quality heuristics, then inserted both
+new releases (with no external identifiers, just the extracted metadata) and
+the associated file.
+
+The metadata filtering pipeline is interesting because of all the bad metadata
+it detected. Eg, long titles, used the normalization and blocklist from the
+Hadoop matching work, poor author metadata, etc.
+
+A big problem that was only noticed after this import was that actually many of
+the papers imported were duplicates of existing fatcat papers with DOIs or
+other identifiers. This was because the crawl ended up spidering some general
+purpose repositories, which contained copies of large-publisher OA papers (eg,
+PLOS papers). The solution to this will use fuzzy matching in two ways. First,
+for future imports of this type, we will fuzzy matches against the catalog to
+check that there isn't already a metadata record; possibly link the file to
+matched existing entities (based on confidence), but certainly don't create new
+records unless sure that there isn't an existing one (`no-match`). Also need to
+ensure there are not duplicates *within* each import batch, but either running
+the import slowly in a single thread (so elasticsearch and the matching system
+has time to synchronize), or doing a batch fuzzy match first. Or possibly some
+other pre-filtering idea. Secondly, we can go back over these longtail OA works
+(which are tagged as such in the fatcat catalog) and attempt to match them
+against non-longtail fatcat releases (eg, those with existing PMID or DOI), and
+merge the releases together (note: redirecting the longtail release to the full
+one, resulting in a single release, not just doing work grouping of releases).
+
+A separate problem from this import is that none of the papers have container
+linkage (though many or all have container names successfully extracted). After
+doing release-level merging, we should use container fuzzy matching to update
+container linkage for these entities. We could potentially do this as a two
+stage project where we dump all the container name strings, prioritize them by
+release count, and iterate on container matching until we are happy with the
+results, then run the actual release updates.
+
+### biblio-glutton
+
+[biblio-glutton][biblio-glutton] is a companion tool for GROBID to do record
+matching and metadata enrichment of both "header" metadata (aka, extracted
+metadata about the fulltext paper in the PDF itself) and references (extracted
+from the reference/bibliography section of the fulltext paper). GROBID calls
+this "consolidation".
+
+biblio-glutton supports a couple different metadata index sources, including
+Crossref dumps. IA has patched both GROBID and biblio-glutton to work with
+fatcat metadata directly, and to embed fatcat release identifiers in output
+TEI-XML when there is a match. We have found performance to be fine for header
+consolidation, but too slow for reference consolidation. This is because there
+is only one glutton lookup per PDF for header mode, vs 20-50 lookups per PDF for
+reference consolidation, which takes longer than the overall PDF extraction. In
+our default configuration, we only do header consolidation.
+
+biblio-glutton runs as a REST API server, which can be queried separately from
+the GROBID integration. It uses the JVM (can't remember if Java or Scala), and
+works by doing an elasticsearch query to find candidates, then selects the best
+candidate (if any) and looks up full metadata records from one or more LMDB
+key/value databases. It requires it's own elasticsearch index with a custom
+schema, and large LMDB files on disk (should be SSD for speed). The process of
+updating the LMDB files and elasticsearch index are currently manual (with some
+scripts), generated using bulk metadata fatcat dumps. This means the glutton
+results get out of sync from the fatcat catalog.
+
+The current update process involves stopping glutton (which means stopping all
+GROBID processing) for a couple hours. Compare this to the fatcat search index
+(search.fatcat.wiki), which is continuously updated from the changelog feed,
+and even during index schema changes has zero (or near zero) downtime.
+
+[biblio-glutton]: https://github.com/kermitt2/biblio-glutton
+
+## Existing External Work and Reading
+
+"The Lens MetaRecord and LensID: An open identifier system for aggregated
+metadata and versioning of knowledge artefacts"
+<https://osf.io/preprints/lissa/t56yh/>
+
+
+### Semantic Scholar
+
+Semantic Scholar described their technique for doing bulk reference matching
+and entity merging, summarized here:
+
+Fast candidate lookups are done using only a subset of the title. Title strings
+are turned in to an array of normalized tokens (words), with stopwords (like
+"a", "the") removed. Two separate indices are created: one with key as the the
+first three tokens, and the other with the key as the last three tokens. For
+each key, there will be a bucket of many papers (or just paper global
+identifiers). A per-paper lookup by title will fetch candidates from both
+indices. It is also possible to iterate over both indices by bucket and doing
+further processing between all the papers, then combined the matches/groups
+from both iterations. The reason for using two indices is to be robust against
+mangled metadata where there is added junk or missing words at either the
+begining or end of the title.
+
+To verify candidate pairs, the Jaccard similarity is calculated between the
+full original title strings. This flexibly allows for character typos (human or
+OCR), punctuation differences, and for longer titles missing or added words.
+Roughly, the amount of difference is proportional to the total length of the
+strings, so short titles must be a near-exact match, while long titles can have
+entire whole words different.
+
+In addition to the title similarity check, only the first author surnames and
+year of publication are further checked as heuristics to confirm matches. If I
+recall correctly, not even the journal name is is compared. They have done both
+performance and correctness evaluation of this process and are happy with the
+results, particularly for reference matching.
+
+My (Bryan) commentary on this is that it is probably a good thing to try
+implementing for bulk fuzzy candidate generation. I have noticed metadata
+issues on Semantic Scholar with similarly titles papers getting grouped, or
+fulltext PDF copies getting matched to the wrong paper. I think for fatcat we
+should be more conservative, which we can do in our match verification
+function.
+
+### Crossref
+
+Crossref has done a fair amount of work on the reference matching problem and
+detecting duplicate records. In particular, Dominika Tkaczyk has published a
+number of papers and blog posts:
+
+    https://fatcat.wiki/release/search?q=author%3A%22Dominika+Tkaczyk%22
+    https://www.crossref.org/authors/dominika-tkaczyk/
+
+Some specific posts:
+
+"Double trouble with DOIs"
+<https://www.crossref.org/blog/double-trouble-with-dois/>
+
+"Reference matching: for real this time"
+<https://www.crossref.org/blog/reference-matching-for-real-this-time/>
+
+Java implementation and testing/evaluation framework for their reference
+matcher:
+
+- <https://gitlab.com/crossref/search_based_reference_matcher>
+- <https://gitlab.com/crossref/reference_matching_evaluation_framework>
+