High-performance location management platform

• US 20020188581A1
• Filed: 06/05/2001
• Published: 12/12/2002
• Est. Priority Date: 06/05/2000
• Status: Active Grant

• Current Assignee: Precisely Software Incorporated
• Original Assignee: Mapinfo Corp.
• Inventors: Berrill, Arthur R., Petronis, Scott, Moon, George, Fortin, Stephen E., Barota, Justinian, Allen, Brian R.
• Granted Patent: US 6,868,410 B2
• Time in Patent Office: Days
• US Class Current: 706/20
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

An apparatus and method for rapid translation of geographic latitude and longitude into any of a number of application-specific location designations or location classifications, including street address, nearest intersection, PSAP (Public Safety Answering Point) zone, telephone rate zone, franchise zone, or other geographic, administrative, governmental or commercial division of territory. The speed of translation meets call-setup requirements for call-processing applications such as PSAP determination, and meets caller response expectations for caller queries such as the location of the nearest commercial establishment of a given type. To complete its translation process in a timely manner, a memory-stored spatial database is used to eliminate mass-storage accesses during operation, a spatial indexing scheme such as an R-tree over the spatial database is used to locate a caller within a specific rectangular area, and an optimized set of point-in-polygon algorithms is used to narrow the caller'"'"'s location to a specific zone identified in the database. Additional validation processing is supplied to verify intersections or street addresses returned for a given latitude and longitude. Automatic conversion of latitude-longitude into coordinates in different map projection systems is provided.

The memory-stored database is built in a compact and optimized form from a relational spatial database as required. The R-tree spatial indexing of the memory-stored database allows for substantially unlimited scalability of database size without degradation of response time. Maximum performance for database retrievals is assured by isolating the retrieval process from all updating and maintenance processes. Hot update of the in-memory database is provided without degradation of response time.

Claims

1. An apparatus to determine, within an acceptable time of setup of a wireless telephone call, a classification of a geographic point, comprising:

a computer system in turn comprising one or more mass storage subsystems, one or more main memory subsystems, one or more interconnected processors, and one or more connections to a telephone network;

a first database stored in one or more of the mass storage subsystems and containing a set of all classifications used, wherein each member of the set identifies a distinct classification of a geographical area and its geographical boundaries;

a second database stored in one or more of the main memory subsystems and containing all information from the first database necessary to determine the classification of a geographic point using the geographic point'"'"'s coordinates;

a retrieval program, operating within one or more of the processors, whereby the geographic point'"'"'s classification is found within the second database and retrieved for use.

2. The apparatus of claim 1 wherein the retrieval program further comprises:

a spatial index retrieval program;

a point-in-polygon determination program for deciding whether a given point falls within a given classification polygon;

a polygon-in-polygon determination program for deciding whether a given first polygon falls within a given second classification polygon, falls outside the second classification polygon, overlaps the second classification polygon, or shares a vertex or boundary with the second classification polygon;

a program means for returning the identity of the determined classification for use.

3. The apparatus of claim 2 further comprising a first conversion program, operating within one or more of the processors, whereby the geographic point'"'"'s latitude and longitude are converted to coordinates uniquely locating the geographic point in a coordinate system used in the second database.

4. The apparatus of claim 3 further comprising a second conversion program, operating within one or more of the processors, whereby the geographic point'"'"'s latitude, longitude, and elevation are converted to coordinates uniquely locating the geographic point in a coordinate system used in the second database.

5. The apparatus of claim 4 wherein each classification comprises geocoded data.

6. The apparatus of claim 5 wherein each classification comprises one of a set of Public Safety Answering Points (PSAPs).

7. The apparatus of claim 5 wherein each classification comprises one of a set of telephone company rate zones.

8. The apparatus of claim 5 wherein each classification comprises one of a set of wireless communication service areas.

9. The apparatus of claim 5 wherein each classification comprises one of a set of commercial franchise areas.

10. The apparatus of claim 5 wherein each classification comprises one of a set of commercial service zones.

11. The apparatus of claim 5 wherein each classification comprises a service area classification.

12. The apparatus of claim 5 wherein the second database further comprises:

a spatial index of recursively nested geographical regions;

a base table associating each region with one or more classifications.

13. The apparatus of claim 12 wherein the base table of the second database comprises the leaf nodes of the spatial index.

14. The apparatus of claim 12 wherein the spatial index of the second database comprises an R-tree index.

15. The apparatus of claim 12 wherein the spatial index of the second database comprises an R*-tree (R-star tree) index.

16. The apparatus of claim 12 wherein the spatial index of the second database comprises an R+-tree (R-plus tree) index.

17. The apparatus of claim 12 wherein the spatial index of the second database comprises a Hilbert R-tree index.

18. The apparatus of claim 12 wherein the spatial index of the second database comprises an X-tree index.

19. The apparatus of claim 1 further comprising an interface program, operating within one or more of the processors, whereby the geographic point may be obtained from a requesting entity and the classification of that point returned to the requesting entity.

20. The apparatus of claim 5 further comprising a loading program, operating within one or more of the processors, whereby the geographic boundary classification contents of the first database are loaded into the second database without interfering substantially with the functioning or the speed of the retrieval program.

21. The apparatus of claim 20 wherein the loading program loads the geographic boundary classification contents of the first database into the second database in a more-compact form to save memory space.

22. The apparatus of claim 1 wherein an acceptable time of setup of a wireless telephone call must be less than one second.

24. The location management platform apparatus of claim 23 wherein the retrieval program further comprises:

a spatial index retrieval program;

a point-in-polygon determination program for deciding whether a given point falls within a given classification polygon;

a polygon-in-polygon determination program for deciding whether a given first polygon falls within a given second classification polygon, falls outside the second classification polygon, overlaps the second classification polygon, or shares a vertex or boundary with the second classification polygon;

a program means for returning the identity of the determined classification for use.

25. The location management platform apparatus of claim 24 further comprising a first conversion program, operating within one or more of the processors, whereby the geographic point'"'"'s latitude and longitude are converted to coordinates uniquely locating the geographic point in a coordinate system used in the second database.

26. The location management platform apparatus of claim 25 further comprising a second conversion program, operating within one or more of the processors, whereby the geographic point'"'"'s latitude, longitude, and elevation are converted to coordinates uniquely locating the geographic point in a coordinate system used in the second database.

27. The location management platform apparatus of claim 26 wherein each classification comprises geocoded data.

28. The location management platform apparatus of claim 27 wherein each classification comprises one of a set of Public Safety Answering Points (PSAPs).

29. The location management platform apparatus of claim 27 wherein each classification comprises one of a set of telephone company rate zones.

30. The location management platform apparatus of claim 27 wherein each classification comprises one of a set of wireless communication service areas.

31. The location management platform apparatus of claim 27 wherein each classification comprises one of a set of commercial franchise areas.

32. The location management platform apparatus of claim 27 wherein each classification comprises one of a set of commercial service zones.

33. The location management platform apparatus of claim 27 wherein each classification comprises a service area classification.

34. The location management platform apparatus of claim 27 wherein the second database further comprises a spatial index of recursively nested geographical regions and a base table associating each region with one or more classifications.

35. The location management platform apparatus of claim 34 wherein the base table of the second database comprises the leaf nodes of the spatial index.

36. The location management platform apparatus of claim 34 wherein the spatial index of the second database comprises an R-tree index.

37. The location management platform apparatus of claim 34 wherein the spatial index of the second database comprises an R*-tree (R-star tree) index.

38. The location management platform apparatus of claim 34 wherein the spatial index of the second database comprises an R+-tree (R-plus tree) index.

39. The location management platform apparatus of claim 34 wherein the spatial index of the second database comprises a Hilbert R-tree index.

40. The location management platform apparatus of claim 34 wherein the spatial index of the second database comprises an X-tree index.

41. The location management platform apparatus of claim 27 further comprising a loading program, operating within one or more of the processors, whereby the geographic boundary classification contents of the first database are loaded into the second database without interfering substantially with the functioning or the speed of the retrieval program.

42. The location management platform apparatus of claim 41 wherein the loading program loads the geographic boundary classification contents of the first database into the second database in a more-compact form to save memory space.

43. The location management platform apparatus of claim 23 wherein an acceptable time of setup of a wireless telephone call must be less than one second.

23. A location management platform apparatus to determine, within an acceptable time of setup of a wireless telephone call, a classification of a geographic point, comprising:

a computer system in turn comprising one or more mass storage subsystems, one or more main memory subsystems, one or more interconnected processors, and one or more connections to a telephone network;

a first database stored in one or more of the mass storage subsystems and containing a set of all classifications used, wherein each member of the set identifies a distinct classification of a geographical area and its geographical boundaries;

a second database stored in one or more of the main memory subsystems and containing all information from the first database necessary to determine the classification of a geographic point using the geographic point'"'"'s coordinates;

a retrieval program, operating within one or more of the processors, whereby the geographic point'"'"'s classification is found within the second database and retrieved for use.

44. An apparatus to determine, within an acceptable caller waiting time during a wireless telephone call, a geographic point, comprising:

a computer system in turn comprising one or more mass storage subsystems, one or more main memory subsystems, one or more interconnected processors, and one or more connections to a telephone network;

a first database stored in one or more of the mass storage subsystems and containing the set of all classifications used, wherein each member of the set identifies a distinct classification of a geographical area and its geographical boundaries;

a second database stored in one or more of the main memory subsystems and containing all information from the first database necessary to determine the classification of a geographic point using said point'"'"'s coordinates;

a retrieval program, operating within one or more of the processors, whereby the geographic point'"'"'s location identifier may be estimated using known reference points in the second database.

45. The apparatus of claim 44 wherein the retrieval program further comprises:

a spatial index retrieval program;

a point-in-polygon determination program for deciding whether a given point falls within a given classification polygon;

a polygon-in-polygon determination program for deciding whether a given first polygon falls within a given second classification polygon, falls outside the second classification polygon, overlaps the second classification polygon, or shares a vertex or boundary with the second classification polygon;

a program means for returning the identity of the determined classification for use.

46. The apparatus of claim 45 further comprising a first conversion program, operating within one or more of the processors, whereby the geographic point'"'"'s latitude and longitude are converted to coordinates uniquely locating the geographic point in a coordinate system used in the second database,

47. The apparatus of claim 46 further comprising a second conversion program, operating within one or more of the processors, whereby the geographic point'"'"'s latitude, longitude, and elevation are converted to coordinates uniquely locating the geographic point in a coordinate system used in the second database.

48. The apparatus of claim 47 wherein each classification comprises geocoded data.

49. The apparatus of claim 48 wherein the location identifier comprises a street address.

50. The apparatus of claim 48 wherein the second database further comprises a spatial index of recursively nested geographical regions and a base table associating each region with one or more classifications.

51. The apparatus of claim 50 wherein the base table of the second database comprises the leaf nodes of the spatial index.

52. The apparatus of claim 50 wherein the spatial index of the second database comprises an R-tree index.

53. The apparatus of claim 50 wherein the spatial index of the second database comprises an R*-tree (R-star tree) index.

54. The apparatus of claim 50 wherein the spatial index of the second database comprises an R+-tree (R-plus tree) index.

55. The apparatus of claim 50 wherein the spatial index of the second database comprises a Hilbert R-tree index.

56. The apparatus of claim 50 wherein the spatial index of the second database comprises an X-tree index.

57. The apparatus of claim 44 further comprising an interface program, operating within one or more of the processors, whereby the geographic point may be obtained from a requesting entity and the location identifier of that point returned to the requesting entity.

58. The apparatus of claim 48 further comprising a validation program, operating within one or more of the processors, whereby the estimated geographic location identifier is validated by comparison to known geographic location identifiers in the second database.

59. The apparatus of claim 48 further comprising a loading program, operating within one or more of the processors, whereby the geographic boundary classification contents of the first database are loaded into the second database without interfering substantially with the functioning or the speed of the retrieval program.

60. The apparatus of claim 59 wherein the loading program loads the geographic boundary classification contents of the first database into the second database in a more-compact form to save memory space.

61. The apparatus of claim 44, wherein an acceptable caller waiting time during a wireless telephone call must be less than five seconds.

62. A method of determining, within an acceptable time of setup of a wireless telephone call, a classification of a geographic point using said point'"'"'s geographic latitude and longitude, comprising the steps of:

accepting from a requesting entity a latitude and longitude for the geographic point;

converting the latitude and longitude to coordinates in a specific coordinate system uniquely identifying the point;

determining one or more minimum enclosing areas in the coordinate system for the point;

determining the specific classification of the geographic point within the minimum enclosing area;

returning to the requesting entity the specific classification of the geographic point.

63. The method of claim 62 wherein the step of determining one or more minimum enclosing areas for the point further comprises the step of determining one or more minimum enclosing rectangles for the point.

64. The method of claim 63 wherein the step of determining one or more minimum enclosing rectangles for the point further comprises the steps of:

accessing a classification database having a spatial index;

finding in the spatial index a first rectangle that encloses the point;

finding in the spatial index each subordinate rectangle within the first rectangle;

repeating the previous two steps using each subordinate rectangle as a first rectangle until no more subordinate rectangles that enclose the point are found;

returning as minimum enclosing rectangles the set of all subordinate rectangles found in the final step to enclose the point;

for each subordinate rectangle found that encloses the point, returning from the classification database the classification that corresponds to the subordinate rectangle found;

for each classification, returning the set of polygon coordinates defining that classification.

65. The method of claim 62 wherein the step of determining the specific classification of the geographic point within the minimum enclosing area further comprises the steps of:

for each subordinate rectangle found that encloses the point, retrieving from the classification database the classification that corresponds to the subordinate rectangle found;

for each classification, retrieving the set of polygon coordinates defining that classification;

for each set of polygon coordinates, determining whether the point is inside or outside the polygon;

returning the set of all classifications for which the point is inside the corresponding polygon.

66. The method of claim 62 wherein an acceptable time of setup of a wireless telephone call must be less than one second.

67. The method of claim 62 further comprising the steps of:

updating components of a form of the classification database and spatial index which is not accessible by a client retrieval process;

converting the updated components into a form capable of access by a client retrieval process;

compressing the converted updated components into a form capable of storage in memory of the system used for client retrieval;

storing the compressed converted updated components in the memory of the system used for client retrieval, without preventing client retrieval access to components not updated;

switching client retrievals to access the compressed converted updated components of the classification database.

69. The method of claim 68 wherein the step of determining a minimum enclosing area further comprises the step of determining a minimum enclosing rectangle.

70. The method of claim 69 wherein the step of determining one or more minimum enclosing rectangles for the point further comprises the steps of:

accessing a classification database having a spatial index;

finding in the spatial index a first rectangle that encloses the point;

finding in the spatial index each subordinate rectangle within the first rectangle;

repeating the previous two steps using each subordinate rectangle as a first rectangle until no more subordinate rectangles that enclose the point are found;

returning as minimum enclosing rectangles the set of all subordinate rectangles found in the final step to enclose the point;

for each subordinate rectangle found that encloses the point, returning from the classification database the classification that corresponds to the subordinate rectangle found;

for each classification, returning the set of polygon coordinates defining that classification.

71. The method of claim 68 wherein the step of determining the specific location identifier of the geographic point within the minimum enclosing area further comprises the steps of:

for each set of polygon coordinates, determining whether the point is inside or outside the polygon;

returning the set of all classifications for which the point is inside the corresponding polygon.

72. The method of claim 68 wherein an acceptable caller waiting time during a wireless telephone call must be less than five seconds.

73. The method of claim 68 further comprising the steps of:

updating components of a form of the classification database and spatial index which is not accessible by a client retrieval process;

converting the updated components into a form capable of access by a client retrieval process;

compressing the converted updated components into a form capable of storage in memory of the system used for client retrieval;

storing the compressed converted updated components in the memory of the system used for client retrieval, without preventing client retrieval access to components not updated;

switching client retrievals to access the compressed converted updated components of the classification database.

68. A method of determining, within an acceptable caller waiting time during a wireless telephone call, a location identifier of a geographic point using said point'"'"'s geographic latitude and longitude, comprising the steps of:

accepting from a requesting entity a latitude and longitude for the geographic point;

converting the latitude and longitude to coordinates in a specific coordinate system uniquely identifying the point;

determining a minimum enclosing area in the coordinate system for the point;

determining the location identifier of the minimum enclosing area;

associating the location identifier with the geographic point;

returning to the requesting entity the location identifier of the geographic point.

74. A method of increasing the size of a combined geographic classification database and spatial index storable in the memory of a computer system, without altering substantially the physical structure, logical structure, software content or software operation within the system, comprising the steps of:

creating a combined geographic classification database and spatial index stored in a database in the mass storage of a computer system;

converting the combined geographic classification database and spatial index into a form capable of access by a client retrieval process;

compressing the converted geographic classification database and spatial index into a form capable of storage in the memory of a computer system;

storing the compressed geographic classification database and spatial index in the memory of a computer system.

75. A method of increasing the size of a combined geographic classification database and spatial index storable in the memory of a computer system, without altering substantially the physical structure, logical structure, software content or software operation within the system, comprising the steps of:

creating a combined geographic classification database and spatial index stored in a database in the mass storage of a computer system;

dividing the combined geographic classification database and spatial index into components independently retrievable;

converting each divided geographic classification database and spatial index into a form capable of access by a client retrieval process;

compressing each converted geographic classification database and spatial index into a form capable of storage in the memory of a computer system;

storing each compressed geographic classification database and spatial index in the memory of a computer system.

76. A location management platform apparatus for determining, within an acceptable time of setup of a wireless telephone call, a classification of a geographic point using said point'"'"'s geographic latitude and longitude, comprising:

means for accepting from a requesting entity a latitude and longitude for the geographic point;

means for converting the latitude and longitude to coordinates in a specific coordinate system uniquely identifying the point;

means for determining one or more minimum enclosing areas in the coordinate system for the point;

means for determining the specific classification of the geographic point within the minimum enclosing area;

means for returning to the requesting entity the specific classification of the geographic point.

77. The location management platform apparatus of claim 76 wherein the means for determining one or more minimum enclosing areas for the point further comprises means for determining one or more minimum enclosing rectangles for the point.

78. The location management platform apparatus of claim 77 wherein the means for determining one or more minimum enclosing rectangles for the point further comprises:

means for accessing a classification database having a spatial index;

means for finding in the spatial index a first rectangle that encloses the point;

means for finding in the spatial index each subordinate rectangle within the first rectangle;

means for repeating the previous two steps using each subordinate rectangle as a first rectangle until no more subordinate rectangles that enclose the point are found;

means for returning as minimum enclosing rectangles the set of all subordinate rectangles found in the final step to enclose the point;

for each subordinate rectangle found that encloses the point, means for returning from the classification database the classification that corresponds to the subordinate rectangle found;

for each classification, means for returning the set of polygon coordinates defining that classification.

79. The location management platform apparatus of claim 76 wherein the means for determining the specific classification of the geographic point within the minimum enclosing area further comprises:

for each subordinate rectangle found that encloses the point, means for retrieving from the classification database the classification that corresponds to the subordinate rectangle found;

for each classification, means for retrieving the set of polygon coordinates defining that classification;

for each set of polygon coordinates, means for determining whether the point is inside or outside the polygon;

means for returning the set of all classifications for which the point is inside the corresponding polygon.

80. A location management platform apparatus for determining, within an acceptable caller waiting time during a wireless telephone call, a location identifier of a geographic point using said point'"'"'s geographic latitude and longitude, comprising:

means for accepting from a requesting entity a latitude and longitude for the geographic point;

means for converting the latitude and longitude to coordinates in a specific coordinate system uniquely identifying the point;

means for determining a minimum enclosing area in the coordinate system for the point;

means for determining the location identifier of the minimum enclosing area;

means for associating the location identifier with the geographic point;

means for returning to the requesting entity the location identifier of the geographic point.

81. The location management platform apparatus of claim 80 wherein the means for determining a minimum enclosing area further comprises means for determining a minimum enclosing rectangle.

82. The location management platform apparatus of claim 81 wherein the means for determining one or more minimum enclosing rectangles for the point further comprises:

means for accessing a classification database having a spatial index;

means for finding in the spatial index a first rectangle that encloses the point;

means for finding in the spatial index each subordinate rectangle within the first rectangle;

means for repeating the previous two steps using each subordinate rectangle as a first rectangle until no more subordinate rectangles that enclose the point are found;

means for returning as minimum enclosing rectangles the set of all subordinate rectangles found in the final step to enclose the point;

for each subordinate rectangle found that encloses the point, means for returning from the classification database the classification that corresponds to the subordinate rectangle found;

for each classification, means for returning the set of polygon coordinates defining that classification.

83. The location management platform apparatus of claim 80 wherein the means for determining the specific location identifier of the geographic point within the minimum enclosing area further comprises:

for each set of polygon coordinates, means for determining whether the point is inside or outside the polygon;

means for returning the set of all classifications for which the point is inside the corresponding polygon.

84. A software program stored on machine-readable media for operating a location management platform to perform the following operations:

accept the coordinates of a geographic point from an input source;

access a classification database having a spatial index;

find in the spatial index a first rectangle that encloses the point;

find in the spatial index each subordinate rectangle within the first rectangle;

repeat the previous two steps using each subordinate rectangle as a first rectangle until no more subordinate rectangles that enclose the point are found;

return as minimum enclosing rectangles the set of all subordinate rectangles found in the final step to enclose the point;

for each subordinate rectangle found that encloses the point, determine from the classification database the classification that corresponds to the subordinate rectangle found;

for each classification, determine the set of polygon coordinates defining that classification

associate the point with each classification and said classification'"'"'s set of polygon coordinates.