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.

1 - 20 . (canceled) 
     
     
         21 . A method for maintaining a density-based geocode tree for a geographic area, the method 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, from embedded positions within messages on a social media platform, 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 respective geohash value of the first leaf node;   incrementing, by a cardinality of the first subset, a first counter value for the first leaf node, the first counter value comprising a count of user posts on the social media platform associated with the respective geohash value of the first leaf node; and   pruning, in response to a first density threshold exceeding the first counter value for the first leaf node, the first leaf node and one or more siblings of the first leaf node from the geocode tree.   
     
     
         22 . The method of  claim 21 , 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 respective geohash value of the second leaf node;   incrementing, by a cardinality of the second subset, a second counter value for the second leaf node, the second counter value comprising a second count of user posts on the social media platform associated with the respective geohash value of the second leaf node; and   grafting, in response to the second counter value exceeding a second density threshold, at least one child node onto the second leaf node.   
     
     
         23 . The method of  claim 21 , wherein the geocode tree is of a type selected from a group consisting of a perfect tree, a complete tree, and a balanced tree. 
     
     
         24 . (canceled) 
     
     
         25 . The method of  claim 21 , wherein the plurality of positions comprise global positions of mobile devices. 
     
     
         26 . The method of  claim 21 , further comprising:
 receiving, from a client device with a global positioning system, a reverse geocode lookup request comprising a new global position;
 generating a new geohash using the new global position; 
 mapping the new geohash to a leaf node of the plurality of leaf nodes of the geocode tree based on the geohash value of the leaf node; and 
 returning an identifier of a subdivision of a geographic area corresponding to the geohash value of the leaf node. 
   
     
     
         27 . The method of  claim 26 , wherein the identifier is of a type selected from a group consisting of a map tile, an address range, a zip code, and a place name. 
     
     
         28 . The method of  claim 26 , wherein the reverse geocode lookup request comprises a first reverse geocode lookup request, wherein the method further comprises:
 receiving, from a second client device with a respective global positioning system, a second reverse geocode lookup request comprising a second new global position different than the new global position;   generating a second new geohash using the second new global position, wherein the second new geohash has a length different than a length for the new geohash;   mapping the second new geohash to a second leaf node of the plurality of leaf nodes of the geocode tree based on a geohash value of the second leaf node; and   returning a second identifier of a second subdivision of a geographic area corresponding to the geohash value of the second leaf node.   
     
     
         29 . The method of  claim 21 , wherein the second leaf node and the one or more siblings of the second leaf node are associated with contiguous subdivisions of the geographic area. 
     
     
         30 . A system for maintaining a density-based geocode tree, the system comprising:
 a computer processor; and   a memory configured to store instructions that are executable by 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, from embedded positions within messages on a social media platform, 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 respective geohash value of the first leaf node; 
 increment, by a cardinality of the first subset, a first counter value for the first leaf node, the first counter value comprising a count of user posts on the social media platform associated with the respective geohash value of the first leaf node; and 
 prune, in response to a first density threshold exceeding the first counter value for the first leaf node, the first leaf node and one or more siblings of the first leaf node from the geocode tree. 
   
     
     
         31 . The system of  claim 30 , wherein the instructions are further executable by 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 respective geohash value of the second leaf node;   increment, by a cardinality of the second subset, a second counter value for the second leaf node, the second counter value comprising a second count of user posts on the social media platform associated with the respective geohash value of the second leaf node; and   graft, in response to the second counter value exceeding a second density threshold, at least one child node onto the second leaf node.   
     
     
         32 . The system of  claim 30 , wherein the geocode tree is of a type selected from a group consisting of a perfect tree, a complete tree, and a balanced tree. 
     
     
         33 . (canceled) 
     
     
         34 . The system of  claim 30 , wherein the plurality of positions comprise global positions of mobile devices. 
     
     
         35 . The system of  claim 30 , wherein the instructions are further executable by the computer processor to:
 receive, from a client device with a global positioning system, a reverse geocode lookup request comprising a new global position;   generate a new geohash using the new global position;   map the new geohash to a leaf node of the plurality of leaf nodes of the geocode tree based on a geohash value of a leaf node; and   return an identifier of the subdivision of a geographic area corresponding to the geohash value of the leaf node.   
     
     
         36 . The system of  claim 35 , wherein the identifier is of a type selected from a group consisting of a map tile, an address range, a zip code, and a place name. 
     
     
         37 . The system of  claim 30 , wherein the second leaf node and the one or more siblings of the second leaf node are associated with contiguous subdivisions of the geographic area. 
     
     
         38 . A non-transitory 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, from embedded positions within messages on a social media platform, 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 respective geohash value of the first leaf node;   increment, by a cardinality of the first subset, a first counter value for the first leaf node, the first counter value comprising a count of user posts on the social media platform associated with the respective geohash value of the first leaf node; and   prune, in response to a first density threshold exceeding the first counter value for the first leaf node, the first leaf node and one or more siblings of the first leaf node from the geocode tree.   
     
     
         39 . The non-transitory computer readable medium of  claim 38 , 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 respective geohash value of the second leaf node;   increment, by a cardinality of the second subset, a second counter value for the second leaf node, the second counter value comprising a second count of user posts on the social media platform associated with the respective geohash value of the second leaf node; and   graft, in response to the second counter value exceeding a second density threshold, at least one child node onto the second leaf node.   
     
     
         40 . The non-transitory computer readable medium of  claim 38 , wherein the instructions further comprise functionality to:
 receive, from a client device with a global positioning system, a reverse geocode lookup request comprising a new global position;   generate a new geohash using the new global position;   map the new geohash to a leaf node of the plurality of leaf nodes of the geocode tree based on a geohash value of the leaf node; and   return an identifier of a subdivision of a geographic area corresponding to the geohash value of the leaf node, wherein the identifier is of a type selected from a group consisting of a map tile, an address range, a zip code, and a place name.   
     
     
         41 . The method of  claim 21 , wherein obtaining the plurality of positions within the geographic area comprises obtaining the plurality of positions from messages on the social media platform transmitted during a predetermined time interval. 
     
     
         42 . The method of  claim 21 , wherein obtaining the plurality of positions within the geographic area comprises obtaining the plurality of positions that are located within a predetermined time zone. 
     
     
         43 . The method of  claim 21 , wherein pruning the first leaf node and the one or more siblings of the first leaf node from the geocode tree comprises pruning every sibling of the first leaf node from the geocode tree. 
     
     
         44 . The system of  claim 30 , wherein the geocode tree includes a first set of nodes for a first subdivision of the geographic area and a second set of nodes for a second subdivision of the geographic area, the first set of nodes having a greater number of levels than the second set of nodes, wherein a first geohash of a first leaf node of the first set of nodes is more precise than a second geohash of a second leaf node of the second set of nodes. 
     
     
         45 . The method of  claim 22 , wherein said grafting, in response to the second counter value exceeding a second density threshold, comprises grafting a plurality of child nodes onto the second leaf node, wherein the plurality of child nodes comprises a respective child node for each of a plurality of subdivisions of the geographic area to which the second leaf node corresponds.