Density-based dynamic geohash

Abstract

A method and system for maintaining a density-based geocode tree for a geographic area, including obtaining a geocode tree including multiple leaf nodes each having a geohash value corresponding to a subdivision of the geographic area, obtaining multiple positions within the geographic area, generating, using the multiple positions, multiple geohashes, mapping a first subset of the multiple geohashes to a first leaf node of the multiple leaf nodes based on the geohash value of the first leaf node, incrementing, by a cardinality of the first subset, a first counter value for the first leaf node, and grafting, in response to the first counter value exceeding a first density threshold, at least one child node onto the first leaf node.

What is claimed is: 
     
         1 . A method for maintaining a density-based geocode tree for a geographic area, comprising:
 obtaining a geocode tree comprising a plurality of leaf nodes each having a geohash value corresponding to a subdivision of the geographic area;   obtaining a plurality of positions within the geographic area;   generating, using the plurality of positions, a plurality of geohashes;   mapping a first subset of the plurality of geohashes to a first leaf node of the plurality of leaf nodes based on the geohash value of the first leaf node;   incrementing, by a cardinality of the first subset, a first counter value for the first leaf node; and   grafting, in response to the first counter value exceeding a first density threshold, at least one child node onto the first leaf node.   
     
     
         2 . The method of  claim 1 , further comprising:
 mapping a second subset of the plurality of geohashes to a second leaf node of the plurality of leaf nodes based on the geohash value of the second leaf node;   incrementing, by a cardinality of the second subset, a second counter value for the second leaf node;   pruning, in response to a second density threshold exceeding the second counter value, at least the second leaf node.   
     
     
         3 . The method of  claim 1 , wherein the geocode tree is of a type selected from the group consisting of a perfect tree, a complete tree, and a balanced tree. 
     
     
         4 . The method of  claim 1 , wherein the plurality of positions are obtained from a data source comprising population density data. 
     
     
         5 . The method of  claim 1 , wherein the plurality of positions comprise global positions of mobile devices. 
     
     
         6 . The method of  claim 1 , further comprising:
 receiving a reverse geocode lookup request comprising a new position;   generating a new geohash using the new position;   mapping the new geohash to a leaf node of the plurality of leaf nodes based on the geohash value of the leaf node; and   returning an identifier of the subdivision of the geographic area corresponding to the geohash value of the leaf node.   
     
     
         7 . The method of  claim 6 , wherein the identifier is of a type selected from the group consisting of a map tile, an address range, a zip code, and a place name. 
     
     
         8 . A system for maintaining a density-based geocode tree, comprising:
 memory; and   a computer processor for executing a tree maintenance application stored m memory and causing the computer processor to:
 obtain a geocode tree comprising a plurality of leaf nodes each having a geohash value corresponding to a subdivision of the geographic area; 
 obtain a plurality of positions within the geographic area; 
 generate, using the plurality of positions, a plurality of geohashes; 
 map a first subset of the plurality of geohashes to a first leaf node of the plurality of leaf nodes based on the geohash value of the first leaf node; 
 increment, by a cardinality of the first subset, a first counter value for the first leaf node; and 
 graft, in response to the first counter value exceeding a first density threshold, at least one child node onto the first leaf node. 
   
     
     
         9 . The system of  claim 8 , wherein the tree maintenance application further causes the computer processor to:
 map a second subset of the plurality of geohashes to a second leaf node of the plurality of leaf nodes based on the geohash value of the second leaf node;   increment, by a cardinality of the second subset, a second counter value for the second leaf node;   prune, in response to a second density threshold exceeding the second counter value, at least the second leaf node.   
     
     
         10 . The system of  claim 8 , wherein the geocode tree is of a type selected from the group consisting of a perfect tree, a complete tree, and a balanced tree. 
     
     
         11 . The system of  claim 8 , wherein the plurality of positions are obtained from a data source comprising population density data. 
     
     
         12 . The system of  claim 8 , wherein the plurality of positions comprise global positions of mobile devices. 
     
     
         13 . The system of  claim 8 , wherein the tree maintenance application further causes the computer processor to:
 receive a reverse geocode lookup request comprising a new position;   generate a new geohash using the new position;   map the new geohash to a leaf node of the plurality of leaf nodes based on the geohash value of the leaf node; and   return an identifier of the subdivision of the geographic area corresponding to the geohash value of the leaf node.   
     
     
         14 . The system of  claim 13 , wherein the identifier is of a type selected from the group consisting of a map tile, an address range, a zip code, and a place name. 
     
     
         15 . A computer readable medium storing instructions for maintaining a density-based geocode tree, the instructions comprising functionality to:
 obtain a geocode tree comprising a plurality of leaf nodes each having a geohash value corresponding to a subdivision of the geographic area;   obtain a plurality of positions within the geographic area;   generate, using the plurality of positions, a plurality of geohashes;   map a first subset of the plurality of geohashes to a first leaf node of the plurality of leaf nodes based on the geohash value of the first leaf node;   increment, by a cardinality of the first subset, a first counter value for the first leaf node; and   graft, in response to the first counter value exceeding a first density threshold, at least one child node onto the first leaf node.   
     
     
         16 . The computer readable medium of  claim 15 , wherein the instructions further comprise functionality to:
 map a second subset of the plurality of geohashes to a second leaf node of the plurality of leaf nodes based on the geohash value of the second leaf node;   increment, by a cardinality of the second subset, a second counter value for the second leaf node;   prune, in response to a second density threshold exceeding the second counter value, at least the second leaf node.   
     
     
         17 . The computer readable medium of  claim 15 , wherein the geocode tree is of a type selected from the group consisting of a perfect tree, a complete tree, and a balanced tree. 
     
     
         18 . The computer readable medium of  claim 15 , wherein the plurality of positions are obtained from a data source comprising population density data. 
     
     
         19 . The computer readable medium of  claim 15 , wherein the plurality of positions comprise global positions of mobile devices. 
     
     
         20 . The computer readable medium of  claim 15 , wherein the instructions further comprise functionality to:
 receive a reverse geocode lookup request comprising a new position;   generate a new geohash using the new position;   map the new geohash to a leaf node of the plurality of leaf nodes based on the geohash value of the leaf node; and   return an identifier of the subdivision of the geographic area corresponding to the geohash value of the leaf node.