Location encoder

• US 6,552,670 B2
• Filed: 05/23/2001
• Issued: 04/22/2003
• Est. Priority Date: 05/26/2000
• Status: Expired due to Term

• Current Assignee: Switchboard LLC
• Original Assignee: Switchboard, Inc. (Mudrick Capital Management LP)
• Inventors: Sundaravel, Vale, Paul, Benjamin J.
• Primary Examiner(s): WAMSLEY, PATRICK G
• Application Number:
  US09/863,962
• Publication Number:
  US 20010051852A1
• Time in Patent Office: 699 Days
• Field of Search: 340/988, 342/457, 434/2, 701/211, 701/212, 701/208, 701/213, 707/100, 341/5
• US Class Current: 341/5
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: H02J 9/061 for DC powered loads
• 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: H04L 9/40 Network security protocols
• CPC Class Codes: H04M 2242/30 Determination of the location of a subscriber
• CPC Class Codes: H04M 3/42 Systems providing special services or facilities to subscribers specially adapted for wireless communication networks H04W4/00

Abstract

A method and apparatus to convert geographic information to a binary representation, or bingeo. The geographic information can be converted to a bingeo for a selected reference or coordinate system, and with respect to a reference within the selected coordinate system. The coordinate system location to bingeo conversion can be hierarchical or iterative and can include segmenting the coordinate system or segments thereof. The iterative algorithm can include identifying a segment including the specified location, and segmenting the identified segment. During an iteration, segments can be assigned a binary code that can be incorporated into the bingeo. Successive segmentation iterations can be performed to provide increased precision. In one embodiment, a precision of 0.16 inches squared can be attained. Two bingeos can be compared, in the simplest form, using a bitwise logical XOR.

Claims

1. A method of forming a binary representation of geographic information based on a coordinate system, the method comprising,

relating the geographic information to the coordinate system,

providing a hierarchical segmentation scheme to create subdivisions based on the geographic information,

assigning a binary code to the subdivisions,

determining a level of the hierarchical scheme to provide a desired precision for the binary representation,

forming the binary representation based on the assigned binary codes and the desired precision.

2. A method according to claim 1, wherein relating the geographic information includes determining a location in the coordinate system.

3. A method according to claim 1, wherein providing a hierarchical segmentation scheme includes providing an iterative scheme.

4. A method according to claim 1, wherein providing a hierarchical segmentation scheme includes providing a recursive scheme.

5. A method according to claim 1, wherein providing a hierarchical segmentation scheme includes providing a scheme to create subdivisions from at least one of the coordinate system or a subdivision of the coordinate system.

6. A method according to claim 1, wherein providing a hierarchical segmentation scheme includes providing a scheme to create four segments from at least one of the coordinate system or a subdivision of the coordinate system.

7. A method according to claim 1, wherein assigning a binary code includes assigning a two bit binary code.

8. A method according to claim 1, wherein forming the binary representation includes associating bits of the binary representation with a level of the hierarchical scheme.

9. A method according to claim 1, further including initializing the binary representation to be zero.

10. A method according to claim 1, further including initializing the binary representation to includes ones in every location.

11. A method according to claim 1, further including at least one of storing the binary representation in a database and storing a precision indicator based on the binary representation precision.

12. A method according to claim 1, further including selecting a reference relative to the coordinate system.

13. A method according to claim 1, wherein relating the geographic information to the coordinate system includes computing a centroid based on the geographic information.

14. A method according to claim 1, wherein relating the geographic information includes relating at least one of latitude, longitude, direction, parcel, ward, street address, city, town, zip code, telephone number, area code, destination, and direction.

15. A method of forming a binary representation of geographic information based on a coordinate system, the method comprising,

relating the geographic information to the coordinate system,

iteratively creating subdivisions from at least one of the coordinate system or a subdivision of the coordinate system,

assigning a binary code to the created subdivisions, and,

forming the binary representation based on the binary code of the identified created subdivision.

16. A method according to claim 15, wherein iteratively creating includes iteratively creating from a subdivision of the coordinate system that is related to a location of the geographical information in the coordinate system.

17. A method according to claim 15, wherein iteratively creating subdivisions further includes dividing into quadrants.

18. A method according to claim 15, further including determining a scheme for assigning the binary codes at the iteration levels.

19. A method according to claim 15, wherein assigning a unique binary code includes assigning a unique two bit binary code.

20. A method according to claim 15, wherein forming the binary representation includes associating an iteration level with positions in the binary representation.

21. A method according to claim 15, further comprising ending the iteration based on a level of precision.

22. A method according to claim 15, further comprising ending the iteration based on a size of the binary representation.

23. A method according to claim 15, wherein relating the geographic information to a location includes computing a latitude and longitude based on the geographic information.

24. A method according to claim 15, wherein relating the geographic information to the coordinate system includes computing a centroid based on the geographic information.

25. A method according to claim 15, wherein iteratively creating subdivisions includes creating subdivisions of equal size.

26. A method according to claim 15, further comprising initializing the binary representation to zero.

27. A method according to claim 15, further comprising initializing the binary representation to include ones in every location.

28. A method according to claim 15, further including specifying a size for the binary representation.

29. A method according to claim 15, further including specifying a size of sixty-four bits for the binary representation.

30. A method according to claim 15, further including selecting a reference frame within the coordinate system.

31. A method according to claim 15, further including providing a scheme to assign a binary code.

32. A method according to claim 15, further including receiving the geographic information as one of latitude, longitude, direction, parcel, ward, street address, town, city, zip code, telephone number, area code, destination, and direction.

33. A method for comparing a first location and a second location, comprising,

using an iterative process to obtain a binary representation of the first location,

using the iterative process to obtain a binary representation of the second location,

performing a binary computation utilizing the first location binary representation and the second location binary representation to obtain a binary result, and

computing a distance measure from the binary result.

34. A method according to claim 33, wherein using an iterative process includes,

relating the location to a coordinate system, and,

iteratively creating subdivisions from at least one of the coordinate system or a subdivision of the coordinate system,

assigning a binary code to the created subdivisions, and,

forming the binary representation based on the binary code of the identified created subdivision.

35. A method according to claim 33, wherein performing a binary computation includes performing an exclusive OR (XOR).

36. A method according to claim 33, wherein computing a distance measure further includes associating binary digits of the binary result to at least one distance measure.

37. A method according to claim 33, further including identifying at least one binary representation corresponding to at least one neighbor of the first location.

38. A method according to claim 33, further including identifying at least one binary representation corresponding to at least one neighbor of the second location.

39. A method according to claim 33, further including computing at least one binary representation corresponding to at least one neighbor of the first location.

40. A method according to claim 33, further including computing at least one binary representation corresponding to at least one neighbor of the second location.

41. A method according to claim 33, further including determining at least one of whether the binary representation of the first location is a neighbor of the binary representation of the second location, and whether the binary representation of the second location is a neighbor of the binary representation of the first location.

42. A system for comparing at least two locations, comprising,

an interface to receive geographical information based on at least one of the at least two locations,

a processor having instructions to convert the geographical information to a binary representation using a hierarchical segmentation scheme, where levels of the hierarchical scheme are associated with a precision for thc binary representation,

a database that includes binary representations of at least another of the at least two locations,

a comparator to perform a binary computation between binary representations.

43. A system according to claim 42, further including a difference translator to determine difference measure from the comparator result.

44. A system according to claim 42, further comprising a neighbor location module to identify the binary representations of neighbors for the at least two locations.

45. A system according to claim 42, wherein the comparator is an exclusive OR.

46. A system according to claim 42, wherein the processor has instructions for,

relating the geographical information to a coordinate system,

iteratively creating subdivisions from at least one of the coordinate system or a subdivision of the coordinate system,

assigning a binary code to the created subdivisions, and,

forming the binary representation based on the binary code of the identified created subdivision.

47. A system according to claim 42, further including precision indicators associated with the binary representations in the database.

48. A system according to claim 42, further including a precision indicator associated with the binary representation.

49. A system according to claim 42, further including identity information associated with the binary representations in the database.

50. A system for forming a binary representation of geographic information based on a coordinate system, the system comprising,

means for providing the geographic information,

means for implementing a hierarchical segmentation scheme to create subdivisions based on the geographic information,

means for determining a level of the hierarchial scheme to provide a desired precision for the binary representation

means for assigning a binary code to the subdivisions, and,

means for forming the binary representation based on the assigned binary codes and the desired precision.

51. A system according to claim 50, wherein the means for providing include any internet-accessible device.

52. A system according to claim 50, wherein means for implementing a hierarchical segmentation scheme include a processor and processor instructions.

53. A computer product for brining a binary representation of geographic information based on a coordinate system, the computer product disposed on a computer readable medium and having instructions for causing a processor to,

relate the geographic information to thc coordinate system,

provide a hierarchical segmentation scheme to create subdivisions based on the geographic information,

determine a level of the hierarchical scheme to provide a desired precision,

assign a binary code to the subdivisions, and,

form thc binary representation based on the assigned binary codes and the desired precision.

54. A computer product according to claim 53, wherein instructions to relate the geographic information include instructions to determine a location in the coordinate system.

55. A computer product according to claim 53, wherein instructions to provide a hierarchical segmentation scheme include instructions to provide an iterative scheme.

56. A computer product according to claim 53, wherein instructions to provide a hierarchical segmentation scheme include instructions to provide a recursive scheme.

57. A computer product according to claim 53, wherein instructions to provide a hierarchical segmentation scheme include instructions to provide a scheme to create subdivisions from at least one of the coordinate system or a subdivision of the coordinate system.

58. A computer product according to claim 53, wherein instructions to provide a hierarchical segmentation scheme include instructions to provide a scheme to create four segments from at least one of the coordinate system or a subdivision of the coordinate system.

59. A computer product according to claim 53, wherein instructions to assign a binary code includes assigning a two bit binary code.

60. A computer product according to claim 53, wherein instructions to form the binary representation include instructions to associate bits of the binary representation with a level of the hierarchical scheme.

61. A computer product according to claim 53, further including instructions to initialize the binary representation to be zero.

62. A computer product according to claim 53, further including instructions to initialize the binary representation to includes ones in every location.

63. A computer product according to claim 53, further including instructions to at least one of store the binary representation in a database and store a precision indicator based on the binary representation precision.

64. A computer product according to claim 53, further including instructions to select a reference relative to the coordinate system.

65. A computer product according to claim 53, wherein instructions to relate the geographic information to the coordinate system include instructions to compute a centroid based on the geographic information.

66. A computer product according to claim 53, wherein instructions to relate the geographic information include instructions to relate at least one of latitude, longitude, direction, parcel, ward, street address, city, town, zip code, telephone number, area code, destination, and direction.

67. A computer product for forming a binary representation of geographic information based on a coordinate system, the computer product disposed on a computer readable medium and having instructions for causing a processor to,

relate the geographic information to the coordinate system,

iteratively create subdivisions from at least one of the coordinate system or a subdivision of the coordinate system,

assign a binary code to the created subdivisions, and,

form the binary representation based on the binary code of the identified created subdivision.

68. A computer product according to claim 67, wherein instructions to iteratively create include instructions to iteratively create from a subdivision of the coordinate system that is related to a location of the geographical information in the coordinate system.

69. A computer product according to claim 67, wherein instructions to iteratively create subdivisions further include instructions to divide into quadrants.

70. A computer product according to claim 67, further including instructions to determine a scheme for assigning the binary codes at the iteration levels.

71. A computer product according to claim 67, wherein instructions to assign a unique binary code include instructions to assign a unique two bit binary code.

72. A computer product according to claim 67, wherein instructions to form the binary representation include instructions to associate an iteration level with positions in the binary representation.

73. A computer product according to claim 67, further comprising instructions to end the iteration based on a level of precision.

74. A computer product according to claim 67, further comprising instructions to end the iteration based on a size of the binary representation.

75. A computer product according to claim 67, wherein instructions to relate the geographic information to a location include instructions to compute a latitude and longitude based on the geographic information.

76. A computer product according to claim 67, wherein instructions to relate the geographic information to the coordinate system include instructions to compute a centroid based on the geographic information.

77. A computer product according to claim 67, wherein instructions to iteratively create subdivisions include instructions to create subdivisions of equal size.

78. A computer product according to claim 67, further comprising instructions to initialize the binary representation to zero.

79. A computer product according to claim 67, further comprising instructions to initialize the binary representation to include ones in every location.

80. A computer product according to claim 67, further including instructions to specify a size for the binary representation.

81. A computer product according to claim 67, further including instructions to specify a size of sixty-four bits for the binary representation.

82. A computer product according to claim 67, further including instructions to select a reference frame within the coordinate system.

83. A computer product according to claim 67, further including instructions to provide a scheme to assign a binary code.

84. A computer product according to claim 67, further including instructions to receive the geographic information as one of latitude, longitude, direction, parcel, ward, street address, town, city, zip code, telephone number, area code, destination, and direction.

85. A computer product for comparing a first location and a second location, the computer product disposed on a computer readable medium and having instructions for causing a processor to,

use an iterative process to obtain a binary representation of the first location,

use the iterative process to obtain a binary representation of the second location,

perform a binary computation utilizing the first location binary representation and the second location binary representation to obtain a binary result, and

compute a distance measure from the binary result.

86. A computer product according to claim 85, wherein instructions to use an iterative process include instructions to,

relate the location to a coordinate system, and,

iteratively create subdivisions from at least one of the coordinate system or a subdivision of the coordinate system,

assign a binary code to the created subdivisions, and,

form the binary representation based on the binary code of the identified created subdivision.

87. A computer product according to claim 85, wherein instructions to perform a binary computation include instructions to perform an exclusive OR (XOR).

88. A computer product according to claim 85, wherein instructions to compute a distance measure further include instructions to associate binary digits of the binary result to at least one distance measure.

89. A computer product according to claim 85, further including instructions to identify at least one binary representation corresponding to at least one neighbor of the first location.

90. A computer product according to claim 85, further including instructions to identify at least one binary representation corresponding to at least one neighbor of the second location.

91. A computer product according to claim 85, further including instructions to compute at least one binary representation corresponding to at least one neighbor of the first location.

92. A computer product according to claim 85, further including instructions to compute at least one binary representation corresponding to at least one neighbor of the second location.

93. A computer product according to claim 85, further including instructions to determine at least one of whether the binary representation of the first location is a neighbor of the binary representation of the second location, and whether the binary representation of the second location is a neighbor of the binary representation of the first location.