Tagging Address Queries in Maps Search

Shekoofeh Mokhtari, Ahmad Mahmoody, Dragomir Yankov, Ning XieAAAI 2019 · DOI

Abstract

Accurate interpretation of address queries is a fundamental challenge for map search engines. This paper evaluates various recurrent neural network (RNN) architectures for the task of address tagging—the process of labeling components like business names, street names, and cities within a query. The study demonstrates that Sequence-to-Sequence (Seq2Seq) models significantly outperform traditional one-directional methods, particularly when handling the complex, unstructured, and multi-entity queries common in real-world search logs.

Introduction

When a user enters a query like "Starbucks near Fremont, Seattle," a geocoder must correctly identify that "Starbucks" is a business, "Fremont" is a neighborhood, and "Seattle" is a city. This process, known as address tagging, is deceptively difficult. Users rarely follow strict postal standards, and search logs are frequently filled with typos, abbreviations, and colloquialisms.

Example of tagging a complex multi-point query involving a business and intersections.

Furthermore, many queries are ambiguous. Without global context, a geocoder might struggle to determine if a term refers to a street, a neighborhood, or a business. Simple lookup tables are often insufficient because the majority of address queries belong to the "long tail"—unique strings that appear only once in search history.

Methodology

The authors framed address parsing as a sequence tagging problem and compared three deep learning architectures:

  1. One-Directional RNNs (Forward-LSTM): These process queries from left to right. Their primary limitation is the inability to use information from the end of a query to help label the beginning.
  2. Bi-Directional RNNs (Bi-LSTM): These process the query in both directions simultaneously, providing the model with full context before it assigns labels.
  3. Sequence-to-Sequence (Seq2Seq): This architecture uses an encoder to compress the entire query into a "context vector" and a decoder to generate the corresponding tags.
The Seq2Seq architecture uses a context vector to inform the decoding of address tags from the input sequence.

All models were implemented using the Microsoft Cognitive Toolkit (CNTK) with a hidden layer size of 128.

Datasets and Evaluation

The study utilized two primary data sources for training and testing:

  • Real-world en-US Logs: Human-labeled English queries from the United States, categorized into Single Point (SP) queries (standard addresses) and Multi-Point (MP) queries (complex queries involving intersections or landmarks).
  • Synthetic Yelp Data: Millions of synthetic queries generated from business data to mimic common search patterns and provide a robust training set.

Key Results

The models were evaluated based on per-query tagging accuracy. The results revealed a clear hierarchy in performance, with multi-directional context proving essential for accuracy.

Model en-US (SP) en-US (SP & MP)
Forward-LSTM 90.09% 73.02%
Bi-LSTM 98.77% 96.69%
Seq2Seq 99.17% 97.50%

Seq2Seq emerged as the overall winner, particularly on the more difficult combined SP & MP dataset. The transition from one-directional to bi-directional processing resulted in a massive ~23% improvement on complex queries, proving that "looking ahead" to the end of a query is vital for resolving ambiguity.

Discussion and Future Work

While Bi-LSTMs are powerful, the Seq2Seq architecture proved most resilient for real-world search logs, which are often messier than synthetic data. However, the authors note several areas for future improvement:

  • Market Expansion: The current study focuses on the US; global address systems (e.g., India) are often more descriptive and less standardized.
  • Granularity: Moving from word-level to character-level models could better handle the high frequency of typos and rare abbreviations found in mobile search.
  • Hierarchy: Future models could utilize hierarchical neural networks to better capture the nested nature of geographic entities (e.g., House -> Street -> City).

Summary updated

BibTeX
@inproceedings{mokhtari2019tagging,
  author = {Shekoofeh Mokhtari and Ahmad Mahmoody and Dragomir Yankov and Ning Xie},
  title = {{Tagging Address Queries in Maps Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33019547},
}
Figure