SoftMatcha: A Soft and Fast Pattern Matcher for Billion-Scale Corpus Searches

Authors: Hiroyuki Deguchi, Go Kamoda, Yusuke Matsushita, Chihiro Taguchi, Kohei Suenaga, Masaki Waga, Sho Yokoi
Primary area: applications to computer vision, audio, language, and other modalities
Keywords: natural language processing, full-text search, word embeddings, inverted index, pattern match

Abstract:
Researchers and practitioners in natural language processing and computational linguistics frequently observe and analyze the real language usage in large-scale corpora.
For that purpose, they often employ off-the-shelf pattern-matching tools, such as grep, and keyword-in-context concordancers, which is widely used in corpus linguistics for gathering examples.
Nonetheless, these existing techniques rely on surface-level string matching, and thus they suffer from the major limitation of not being able to handle orthographic variations and paraphrasing---notable and common phenomena in any natural language.
In addition, existing continuous approaches such as dense vector search tend to be overly coarse, often retrieving texts that are unrelated but share similar topics.
Given these challenges, we propose a novel algorithm that achieves soft (or semantic) yet efficient pattern matching by relaxing a surface-level matching with word embeddings.
Our algorithm is highly scalable with respect to the size of the corpus text utilizing inverted indexes.
We have prepared an efficient implementation, and we provide an accessible web tool.
Our experiments demonstrate that the proposed method
(i) can execute searches on billion-scale corpora in less than a second, which is comparable in speed to surface-level string matching and dense vector search;
(ii) can extract harmful instances that semantically match queries from a large set of English and Japanese Wikipedia articles;
and (iii) can be effectively applied to corpus-linguistic analyses of Latin, a language with highly diverse inflections.

Decision: accept (poster)
Reviewer scores: 5, 6, 6

Reviews and discussion:
<thread>
creation date:
1730495097553

thread_type:
official_review

<thread_object>
creator: reviewer_4jzq

<content>
summary:
This paper introduces a pattern-matching algorithm designed to efficiently handle semantic matching across vast text corpora, addressing the limitations of existing methods that struggle with language variations like orthographic diversity and paraphrasing. Unlike conventional string-based approaches, which lack flexibility, the proposed algorithm leverages word embeddings and inverted indexing to perform "soft" matching, enabling it to find meaningfully related phrases without relying on exact string matches. The algorithm operates at a speed comparable to traditional methods, achieving search times of under a second on billion-word corpora. It proves effective in practical applications: identifying harmful content in large English and Japanese datasets, and retrieving linguistically relevant examples in Latin, where morphological variations are common. SoftMatcha, the resulting tool, is accessible via a web interface, making it practical for users in NLP and digital humanities.

strengths:
The algorithm is optimized for billion-scale corpora, achieving search speeds that are comparable to traditional tools but with a much richer, semantic matching capability. This scalability and speed are significant achievements, especially for applications involving extensive datasets like web-scale corpora.

The paper is well explained and the demo is functional and can be accessed easily. The examples in different languages give a good overview of the applicability potential of the algorithm.

weaknesses:
An important limitation is the reliance on static embeddings, such as GloVe, which have largely been superseded by contextual embeddings in modern NLP applications. The continued use of GloVe and similar embeddings raises questions about the model's ability to capture context-dependent semantics, which are crucial in diverse language patterns and semantic matching tasks. The paper's illustrative example, where semantically "opposite" concepts (e.g., "lived" vs. "died") are matched, does not illustrate, in my opinion, the advantage of using this soft matching but instead it highlights a potential issue, which derives from the use of "classic" embeddings. "live" and "die" are used in similar contexts, which yields a high similarity according to the embedding spaces of word2vec or GloVe, but they are opposite semantically.

I also think that while the paper contains notable technical contributions, the primary focus on linguistic applications, corpus search, and retrieval, with an emphasis on efficiency, suggests that it may align more closely with the interests of venues like ACL rather than ICLR.

questions:
Since the algorithm operates solely on the vocabulary present in the corpus, there is limited discussion on its approach to out-of-vocabulary (OOV) items. This omission raises questions about how the system performs when faced with rare or unseen words and could impact its scalability across languages and domains with rich vocabularies or evolving terminologies.

So my question is: how the matching algorithm deals with OOV words? For instance, if "John" is not in the vocabulary, does it means I can't search for phrases containing "John"?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730691507731

thread_type:
official_review

<thread_object>
creator: reviewer_y3li

<content>
summary:
This paper presents an efficient method for pattern matching over billion-token corpus by combining soft matching via word embeddings and inverted indexes. The method is compared to exact matching and dense vector search as baselines over wikipedia corpora in English and Japanese. They show that the running time of the proposed algorithm is on par with the exact matching but much faster than dense vector search. Through qualitative case analysis, they also show that the algorithm returns relevant results and can be more robust than the other baselines.

strengths:
The algorithm proposed is straightforward and effective, and it can be quite helpful for quickly locating relevant texts in massive pretraining data. The paper is also well-written and structured clearly, especially the demo interface.

weaknesses:
The empirical evaluation can be further strengthened. It would be helpful to include analysis that shows 1) how the threshold influences speed and the relevance of the retrieved results. 2) a tradeoff analysis between the efficiency and the qualitative analysis. Table 3 seems to show that SoftMatcha retrieve relevant and robust texts fast. However I wonder if the observed relevancy can be quantified with a information retrieval corpora so that we can understand its relevant performance compared to the baselines.

questions:
n/a
</content>
</thread_object>

</thread>
<thread>
creation date:
1730714289743

thread_type:
official_review

<thread_object>
creator: reviewer_9dur

<content>
summary:
Paper addresses the problem of soft (or semantic) pattern matching over a billion-scale text corpora. Exact matching is often too stringent; on the other hand, naive semantic matching based on computing similarities between word embeddings is much slower, since it requires a lot of floating point operations with high-dimensional vectors instead of fast bitwise comparisons. 

Authors leverage inverted indexes data structure to reduce the amount of required soft matches, and propose an algorithm which requires only a constant amount of soft matches with respect to corpura size. They also conduct two case studies: testing the speed of the proposed implementation on a billion-scale search, and retrieving patterns from a morphologically complex language (Latin). Finally, they provide a demo to interact with the proposed algorithm.

strengths:
- Paper is very clearly written and easy to follow.

- Main algorithm is simple and straightforward Notably, it requires a constant amount of costly soft word comparisons (which can be ~1000 longer compared to hard comparisons) with respect to corpus size Meanwhile, it still allows for much more flexible matching.

- Provided demo works.

weaknesses:
1. Description of dense vector search lacks details.
- e.g. in Line 415, what is a “training instance” — a sentence? A paragraph?
- How the training instances and queries were formatted for the model? Does it follow the description at https://huggingface.co/intfloat/multilingual-e5-large?
- What was the maximal length of training instances encoded by the model?
If maximal length of a training instance is too long for the model, was it truncated or split into chunks?
- How token embeddings were pooled in a single chunks-level score?
- What were the HNSW hyperparameters?

2. Table 2 lacks details.
- How many search queries were done (e.g. 1, 100, 1000)?
- How long the queries were (e.g. <20 words)?
- What are the variation in search time (standard deviation of search time over multiple queries, maximal / minimal search time for a single query)?

3. Approximate string matching baselines were not included (e.g. agrep (Wu & Manber, 1992b;a) or TRE (https://en.wikipedia.org/wiki/TRE_(computing))). While unlike SoftMatcha they can not e.g. find synonyms, they are still useful for finding matches with typos / inflected word forms (which e.g. was part of the goal in “Section 4.3 Case study in computational linguistics — retrieving Latin examples), and it is interesting to compare search speed.
- In Section 2.3 String Matching, lines 200-202 you state that approximate string matching is orthogonal to your work as it focuses on surface-level comparison, while you target semantic-level similarity.
However, in Introduction, lines 076-080 you mention that “...it is often desirable to catch non-standard spellings as well, such as how r u instead of how are you … Additionally, it is desirable to catch different inflected word forms such as sing, sang, sung, signs and singing, which differ only in their morphological features and share the same lemma (base form).”

One big difficulty with assigning an overall score is the fact, that there are basically no metrics in the paper, except for running time. 
For approximate/fuzzy pattern matching algorithms it is interesting to estimate how relevant are the search results, using ranking metrics like mean average precision, or NDCG. However, these require a labeled dataset, which is hard to obtain.

On a qualitative level, this algorithm looks like a noticeable improvement over exact matching, and it might have some benefits compared to dense vector search (e.g. 100% recall in cases where the query exactly matches the pattern, higher speed, simpler implementation). Nonetheless, with more search results there arises a need to rank them. Considering Figure 3: while in some cases the ability to match “July 16, 2015” by the query “March 1, 2016” is useful, in others this might be a completely irrelevant search result.

questions:
Major:
- There are some questions in Weaknesses section.
- How the sample search results were selected for Table 3?

Minor:
- How to choose alpha?
- How much more search results does SoftMatcha retrieve depending on alpha?
    - How many of additional entries are irrelevant?
    - How to rank additional entries found by Softmatcha?
- For potential future work: is it possible to modify the algorithm to allow flexible order of words in the query, or matching with some words omitted / inserted (e.g. finding “a fantastic jazz musician” by a query “the jazz musician”)? Fixed word order is still quite restrictive, especially for queries containing many words.

Suggestions:

- In footnote 5, page 8 information about Japanese as fifth language in Wikipedia by total amount of articles is outdated — Japanese is now 17th, while Chinese is 10th with almost twice as many total articles. Source: https://wikistats.wmcloud.org/display.php?t=wp. I propose to update the footnote.
- Lines 099-100: “0.1 seconds … without GPU” — I’d propose to add hardware specifications used for speed evaluations (156 cores and 226 Gib of main memory), to make the claim more concrete.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732163041713

thread_type:
official_comment

<thread_object>
creator: area_chair_qpqg

<content>
title:
Reminder: Please respond and update the score if necessary

comment:
Dear Reviewers,

Kindly ensure that you respond proactively to the authors' replies (once they are available) so we can foster a productive discussion. If necessary, please update your score accordingly. We greatly appreciate the time and effort you’ve dedicated to the review process, and your contributions are key to making this process run smoothly.

Thank you,

AC
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper presents an algorithm for semantic pattern matching across large-scale text corpora, addressing the shortcomings of exact and traditional semantic matching methods. By combining word embeddings with inverted indexing, the proposed method achieves efficient "soft" matching. It maintains search speeds comparable to exact matching while being faster and more robust than dense vector search. Tested on English, Japanese, and Latin corpora, the algorithm effectively balances speed and semantic relevance. The resulting tool is accessible via a web interface, making it useful for various applications in natural language processing and digital humanities.

On the positive note, reviewers agree that the paper introduces a straightforward and effective algorithm optimized for billion-scale corpora, offering search speeds comparable to traditional tools while providing enhanced semantic matching capabilities. This significant advancement is particularly useful for applications involving extensive datasets, such as web-scale corpora. The paper is well-written and structured clearly, making it easy to follow. The demonstration interface is functional and accessible, with examples in various languages showcasing the algorithm's broad applicability. Notably, the algorithm requires a constant amount of computationally intensive soft word comparisons relative to corpus size, ensuring flexible matching without compromising speed.

The reviewers have highlighted key areas needing enhancement, particularly the necessity for a more detailed empirical evaluation and analysis of how threshold settings impact speed and result relevance. The paper's reliance on static embeddings such as GloVe is noted as a limitation, given that these are less effective than contemporary contextual embeddings at capturing nuanced semantics. Additionally, the reviewers remarked that, despite the paper's notable technical contributions, its primary focus on linguistic applications and efficiency may not align well with venues centered on representation learning.

Overall, the paper has significant merits, I recommend acceptance.