Robust location search from text queries

ABSTRACT

Robust, global, address geocoding is challenging because there is no single address format that applies to all geographies, and in any case, users may not restrict themselves to well-formed addresses. Particularly in online mapping systems, users frequently enter queries with missing or conflicting information, misspellings, address transpositions, and other such variations.

We present a novel system which handles these difficulties by using a combination of textual similarity and spatial coherence to guide a depth-first search over the large space of possible interpretations of a text query. The system robustly matches text subsequences of a query with text attributes (i.e., any text labels associated with the entity) in a spatial-entity database. Each matched attribute is associated with the pre-computed spatial union of all entities that have that attribute. Candidate results are formed by incremental spatial intersections of these unions.

Experimental results demonstrate that our system is capable of supporting regions with widely differing address formats, without region-specific customization or training. Furthermore, we show that our system significantly outperforms commercial systems for unstructured location queries and queries containing errors.

REFERENCES

• 1: Rahul Bakshi , Craig A. Knoblock , Snehal Thakkar, Exploiting online sources to accurately geocode addresses, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA [doi>10.1145/1032222.1032251]
• 2: Cayo, M. R. and Talbot, T. O. Positional error in automated geocoding of residential addresses. International Journal of Health Geographics 2003, 2:10.
• 3: Surajit Chaudhuri , Kris Ganjam , Venkatesh Ganti , Rajeev Motwani, Robust and efficient fuzzy match for online data cleaning, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872796]
• 4: Yen-Yu Chen , Torsten Suel , Alexander Markowetz, Efficient query processing in geographic web search engines, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142505]
• 5: Christen, P., Churches, T. and Willmore, A. A Probabilistic Geocoding System based on a National Address File. Proceedings of the 3rd Australasian Data Mining Conference, Cairns, December 2004.
• 6: Irene Gargantini, An effective way to represent quadtrees, Communications of the ACM, v.25 n.12, p.905-910, Dec 1982 [doi>10.1145/358728.358741]
• 7: Goldberg, D. W., Wilson, J. P. and Knoblock, C. A. From Text To Geographic Coordinates: The Current State of Geocoding. Urban and Regional Information Systems Association Journal 2006
• 8: Edwin H. Jacox , Hanan Samet, Spatial join techniques, ACM Transactions on Database Systems (TODS), v.32 n.1, p.7-es, March 2007 [doi>10.1145/1206049.1206056]
• 9: Kimler M. Geo-Coding: Recognition of geographical references in unstructured text and their visualization. Diplomarbeit, Fachhochschule Hof, 2004
• 10: Krieger, N., Waterman, P., Lemieux, K., Zierler, S. and Hogan J. W. On the wrong side of the tracts? Evaluating the accuracy of geocoding in public health research American Journal of Public Health, Vol 91, Issue 7 2001
• 11: Jochen L. Leidner, Toponym resolution in text (abstract only): "which sheffield is it?", Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009147]
• 12: Nicoara, G. Exploring the Geocoding Process: A Municipal Case Study using Crime Data. Masters thesis, The University of Texas at Dallas, Dallas, TX, USA 2005
• 13: Bruno Pouliquen , Ralf Steinberger , Camelia Ignat , Tom De Groeve, Geographical information recognition and visualization in texts written in various languages, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968115]
• 14: Rajagopalan S., Spatial Data in Telematics: An Indian Experience Conference cum Exposition on Telematics in Transportation, Chennai September 2004
• 15: Ratcliffe, J. H., On the accuracy of TIGER-type geocoded address data in relation to cadastral and census areal units. International Journal of Geographic Information Sciences 15 (5) 2001
• 16: Graham Rhind, Global SourceBook of Address Data Management: A Guide to Address Formats and Data in 194 Countries, Gower Publishing Co., Brookfield, VT 05036, 1998
• 17: Trillium Software System ®, Harte-Hanks Trillium Software, Billerica, MA 01821. http://www.trilliumsoftware.com
• 18: Paul Viola , Mukund Narasimhan, Learning to extract information from semi-structured text using a discriminative context free grammar, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076091]
• 19: Yinghua Zhou , Xing Xie , Chuang Wang , Yuchang Gong , Wei-Ying Ma, Hybrid index structures for location-based web search, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099584]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Abstracting methods

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.3 Information Search and Retrieval
          Subjects: Search process; Selection process; Query formulation

General Terms:
Algorithms, Design

Keywords:
ambiguous spatial queries, geocoding, location search