Proximity search for point-of-interest names combining inexact string match with an expanding radius search
A point-of-interest mapping search system that combines inexact string searches with a proximity search to provide an extremely high probability of return of a set of search results in an initial search response that are useful to the user. Relevance of any particular point-of-interest item in a combined inexact string/proximity is dependent on both (1) a quality of the name match; and (2) a proximity to the starting location (or other relevant search center point) of the POI search. The inexact string name/proximity search is performed efficiently by iteratively expanding a search radius around a given location, searching concentric circles of proximity until a specified target number of relevant results have been found. It is the combination of the use of a combined inexact string match together with a proximity search performed against a database of geo-referenced business names that provides advantageous results.
1 . A Point-Of-Interest (POI ) search engine for a mapping device, comprising:
a POI database comprising a plurality of POIs, each POI including a name substring index, and each POI including a spatial index; and
an inexact string match and proximity search module to retrieve a plurality of POIs from said POI database that inexactly match at least one of said substrings associated therewith to an input search request having a desired proximity to a current location.
2 . The Point-Of-Interest (POI) search engine for a mapping device according to claim 1 , wherein said plurality of POIs each further comprise:
a value for area density
3 . The Point-Of-Interest (POI) search engine for a mapping device according to claim 1 , wherein:
said mapping device is a navigation system for an automobile.
4 . The Point-Of-Interest (POI) search engine for a mapping device according to claim 1 , wherein:
said mapping device is a phone-based wireless application for local search.
5 . The Point-Of-Interest (POI) search engine for a mapping device according to claim 1 , further comprising:
scoring relevant POIs against said input search request using a string edit distance calculation.
6 . A method of loading a Point-Of-Interest (POI) database into a navigation system, comprising:
loading a plurality of POI listings into a POI listings database;
providing a spatial index for each POI listing; and
indexing each of said plurality of POI listings into an inexact string match substring index, each entry having a given number of adjacent alphanumeric characters contained within said respective POI listing.
7 . The method of loading a Point-Of-Interest (POI) database into a navigation system according to claim 6 , wherein:
said given number of adjacent alphanumeric characters is three.
8 . The method of loading a Point-Of-interest (POI) database into a navigation system according to claim 6 , further comprising:
providing an area density for each POI listing.
9 . Apparatus for loading a Point-Of-Interest (POI) database into a navigation system, comprising:
means for loading a plurality of POI listings into a POI listings database;
means for providing a spatial index for each POI listing; and
means for indexing each of said plurality of POI listings into an inexact string match substring index, each entry having a given number of adjacent alphanumeric characters contained within said respective POI listing.
10 . The apparatus for loading a Point-Of-Interest (POI) database into a navigation system according to claim 9 , wherein:
said given number of adjacent alphanumeric characters is three.
11 . The apparatus for loading a Point-Of-Interest (POI) database into a navigation system according to claim 9 , further comprising:
means for providing an area density for each POI listing.