Disambiguating road names in text route descriptions using Exact-All-Hop Shortest Path algorithm

Xiao Zhang, Baojun Qiu, Prasenjit Mitra, Sen Xu, Alexander Klippel, Alan M. MacEachren

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


Automatic extraction and understanding of human-generated route descriptions have been critical to research aiming at understanding human cognition of geospatial information. Among all research issues involved, road name disambiguation is the most important, because one road name can refer to more than one road. Compared with traditional toponym (place name) disambiguation, the challenges of disambiguating road names in human-generated route description are three-fold: (1) the authors may use a wrong or obsolete road name and the gazetteer may have incomplete or out-of-date information; (2) geographic ontologies often used to disambiguate cities or counties do not exist for roads, due to their linear nature and large spatial extent; (3) knowledge of the co-occurrence of road names and other toponyms are difficult to learn due to the difficulty in automatic processing of natural language and lack of external information source of road entities. In this paper, we solve the problem of road name disambiguation in human-generated route descriptions with noise, i.e. in the presence of wrong names and incomplete gazetteer. We model the problem as an Exact-All-Hop Shortest Path problem on a semi-complete directed k-partite graph, and design an efficient algorithm to solve it. Our disambiguation algorithm successfully handles the noisy data and does not require any extra information sources other than the gazetteer. We compared our algorithm with an existing map-based method. Experiment results show that our algorithm significantly outperforms the existing method.

Original languageEnglish (US)
Title of host publicationECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration
PublisherIOS Press BV
Number of pages6
ISBN (Print)9781614990970
StatePublished - 2012
Event20th European Conference on Artificial Intelligence, ECAI 2012 - Montpellier, France
Duration: Aug 27 2012Aug 31 2012

Publication series

NameFrontiers in Artificial Intelligence and Applications
ISSN (Print)0922-6389
ISSN (Electronic)1879-8314


Other20th European Conference on Artificial Intelligence, ECAI 2012

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence


Dive into the research topics of 'Disambiguating road names in text route descriptions using Exact-All-Hop Shortest Path algorithm'. Together they form a unique fingerprint.

Cite this