## Data Structure Name: Geohash ### Description: A geohash is... #flashcard a geospatial data structure that encodes coordinates into a string representation. The encoding uses a [[BASE]]-32 alphabet. This means the world is divided into 32 regions each with a corresponding Base-32 character associated with it. Each sub-region is further divided by 32 using the same characters. This continues recursively until the deepest level of 12 (i.e., a geohash with 12 characters). This approach allows for capturing a rather precise location only using a string. <!--ID: 1751507777653--> ### Variations: ### Diagram: ![[Geohash 2024-09-10 12.27.28.excalidraw.svg]] ### General Use: ## Key Considerations ### Properties of Geohash: #flashcard - **Geohash Lengths** - the lengths of a geohash directly correspond to a certain level of granularity or precision: - A Geohash of length 1 represents a large area, such as a continent. - A Geohash of length 2 represents a smaller area, such as a country. - A Geohash of length 3 represents a region or large city. - A Geohash of length 4 represents a smaller city or town. - Geohashes of length 5 or higher represent progressively smaller areas, down to street level and even specific locations. - **Shared Characters** - two geohashes that start with shared characters mean they share those specific regions <!--ID: 1751507777656--> ### Strengths of Geohash: #flashcard - Simple representation of a single string, making it easy to store and share - Efficient for proximity searches as nearby locations often share a prefix - Uniform distribution of hash values <!--ID: 1751507777658--> ### Weaknesses of Geohash #flashcard - Precision varies across latitude; higher latitudes have less precision - Not as efficient for bounding box search when compared to [[Quad Trees]] due to its [[z-ordering]] curve properties - Boundary issue - adjacent areas may not share the same prefix, complication proximity searches <!--ID: 1751507777664--> ### Implementation Details: | | [[Big O - Time Complexity]] | [[Big O - Space Complexity]] | | ------ | --------------------------- | ---------------------------- | | Access | | | | Add | | | | Delete | | | | Search | O(logn) | | ### Implementation Tips ### Special Properties ## Specific Use Cases ## Reference #### Working Notes #### Sources