Progressive spatial searching using augmented structures

• US 10,204,142 B2
• Filed: 11/30/2014
• Issued: 02/12/2019
• Est. Priority Date: 12/29/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Chakrabarti, Kaushik, Chaudhuri, Surajit, Roy, Senjuti Basu
• Primary Examiner(s): Yen, Syling
• Application Number:
  US14/556,232
• Publication Number:
  US 20150088904A1
• Time in Patent Office: 1,535 Days
• Field of Search: 707706, 707713, 707722, 707736, 707748, 707758, 707759, 707760, 707764, 707769, 707781, 707999002-999006
• CPC Class Codes: G01C 21/3611 using character input or menus, e.g. menus of POIs character input methods in general G06F3/0233
• CPC Class Codes: G01C 21/3679 Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities G01C21/3611 takes precedence
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A location associated with a user of a computing device and a prefix portion of an input string may be received as one or more successive characters of the input string are provided by the user via the computing device. A list of suggested items may be obtained based on a function of respective recommendation indicators and proximities of the items to the location in response to receiving the prefix portion, and based on partially traversing a character string search structure having a plurality of non-terminal nodes augmented with bound indicators associated with spatial regions. The list of suggested items and descriptive information associated with each suggested item may be returned to the user, in response to receiving the prefix portion, for rendering an image illustrating indicators associated with the list in a manner relative to the location, as the user provides each successive character of the input string.

Claims

1. A mobile device comprising:

a processor;

a display;

a prefix string receiving engine, when executed by the processor, configured to detect a prefix portion of an input string as one or more successive characters of the input string are provided by the user via the mobile device;

a location determination engine, when executed by the processor, configured to automatically determine a current location associated with the user of the mobile device at substantially the same time as a detection of the input string provided by the user;

a suggestion engine, when executed by the processor, in response to detecting the prefix portion of the input string, configured to obtain a list of suggested businesses associated with valid string completions of the prefix portion, and sort the obtained list of suggested businesses based on at least rating indicators of the suggested businesses and spatial proximities of the suggested businesses to the current location, wherein the suggestion engine is further configured to;

(1) send at least one detected prefix portion to a server comprising a search engine, (2) receive, from the search engine, at least one autocompleted string identifying a name of a business based on the at least one detected prefix portion, and (3) upon receiving a selection of the at least one autocompleted string by the user, obtain the list of the suggested businesses from the search engine; and

a rendering engine, when executed by the processor, configured to, display to the user via the display a rating indicator associated with each of at least a subset of businesses in the list of the suggested businesses and display to the user via the display an image illustrating a geographic location of each of at least a subset of businesses in the suggested list of businesses in a manner relative to the current location of the user of the mobile device.

2. The mobile device of claim 1, wherein the one or more successive characters of the input string are provided by the user via one of a touchscreen, touchpad, keyboard, keypad, audio input device, or another input sensing device.

3. The mobile device of claim 1, wherein the current location associated with the user of the mobile device is determined using global positioning system.

4. The mobile device of claim 1, wherein the rendering engine is further configured to display to the user a geographic distance of each of the suggested businesses from the current location associated with the user of the mobile device.

5. The mobile device of claim 1, wherein the rendering engine is further configured to display to the user a geographic address of each of the suggested businesses.

6. The mobile device of claim 1, wherein the rendering engine is further configured to display to the user a name of each of the suggested businesses.

7. The mobile device of claim 1, wherein the image on the display illustrating the geographic location of each of the at least the subset of the businesses in the suggested list of businesses further comprises the current location associated with the user of the mobile device.

8. A method implemented by at least one processor in a mobile device, the method comprising:

detecting a prefix portion of an input string as one or more successive characters of the input string are provided by the user via the mobile device;

automatically determining a current location associated with the user of the mobile device at substantially the same time as a detection of the input string provided by the user;

in response to detecting the prefix portion of the input string, obtaining a list of suggested businesses associated with valid string completions of the prefix portion and sorting the obtained list of suggested businesses based on at least rating indicators of the suggested businesses and spatial proximities of the suggested businesses to the current location, wherein the obtaining the list of the suggested businesses further comprises;

(1) sending at least one detected prefix portion to a server comprising a search engine, (2) receiving, from the search engine, at least one autocompleted string identifying a name of a business based on the at least one detected prefix portion, and (3) upon receiving a selection of the at least one autocompleted string by the user, obtaining the list of the suggested businesses from the search engine; and

displaying to the user a rating indicator associated with each of at least a subset of businesses in the list of the suggested businesses and displaying to the user an image illustrating a geographic location of each of at least a subset of businesses in the suggested list of businesses in a manner relative to the current location of the user of the mobile device.

9. The method of claim 8, wherein the one or more successive characters of the input string are provided by the user via one of a touchscreen, touchpad, keyboard, keypad, audio input device, or another input sensing device.

10. The method of claim 8, wherein the current location associated with the user of the mobile device is determined using global positioning system.

11. The method of claim 8 further comprising displaying to the user a geographic distance of each of the suggested businesses from the current location associated with the user of the mobile device.

12. The method of claim 8 further comprising displaying to the user a geographic address of each of the suggested businesses.

13. The method of claim 8 further comprising displaying to the user a name of each of the suggested businesses.

14. The method of claim 8, wherein the image illustrating the geographic location of each of the at least the subset of the businesses in the suggested list of businesses further comprises the current location associated with the user of the mobile device.

15. A non-transitory computer-readable medium comprising instructions configured to, when executed by at least one processor in a mobile device, cause the at least one mobile device to:

detect a prefix portion of an input string as one or more successive characters of the input string are provided by the user via the mobile device;

automatically determine a current location associated with the user of the mobile device at substantially the same time as a detection of the input string provided by the user;

in response to a detection of the prefix portion of the input string, obtain a list of suggested businesses associated with valid string completions of the prefix portion and sort the obtained list of suggested businesses based on at least rating indicators of the suggested businesses and spatial proximities of the suggested businesses to the current location, wherein to obtain the list of the suggested businesses, the instructions are further configured to, when executed by the at least one processor in the mobile device, cause the at least one mobile device to (1) send at least one detected prefix portion to a server comprising a search engine, (2) receive, from the search engine, at least one autocompleted string identifying a name of a business based on the at least one detected prefix portion, and (3) upon receiving a selection of the at least one autocompleted string by the user, obtain the list of the suggested businesses from the search engine; and

display to the user a rating indicator associated with each of at least a subset of businesses in the list of the suggested businesses and display to the user an image illustrating a geographic location of each of at least a subset of businesses in the suggested list of businesses in a manner relative to the current location of the user of the mobile device.

16. The non-transitory computer-readable medium of claim 15, wherein the one or more successive characters of the input string are provided by the user via one of a touchscreen, touchpad, keyboard, keypad, audio input device, or another input sensing device.

17. The non-transitory computer-readable medium of claim 15, wherein the current location associated with the user of the mobile device is determined using global positioning system.

18. The non-transitory computer-readable medium of claim 15, wherein the instructions are further configured to cause the mobile device to display to the user a geographic distance of each of the suggested businesses from the current location associated with the user of the mobile device.

19. The non-transitory computer-readable medium of claim 15, wherein the instructions are further configured to cause the mobile device to display to the user a geographic address of each of the suggested businesses and a name of each of the suggested businesses.

20. The non-transitory computer-readable medium of claim 15, wherein the image illustrating the geographic location of each of the at least the subset of the businesses in the suggested list of businesses further comprises the current location associated with the user of the mobile device.