COMPUTER-IMPLEMENTED METHODS AND SYSTEMS FOR MULTI-LEVEL GEOGRAPHIC QUERY

• US 20110145228A1
• Filed: 12/14/2010
• Published: 06/16/2011
• Est. Priority Date: 12/15/2009
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: MapQuest, Inc. (Apollo Global Management, Inc.)
• Inventors: Nesbitt, David William, Beyeler, Eric, Laurenzo, Terry M.
• Granted Patent: US 8,458,173 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3682 output of POI information on a road map G01C21/3614, G01C21/3685 take precedence
• CPC Class Codes: G01C 21/3811 Point data, e.g. Point of Interest [POI]
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/444 Spatial browsing, e.g. 2D maps, 3D or virtual spaces
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• 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
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G09B 29/007 using computer methods

Abstract

According to one aspect of the present disclosure, a computer-implemented method is provided for processing a query for points of interest (POIs) using a hierarchical grid structure representing a geographic area. The method includes receiving a query for POIs; defining a query footprint for the query based on a location corresponding to the query, wherein the query footprint comprises query spatial identifiers for a plurality of levels of the hierarchical grid structure; matching the query spatial identifiers with one or more POI spatial identifiers organized into a plurality of indexes, wherein each one of the plurality of indexes comprises an index of the POI spatial identifiers for one of the plurality of levels; and providing an output specifying one or more POIs corresponding to the matched POI spatial identifiers.

Claims

1. A computer-implemented method for processing a query for points of interest (POIs) using a hierarchical grid structure representing a geographic area, the method comprising:

receiving a query for POIs from a user workstation;

defining a query footprint for the query based on a location corresponding to the query and the hierarchical grid structure, wherein the query footprint comprises query spatial identifiers over one or more of a plurality of levels of the hierarchical grid structure;

matching the query spatial identifiers with one or more POI spatial identifiers in a plurality of indexes for the hierarchical grid structure;

calculating scores based on the results of matching; and

providing a list representing one or more POIs to the user workstation based on the scores.

2. The computer-implemented method of claim 1, further comprising assigning weights to each one of the plurality of levels based on at least one of preciseness of the location and a type of point of interest described by preferences in the query, wherein calculating the scores comprises calculating based on the weights.

3. The computer-implemented method of claim 1, further comprising:

selecting one or more of the levels of the hierarchical grid structure to be searched for the query; and

selecting one or more of the indexes corresponding to the one or more levels, wherein matching comprises matching between the query spatial identifiers and only the POI spatial identifiers in the selected indexes.

4. The computer-implemented method of claim 1, wherein:

a first one of the POI spatial identifiers comprises a first level indicator and a first quadrant indicator corresponding to the first level of the plurality of levels; and

a second one of the POI spatial identifiers comprises a second level indicator and a second quadrant indicator corresponding to the second level of the plurality of levels.

5. The computer-implemented method of claim 4, wherein a first one of the query spatial identifiers comprises the first level indicator and the first quadrant indicator when the first one of the query spatial identifiers matches the first one of the POI spatial identifiers.

6. The computer-implemented method of claim 1, wherein the list of POIs includes at least one of a business listing, a public entity, a property for sale or rent, and a moving entity.

7. The computer-implemented method of claim 1, wherein:

the list is a rank ordering of the one or more POIs based on the scores; and

a first one of the scores is calculated based on a geographic score, a relevance score, and a weight of one of the plurality of levels, for a match between a first one of the POI spatial identifiers and a first one of the query spatial identifiers on the one of the plurality of levels.

8. The computer-implemented method of claim 1, further comprising:

prior to receiving the query, defining a first POI footprint by;

determining a significance a first POI;

selecting one or more of the plurality of levels for which to define the POI spatial identifiers for the first POI based on the determined significance of the first POI; and

defining the POI spatial identifiers for the first POI only on the selected levels.

9. The computer-implemented method of claim 1, wherein the plurality of levels in the hierarchical grid structure are defined based on at least one of population information and predetermined map information.

10. The computer-implemented method of claim 1, wherein defining the query footprint comprises generating the query spatial identifiers based on a latitude of the location and a longitude of the location.

11. The computer-implemented method of claim 1, wherein a first one of the POI spatial identifiers comprises a first level indicator and a first quadrant indicator when the position of a first POI indicates that an address corresponding to the first POI is located within a grid defined by the first level indicator and the first quadrant indicator, when the position is located within a predetermined buffer region around the grid, or when a buffer around the position is within the grid.

12. A computer-implemented method for processing a query for points of interest (POIs) using a hierarchical grid structure representing a geographic area, the method comprising:

receiving a query for POIs from a user workstation;

defining a query footprint for the query based on a location corresponding to the query, wherein the query footprint comprises query spatial identifiers for a plurality of levels of the hierarchical grid structure;

matching the query spatial identifiers with one or more POI spatial identifiers organized into a plurality of indexes, wherein each one of the plurality of indexes comprises an index of the POI spatial identifiers for one of the plurality of levels; and

providing, to the user workstation, an output specifying one or more POIs corresponding to the matched POI spatial identifiers.

13. The computer-implemented method of claim 12, further comprising:

receiving documents concerning a plurality of POIs from one or more data systems;

defining POI footprints for the plurality of POIs based on location information of each POI, wherein the POI footprints comprise the POI spatial identifiers; and

creating the indexes for the plurality of POIs based on the POI spatial identifiers.

14. The computer-implemented method of claim 12, further comprising:

assigning weights to each one of the plurality of levels based on at least one of preciseness of the location and a type of point of interest described by preferences in the query; and

calculating scores for the matched POI spatial identifiers based on the weights.

15. The computer-implemented method of claim 12, further comprising:

selecting one or more of the plurality of levels to be searched based on the query, wherein defining the query footprint comprises defining the query spatial identifiers only corresponding to the one or more selected levels; and

selecting one or more of the plurality of indexes corresponding to the one or more selected levels, wherein performing matching comprises matching between the query spatial identifiers and only the POI spatial identifiers in the one or more selected indexes.

16. The computer-implemented method of claim 12, wherein:

a first one of the query spatial identifiers comprises a first level indicator and a first quadrant indicator corresponding to a first level of the plurality of levels in the hierarchical grid structure;

a second one of the query spatial identifiers comprises a second level indicator and a second quadrant indicator corresponding to a second level of the plurality of levels in the hierarchical grid structure, and

the second level is a quadrant of an area indicated by the first level indicator.

17. The computer-implemented method of claim 16, wherein a first one of the POI spatial identifiers comprises the first level indicator and the first quadrant indicator when the first one of the POI spatial identifiers matches the first one of the query spatial identifiers.

18. A system for processing a query for points of interest (POIs) using a hierarchical grid structure representing a geographic area, the system comprising:

a storage configured to store a plurality of indexes, wherein each one of the indexes comprises an index of POI spatial identifiers for a plurality of levels of the hierarchical grid structure; and

a processor configured to;

receive a query from a user workstation;

define a query footprint for the query based on a location corresponding to the query, wherein the query footprint comprises query spatial identifiers for one or more of the plurality of levels;

perform matching between the query spatial identifiers and the POI spatial identifiers in one or more of the plurality of indexes; and

provide an output representing one or more matched POIs corresponding to the matched POI spatial identifiers.

19. The system of claim 18, wherein the processor is further configured to:

receive documents for a plurality of POIs from one or more data systems;

define POI footprints for the plurality of plurality POIs based on location information of each POI, wherein the POI footprints comprise the POI spatial identifiers;

create the indexes for the plurality of point of interests based on the POI spatial identifiers; and

store the plurality of indexes in the storage.

20. The system of claim 18, wherein the processor is further configured to:

assign weights to each one of the plurality of levels based on at least one of preciseness of the location and a type of point of interest described by preferences in the query; and

calculate scores for the matched POI spatial identifiers based on the weights.