Location-based recommendations using nearest neighbors in a locality sensitive hashing (LSH) index

• US 10,521,413 B2
• Filed: 11/20/2015
• Issued: 12/31/2019
• Est. Priority Date: 11/20/2015
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Oath Inc. (Verizon Communications Inc.)
• Inventors: Pappu, Aasish, Stent, Amanda
• Primary Examiner(s): Beausoliel, Jr., Robert W
• Assistant Examiner(s): Khakhar, Nirav K
• Application Number:
  US14/948,213
• Publication Number:
  US 20170147575A1
• Time in Patent Office: 1,502 Days
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/387 using geographical or spatial information, e.g. location
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/024 Guidance services

Abstract

Software for a website hosting short-text services creates an index of buckets for locality sensitive hashing (LSH). The software stores the index in an in-memory database of key-value pairs. The software creates, on a mobile device, a cache backed by the in-memory database. The software then uses a short text to create a query embedding. The software map the query embedding to corresponding buckets in the index and determines which of the corresponding buckets are nearest neighbors to the query embedding using a similarity measure. The software displays location types associated with each of the buckets that are nearest neighbors in a view in a graphical user interface (GUI) on the mobile device and receives a user selection as to one of the location types. Then the software displays the entities for the selected location type in a GUI view on the mobile device.

Claims

1. A method, comprising operations of:

creating an index of a plurality of buckets for locality sensitive hashing (LSH), wherein each bucket includes one or more word or phrase embeddings derived from a corpus of documents that describe entities associated with geographic locations;

storing the index in an in-memory database of key-value pairs;

creating, on a mobile device, a cache backed by the in-memory database, wherein the cache is in-memory;

using a short text to create a query embedding;

mapping the query embedding to corresponding buckets in the index and determining which of the corresponding buckets are nearest neighbors to the query embedding using a similarity measure;

displaying location types associated with each of the buckets that are nearest neighbors in a view in a graphical user interface (GUI) on the mobile device and receiving a user selection as to one of the buckets; and

displaying the entities for a selected location type in a GUI view on the mobile device, wherein each operation is performed by one or more processors.

2. The method of claim 1, wherein the operations involving the query embedding are performed in real-time or near real-time.

3. The method of claim 1, wherein the one or more word or phrase embeddings are derived from the corpus using a continuous distribution model.

4. The method of claim 3, wherein the continuous distribution model is a continuous hag-of-words model or a continuous skip-gram model.

5. The method of claim 4, further comprising an operation of ranking the entities for the selected location type according to geographical proximity to the mobile device, using a mapping app that uses a geo-location or a geo-position for the mobile device.

6. The method of claim 5, further comprising an operation of using rankings to determine prominence when displaying the entities.

7. The method of claim 1, wherein the short text is from a text message, an email, a calendar event, or a to-do list.

8. The method of claim 1, wherein a particular geographic location of said geographic locations is a geo-location or geo-position associated with the mobile device.

9. The method of claim 1, wherein said similarity measure uses one or more of cosine:

similarity, city-block similarity, and Euclidian similarity.

10. One or more non-transitory computer-readable media persistently, storing instructions that, when executed by a processor, perform the following operations:

creating an index of a plurality of buckets for locality sensitive hashing (LSH), wherein each bucket includes one or more word or phrase embeddings derived from a corpus of documents that describe entities associated with geographic locations;

storing the index in an in-memory database of key-value pairs;

creating, on a mobile device, a cache backed by the in-memory database, wherein the cache is in-memory;

using a short text to create a query embedding;

map the query embedding to corresponding buckets in the index and determine which of the corresponding buckets are nearest neighbors to the query embedding using a similarity measure;

display location types associated with each of the buckets that are nearest neighbors in a view in a graphical user interface (GUI) on the mobile device and receive a user selection as to one of the buckets; and

display the entities for a selected location type in a GUI view on the mobile device.

11. The non-transitory computer-readable media of claim 10, wherein the operations involving the query embedding are performed in real-time or near real-time.

12. The non-transitory computer-readable media of claim 10, wherein the one or more word or phrase embeddings are derived from the corpus using a continuous distribution model.

13. The non-transitory computer-readable media of claim 12, wherein the continuous distribution model is a continuous bag-of-words model or a continuous skip-gram model.

14. The non-transitory computer-readable media of claim 13, further comprising an operation of ranking the entities for the selected location type according to geographical proximity to the mobile device, using a mapping app that uses a geo-location or a geo-position for the mobile device.

15. The non-transitory computer-readable media of claim 14, further comprising an operation of using rankings to determine prominence when displaying the entities.

16. The non-transitory computer-readable media of claim 10, wherein the short text is from a text message, an email, a calendar event, or a to-do list.

17. The non-transitory computer-readable media of claim 10, wherein a particular geographic location of said geographic locations is a geo-location or a geo-position associated with the mobile device.

18. The non-transitory computer-readable media of claim 10, wherein the similarity is one or more of cosine similarity, city-block similarity, and Euclidian similarity.

19. A method, comprising operations of:

creating an index of a plurality of buckets for locality sensitive hashing (LSH), wherein each bucket includes one or more word or phrase embeddings derived, using a continuous distribution model, from a corpus of documents that describe entities associated with geographic locations;

storing the index in an in-memory database of key-value pairs;

creating, on a mobile device, a cache backed by the in-memory database, wherein cache is in-memory;

using a short text to create a query embedding;

mapping the query embedding to corresponding buckets in the index and determining which of the corresponding buckets are nearest neighbors to the query embedding using cosine similarity, city-block similarity, or Euclidian similarity;

displaying location types associated with each of the buckets that are nearest neighbors in a view in a graphical user interface (GUI) on the mobile device and receiving a user selection as to one of the buckets; and

displaying the entities for a selected location type in a GUI view on the mobile device, wherein the each operation is performed by one or more processors.

20. The method of claim 19, wherein the operations involving the query embedding are performed in real-time or near real-time.