User interface and geo-parsing data structure

• US 10,192,254 B2
• Filed: 12/22/2016
• Issued: 01/29/2019
• Est. Priority Date: 08/04/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Dharmarajan, Baskaran, Jacobs, Jay C.
• Primary Examiner(s): Wong, Leslie
• Application Number:
  US15/388,863
• Publication Number:
  US 20170169494A1
• Time in Patent Office: 768 Days
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 30/0203 Market surveys; Market polls
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration
• CPC Class Codes: G06Q 30/0625 Directed, with specific intent or strategy

Abstract

A method to allocate memory, in response to application requests, for a compact data structure having location data and a trailer section is provided. The trailer section of the compact data structure is checked to determine an offset for listings and indices representing the location data. Upon determining the offset, the listings and indices are loaded into memory and responses to the application requests are generated by utilizing the listings and indices stored in the memory.

Claims

1. A computer-implemented method by a computing device including a processor and a memory to provide selections that complete partial address information utilizing an improved storage format of a compact data structure including address information, the method comprising:

receiving by the processor the partial address information at a graphical user interface having a set of fields for geographic locations, wherein the partial address information completes less than all of the fields included in the set of fields;

parsing by the processor the partial address information to determine missing portions of the partial address information;

locating by the processor in the compact data structure offsets to the address information corresponding to the missing portions, wherein the compact data structure organizes geographic location information and includes a header section, a trailer section and a body section, wherein the header section provides metadata to a plurality of applications, the trailer section specifies at least the offsets allowing the plurality of applications to access the data structure and a version allowing one or more data sources to update the data structure, and the body section having the address information represented by a plurality of offset count pairs, and wherein the offsets to address information specifies the location in the compact data structure where the address information corresponding to the missing portions of the partial address information from the request is stored; and

generating by the processor, for selective display, a set of options that includes the address information corresponding to the missing portions that complete a subset of the set fields in the graphical user interface and restricts the set of options to a number of potential addresses that complete the partial address information.

2. The method according to claim 1, further comprising validating the partial address information.

3. The method according to claim 1, further comprising completing the fields of the missing information based on user selections that complete the partial address received at the graphical user interface.

4. The method according to claim 1, further comprising restricting states and zip codes selectively displayed in a zip code field and a state field of the missing information to states and zip codes related to a city included in the partial address information.

5. The method according to claim 3, further comprising restricting cities and states selectively displayed in a state field and a city field of the missing information to cities and states related to a zip code included in the partial address information.

6. The method according to claim 1, wherein the compact data structure is memory-mapped.

7. A method to allocate memory by a computing device including a processor and a memory for a data structure having address information stored in an improved storage format the method comprising:

receiving by the processor an application request;

checking by the processor a trailer portion of the data structure, wherein the data structure includes a header section, a trailer section and a body section, wherein the header section provides metadata to a plurality of applications, the trailer section specifies at least the offsets allowing the plurality of applications to access the data structure and a version allowing one or more data sources to update the data structure, and the body section having the address information represented by a plurality of offset count pairs, and wherein the offsets to address information specifies the location in the compact data structure where the address information corresponding to the missing portions of the partial address information from the request is stored;

retrieving by the processor an offset to a set of lists and indices from the trailer portion of the data structure;

loading by the processor the set of lists and indices into the memory; and

processing by the processor the application request with the set of lists and indices to generate a response.

8. The method according to claim 7, wherein retrieving the offset to the set of lists and indices from the trailer portion of the data structure further comprises:

determining whether an application-specific index exists in the data structure, and when the application-specific index exists, retrieving the application-specific index in addition to the set of lists and indices.

9. The method according to claim 7, wherein the application request is an auto-complete, validation, or driving direction request.

10. The method according to claim 7, wherein at least one of the indices included in the set of list and indices is a sparse index.

11. The method according to claim 7, wherein the set of list and indices provides offset-count pairs that represent location data.

12. The method according to claim 10, wherein processing the application request with the set of lists and indices to generate a response further comprises:

utilizing a divide and conquer strategy to search the sparse index.

13. The method according to claim 11, wherein the location data includes cities, roads, or points of interest.

14. A computing device having processors and memories, wherein the memories store computer-executable instructions and an compact data structure including address information stored in an improved storage format, the computer-executable instructions perform a method to provide selections that complete partial address information utilizing the address information, and the computing device further comprising:

the compact data structure which organizes geographic location information and includes a trailer section specifying at least a version and an offset to location data, wherein the trailer section allows a plurality of applications to access the data structure, and the version allows one or more data sources to update the data structure, a body section having the location data represented by a plurality of offset count pairs, and a header section providing metadata to the plurality of applications, and wherein the offset to location data specifies the location in the compact data structure where the address information corresponding to the missing portions of the partial address information from the request is stored;

an input component which provides an application request having partial address information; and

a display component which renders a graphical user interface having a set of fields for geographic locations, wherein the partial address information completes less than all of the fields included in the set of fields, and the display component is updated by generating, for selective display based on the location data stored in the compact data structure, a set of options that includes address information corresponding to missing portions that complete a subset of the set fields in the graphical user interface.

15. The computing device of claim 14, wherein the location data includes cities, roads, or points of interest.

16. The computing device of claim 14, wherein the set of options is restricted to a number of potential addresses that complete partial address information in the graphical user interface.

17. The computing device of claim 14, wherein the applications executing on the computing device read at least one of the plurality of offset-count pairs to determine a location of a list of cities in the data structure, and a number of cities in the list of cities.

18. The computing device of claim 14, wherein the compact data structure is in a compressed format.

19. The computing device of claim 14, wherein the compact data structure is organized to optimize reference locality.

20. The computing device of claim 14, wherein updating the compact data structure appends data after the trailer section.