Structural Similarity Search for Formulas using Leaf-Root Paths in Operator Subtrees - read online free

Sep 4, 2026

Uploaded by Ezra

A new search method for mathematical formulas uses Operator Trees (OPTs) to represent operator application over operands. The approach introduces an indexing scheme based on OPT leaf-root paths, performs practical matching of the K largest common subexpressions, and scores matched OPT subtrees by counting nodes mapped to visible symbols with lower weighting for operators than operands. On the NTCIR-12 Wikipedia Formula Browsing Task (K=1), results outperform existing engines for non-wildcard queries. Execution remains practical without parallelization or pruning, showing low-time variance versus other state-of-the-art systems.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages14

Reading Time35 min

AccessFree to download

Introduction

Related Work

Two major approaches: Text-based vs Tree-based

Tree representations: SLTs and OPTs

Measuring similarity and leaf-root path indexing

Structural Similarity Search for Formulas using Leaf-Root Paths in Operator Subtrees Wei Zhong B and Richard Zanibbi [wxz8033@rit.edu](wxz8033@rit.edu) , [rlaz@cs.rit.edu](rlaz@cs.rit.edu) Rochester Institute of Technology Abstract. We present a new search method for mathematical formulas based on Operator Trees (OPTs) representing the application of operators to operands. Our method provides (1) a simple indexing scheme using OPT leaf-root paths,(2) practical matching of the K largest common subexpressions, and (3) scoring matched OPT subtrees by counting nodes corresponding to visible symbols, weighting operators lower than operands. Using the largest common subexpression (K=1), we outperform existing formula search engines for non-wildcard queries on the NTCIR-12 Wikipedia Formula Browsing Task. Stronger results are obtained when using additional subexpressions for scoring. Without parallelization or pruning, our system has practical execution times with low variance when compared to other state-of-the-art formula search engines. Keywords: Mathematical Information Retrieval 􀀁 formula search 􀀁 similarity search 􀀁 subexpression matching 1 Introduction Mathematical Information Retrieval (MIR [5, 21]) requires specialized tasks including detecting and recognizing math in documents, math computation and knowledge search (e.g., in Wolfram Alpha), and similarity search for math expressions. Formula search engines are useful for looking up unfamiliar notation and math question answering. Traditional text search engines are unaware of many basic characteristics of math formulas. Key problems in math formula similarity search include: { How do we represent math formulas for search? { How do we measure math formula similarity? 􀀏 Structural similarity: Common subexpression(s), operator commutativity and operator associativity. 􀀏 Symbol set similarity: Being aware of uni􀀌able/interchangeable elements (e.g. , (1 + 1=n)n and (1 + 1=x)x ), while still distinguishing e = mc2 from y = ax2 ; weighting identical symbols appropriately. 􀀏 Semantic similarity of mathematical formulas, including equivalent formulas (e.g. , x 􀀀1 and 1=x) . { What is a good trade-o􀀋 between feature-based matching and costly structure matching, to identify similar formulas e􀀎ciently and e􀀋ectively? 2 Wei Zhong B and Richard Zanibbi We present a new formula search engine based on Operator Trees (OPTs) . OPTs represent the semantics of a formula, in terms of the application of operators to operands in an expression. We adapt the leaf-root path indexing of all subtrees used in MCAT [8], where these paths act as the retrieval units or \keywords" for formulas. MCAT uses additional encodings (e.g., Presentation MathML) that we do not consider in this work. Our scoring function generalizes subtree scoring methods which only consider single best matched tree such as the Maximum Subtree Similarity (MSS) of Tangent [22] . To the best of our knowledge, our model is the 􀀌rst using multiple common subexpressions to score formula hits. Our approach has achieved usable execution times using a single process without any dynamic pruning applied so far, and produces stateof-the-art results for non-wildcard queries in the NTCIR-12 Wikipedia Formula Browsing Task [20] . Our system is available for download.1 2 Related Work There are two major approaches to math representation and indexing, Text-based and Tree-based [21] . Text-based approaches apply traditional text search engines, converting formulas to canonically ordered text strings with index augmentation [11, 12, 14] to deal with operator commutativity, operator associativity, and subexpression matching. Tree-based approaches index formulas directly from hierarchical representations of appearance and semantics. In the recent NTCIR-12 MIR tasks [20], tree-based MIR systems achieve the best accuracy. Tree representations are primarily divided into SLTs (Symbol Layout Trees) and OPTs (Operator Tr

FAQs

What representation does the method use for formulas?

It represents formulas with Operator Trees (OPTs), where internal nodes are operators and leaves are operands.

How does the search index and match formulas?

It uses an indexing scheme based on OPT leaf-root paths and matches the K largest common subexpressions to form candidate hits.

How are matched subtrees scored?

Matched OPT subtrees are scored by counting nodes corresponding to visible symbols, with operator nodes weighted lower than operand symbols.

Sep 4, 2026

Uploaded by Ezra