Location searching with category indices

• US 9,727,595 B2
• Filed: 09/20/2013
• Issued: 08/08/2017
• Est. Priority Date: 09/20/2013
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Uber Technologies, Inc.
• Inventors: Song, Zhaolei, Hamby, Brent
• Primary Examiner(s): PEACH, POLINA G
• Application Number:
  US14/033,328
• Publication Number:
  US 20150088860A1
• Time in Patent Office: 1,418 Days
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

A map searching system determines locations responsive to a search query. The map searching system parses the search query to generate a set of search tokens and searches a plurality of location category indices using the search tokens. The location category indicies specify indexes of locations according to various location categories, such as points of interest and cross streets. The resulting records selected from the search tokens are scored based on scoring weights specific to the location category index that a record was selected from. After scoring, a number of high-scoring records are selected as the responsive records to the location search.

Claims

1. A method for selecting a location responsive to a location search query, the method comprising:

receiving, by one or more processors, a location search query comprising a textual string;

parsing, by the one or more processors, the textual string to generate a set of search tokens;

identifying a first location category index describing locations using a first plurality of fields;

identifying a second location category index describing locations using a second plurality of fields including at least a common field with the first plurality of fields and a different field than the first plurality of fields;

searching, by the one or more processors, the first location category index to select a first set of index search results by identifying locations in the first location category index that have one or more fields of the first plurality of fields at least partially matching a search token in the set of search tokens;

identifying a first set of scoring weights designating a weight for each field in the first plurality of fields of the first location category index;

scoring each index search result in the first set of index search results by scoring each field of the first plurality of fields that at least partially matches a search token in the set of search tokens according to the scoring weight for that field of the first set of scoring weights;

searching, by the one or more processors, the second location category index to select a second set of index search results by identifying locations in the second location category index that have one or more fields of the second plurality of fields at least partially matching a search token in the set of search tokens;

identifying a second set of scoring weights designating a weight for each field in the second plurality of fields of the second location category index, the common field designated with different weights by the first and second sets of scoring weights, the weights of the common field determined based on a relative importance of the common field to the respective location category index;

scoring each index search result in the second set of index search results by scoring each field of the second plurality of fields that at least partially matches a search token in the set of search tokens according to the scoring weight for that field of the second set of scoring weights; and

selecting, for the location, an index search result of the first set of index search results or the second set of index search results based on the scoring of the first set of index search results and the scoring of the second set of index search results.

2. The method of claim 1, wherein the scoring for each index search result in the first set of index search results includes a distance score using a distance of the index search result from a determined location, and wherein the scoring excludes index search results that exceed a threshold distance from the determined location.

3. The method of claim 1, wherein the first and second sets of scoring weights are further determined based on reputations of a first and second provider of the first and second location category indices, respectively.

4. The method of claim 3, wherein the first provider is different than the second provider.

5. The method of claim 1, wherein the first category location index describes one or more of:

points of interest, point addresses, address ranges, streets, cross streets, and geographies.

16. The method of claim 1, wherein at least one location is described by the first location category index and by the second location category index.

18. The method of claim 1, wherein the second weight is greater than the first weight based on user feedback indicating that index search results from the second set of index search results are selected more frequently than index search results from the first set of index search results.

6. A computer program product for selecting a location responsive to a location search query, the computer program product comprising a non-transitory computer-readable storage medium containing computer program code for:

receiving, by one or more processors, a location search query comprising a textual string;

parsing, by the one or more processors, the textual string to generate a set of search tokens;

identifying a first location category index describing locations using a first plurality of fields;

identifying a second location category index describing locations using a second plurality of fields including at least a common field with the first plurality of fields and a different field than the first plurality of fields;

searching, by the one or more processors, the first location category index to select a first set of index search results by identifying locations in the first location category index that have one or more fields of the first plurality of fields at least partially matching a search token in the set of search tokens;

identifying a first set of scoring weights designating a weight for each field in the first plurality of fields of the first location category index;

scoring each index search result in the first set of index search results by scoring each field of the first plurality of fields that at least partially matches a search token in the set of search tokens according to the scoring weight for that field of the first set of scoring weights;

searching, by the one or more processors, the second location category index to select a second set of index search results by identifying locations in the second location category index that have one or more fields of the second plurality of fields at least partially matching a search token in the set of search tokens;

identifying a second set of scoring weights designating a weight for each field in the second plurality of fields of the second location category index, the common field designated with different weights by the first and second sets of scoring weights, the weights of the common field determined based on a relative importance of the common field to the respective location category index;

scoring each index search result in the second set of index search results by scoring each field of the second plurality of fields that at least partially matches a search token in the set of search tokens according to the scoring weight for that field of the second set of scoring weights; and

selecting, for the location, an index search result of the first set of index search results or the second set of index search results based on the scoring of the first set of index search results and the scoring of the second set of index search results.

7. The computer program product of claim 6, wherein the scoring for each index search result in the first set of index search results includes a distance score using a distance of the index search result from a determined location, and wherein the scoring excludes index search results that exceed a threshold distance from the determined location.

8. The computer program product of claim 6, wherein the first and second sets of scoring weights are further determined based on reputations of a first and second provider of the first and second location category indices, respectively.

9. The computer program product of claim 8, wherein the first provider is different than the second provider.

10. The computer program product of claim 6, wherein the first category location index describes one or more of:

points of interest, point addresses, address ranges, streets, cross streets, geographies.

17. The computer program product of claim 6, wherein at least one location is described by the first location category index and by the second location category index.

19. The computer program product of claim 6, wherein the second weight is greater than the first weight based on user feedback indicating that index search results from the second set of index search results are selected more frequently than index search results from the first set of index search results.

11. A system for selecting a location responsive to a location search query, comprising:

one or more processors configured for executing instructions; and

a non-transitory computer-readable storage medium, storing instructions that when executed by the one or more processors cause the one or more processors to;

receive a location search query comprising a textual string;

parse the textual string to generate a set of search tokens;

identify a first location category index describing locations using a first plurality of fields;

identify a second location category index describing locations using a second plurality of fields including at least a common field with the first plurality of fields and a different field than the first plurality of fields;

search, by the one or more processors, the first location category index to select a first set of index search results by identifying locations in the first location category index that have one or more fields of the first plurality of fields at least partially matching a search token in the set of search tokens;

identify a first set of scoring weights designating a weight for each field in the first plurality of fields of the first location category index;

score each index search result in the first set of index search results by scoring each field of the first plurality of fields that at least partially matches a search token in the set of search tokens according to the scoring weight for that field of the first set of scoring weights;

search, by the one or more processors, the second location category index to select a second set of index search results by identifying locations in the second location category index that have one or more fields of the second plurality of fields at least partially matching a search token in the set of search tokens;

identify a second set of scoring weights designating a weight for each field in the second plurality of fields of the second location category index, the common field designated with different weights by the first and second sets of scoring weights, the weights of the common field determined based on a relative importance of the common field to the respective location category index;

score each index search result in the second set of index search results by scoring each field of the second plurality of fields that at least partially matches a search token in the set of search tokens according to the scoring weight for that field of the second set of scoring weights; and

select, for the location, an index search result of the first set of index search results or the second set of index search results based on the scoring of the first set of index search results and the scoring of the second set of index search results.

12. The system of claim 11, wherein the scoring for each index search result in the first set of index search results includes a distance score using a distance of the index search result from a determined location, and wherein the scoring excludes index search results that exceed a threshold distance from the determined location.

13. The system of claim 11, wherein the first and second sets of scoring weights are further determined based on reputations of a first and second provider of the first and second location category indices, respectively.

14. The system of claim 13, wherein the first provider is different than the second provider.

15. The system of claim 11, wherein the first category location index describes one or more of:

points of interest, point addresses, address ranges, streets, cross streets, and geographies.