METHODS, DEVICES AND COMPUTER SOFTWARE FOR FACILITATING SEARCHING AND DISPLAY OF LOCATIONS RELEVANT TO A DIGITAL MAP

• US 20160078037A1
• Filed: 04/17/2014
• Published: 03/17/2016
• Est. Priority Date: 04/17/2013
• Status: Active Grant

• Current Assignee: TomTom Navigation B.V (TomTom NV)
• Original Assignee: TomTom Navigation B.V (TomTom NV)
• Inventors: Wolf, Martin, Hol, Maurits, De Boer, Michel, Ziezold, Hendrik Sebastian, Tertoolen, Simone Francine, Doorduyn, Mathieu M.B., Viddeleer, Marc Alexander, Bogdan, Adrian Catalin, Voogt, Joost Cornelis Frederik, Willemstein, Ruud
• Granted Patent: US 11,720,574 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/3335 Syntactic pre-processing, e.g. stopword elimination, stemming
• CPC Class Codes: G06F 16/444 Spatial browsing, e.g. 2D maps, 3D or virtual spaces
• CPC Class Codes: G06F 3/0484 for the control of specific functions or operations, e.g. selecting or manipulating an object, an image or a displayed text element, setting a parameter value or selecting a range

Abstract

A portable electronic device is disclosed comprising data processing means and a data repository containing: data records representative of locations relevant to or within a digital map; and data representative of an index associating words contained in the data records with the records in which those words appear. The device further comprises means for, in relation to a received search query including a search string, processing the search string to provide one or more search words; querying the index to identify data records containing the or each search word; and generating a rank for each of the one or more identified data records indicative of the relevance of each identified data record to the search query.

Claims

1. A portable electronic device comprising:

one or more processors;

data repository containing;

data records representative of locations relevant to or within a digital map; and

data representative of an index associating words contained in the data records with the records in which those words appear; and

computer readable medium comprising instructions which, when executed by the one or more processors, cause the electronic device, in relation to a received search query including a search string derived from user input on a user interface of the electronic device, to;

process the search string to provide one or more search words;

query the index to identify data records containing the or each search word;

generate a rank for each of the one or more identified data records indicative of the relevance of each identified data record to the search query; and

cause the display of the results of the search query on a display of the electronic device.

2. A portable electronic device as claimed in claim 1, the instructions further cause the electronic device, when processing the search string, to perform one or more of:

splitting the search string into words;

normalising the words;

identifying and treating special words.

3. A portable electronic device as claimed in claim 2, wherein normalising the words includes one or more processing steps intended to account for irregularities in the content of the search string, optionally including one or more of:

converting all letters to lower case;

removing accents from letters;

replacing a sequence of the same letter by a single letter;

replacing single letters with other letters;

replacing words and abbreviations with standard abbreviations.

4. A portable electronic device as claimed in claim 2, wherein the index contains normalised versions of the words contained in the data records and the search string is processed to normalise the words contained therein using the same normalisation rules used in the generation of the index.

5. A portable electronic device as claimed in claim 2, wherein identifying and treating special words includes one or more of:

converting country names and codes to standard country codes;

removing house numbers;

identifying words that correspond to categories of places of interest (POI), and replacing with a POI category code.

6. A portable electronic device as claimed in claim 5, wherein if the full search string is a POI category name or a prefix of a single POI category name, the query is for records in the POI category.

7. A portable electronic device as claimed in claim 5, wherein if the full search string includes more than one word and starts with a POI category name, two queries are produced as follows:

a first query in which the POI category name is provided as a search word;

a second query in which the POI category name is replaced by a POI category code.

8. A portable electronic device as claimed in claim 1, wherein the instructions further cause the electronic device, when query the index to identify data records containing the or each search word, to:

for each search word, find the set of matching records from the index; and

determine the intersection of the sets of records to provide the records that match all words.

9. A portable electronic device as claimed in claim 1, wherein the instructions further cause the electronic device, when generating a rank for each data record, to:

calculate a score for each record;

ranking the records based on their scores;

if two records have the same score, reconcile their rank ordering based on a distance from a search centre if available, otherwise the rank order if the two records is random.

10. A portable electronic device as claimed in claim 9, wherein calculating a ranking score for each record includes starting from a starting score and perform one or more of:

subtract a penalty from the score for each word contained in the search string not exactly matched to a word contained in the data record;

subtract a penalty from the score for a structural difference between the search words arranged in the search string and how the words appear in the data record, including incorrect word order and word gaps;

subtract a penalty from the score for each unmatched word contained in a component for which there is a word matching a search word;

add a bonus to the score for data records indicated as important matches.

11. A portable electronic device as claimed in claim 10, wherein calculating a ranking score for a record representing an address includes one or more of:

not ranking the data record if there is no search word matched against a word in the index contained in the street name of the data record;

if there is a search centre, adjusting one or more of the penalties to;

suppress penalties for data records relatively near to the search centre, or increase penalties for data records relatively distant to the search centre, or both;

add a bonus to the score if there is a word match with a centre of settlement, dependent on the size of the centre of settlement and a distance of the centre of settlement from a search centre, if available.

12. A portable electronic device as claimed in claim 10, wherein calculating a ranking score for a record representing a place of interest (POI) includes one or more of:

not ranking the data record if there is no search word matched against a word in the index contained in the one of the components of the data record representing the name of the POI, the brand name of the POI or the POI category;

if there is a search centre, not subtracting a penalty from the score for each unmatched word contained in a component for which there is a word matching a search word;

if there is no search centre, subtracting a penalty from the score for each unmatched word contained in a component of the data record representing the name of the POI or the brand name of the POI for which there is a word matching a search word;

if there is no search centre, subtracting a penalty from the score if there is no search word matched against a word in the index contained in the name of the POI or the brand name of the POI.

13. A portable electronic device as claimed in claim 1, wherein the data records contain a location reference representative of a region of at least one of a digital map and a record identifier.

14. A portable electronic device as claimed in claim 13, wherein the record identifier comprises a first portion and a second portion:

the first portion being the location reference; and

the second portion being a reference or pointer to information associated with the location of the data record in the digital map.

15. A portable electronic device as claimed in claim 13, wherein the index includes tuples one for each word of the set of words contained in the data records relating each of said words to the respective record identifiers of all the records in which those words appear.

16. A portable electronic device as claimed in claim 1, wherein each data record represents either an address or a Place of Interest (POI).

17. A portable electronic device as claimed in claim 16, wherein the data records contain one or more of the following components or data indicative thereof:

street name;

place name;

postal code;

country code;

POI name;

POI brand name;

POI address; and

POI category code.

18. A portable electronic device as claimed in claim 1, wherein the search string is derived from a single field free-text string input by the user on the user interface.

19. A method of operating a portable electronic device comprising one or more processors, data repository containing:

data records representative of locations relevant to or within a digital map; and

data representative of an index associating words contained in the data records with the records in which those words appear, the method comprising, in relation to a received search query including a search string derived from user input on a user interface of the electronic device;

processing the search string to provide one or more search words;

querying the index to identify data records containing the or each search word;

generating a rank for each of the one or more identified data records indicative of the relevance of each identified data record to the search query; and

causing the display of the results of the search query on a display of the electronic device.

20. A non-transitory computer readable medium comprising instructions which when executed by one or more processors of a portable electronic device cause the electronic device to be configured to carry out the method of claim 19.