Contextual search for location services

• US 10,565,279 B2
• Filed: 10/05/2016
• Issued: 02/18/2020
• Est. Priority Date: 10/05/2016
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Uber Technologies, Inc.
• Inventors: Reddy, Srihari, Mahon, Paul, Hamby, Brent, Iles, Brandon, Sarawgi, Aditya, Salisbury, Will, Song, Zach, Dabholkar, Juthika
• Primary Examiner(s): Somers, Marc S
• Application Number:
  US15/286,553
• Publication Number:
  US 20180095977A1
• Time in Patent Office: 1,231 Days
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

A travel coordination system identifies geographic locations responsive to a location search request. The geographic locations are organized into a plurality of hierarchical geohash levels, each geohash level mapping the geographic location into a geohash of a different area. The locations search request designates a search context for the search, such as whether the user is searching for an origin of a trip or a destination. The context of the search can be used to determine a geohash level for selecting candidate search results. The candidate search results may be scored based on the context using prior user selections and trips scheduled with the trip coordination system. A geohash and context associated with the user'"'"'s request may be used to modify a scoring function of the candidate search results based on prior trips.

Claims

1. A method comprising:

receiving a location search request from a client device specifying a search query;

identifying, for a search context and at each search level, a percentage of locations historically selected by users within a historical geohash corresponding to a historical request location at the geohash level;

selecting a geohash level from a plurality of hierarchical geohash levels, the selection being based on the percentage for that geohash level and the search context describing one or more parameters of the location search request, each level of the plurality of hierarchical geohash levels being associated with a different area size and a set of geohashes, each geohash being associated with geographic locations within a geographic area having the area size of the geohash level, the geographic locations indexed with respect to indices at multiple geohash levels;

identifying a set of candidate locations for the search query based on a first geohash for a location of the client device at the selected geohash level, the set of candidate locations determined from an index of the selected geohash level and the identified percentage of locations; and

providing the set of candidate locations to the client device.

2. The method of claim 1, wherein a first geohash level associated with a first area size is selected when the search context indicates the location search request is for an origin of a trip, and a second geohash level associated with a second area size is selected when the search context indicates the location search request is for a destination of a trip, wherein the first area size is smaller than the second area size.

3. The method of claim 1, wherein the geohash level is selected that has at least 90% of locations historically selected by users.

4. The method of claim 1, wherein each geohash is associated with a search shingle identifying locations within the geohash and additional locations within a threshold distance of the geohash;

and wherein the set of candidate locations are identified from the search shingle associated with the first geohash.

5. The method of claim 4, wherein the threshold distance is a percentage of the area size of the geohash.

6. The method of claim 5, wherein the percentage is 50%.

7. A method comprising:

receiving a location search request from a client device specifying a search query;

identifying a search context for the client device describing one or more parameters of the location search request;

identifying a user geohash corresponding to a location of the client device from a set of geohashes, each geohash being associated with geographic locations within a geographic area;

identifying a set of candidate locations for the search query;

determining a scoring function that assesses the probability of the user selecting a candidate location based at least in part on the distance of the user geohash to the candidate location, wherein the scoring function is based on a distribution of trip distances, the distribution selected based on the search context at the user geohash;

scoring each candidate location from the set of candidate locations using the scoring function; and

providing the set of candidate locations to the client device.

8. The method of claim 7, wherein the scoring function scores a candidate location based on a geohash associated with the candidate location.

9. The method of claim 8, wherein the scoring function scores the probability of a user selecting a location in a destination geohash from the user geohash, wherein the destination geohash is the geohash associated with the set of candidate locations.

10. The method of claim 7, wherein each geohash of the set of geohashes is associated with a scoring function.

11. The method of claim 7, wherein:

each geohash of the plurality of geohashes is associated with a plurality of scoring functions, each associated with a search context; and

the scoring function is selected from among the plurality of scoring functions for the user geohash by matching the search context for the client device with a search context of the plurality of scoring functions.

12. The method of claim 7, wherein one of the search context parameters specifies whether the location search request is for an origin or a destination of a trip request.

13. The method of claim 12, wherein one of the search context parameters specifies a time of day for the search.

14. The method of claim 7, wherein the scoring function specifies a set of weights for scoring a location.

15. The method of claim 7, wherein distribution of trip distance is associated with a destination geohash of the candidate location, wherein the destination geohash is the geohash associated with the set of candidate locations.