---
abstract: 'Digital mathematical libraries (DMLs) such as arXiv, Numdam, and [EuDML](https://eudml.org) contain mainly documents from STEM fields, where mathematical formulae are often more important than text for understanding. Conventional information retrieval (IR) systems are unable to represent formulae and they are therefore ill-suited for math information retrieval (MIR). To fill the gap, we have developed, and open-sourced the MIR system. MIaS is based on the full-text search engine Apache Lucene. On top of text retrieval, MIaS also incorporates a set of tools for preprocessing mathematical formulae. We describe the design of the system and present speed, and quality evaluation results. We show that MIaS is both efficient, and effective, as evidenced by our victory in the NTCIR-11 Math-2 task.=-1'
author:
- Petr Sojka
- Michal Ružička
- Vít Novotný
bibliography:
- 'main.bib'
- 'sojka.bib'
title: '*MIaS*: Math-Aware Retrieval in Digital Mathematical Libraries'
---

=1

renderers=

headingOne=

\#1 {#section .unnumbered}
===

, headingTwo=

\#1 {#section-1 .unnumbered}
---

, strongEmphasis=,

\# CIKM 2018 \#\# TODOs - For the review: - \*\*Convert to the \[ACM LaTeX template\](https://www.acm.org/publications/proceedings-template), use ‘sample-sigconf.tex‘ as example, aim for 4 pages.\*\* - \*\*Make sure the article is properly anonymized. (not necessary for Demo paper\*\* - \*\*Make sure the bibliography is properly formatted.\*\* - \*\*Extend the evaluation section with results from NTCIR\*\* - \*\*Describe query expansion, and striping\*\* - For the camera-ready:

\#\# Links - \[Topics of Interest\](http://www.cikmconference.org/\#topics): - Performance evaluation - Information storage and retrieval and interface technology - Digital libraries - \[Call for Demonstrations\](http://www.cikm2018.units.it/callfordemo.html)

\# MIaS Figures - WebMIaS web interface: - \[@dml:Liskaetal2011, Figure 2\] - \[@dl:liska2010eng, Figure 4.1\] - \[@MIR:MIRMU, Figure 1\] \*\[shows two extra webpage screenshots\]\* - \[@dml:cicm2014liskaetal, Figure 1\] - \[@Ruzicka17Math, Figure 4\] - Scheme of system workflow: - \[@dml:Liskaetal2011, Figure 1\] - \[@dl:liska2010eng, Figure 3.1\] \*\[in Slovak\]\* - \[@mir:LiskaMasters2013, Figures 4.1, and 4.2\] - \[@dml:sojkaliska2011, Figures 1, and 2\] - \[@dml:doceng2011SojkaLiska, Figure 1\] - \[@Ruzicka17Math, Figures 1, and 2\] \*\[shows extra detail\]\* - Formula preprocessing: - \[@dl:liska2010eng, Appendix B\] \*\[in Slovak\]\* - \[@dml:sojkaliska2011, Figure 3\] - \[@dml:doceng2011SojkaLiska, Figure 2\] - Unpublished CICM 2017 article \*„Towards Math-Aware Automated Classification and Similarity Search of Scientific Publications“\* (Figure 1) - \[@Ruzicka17Math, Figure 3\] - Relative number of results found using different subqueries in NTCIR-11 CMath run of MIR MU: - \[@LiskaSojkaRuzicka15Combining, Figure 1\] - \[@mir:MIaSNTCIR-11, Figure 1\] - \[@Ruzicka17Math, Figure 5\] - NTCIR-11 BPREF evaluation results: - \[@RuzickaSojkaLiska16Math, Figure 2\] - MathML structural unification: - \[@RuzickaSojkaLiska16Math, Figure 1\] - \[@Ruzicka17Math, Figure 7\] - Scalability diagrams: - \[@dml:sojkaliska2011, Figure 4\] \*\[MREC dataset\]\* - \[@mir:LiskaMasters2013, Figures 5.1–5.3\] \*\[MIR workshop dataset\]\* - MIaS UML diagrams: - \[@mir:LiskaMasters2013, Figures B.1–B.3\] - MSC topic modelling: - Unpublished CICM 2017 article \*“Towards Math-Aware Automated Classification and Similarity Search of Scientific Publications”\* (Figures 2, and 3) - \[@Ruzicka17Math, Figures 26, and 27\] - Relevance density estimates: - Unpublished COLING 2018 article \*“Weighted Averaging in Disjoint Passage Retrieval for Question Answering”\* (Figure 4).

\# Top-level outline - Abstract 1. Background 2. Aim 3. Methods 4. Results 5. Conclusion 1. Introduction (following the organizational pattern set forth by \*“Academic Writing for Graduate Students: Essential Tasks and Skills”\* by Swales, and Feak, 1994) - Move 1a: Establishing a research territory - Move 1b: Introducing previous research - Move 2: Establishing a niche - Move 3: Occupying a niche 2. System Description - MIaS - MathML Canonicalizer - MathML Unificator - MIaSMath - WebMIaS - Figure 1: WebMIaS web interface 3. Evaluation - MREC evaluation results \[@dml:Liskaetal2011, Section 5\] - MIR workshop evaluation results \[@mir:LiskaMasters2013, Chapter 5\] - NTCIR-10 evaluation results: - \[@MIR:MIRMU, Sections 4, and 5\] - \[@mir:NTCIR-10-Overview, Table 7\] - NTCIR-11 evaluation results: - \[@mir:MIaSNTCIR-11, Sections 4, and 5\] - \[@NTCIR11Math2overview, Table 8\] - NTCIR-12 evaluation results: - \[@RuzickaSojkaLiska16Math, Section 5\] - \[@ZanibbiEtAl16NTCIR, Tables 8, and 9\] 4. Conclusion and Future Work - Extending the techniques to general semi-structured text - Incorporating static relevance estimates based on the position of resulting documents - Figure 2: Relevance density estimates - Migrating MIaS to ElasticSearch - Extending ordering to a rewriting system in a computer algebra system (CAS) \[@cohl2017semantic\] - References

Introduction
============

In mathematical discourse, formulae are often more important than text for understanding. As a result, digital mathematical libraries (DMLs) require math information retrieval (MIR) systems that recognize both text and math in documents and queries. Conventional IR systems represent both text, and formulae using the bag-of-words vector-space model (VSM). However, the VSM captures neither the structural, nor the semantic similarity between mathematical formulae, which makes it ill-suited for MIR.

To fill the gap, new math-aware IR systems started to appear after the pioneering workshop on DMLs [@dml:dml2008proceedings]. Springer’s [[^1]]{} system takes formulae from papers with available LaTeX sources, and hashes the formulae to obtain a text representation. Zentralblatt Math uses the system[[^2]]{} [@kohlhase2008mathwebsearch], which represents formulae with substitution trees. We have developed and open-sourced the MIaS (Math Indexer and Searcher) system[[^3]]{} [@mir:MIaSNTCIR-11; @Ruzicka17Math] using the robust highly-scalable full-text search engine [Apache Lucene](https://lucene.apache.org/) [@bialecki12] and our own set of tools for the preprocessing of mathematical formulae. Since 2012, MIaS has been deployed in [the European Digital Mathematical Library (EuDML)[[^4]]{}]{}, making it historically the first system to be deployed in a DML.

![image](figs/system){width="\textwidth"}

System Description
==================

MIaS processes text and math separately. The text is tokenized and stemmed to unify inflected word forms. Math is expected to be in [the MathML format[[^5]]{}]{}. Open tools such as [Tralics[[^6]]{}]{}, [LaTeXML[[^7]]{}]{} convert documents in the popular math authoring language of LaTeX to MathML. Other tools such as [InftyReader](http://www.inftyreader.org/) [@dml:suzukietal2003] , and [MaxTract](https://github.com/zorkow/MaxTract) [@DBLP:conf/aisc/BakerSS12] convert raster, and vector PDF documents, respectively, to MathML. The math is then canonicalized, ordered, tokenized, and unified (see Figure \[fig:system\]). We will describe each of these processing steps in detail in the following paragraphs.

#### Canonicalization

As explained above, MathML can originate from multiple sources and each can encode equivalent mathematical formulae a little differently. To obtain a single *canonical* representation, we initially used the third-party MathML canonicalizer from the UMCL library that converts math to a subset of MathML called the Canonical MathML [@acc:archambaultmoco06cmathml]. However, since the conversion speed and accuracy did not match our expectations, we have developed and open-sourced our own MathML canonicalizer[^8] [@FormanekEtAl:OpenMathUIWiP2012].

#### Ordering

MathML canonicalization only affects the encoding of mathematical formulae and does not result in any syntactic manipulation. We go a step further and reorder the operands of commutative operators alphabetically. For example, we convert the formulae $a+b$, and $b+a$ to a single canonical form $a+b$.=-1

#### Tokenization

A user of our system may not know the precise form of a formula they are searching for. To enable partial matches, we index not only the original formula, but also all its *subformulae*, which correspond to all the XML subtrees of the original formula XML tree. To penalize partial matches, the weight of subformulae is inversely proportional to their depth in the XML tree. [@dml:sojkaliska2011]

A user is likely interested in documents that contain either the query formula itself, or larger formulae with the query formula as a subformula. On the other hand, a user is unlikely to be interested in documents that contain only small parts of the query formula, such as isolated numbers, and symbols. For that reason, we only tokenize formulae in indexed documents, not in user queries.

#### Unification

In theory, the naming of variables does not affect the meaning of formulae. To match formulae in different notations, we replace each variable with a numbered identifier. For example, we convert the formulae $a+b^a,$ and $x+y^x$ to a single *unified* form $\text{id}_1+\text{id}_2^{\text{id}_1}$. In practice, many fields have an established notation and variable names are meaningful. To encourage precise matches, we keep the original formulae in addition to the unified formulae.

Two formulae that only differ in numeric constants are often related. For example, both $3x^2-2x+2,$ and $8x^2-3x+6$ are quadratic polynomials. We replace every numeric constant with a constant identifier. For example, we convert the above formulae to a single unified form $\text{const}x^2-\text{const}x+\text{const}$. To encourage precise matches, we keep the original formulae in addition to the unified formulae.

In predicate logic, a variable can represent an arbitrary formula. For example, the formulae $a^2+{}$, and $a^2+{}$ are equivalent if $x$ equals $\sqrt b$. Starting with the deepest subformulae, we replace all subformulae at a given depth with a unifying identifier. [@RuzickaSojkaLiska16Math] For example, we convert the formula $a^2+{}$ to a sequence of *structurally unified* formulae $a^2+{}$$,\Unif^{\unif}+{}$, and $\Unif+\Unif$ and the formula $a^2+{}$ to a sequence of structurally unified formulae $\Unif^{\unif}+{}$, and $\Unif+\Unif$. To penalize partial matches, the weight of the formulae is proportional to the depth of replacement. To encourage precise matches, we keep the original formulae in addition to the unified formulae. We have open-sourced [the MathML structural unificator[[^9]]{}]{}.

  ------------- ------- ------- ------- ------- -------
  Subquery 1:    $f_1$   $f_2$   $t_1$   $t_2$   $t_3$
  Subquery 2:    $f_1$   $f_2$   $t_1$   $t_2$  
  Subquery 3:    $f_1$   $f_2$   $t_1$          
  Subquery 4:    $f_1$   $f_2$                  
  Subquery 5:    $f_1$           $t_1$   $t_2$   $t_3$
  Subquery 6:                    $t_1$   $t_2$   $t_3$
  ------------- ------- ------- ------- ------- -------

adddotafter

#### 

After preprocessing, a query consists of a weighted set of terms, and formulae. Since we are now going to search for documents that match at least one term, and at least one formula from the query, ill-posed terms, and formulae will negatively impact the recall of our system. To overcome this problem, we remove selected terms and formulae to produce a set of *subqueries*. Figure \[fig:query-expansion\] shows an example strategy for producing subqueries. @LiskaSojkaRuzicka15Combining describe other strategies that we use. We then submit the subqueries to Apache Lucene and receive ranked lists of resulting documents. Since the scores of the resulting documents are incomparable between subqueries, we cannot merge and rerank the individual result lists. Instead, we interleave them to obtain the final search results that we present to the user.

![image](figs/webmias){width="\textwidth"}

  --------- ------------- --------------- ---------- ----------
                                                     
       Docs         Input         Indexed       Real        CPU
     10,000     3,406,068      64,008,762      35.75      35.05
     50,000    18,037,842     333,716,261     189.71     181.19
    100,000    36,328,126     670,335,243     384.44     366.54
    200,000    72,030,095   1,326,514,082     769.06     733.44
    300,000   108,786,856   2,005,488,153   1,197.75   1,116.64
    350,000   125,974,221   2,318,482,748   1,386.66   1,298.10
    439,423   158,106,118   2,910,314,146   1,747.16   1,623.22
  --------- ------------- --------------- ---------- ----------

  : Speed evaluation results on the NTCIR-11 Math-2 dataset using the same computer as above.[]{data-label="tab:speed-eval-ntcir11"}

  ----------- ------------ --------------- --------- ----------
                                                     
         Docs        Input         Indexed      Real        CPU
    8,301,545   59,647,566   3,021,865,236   1940.07   3,413.55
  ----------- ------------ --------------- --------- ----------

  : Speed evaluation results on the NTCIR-11 Math-2 dataset using the same computer as above.[]{data-label="tab:speed-eval-ntcir11"}

adddotafter

#### 

To provide a web user interface to MIaS, we have developed and open-sourced [WebMIaS[[^10]]{}]{}$^,$[[^11]]{} [@mir:MIaSNTCIR-11; @dml:cicm2014liskaetal]. Users can input their query in a combination of text, and math with a native support for LaTeX provided by Tralics, and [MathJax](https://www.mathjax.org/) [@cervone2012mathjax]. Matches are conveniently highlighted in the search results. The user interface of WebMIaS is shown in Figure \[fig:webmias\]. We have deployed a demo of [the latest development version of WebMIaS[[^12]]{}]{} using the [Apache Tomcat[[^13]]{}]{} implementation of the Java Servlet. The demo uses an index built from a subset of the arXMLiv dataset [@dml:arXMLiv2010] made available to the NTCIR-12 conference participants and will serve as the basis for our live demonstration at the conference.

Evaluation
==========

We performed a speed evaluation of MIaS on the MREC dataset of 439,423 documents [@dml:liska2011] (see Table \[tab:speed-eval-mrec\]), a quality and speed evaluation on the NTCIR-10 Math [@mir:NTCIR-10-Overview; @MIR:MIRMU] dataset of 100,000 documents, and a quality and speed evaluation on the NTCIR-11  [@NTCIR11Math2overview; @mir:MIaSNTCIR-11] (see Tables \[tab:speed-eval-ntcir11\], and \[tab:quality-eval-ntcir11\]), and NTCIR-12 MathIR [@ZanibbiEtAl16NTCIR; @RuzickaSojkaLiska16Math] dataset of 105,120 documents that were split into 8,301,578 paragraphs. Speed evaluation shows that the indexing time of our system is linear in the number of indexed documents and that the average query time is 469ms. With respect to quality evaluation, MIaS has notably won the NTCIR-11 Math-2 task.

  Measure   Level   PMath    CMath            PCMath           LaTeX
  --------- ------- -------- ---------------- ---------------- --------
  MAP       3       0.3073   **0.3630 /1/**   0.3594           0.3357
  P@10      3       0.3040   **0.3520 /1/**   0.3480           0.3380
  P@5       3       0.5120   **0.5680 /1/**   0.5560           0.5400
  MAP       1       0.2557   **0.2807 /2/**   0.2799           0.2747
  P@10      1       0.5020   0.5440           **0.5520 /1/**   0.5400
  P@5       1       0.8440   **0.8720 /2/**   0.8640           0.8480

  : Quality evaluation results on the NTCIR-11 Math-2 dataset. The mean average precision (MAP), and precisions at ten (P@10), and five (P@5) are reported for queries formulated using Presentation (PMath), and Content MathML (CMath), a combination of both (PCMath), and LaTeX. Two different relevance judgement levels of $\geq1$ (partially relevant), and $\geq3$ (relevant) were used to compute the measures. Number between slashes (/$\cdot$/) is our rank among all teams.[]{data-label="tab:quality-eval-ntcir11"}

Conclusion and Future Work
==========================

With the growing importance of DMLs, there is a growing demand for effective MIR systems. The evaluation shows that our open-source system is both efficient, and effective while building on industrial-strength full-text search engine Apache Lucene. The system allows low-latency responses even on the big math corpora as proved by its deployment in EuDML.

The speed of indexing and response latency of MIR will be further increased by the migration of from Apache Lucene to the distributed full-text search engine [ElasticSearch[[^14]]{}]{}. The idea of indexing structures rather than terms can be generalized from mathematical formulae to semi-structured text. Reordering the operands of associative operators is only a simple transformation. For example, to convert $\sqrt[n]{a}$, and $a^{1/n}$ to a single canonical representation, a general computer algebra system (CAS) can be used. We experiment [@rygletal16] with improving the vector space representations of document passages, aiming to add support for mathematics in the future. Embeddings can also be computed for equations [@mir:krstowski2018arXiv] now, which presents new possibilities of using language modeling for the semantic segmentation of STEM articles, and weighting the segments [@rygletal16]. Grasping the meaning of mathematical formulae is crucial: content is king. =-1

### Acknowledgements {#acknowledgements .unnumbered}

We gratefully acknowledge the support by the European Union under the FP7-CIP program, project 250,503 (EuDML), and by the ASCR under the Information Society R&D program, project 1ET200190513 (DML-CZ). We also sincerely thank three anonymous reviewers for their insightful comments.

[^1]: <https://www.ams.org/notices/201004/rnoti-apr10-cov4.pdf>

[^2]: <https://zbmath.org/formulae/>

[^3]: <https://github.com/MIR-MU/MIaS>

[^4]: <https://eudml.org/search>

[^5]: <https://www.w3.org/TR/MathML3/>

[^6]: <https://www-sop.inria.fr/marelle/tralics/>

[^7]: <https://dlmf.nist.gov/LaTeXML/>

[^8]: <https://github.com/MIR-MU/MathMLCan>

[^9]: <https://github.com/MIR-MU/MathMLUnificator>

[^10]: <https://mir.fi.muni.cz/webmias/>

[^11]: <https://github.com/MIR-MU/WebMIaS>

[^12]: <https://mir.fi.muni.cz/webmias-demo/>

[^13]: <https://tomcat.apache.org/>

[^14]: <https://elastic.co>
