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

• US 11,238,024 B2
• Filed: 12/30/2019
• Issued: 02/01/2022
• Est. Priority Date: 11/20/2015
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Inventors: Pappu, Aasish, Stent, Amanda
• Primary Examiner(s): Beausoliel, Jr., Robert W
• Assistant Examiner(s): Khakhar, Nirav K
• Application Number:
  US16/729,802
• Publication Number:
  US 20200133931A1
• Time in Patent Office: 764 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:

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

mapping a 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 one or more location types associated with one or more buckets that are nearest neighbors in a view in a graphical user interface (GUI) on a mobile device;

receiving a user selection of a location type of the one or more location types; and

displaying one or more entities associated with the location type in a GUI view on the mobile device.

2. The method of claim 1, comprising ranking the one or more entities based on geographical proximity to the mobile device.

3. The method of claim 2, comprising using the ranking to determine prominence when displaying the one or more entities.

4. The method of claim 2, wherein the ranking is performed using a mapping app.

5. The method of claim 4, wherein the mapping app uses at least one of a geo-location or a geo-position for the mobile device.

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

7. The method of claim 6, wherein the continuous distribution model is at least one of a continuous bag-of-words model or a continuous skip-gram model.

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

9. The method of claim 1, wherein the similarity measure uses at least one of cosine similarity, city-block similarity, or Euclidian similarity.

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

creating an index of a plurality of buckets, wherein a bucket of the plurality of buckets includes one or more word or phrase embeddings derived from a corpus of documents that describe entities associated with geographic locations;

map a 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 one or more location types associated with one or more buckets that are nearest neighbors in a view in a graphical user interface (GUI) on a device;

receive a user selection of a location type of the one or more location types; and

display one or more entities associated with the location type in a GUI view on the device.

11. The non-transitory computer-readable media of claim 10, the operations comprising ranking the one or more entities based on geographical proximity to the device.

12. The non-transitory computer-readable media of claim 11, comprising using the ranking to determine prominence when displaying the one or more entities.

13. The non-transitory computer-readable media of claim 11, wherein the ranking is performed using a mapping app.

14. The non-transitory computer-readable media of claim 13, wherein the mapping app uses at least one of a geo-location or a geo-position for the device.

15. 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.

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

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

18. The non-transitory computer-readable media of claim 10, wherein the similarity measure uses at least one of cosine similarity, city-block similarity, or Euclidian similarity.

19. A method, comprising:

creating an index of a plurality of buckets, wherein a bucket of the plurality of buckets includes one or more word or phrase embeddings derived from a corpus of documents that describe entities associated with geographic locations;

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

displaying one or more location types associated with one or more buckets that are nearest neighbors in a view in a graphical user interface (GUI) on a device;

receiving a user selection of a location type of the one or more location types; and

displaying one or more entities associated with the location type in a GUI view on the device.

20. The method of claim 19, comprising ranking the one or more entities based on geographical proximity to the device.