Faceted search represents one of the most practical ways to browse a large corpus of information. Information is categorized automatically for a given query and the user is given the opportunity to further re ne his/her query. Many search engines o er a powerful faceted search engine, but only on the textual level. Faceted Search in the context of Math Search is still unexplored territory. In this paper, we describe one way of solving the faceted search problem in math: by extracting recognizable formula schemata from a given set of formulae and using these schemata to divide the initial set into formula classes. Also, we provide a direct application by integrating this solution with existing services.
research and overall study process would be facilitated once they are provided with more than textual search. For all these applications, we rst need a strong math search engine and second, a large corpus of math to index.
The Cornell e-Print Archive, arXiv, is an example of such a corpus,
containing over a million STEM documents from various scienti c elds (Physics,
Mathematics, Computer Science, Quantitative Biology, Quantitative Finance
and Statistics) [
Zentralblatt Math now employs formula search for access to mathematical
reviews [
There are multiple ways in which we could understand a \math facet". One
way would be through the MSC classi cation [
We are attempting to solve this problem by extracting formula schemata from the query hits, as formula facets. A math facet consists of a set of formula schemata generated to further disambiguate the query by re ning it in a new dimension. For instance, for the query above we could have the formulae in Figure 2, which allows the user to drill in on i) variation theory and minimal surfaces, ii) higher-order uni cation, and iii) type theory. Following the MWS (see 2.1) tradition, the red identi ers stand for query variables, their presence making the results formula schemata.
These formula schemata were manually created to judge the feasibility of using schemata as recognizable user interface entities, but for an application we need to generate them automatically from the query. Moreover, each schema should further expand to show the formula class it represents. Formula classes would consist of all formulae sharing the same schema. This is the algorithmic problem we explore in this paper.
Acknowledgements This work has been supported by the Leibniz Association under grant SAW-2012-FIZ KA-2 (Project MathSearch). The authors gratefully 2 Mathematics Subject Classi cation Fig. 1: Faceted Search in ZBMath
R M X:h(H1X) (dpf )dvol
HnX `A
D
Fig. 2: formula facets acknowledge fruitful discussions with Fabian Muller, Wolfram Sperber, and Olaf Teschke in the MathSearch Project, which led to this research (the ZBMath information service uses faceted search on the non-formula dimensions very successfully) and clari ed the requirements from an application point of view. 2
In this section we describe the existent systems on which our work will be based, with the intention of making this paper self-contained. 2.1
At its core, the MathWebSearch [
Internal to MWS, each mathematical expression is encoded as a set of substitutions based on a depth- rst traversal of its Content MathML tree. Furthermore, each tag from the Content MathML tree is encoded as a TokenID, to lower the size of the resulting index. The (bijective) mapping is also stored together with the index and is needed to reconstruct the original formula. The index itself is an in-memory trie of substitution paths.
To facilitate fast retrieval, MWS stores FormulaIDs in the leaves of the
substitution tree. These are integers uniquely associated with formulae, and they
are used to store the context in which the respective expressions occurred. These
identi ers are stored in a separate LevelDB [
MathWebSearch exposes a RESTful HTTP API which accepts XML queries. A valid query must obey the Content MathML format, potentially augmented with qvar variables which match any subterms. A qvar variable acts as a wildcard in a query, with the restriction that if two qvar s have the same name, they must be substituted in the same way. 2.2
Elasticsearch [
LATEXML An overwhelming majority of the digital scienti c content is written using LATEX or TEX, due to its usability and popularity among STEM researchers. However, formulae in these formats are not good candidates for searching because they do not display the mathematical structure of the underlying idea. For this purpose, conversion engines have been developed to convert LATEX expressions to more organized formats such as MathML.
An open source example of such a conversion engine is LATEXML [
In this section, we provide a theoretical description of the problem of generating formula schemata and a practical implementation. 3.1
Let us now formulate the problem at hand more carefully.
De nition 1. Given a set D of documents (fragments) { e.g. generated by a search query, a coverage 0 < r 1, and a width n, the Formula Schemata Generation (FSG) problem requires generating a set F of at most n formula schemata (content MathML expressions with qvar elements for query variables), such that F covers D with coverage r.
De nition 2. We say that a set F of formula schemata covers a set D of document fragments, with coverage r, i at least r jDj formulae from D are an instance (f ) of some f 2 F for a substitution . 3.2
To generate formula schemata, we must de ne a \cuto heuristic", which tells the program when two formulae belong to the same schema class. If there is no heuristic, two formulae would belong to the same class, only if they were identical. However, we want formulae that have something in common to be grouped together, even if they are not perfectly identical.
We experimented with several possibilities for the heuristic and found out that a dynamic cuto which preserves the operators is optimal. We can identify the operators by looking at the rst child of the apply token in the CMML tree. The user is given the option to have an absolute ( xed) or relative (depending on the depth of the CMML tree) cuto for the operands.
Figure 3 illustrates this heuristic at depth 1. The divide element was kept, because it was the rst child of apply, while the other children were removed. If we were to use a depth of 2, the plus element would also be included in the schema. The full faceted search system comprises of the following components: the Formula Schematizer 3.4, Elasticsearch, a proxy to mediate communication between the Schematizer and Elasticsearch and a Web front-end. The architecture of the system is shown in Figure 4.
Once the user enters a query (which consists of keywords and a depth), the front-end forwards the request to a back-end proxy. The proxy sends the text component of the query to Elasticsearch and receives back math contained in matching documents. Afterwards, it sends the retrieved math and the depth parameter (from the original query) to the Schematizer. The Schematizer will respond with a classi cation of the math in formula classes, as well as the corresponding schema for each class. Finally, the proxy forwards the result to the front-end which displays it to the user. 3.4
The Schematizer is the core part of our system. It receives a set of formulae in their Content MathML representation, generates corresponding formula schemata and classi es the formulae according to the generated schemata. It provides an HTTP endpoint and is therefore self-contained, i.e. it can be queried independently, not only as part of the faceted search system. As a consequence, the Schematizer displays a high degree of versatility, and can be integrated seamlessly with other applications.
The central idea behind the schematization process is to generate signatures from formulae which can be used to identify formula classes. We use the MathWebSearch encoding for MathML nodes, where each node is assigned an integer ID based on its tag and text content. If the node is not a leaf, then only the tag is considered. The signature will be a vector of integer IDs, corresponding to the pre-order traversal of the Content MathML tree.
Naturally, the signature depends on the depth chosen for the cuto heuristic. At depth 0, the signature consists only of the root token of the Content MathML expression. At full depth (the maximum depth of the expression), the signature is the same as the depth- rst traversal of the Content MathML tree.
Based on these computed signatures, we divide the input set of formulae into formula classes, i.e. all formulae with the same signature belong to the same class. For this operation we keep an in-memory hash table, where the keys are given by the signatures and the values are sets of formulae which have the signature key. After lling the hash table, we sort it according to the number of formulae in a given class, since the signatures which cover the most formulae should come at the beginning of the reported result.
The Schematizer caller can place an optional limit on the maximum number of schemata to be returned. If such a limit was speci ed, we apply it to our sorted list of signatures and take only the top ones.
As a last step, we need to construct Content MathML trees from the signatures, to be able to show the schemata as formulae to the user. We are able to do this because we know the arity of each token and the depth used for cuto . The tree obtained after the reconstruction might be incomplete, so we insert query variables in place of missing subtrees. We nally return these Content MathML trees with query variables (the formula schemata), together with the formulae which they cover. 3.5
To show the capabilities of the Schematizer we have prepared two demos. The rst one is a text-only search engine which returns the math from the matching documents, after running it through the Schematizer. This is the demo for showcasing the schematization process. The second one is a direct application of the Schematizer into a Math Search Engine which is capable of mathematical faceted search.
The SchemaSearch front-end provides just a textual search input eld. It is intended for users who want an overview of the formulae contained in a corpus. The user can enter a set of keywords for the query, as well as a schema depth, which defaults to 3. The maximum result size is not accessible to the user, to prevent abuses and reduce server load. There is also an \R" checkbox which speci es if the cuto depth should be absolute or relative. If relative, the depth should be given in percentages.
The TemaV2 front-end extends TeMaSearch to be able to perform mathematical faceted search. It is intended for users who want to lter query results based on a given facet (formula schema in this case). The look and feel is similar to the previous version of TeMaSearch, where the rst input eld is used to specify keywords and the second one is used to specify LATEX-style formulae for the query. When returning results, a \Math Facets" menu will be presented to the user. We discuss this in Section 4.2. 3.6
After obtaining the schemata and formula classes, we need to be able to display
the result to the user. One possibility would be to have the Schematizer return
Content MathML expressions for the schemata and use an XSL stylesheet [
Since the XSL conversion is unreliable, we will make use of the cross reference system provided by LATEXML, as discussed in Section 2.3. Instead of returning Content MathML expressions, the Schematizer will use the rst formula in each class as a template and \punch holes into it", e ectively returning the ID of the nodes that are to be substituted with query variables. We will use this IDs to replace the referenced PMML nodes with <mi> nodes representing the qvars.
Figure 5 shows the presentation by replacement technique for a given schema. The Schematizer returned a schema which was checked against the rst formula in its class ( x+23 ) to generate two substitutions, marked with red on the left side. Due to the cross-reference system provided by LATEXML, we are able to nd the corresponding PMML elements and substitute them with <mi> tokens. The result will be displayed to the user as ??xy . 4 4.1
(a) Faceted Results at depth 3 (b) Expansion of a Formula Class shown, but the results are truncated for brevity. The bold number on the left side of each result item indicates how many formulae are present in each formula class. For instance, the third schema represents a formula class containing 10 formulae. The entities marked in blue are query variables (qvars).
Figure 6b shows the expansion of a formula class. There are 22 formulae in the class given by this particular math schema, as indicated by the count on the left upper side, out of which only ten are shown to the user (for brevity the class is truncated to 5 formulae).
We can see 2 unnamed query variables marked with blue as ?a and ?b. By seeing the schema, the user can form an impression about the general structure of the formulae from that class. After expanding the class, the listing of concrete formulae appears. If the user clicks on one of them, he is redirected to the source document from which that expression was extracted. 4.2
Fig. 7: TeMa v2 Query Results truncated for brevity). We have also implemented a \search-on-click" functionality that allows the user the do a fresh search using the clicked schema and the initial keyword, which e ectively lters the current results. 4.3
We designed the Schematizer to be a very lightweight daemon, both as memory requirements and as CPU usage. To test if we achieved this goal, we benchmarked it on a server running Linux 3.2.0, with 10 cores (Intel Xeon CPU E5-2650 2.00GHz) and 80 GB of RAM.
We obtained the 1123 expressions to be schematized by querying Elasticsearch with the keyword \Fermat". While the overall time taken by the faceted search engine was around 5 seconds, less than a second was spent in the Schematizer. Also, the CPU utilized by the Schematizer never rose higher than 15% (as indicated by the top utility). Asymptotically, the algorithm would run in O(N ) time, where N is the number of input formulae. We are able to reach linear time performance, because each formula is processed exactly once and the signature is stored in a hash table, as discussed in Section 3.4.
Due to its implementation, the Schematizer is inde nitely scalable, because
it does not require shared state between formulae and can therefore be
implemented as a MapReduce [
Fig. 8: Math Facets in TeMa v2 5
One application of the faceted search engine can be providing mathematical
definitions with the help of NNexus [
Another, more direct, application of the Schematizer would be Similarity Search. One could create a MathWebSearch based search engine, which accepts an input formula and a similarity degree (between 0% and 100%). The engine would then create a formula schema at a relative depth corresponding to the similarity degree and use this schema to search the corpus. This approach de nes the similarity between two formulae as the percentage of the CMML tree depth that they share. 6
We have presented the design and implementation of a system capable of mathematical faceted search. Moreover, we have described a general purpose scalable Schematizer which can generate intuitive and recognizable formula schemata and divide expressions into formula classes according to said schemata.
Although the Schematizer provides recognizable formulae, some queries to SchemaSearch (e.g. using an author as keyword) provide hits with a very low relevance. This is because we cannot distinguish between the work of the author and work where the author is cited at the textual level. As a consequence, searching for \Fermat" would also show formulae from papers where Fermat was cited and if these papers are numerous, as it happens with known authors, would provide the user with misleading results. This suggests that a better source of mathematical expressions might be required for the SchemaSearch demo.