A Robust Retrieval Engine for Proximal and Structural Search

Katsuya Masuda, Takashi Ninomiya, Yusuke Miyao, Tomoko Ohta, Jun'ichi TsujiiNAACL 2003 · OpenReview

Authors: Katsuya Masuda, Takashi Ninomiya, Yusuke Miyao, Tomoko Ohta, Jun’ichi Tsujii
Source: Companion Volume of the Proceedings of HLT-NAACL 2003 - Short Papers (2003)

Introduction

Information Retrieval (IR) has traditionally been divided into two distinct paradigms: keyword-based search and structural search. Keyword search is highly robust, offering ranked results based on statistical relevance (e.g., TF-IDF), but it typically ignores the internal hierarchy and semantic structure of documents. Conversely, structural search frameworks, such as Region Algebra or XML-based querying, allow for precise constraints (e.g., "find a gene name within a title tag"). However, these structural systems are often brittle; they rely on exact matching, meaning that minor deviations in document structure can result in zero hits.

This paper introduces a ranked retrieval model designed to bridge this gap. By combining the precision of structural constraints with the flexibility of keyword-based ranking, the authors propose an engine that can retrieve and rank relevant documents even when they do not perfectly conform to the requested structure.

Methodology: Subquery Decomposition and Relevance Vectors

The core of the proposed engine is the decomposition of complex structural queries into manageable sub-components. The authors build upon Region Algebra, a framework that defines relationships between text "extents" (continuous fragments of text).

Subquery Decomposition

A structured query is represented as a tree. The system systematically breaks this tree down into every possible sub-component. For example, a query seeking a specific term within a specific tag is decomposed into the term itself, the tag itself, and the relationship between them.

Figure 1: Decomposition of a structured query into subqueries.

Relevance Vectors and Ranking

Instead of a binary "match/no match" result, the system calculates a relevance score for every subquery using traditional IR metrics like TF-IDF. This treats structural "extents" as if they were keywords. The total relevance of a document is then represented as a vector of these subquery scores. To rank the results, the engine maps these vectors to a single scalar value using one of three proposed methods:

  1. Simple Sum: A straightforward addition of all subquery scores.
  2. Structure Coefficient: Weighting scores based on the information density or rarity of a specific structural relationship.
  3. Interpolated Coefficient: A recursive weighting scheme that balances the importance of a parent node in the query tree against its children, allowing for fine-tuned control over structural strictness.

Experimental Setup

The researchers evaluated their model using the GENIA corpus, a collection of 1,990 biomedical paper abstracts. The GENIA corpus is uniquely suited for this task as it is richly annotated with XML-style semantic tags (e.g., <term>, <sentence>, <protein>), providing a complex structural landscape for testing.

Because no standard benchmark exists for ranked structural queries, the authors utilized expert manual evaluation to determine the relevance of the top 10 results for several complex biomedical queries.

Key Results

The proposed model was compared against two baselines: an Exact Match model (traditional structural search) and a Flat Model (standard keyword search that ignores structure).

Figure 4: Performance comparison across four test queries.

As shown in the results table, the proposed model consistently outperformed both baselines. In Query 1 and 3, it achieved perfect precision (10/10) in the top results.

Robustness to Noise

A critical finding occurred in Query 4, where a "dummy" (non-existent) tag was intentionally included in the query. The Exact Match model failed completely, returning zero results because the structure did not exist. However, the proposed model achieved a 7/10 relevance rate. By decomposing the query, the engine was able to "ignore" the impossible constraint and still find highly relevant documents based on the remaining valid parts of the query tree.

Conclusion and Future Work

The authors successfully demonstrated that treating structural fragments as searchable units allows for a more robust and flexible IR system. This approach provides "partial credit" for documents that are semantically relevant but structurally imperfect.

While promising, the study notes several areas for future development. The current experiments were conducted on a relatively small corpus, and scaling the vector-based ranking to millions of documents remains a challenge. Additionally, the reliance on manual expert evaluation highlights the need for a standardized, large-scale test collection for structural IR research.

Summary updated

Abstract

Katsuya Masuda, Takashi Ninomiya, Yusuke Miyao, Tomoko Ohta, Jun’ichi Tsujii. Companion Volume of the Proceedings of HLT-NAACL 2003 - Short Papers. 2003.
BibTeX
@inproceedings{masuda2003robust,
  author = {Katsuya Masuda and Takashi Ninomiya and Yusuke Miyao and Tomoko Ohta and Jun'ichi Tsujii},
  title = {{A Robust Retrieval Engine for Proximal and Structural Search}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2003},
  url = {https://openreview.net/forum?id=mGQ5NLzrGxT},
}
Figure