Geohashing Algorithm | Proximity Search Based Applications | System Design
ฝัง
- เผยแพร่เมื่อ 14 มิ.ย. 2024
- Learn about a common geocoding technical called Geo Hashing which will allow you to find points of interests (POI) around your user’s location very efficiently. This will let you build proximity apps such as Uber, Lyft, Yelp, and many more.
Use this interactive map for visualization: [www.movable-type.co.uk/script...](www.movable-type.co.uk/script...)
System Design Playlist: • System Design Beginner...
More References from the video:
[www.pubnub.com/learn/glossary...](www.pubnub.com/learn/glossary...)
[ / geohashing ]( / geohashing )
00:00 Why Use Geohashing?
00:32 What is Geohashing?
00:50 Visualization
03:45 Greater Precision
05:25 San Francisco Map Example
08:10 How to find POIs using Geohash
12:30 Map Prefix Length Match to Distance
15:45 Optimize the number of POIs
16:25 Future Videos using Geohash
17:05 Geohash Visualization Tool
17:50 Feedback Please!
#systemDesign #geohashing #location
Visit me at: irtizahafiz.com
Reach me at: irtizahafiz9@gmail.com
Just started to prepare my system design interview, and found this video with very detailed explanation and pretty useful.
So glad these are helping : ) Good luck on your system design interviews! You got this!
Such a clear and well-explained video! It's my first time learning about Geohasing and I totally get it now. Thank you Irtiza!
Glad you found it helpful!
Pretty crisp and clear explanation , thank you!
Glad it was helpful!
Great Explaination. Thanks!
very useful system, thanks for the explanation, this has such a wide range of uses.
So glad it was helpful! Please let me know if you have any feedback. Always looking to improve the content.
very useful
thanks !!!
its amazing. I wish u all the best.wish u post more videos on system design
Thank you! I will start posting again very soon.
Brilliant explanation
Thank you! Glad you found it valuable.
Excellent explanation
Thanks for that!
thanks
Think of each co-ordinate in Level 1 in Binary representation. (00,01,10,11), You can then prefix each cell and zoom into the map.
Thank you for the video! I have subscribed! :) I have got a question not all POIs have the same prefix even when they are close. What are the other ways to find nearest POI using geohashing ?
Hi! That's a good question.
I would recommend getting a few "boxes" around your POI, not one box only. That will help you get around the "boundary problem".
Correction: It's "representing" not "representating" -_- Don't know what happened to me.. Anyways, hope it was helpful!
we care only about the valuable knowledge you've given to us bro, and we are grateful to you!
How we will handle the case of different quadrants where user and POIs are close but they are in different quadrant of level 1
Good video. If I am standing near one corner of a geolocation quadrant,this logic will give me all the businesses that are in my geolocation(the square i am in). But since I am near the edge, would the businesses near the edge of adjacent quadrants get excluded in my search though they are within the distance I am searching for?
That's a very good observation.
That's the downside of using only one of the quadrant. To get over the boundary problem, you want to look up businesses from a few quadrant around you, rather than just one.
So you map the sphere to a rectilinear grid.
I would be interested in the thinking leading to choosing this algorithm. So, what other algorithms were considered for solving this problem, why arrive at dividing the world this way, what are the pros/cons of this and other algos for consideration. The algo itself is gettable, but arriving at the conclusion to use this algo over others in more crucial to me
I am sure there are some great researches behind it, and I wouldn't be surprised if there are more preferred algorithms for this use case. This was just one example.
Hi, thanks for the video. What about a case when POIs is around the border of rectangle? For example 2 points are close to each other on the map, but have different first character of hash.
I'm also wondering how to solve this. Did you find a solution?
@@powerhead Not yet :(
@@Arkham_nine in this case you can expand your search radius by +- few Km
As Vippan pointed out above, you can expand the radius.
@@irtizahafiz Hi. How expanding the radius can fix this problem? I don't understand :( Can you show an example please?
hey super detailed video!, i enjoyed it thoroughly. Just wanted to ask if you could point me to any guide or an example even of how this could be implemented in code for python
Hi! Glad you enjoyed it. Will appreciate any feedback that you can give for future videos.
Here is a good implementation in Python: github.com/wdm0006/pygeohash The documentation the author provided is also super helpful : ) Hopefully that helps!
@@irtizahafiz thanks a lot for the pointer will take a look at this. And i have subscribed to you channel so i can watch more of your content
Excellent Tutorial. Where can I find the pointer to your notes?
Hi! I try my best to upload the notes. But for some videos, it's not there unfortunately.
why this guy only this much subs
Thank you! I will start posting again soon, so please let me know what type of content interests you the most.
Very impressive explanation. I was just having assimilation problem trying to understand the algorithm on wikipedia and some sites.
Your explanation made it something a 5 year old can easily understand.
Thanks. Just subscribed.
Thank you! Glad you found it valuable.
Video could be edited to avoid repeated info and more examples etc and can be reduced to half of present length.
Don't know if somebody mentioned but there's a typo in you table on line 6: there sould be 1220 meters.
Thank you for correcting. Hopefully this will help others.
Are Geo-hashing & Quadtress two different strategies? Which one is better ?
Not too familiar with Quadtrees :(
We are dividing the world into 64 cells not 32 cells... 4*4*4 (in each level we are dividing each cell into 4 so by level 3 we are multiplying 4, 3 times to it self meaning 4 to the power of 3)
I’m not getting what exactly is computed by multiplying width and height in meters and dividing by 1000 🤔
Hi! It's been a very busy couple of weeks because I am changing places. I will try to get back to this comment later in the week.
Correct me If I'm wrong, @@irtizahafiz
So, basically, the area of a rectangle is `width*height`. As width and height are in meters, dividing it by 1000 gives you the Kilometres denomination. So, the computation, width*height/1000 represents the area of the location covered by Geohash. As the Geohash length increases, the area decreases
Irtiza Can you please share your slides with us? These slides are really concise
Hi! Unfortunately, I don't have the slides anymore for this video. I think starting from the next video, I made it a regular thing to upload slides in the Description section.
@@irtizahafiz thanks
Would you mind to upload your ppt(documentation) for study
Hi. For sure. Sorry I forgot to upload the notes for this one. Other System design videos should have their notes in the video description.
Here's the notes for this video: docdro.id/07Vq6FT
@@irtizahafiz
Appreciate it, actually I think your lecture and presentation is really impressive and is really beneficial
So glad to hear that. Let me know if there is anything I can improve on. Cheers!
Why 32? Is there an explanation somewhere?
Not that I am aware of unfortunately. I was mostly trying to explain the concept. I "think" 32 is configurable and used for demonstration purposes only here.
However, I would recommend checking out some other resources if you wanted a more thorough explanation.
As a native English speaker, I would say "represented" instated of "representated" :).
Hi! Thank you for correcting. English is difficult haha.
@@irtizahafiz Yep :). I even had a typo in my response... (instated -> instead)
Representated -> represented / represent
Haha, my apologies. English is hard.
@@irtizahafiz no worries haha, just came to my mind when watching. great vid!
In a 18 minute video about geo-hashes you do not talk about or even mention the boundary problem. What if I am near the equator? All points to the south of me will have totally different prefixes.
I believe I mention the boundary problem, and ways to deal with it in the later part of the video.
Your math is not right. Width * height gives you square meters not km 😊
I agree, its not distance at all
This is just a quad tree