Geohashing ও Quadtrees

আপনি Uber-এ ride চেয়েছেন। App কীভাবে আপনার ৫ কিমি-র মধ্যে available driver খুঁজে বের করে? Database-এ লক্ষ লক্ষ driver — সবার সাথে distance calculate করলে slow। Solution: Geospatial indexing।

Geographic Search-এর সমস্যা

একটি table-এ million location (lat/lng pair)। Question: "এই point-এর ৫ কিমি-র মধ্যে কোন কোন point আছে?"

• Naive: সবার সাথে distance compute → O(N) — slow।
• Single-column index (lat বা lng) — uses করতে পারে কিন্তু optimal না।
• 2D space-এ spatial structure দরকার।

Geohash কী?

Geohash = একটি geographic coordinate (lat, lng) এনকোড করার system যা একটি ছোট string-এ পরিণত হয়। কাছাকাছি location-এর geohash গুলো similar prefix থাকে।

Encoding

World-কে recursively rectangle-এ ভাগ:

1. প্রথমে পৃথিবী 32 part-এ split।
2. প্রতিটি part-এ 32 sub-part — string-এ extra char।
3. যত character → তত precision।

Property: Prefix Match = Proximity

Two geohash একই prefix থাকলে → কাছাকাছি location।

• wh0qe ও wh0qf — adjacent box।
• Database-এ prefix index দিয়ে fast lookup।

Edge Cases

• Box boundary-এ — adjacent box-গুলো check করতে হয়।
• Equator/poles — distortion।

Quadtree

Quadtree = একটি tree data structure যেখানে প্রতিটি internal node-এর ৪টি child। 2D space-কে recursively ৪ quadrant-এ ভাগ।

Structure

Adaptive Splitting

সব region same size না — busy area (Dhaka) deeper, empty area (sea) shallow।

Use cases

• Dynamic location data (moving cars)।
• Region-based query।
• Game development।
• Image processing।

R-Tree

R-Tree = Bounding rectangle দিয়ে spatial index। Polygon, complex shape-এ ভালো।

• Internal nodes = bounding box।
• Leaf = actual geometry।
• PostgreSQL/PostGIS, MySQL spatial — R-tree based।

Geohash vs Quadtree vs R-Tree

Proximity Query

"Find drivers within 5km"

1. User-এর location → geohash (5-char precision ≈ 2.4km)।
2. 9 neighboring geohashes (target + 8 adjacent box) compute।
3. Database-এ prefix match query।
4. Results-এ exact distance filter (Haversine formula)।
5. Sort by distance।

বাস্তব ব্যবহার

• Uber: Geohash + custom indexing — driver-rider matching।
• Lyft: Quadtree-based S2 (Google library)।
• Foursquare: Geohash for venue search।
• Tinder: Geohash-based nearby user discovery।
• Pokemon Go: S2 cells।
• Redis: Built-in GEO commands (geohash inside)।

Redis GEO Commands

Redis internally geohash use করে।

Google S2 Geometry Library

Google-এর open-source geospatial library:

• Sphere-based (more accurate than rectangular geohash)।
• Hilbert curve — adjacent cells contiguous।
• Variable cell size।
• Used by Google Maps, Lyft, Pokemon Go।

Haversine Formula

Two lat/lng-এর মধ্যে great-circle distance:

Geohash দিয়ে candidate filter, তারপর Haversine দিয়ে exact distance।

সাধারণ ভুল ধারণা

1. "Geohash exact distance": না — bucket-based; Haversine দিয়ে refine।
2. "Adjacent prefix always proximity": Boundary-এ near point ভিন্ন prefix-এ পড়তে পারে।
3. "Quadtree DB-তে standard": R-Tree বেশি common DB-তে।

Best Practices

• Use case match: static = geohash; dynamic = quadtree; complex shape = R-tree।
• Boundary handling — neighboring cells check।
• Geohash precision use case-অনুযায়ী choose।
• Two-stage search: spatial filter + exact distance।
• PostGIS production-grade DB ব্যবহার করুন।
• Redis GEO simple use case-এ যথেষ্ট।