dataesr/scientific-paragraphs-categorization huggingface dataset:
KS is not as effective as ESS-color on our datasets, using between 1. 4x and 3. 3x more space than ESS-color (Table  2 ). We note that even though KS is also designed to exploit the fact that are shared across colors, it makes a different design trade-off compared to ESS-color. Specifically, it does not allow simplitigs to extend beyond a single color class (resulting in more space needed to store k-mers), but, in exchange, it is more efficient in storing color information. GGCAT is generally the closest competitor against ESS-color, using between 14 and 44% more space on the non-Fungi datasets (note that for Fungi all tools did well). Like ESS-color, it builds a kind of global class table, constructs an SPSS of the k-mers, and annotates each run of single-class with their class ID. Unlike ESS-color, however, it does not use ESS, does not encode small class differences, and does not use local class tables.
As expected, ESS-basic is not as effective as ESS-color, using up to 6. 9x more space than ESS-color (Table  2 ). These results are not surprising since ESS-basic does not exploit the redundancy created by shared k-mers across samples. For the assemblies datasets, the compression improvement of ESS-color over ESS-basic closely tracks that of ESS-color over the original fasta. gz, since ESS-basic achieves only about 1. 2x compression relative to the fasta. gz. For the sequencing datasets, ESS-basic uses between 1. 3 and 1. 9 more space than ESS-color. Tables  3  and 4  show the run time and memory usage of compression, respectively. Here, ESS-color is outperformed by other tools. In particular, if optimal compression space is not needed, then GGCAT becomes a good alternative to ESS-color. Note that the decompression time (    Recall that ESS-color chooses one of six different compression modes for each simplitig, i.
e. U seLocalId ∈ {0, 1} and maxDif ∈ {0, 1, 2}. In order to access the relative contribution of the various compression techniques, we count the frequency with which each mode occurs (Table  7 ). First, we observe that the idea of a local table was rarely helpful on our data. Local tables are only beneficial when a single color class appears in more than one run in a simplitig, which apparently was rare. Second, the majority of simplitigs use maxDif = 0. This mode is optimal when the simplitig has just one color class. There is also a more complicated trade-off since setting maxDif > 0 adds one extra bit for each run encoding, which may outweigh the benefits of encoding some k-mers with a class difference. Third, the Gut dataset demonstrates the benefit of encoding class differences, especially compared to GGCAT.
Conclusion Colored de Bruijn graphs are a popular way to represent sequence databases. In spite of their ever-growing sizes, there have not been many specialized tools for compressing them to disk. In this paper, we present a  novel disk compression algorithm tailormade for cdBGs that achieves superior space compared to all other tools on the evaluated datasets. Our algorithm is a novel combination of ideas borrowed from previous work on disk compression of k-mer sets and indexing of cdBGs. We use a string-preserving string set (SPSS) as a basis for both compressing the nucleotide sequences and for ordering the rows in the color matrix. By using the SPSS ordering, we can avoid the costly storage of an indexed de Bruijn graph (e. g. BOSS in  [24, 25]  or a counting quotient filter in  [19] ).
We also exploit the fact that consecutive k-mers in an SPSS likely have the same or similar color class. A major component of our approach is that we select a different compression scheme for each simplitig, depending on what gives the best compression on that simplitig. The most important practical direction for future work is to improve the running time of our algorithm. The generation of the union ESS is done by ESS-basic. ESS-basic can be sped up by extending the latest SPSS generation tools  [14, 10]  to also compute an ESS. We could even built on top of the GGCAT, taking advantage of their efficient implementation (unfortunately, GGCAT was only released once our project was near completion). Another bottleneck is the color matrix generation step, which could be parallelized or even avoided by using color lists.
A theoretical future direction is to derive bounds on the bits used by the compression scheme. Unfortunately, we do not see an easy way to do this, since the choice of encoding depends on the order of the k-mers in the SPSS and on the decomposition of the k-mers into simplitigs. It is unclear to us how to capture these properties as a function of the input data. Finally, we could further improve the compression algorithm by modifying the SPSS generated by the ESS-basic algorithm. Currently, the choice of how to select from multiple simplitig extensions is made arbitrarily. Instead, the choice could be made to use the extension that has the most similar color class. Such a modification to the SPSS construction algorithm would likely be computationally non-trivial, since it would require accessing the color information.
Acknowledgements: We would like to thank  R. Chikhi  for helpful discussions. This material is based upon work supported by the  National Science Foundation  under grant nos. 2138585  and  1931531. Research reported in this publication was also supported by the  National Institutes of Health  under Grant  NIH R01GM146462  (to P. M. ). A. R. was supported by the  National Institutes of Health Computation, Bioinformatics, and Statistics  ( CBIOS) training program. The content is solely the responsibility of the authors and does not necessarily represent the official views of the National Institutes of Health.
pedigrees and an integrated dataset of persons, families and family trees in four provinces. The paper ends with a summary and conclusion. First attempts with record linkage in historical demography were done with data from church records and civil registers. Louis Henry is the well-known founder of a methodologically grounded way of linking this kind of records. Together with Michel Fleury he developed a form to create and record family reconstitutions  (Henry & Fleury, 1956; Séguy, 2016). The first datasets of this kind were limited to the parish area. Examples are the reconstitution of 34,812 families in 39 French parishes from the period 1640-1829  (Séguy, 2001)  and the database constructed by the Cambridge Group for the History of Population and Social Structure for 26 parishes in England and Wales over de period 1580-1837  (Wrigley, Davies, Oeppen, & Schofield, 1997).
Based on the Dutch civil records, LINKS is a continuation along the path set out especially by these French historical demographers. Civil registration was introduced in the Netherlands in 1810, as a consequence of the annexation by the French Empire. The Code Napoléon provided for the compulsory, standardized recording of vital events in certificates. The certificates had to be drawn up in the municipality where the vital event occurred. Most Dutch municipalities introduced civil registration over the course of 1811. However, since the Dutch province of Limburg and the south of Zeeland (Zeeuws-Vlaanderen) were annexed by France in 1796, civil registration for these provinces was introduced in that year  (Vulsma, 1988). All certificates of birth, marriage, or death ever made in the Netherlands are still available, as each certificate was made in duplicate and stored in books for safekeeping.
Currently about 85% of the indexing has been done. In all, 27 million civil certificates were digitized, containing information on about 120 million person mentions. However, archives are quickly catching up, and we expect countrywide coverage in about 5 years. Figure  1  Provinces of the Netherlands between  1811 and 1940  Explanation: Provinces for which occupational titles are available have a black frame; in the province of South-Holland the cities The Hague and Leiden are a positive exception since they also included the occupational titles in the index. In the case of brides and parents one often finds the term "without occupation". Occupations of deceased parents are not mentioned at all. Sources: The numbers of total events before 1850 were provided by van der  Bie and Smits (2000) , except the marriages 1812-1839 which were estimated; the number for the period from 1850 onwards were provided by the Historical Database of Dutch Municipalities (HDNG;  Mourits, Boonstra, Knippenberg, Hofstee, & Zijdeman, 2016).
The number of indexed certificates was calculated from the data that were gathered by LINKS in September 2018. The LINKS system is designed in a generic way and can handle nominal data from all kinds of sources. But in the development phase, we used data from the civil registration available in WieWasWie to create datasets with linked certificates in an enriched way and made them available to the scientific community. We also created reconstructions of life courses and families for separate regions in the Netherlands. In Figure  2  the general outline of the LINKS workflow process is sketched. Data are delivered by the regional and city archives to the WieWasWie-system. The ownership and responsibility for the content rest with these archives. LINKS harvests the data from WieWasWie in the LINKS original database as soon as new releases of data are added to WieWasWie.
From LINKS original the data are cleaned and standardized and subsequently added to the LINKS cleaned database. We give feedback to the WWW community on the errors and problems we found. These cleaned data form the basis of the different matching procedures. The resulting links are stored in LINKS linked, while the links between the certificates are also returned to the Dutch Family Center to be published on the website of WieWasWie. In a further stage the data from LINKS cleaned and LINKS linked are combined into LINKS datasets with, for instance, pedigrees and families, and enriched with geographical data and occupational coding. These data sets are released for scientific research.
CONVERTING, CLEANING AND STANDARDIZATION One for "valid and standardized", one for "not valid, but clear enough to be standardized" and "not valid and not standardized. Based on knowledge of name spelling and after experimental matching with marriage certificates of Zeeland (see Section 5. 2), we decided to apply a simple initial standardization for both first and family names by replacing all "ch" by "g", "c" by "k", "ph" by "f", "z" by "s", and "ij" by "y". Furthermore, family names or first names occurring in the whole dataset less than three times were considered to be spelling errors and were standardized to the most frequent corresponding name with a Levenshtein distance of 1. We considered them by definition as spelling mistakes, for example "Gerrjt" with frequency 2 was standardized to "Gerrit".
For the marriage and death certificates there are respectively 54 and 36 different conditions. The calculation of age ranges is even more complicated since in some cases interdependencies exist between the different procedures which have been solved by developing several specific functions that overrule the outcomes of the initial calculations. In the previous example, this concerns the theoretical marriage range of the father (1792-1863) which is limited by the marriage range of the mother (1827-1863) or the minimum range of death which is always defined by an event in which a person is registered as being alive. The linkage problem posed by the LINKS database is the identification of individuals and their family relations on the basis of multiple mentions in historical civil records. This process is complicated because names are seldomly unique identifiers for persons, even though in the Dutch civil administration everyone (also women) keeps the first name and family name given at birth during life time.
Links to their mentions as parents in the birth certificates of their children makes it possible to form families, while links to their mentions in death certificates complete their life history of vital events. In several matching operations combinations of three or four persons could be used to match certificates. In principle, by using more than two persons these matches show less ambiguous results than matching on only two persons (ego and mother). Once these relationships have been established the full family reconstruction is realized in a postmatching stage (see Section 6. 3). In the first instance a matching program was developed using SQL queries in a MySQL database. In Section 4. 2 we will explain this SQL-based system. However, this system was relatively slow.
PREMATCH TABLES First names may also contain more than one element, so-called multiple names, e. g. , "Cornelia Theresa Antonia Maria. " In the look up tables we handle each name separately. This makes it possible to match only the first or the first two names of a multiple name or matching one part of a multiple name with any part of the other name or more variations. To speed up the matching process, all (standardized) family names and first names were replaced by numbers (one unique number for each name). In another step these tables with names and numbers were enriched with the frequency of each name in the whole dataset. By way of these frequencies, it was possible to direct the matching algorithm in such a way that names with the lowest frequencies were compared first. In this way the selections of potential matches were kept as minimal as possible to save computing time.
The matching software within the MySQL environment was used to match records from the Dutch province of Zeeland and other relatively small areas. On the basis of the matching results, family reconstitutions were created (see Section 6). But on a national level, where tens of millions of certificates needed to be matched, the SQL environment proved to be relatively slow, which led to run-time problems and compelled splitting the job into sub-jobs. An alternative to the LINKS software was needed to speed up matching and to create a more general system that could be used outside the LINKS environment. Hence, burgerLinker was developed in a collaboration between the IISH, Utrecht University and Vrije Universiteit Amsterdam (for a comparison of record linkage techniques, see  Christen, Vatsalan & Fu, 2014; Raad et al.
BACKGROUND BurgerLinker is a graph-based record linkage program that uses the existing matching rules from the LINKS SQL-query environment, but retrieves candidate matches between certificates more efficiently. The program is designed as a stand-alone, scalable, and flexible software that allows the matching of other types of historical demographic records. Just as in LINKS, users can change the default settings for Levenshtein distance, ignoring filtering based on the dates of the certificates, avoiding matches without an identical first letter on the family name, ignoring parental names, or a mixture of the above. This leaves the desired precision and recall to the user, allowing users to see which candidate matches are filtered out and why. This contrasts with the MySQL environment, which was designed to deliver an optimal number of matches based on the discussions and decisions of the experts associated with the LINKS database.
Users of previous releases could decide not to use certain matches which were flagged as weak, but were unable to create new matches based on their own criteria. In the following, we will go into the processing aspect of the data and the data model, the working of the Levenshtein algorithm, the flexible recall and the increased transparency of the system. BurgerLinker is graph-based and expects an HDT file (Header, Dictionary, Triples) as input, which is a standard format used within the Resource Description Framework (RDF). HDT compresses datasets in a significant way while maintaining efficient search and browse operations without prior decompression. The RDF format is a W3C standard (along with HTML, CSS, and XML) that models data through socalled triples, describing an entity with attributes and the value of attributes.
An RDFS reasoner allows us to infer on demand a third triple indicating that personID_9999 is also an instance of the class schema:Person, as the second triple declares that all instances of civ:Male are also instances of schema:Person. Data for burgerLinker is exported from the LINKS MySQL database of standardized and cleaned data as a Comma Separated File (CSV). By way of the IISH standard tool COW, a script is run to convert the data from CSV to RDF. 8 The required HDT input for burgerLinker is created by a) importing the data in RDF format and b) using an embedded tool to convert the RDF dataset into HDT. Within burgerLinker we can then match the civil certificates, and export the results as RDF or CSV.
Each arrow in Figure  4  represents a triple pattern which defines the roles of the persons involved in an event and the attributes that are included in the model, for example, the name with the gray node indicating the type of literal values that are expected. In Appendix B we have included a more formal and complete description of the CIV model. After matching, the results need to be combined with other retrieved data such as professional titles and combined into event histories and family reconstitutions  (Mourits et al. , 2020). Just like the SQL-query environment, burgerLinker uses a Levenshtein algorithm to match cases. Calculating Levenshtein distances is a time-costly process, as the number of possible matches that a Levenshtein algorithm needs to consider grows exponentially with each new name that is added to the database, thus increasing the required run-time exponentially.
In the MySQL database this problem was solved by making prematch tables that store the Levenshtein distance between unique names before starting the actual matching procedure. These prematch tables made the linking within the SQL-query environment more efficient, but are an extra step in the linking process that must be reproduced when new data are added to the system. In burgerLinker, the Levenshtein distances are calculated efficiently on the fly. To speed up the computation of Levenshtein distances, burgerLinker indexes the list of target names as a Minimal Acyclic Finite-State Automaton (MA-FSA), also known as Directed Acyclic Word Graphs (DAWG). An FSA is a mathematical model or an abstract machine that operates by moving through a series of states in response to inputs, where each state represents a particular condition or configuration of the machine.
However, during the testing of burgerLinker we changed strategies and opted to aim at retrieving as many candidate matches as possible. The policy for the construction of releases in the SQL environment focused on finding as many unique matches as possible within the Dutch civil registry, prioritizing the quality of established matches and limiting the retrieval of candidate matches as soon as too many multiple matches appeared. This restrictiveness on the number of matches was advantageous for researchers as the retrieved dataset was ready for analysis. Yet, this optimum is not always the same for different datasets and there is also some variance between disciplines in what researchers deem the optimal balance between recall and precision (see Section 5. 2 for an elaborate discussion of this balance).
The structure and matching speed of burgerLinker make it relatively easy to match with different alternative designs and define how we filter matches to get more precision at a later stage. Secondly, by increasing the importance of the filtering procedure after the matching, burgerLinker makes the whole matching process more flexible and transparent. Just like the LINKS query system of the MySQL database, burgerLinker provides extensive data on the background of these matches. However, since burgerLinker can be used as a stand-alone tool, users are independent from the database manager in running the matching program, and can decide the maximum Levenshtein distance per name on the spot, as well as the number of persons on a certificate that should match. 9 Just as in the SQL-environment, the Levenshtein distances are made dependent on the character length of the smallest item to be matched (see Table  5  and compare Table 4 ).
However, to limit obvious mismatches, two entries with multiple first names will not match when separate elements of the shortest multiple first name does not match. For example, "Hendrikus Kornelis" can match to "Hendrik Kornelis Aloysius", but not to "Johannes Hendrikus Wilhelm", because the last one lacks "Kornelis. " Systematic filtering is possible due to the detailed metadata on the number of matched first names, the Levenshtein distance per matched first name, and the total Levenshtein distance of all matched first names. As a result, we can still retrieve the same matches as the SQL-environment, provided that we use the same rules for filtering. Like the database manager in the LINKS MySQL-system, users of the burgerLinker system may choose to ignore the date consistency check, ignore blocking of the first letter of the last name, or match only on the name of one of the indexed persons (see Table  5 ).
In general, matching on one person is not advisable, since it will give an enormous number of false matches. By default, the system will match on the ego and the mother and additionally on the father and a partner if possible. We also made it easy for the user to decide if children should be born in wedlock or not (see discussion in Section 3. 2). The main difference between burgerLinker and the MySQL query environment is that burgerLinker is designed as a tool for general use. Our hope is that burgerLinker can serve as a tool to make matching procedures within historical demography easier for researchers and also more comparable by introducing a standard way of matching. The introduction of the Intermediate Data Structure (IDS) for life course databases  (Alter & Mandemakers, 2014)  and its wide acceptance in the field, have laid the basis for common software, but the system supposes that the record linkage is done by the database itself.
Because each database has its own selection of sources with their own local peculiarities, database managers have developed a wide range of different matching strategies. BurgerLinker will not replace these existing matching programs, but it can easily link new data to existing datasets. It could also be used in validating the quality of existing matches and help to make alternative matchings which deviate on some aspects from the standard release. This will be facilitated by converting unlinked data into IDS. The IDS is structured according to the principle of the Entity Attribute Value model (EAV) or object-attribute-value model, which was introduced in the 1970s  (Stead, Hammond, & Straube, 1982). This is exactly the same structure as the RDF triple system in which the subject is the entity, the predicate is the attribute, and the object is the value (https://graphdb.
ontotext. com/ documentation/9. 8/enterprise/devhub/rdfs. html#what-is-rdf). This makes the creation of conversion scripts to create triple systems a relatively easy job. Hence, burgerLinker is the HSNDB's effort to share our experience in matching civil records with the community. In this section we will show the result of our experiments with the matching system, limiting our evaluation to the marriage certificates of the province of Zeeland. We choose the province of Zeeland because of the completeness of the dataset and the relatively limited number of inhabitants (on average about 5% of Dutch population). Figure  5  presents the challenge: the father and mother of a bride or a groom are to be matched with their own marriage certificate. As soon as a match is found we have a family tie between three generations.