Designing a location database: QuadTrees and Hilbert Curves
Вставка
- Опубліковано 8 лип 2024
- Location-based databases are extensively used by apps like Google Maps, Uber, and Swiggy. We explore the data structures and algorithms that allow spatial or location-based queries, like the quadtree and the Hilbert Curve.
For now, we haven't dived deep into polygon intersections or R-trees.
00:00 Who should watch this?
00:27 Pincodes
01:27 Measurable Distance
02:04 Proximity
02:39 Suitable Data Structures
03:48 2D Representation
05:13 Bits for X,Y axes
06:20 Searching in 2D
07:45 Potential Drawback
08:16 Quad Trees
10:07 Range Queries
10:52 Fractals from 2D to 1D
16:06 Hilbert Curve Examples
21:50 Course Questions
22:15 Thank you!
Looking to ace your following interview? Try this System Design video course! 🔥
interviewready.io
Course chapters:
1) Design an email service like Gmail
2) Design a rate limiter
3) Design an audio search engine
4) Design a calling app like WhatsApp
5) Design and code a payment tracking app like Splitwise
6) Machine coding a cache
7) Low-level design of an event bus
The chapters have architectural diagrams and capacity estimates, along with subtitled videos. Use the 'HELLOWORLD' code to get an exclusive discount.
References:
Google S2: blog.christianperone.com/2015...
Hilbert Curve: • Hilbert's Curve: Is in...
Fractals: • Fractals are typically...
System Design Playlist: • System Design for Begi...
Segment Trees: • Segment Trees explaine...
Z-order curve: en.wikipedia.org/wiki/Z-order...
You can follow me on:
LinkedIn: / gaurav-sen-56b6a941
Twitter: / gkcs_
The high-level design of Uber:
interviewready.io/learn/system-design-course/design-a-cab-aggregator-app-like-uber/requirements-of-a-cab-aggregator
I should have the high level design of Google Maps out this week. Wish me luck!
EDIT:
Google Maps: interviewready.io/learn/system-design-course/design-a-location-based-service-like-google-maps/requirements-of-a-map-application
Is seems similar to geohash, are they both same or different approach?
It's really overwhelming for me but the passion you have it towards making us understand the thinking behind designing a schema !! inspires me Gaurav. More power to you man.
This guy has more knowledge than all of my Engg clg's faculty combined.
😂😂😂😂😂
It is so easy to criticize your teachers but have you ever thought why are you enrolled in such a college?
@@swapk99 just one word "Majburi"
@@jibrankhan499 bhai shi kha aapka to naam bhi jabran hai :P
@@jibrankhan499 Apni Galti ki wajha majburi ko mat do!
Clearly, you are very passionate about Computer Science and love spreading the knowledge. How do you manage exploring so much around? You must be a very productive person to delve into stuff. It gets overwhelming for me thinking if I’ll ever be this knowledgeable. Thanks for all the inspiration!
I frequently feel the same (about my productivity and the overwhelming sense that I am slow).
But every now and then, I look back and feel good again 😁
And the best part about Gaurav is .. .he teaches not for views but for a more higher purpose B)
Bro, I bow down to you. To break down such a big concept into smaller parts and then not only explain the solution but how we reached the particular design. Can find a lot of videos on how something is implemented but this video tells why it is implemented the way it is. Job very well done.
Working in the maps industry I'm really happy to see this come up on my feed. Looking forward to watching. Thanks for all your content. It's very accessible.
😁
Literally 2 days ago I was reading about Google Maps algorithm and it's working, and you have made my wish come true by uploading this
I would say “Star of the show” is always u , I’m mersmerised with your knowledge in each subject with which u build solutions.. cheers bud .. u r going to give a tough fight to even PhD guys in Berkeley
Thank you 😁
I think I know why I was recommended this, but I wasn't really in the mood - if attention span isn't already a metric, here you go youtube, enhance your algorithm - any way, this was incredibly insightful. I like your thought process. It's very logical and understandable. You're brilliant and I appreciate your insight. Thank you.
You blew my mind up so hard it's spilt all over my computer!! This is amazing!
"taxiii sharing services" was wicked
that pause! I really laughed out loud xD
I loved the way you explained 2d to linear. It can not be simpler than this.
I just don't know , how the heck a person can be this talented , you are intelligent , you are humorous(coming from interview with miss Rainy Jain).I could never even think of exploring so much and i will fight with the one if he says you aren't passionate enough . I know no one will say.YOUR parents must be so proud of you...oh gosh i will stop now
😁
I do have an onsite tomorrow and I found your channel late, you have so much talent explaining complex topics. It's good you are sharing that talent with the community.
You just opened a whole new world to explore! Very interesting and exciting to expand it's applications.
Your video has come at such a great time. I'm getting started with building a rental car app and I've had a few issues while using maps in the app. This is going to help and I'm waiting for your next video on this topic. Thanks 😊
Wow! The concept is really interesting. Thanks, man!
Loved the way you explained the hilbert curve and its application to the problem at hand.
You are awesome at explaining, thank you for all your effort!
I've never seen such a perfect video explaining hilbert curve!!
wow Gaurav, you are amazing :), happy enough to watch this, as the video was just released, very well done
Intro is solid, content is as usual as dope
Exactly what I was stuck on today... You made it simpler gaurav... Thanks loads.
Wow the fractal connection was totally unexpected. When you told dimensionality reduction, my mind immediately went to Principal Component Analysis but couldn't figure out how. Fractals was elegant👍
Interesting, I think PCA was a good guess!
I thought of PCA too but I was wondering how he would apply it. Good thing he went to Hilbert Curves and I learnt something new today
This guy has huge knowledge and logic I wish I could have 1% of him...everything went out of my mind I could not understand anything
This video deserves far more views/attention, excellent efforts
One of the best content I have seen, in such a short time !!! Thanks Man !
Thank you!
Wow this is exactly what we were discussing in our project today
Thanks a lot, I'm just 15. I learnt new thing. Bro you can yourself start a bigger company than Google.
Wow! I like your style of teaching. This was very well explained. Keep it up!
The most interesting video I have ever seen!!!
Thanks!!
This is basically masterclass in system design...inspiring
Hi just commenting on channels which helped me in one way or the other, land a great job offer from a huge firm! Thanks! I shared the channel with other people too!
Thanks for this one. Much anticipated one!
More to come! 😁
Love your videos Gaurav thanks a lot and keep them coming.
Great Effort! Appreciate it!
It's amazing, Literary encounters some new concepts and thoughts, we never heard before.
Thank you so much, Sir🙂
Thanks 😁
Beautiful explanation and the best part is the way you explained the application of hilbert curve. Kudos!
Thank you 😁
Great explanation of hilbert curve! thanks!
Bro, today you have gained my utter respect for your knowledge and your passion to pursue more knowledge. This video is mind-blowing, So much profound mathematical concepts linking with hardcore real-life applications.
When the Master teaches, us Students listen. thank you for the great video, most of it made sense towards the end,
Always wanted to know this
Finally 🙌
Like before watch. That much, I trust your teaching skills.
Appreciate that 😁
So cool edits in the video. Perfect.
Wonderful explanation! :)
S_id, Hilbert curves I guess is the short answer? The fractal part was very interesting
Thanks . Much needed
Your passion for tech shows in your videos.
I am not even a tech guy and i watched the whole video.
😁
Brilliant video, explained really well. Thanks Gaurav
This is an ideal use of UA-cam.. . Well done GKCS
your editing skills are too good like your teaching skills.
Amazingly explained
Enjoyed the video very much, Thanks gkcs Bhaiya!!
Waouh thanks for your work, this video is what I was looking for
Thanks, learned something new
Gaurav man.. i always wanted to know about these Spatial Database topics concepts. Thanks alot 😊
You really know how to explain. Keep it up 👍
explained well, such a complicated topic.
I was curious about how these apps work before watching this. Now I'm even more curious and feel i don't know anything . this is just great work!
They have some super cool stuff under the hood 😁
@@gkcs yep i hope to work on that under the hood stuff someday :P
Respect for your knowledge Gaurav.
Gr8 Content Gaurav ! Keep learning and sharing !
Me: currently working on geo spatial visual representations
Algorithm: where did that bring you? back to me.
Got an opportunity to learn something new! Thanks so much!
this is the channel i was looking for...
Love the new intro bro!
wow, this is alot of information in one video :D, ive watched it twice now, and im still confused. Ill get the hang of it though, thanks Guarav!!!
Suppose we are using the Hilbert curve method on a 4 quadrant (A,B,C,D), when we are trying to get proximity of two points in A(top-left) & D(bottom-left). The proximity result would be "faaar away" in spite of being in adjacent quadrants. How do we overcome this problem?
18:00 Hi Gaurav - I'm curious how we have the established configuration of the rotation of Hilbert curves within each quadrant?
Also - thanks for reviewing that continuity of lines -> infinite partitioning - I forgot this cool property of continuity from epsilon-delta definitions - and showing the intuition of quad trees lending to range queries via the line segment.
This dude is brilliant.
truly beautiful
Awesome... Trying to get this kind of solution for the proximity use case from loong time.. Happy to see this explanation.. Pls make the other video also here, not in your course🤓
most underrated channel bro please do video on competitive program tutorial questions..love from nepal
Very Nice explanation.
I am really looking forward to the food delivery app system design!
Wow! I'm mind blown.
Wow Gaurav, you are amazing :), I learnt this concept from educative but your explanation is too good.
Thanks 😁
Every time I watch your videos I always learn something new and unique, appreciate your efforts. I have a doubt though, I am trying to solve the same range problem for my location-based application using coordinates with the haversine formula in my SQL query, coordinates are stored as 'char'. Please clarify if there's something wrong with my approach.
this was great..
kinda cool the 2 projection works incredibly well on most road systems since they are in effect a 2-D lattice so you are fine with 90 degree turns at some accuracy threshold.
This video series explains a more suitable algorithm (A* search) for Google Maps:
interviewready.io/learn/system-design-course/design-a-location-based-service-like-google-maps/requirements-of-a-map-application
brilliant!
Hats off !
14:53 Why can’t we have 1 in fourth quadrant? Can you please elaborate the reason?
And also explain why in certain permutation which number cannot be in which quadrant and why.
thanks.
We are taking permutations which form unique shapes. Hence we must exclude rotations of the same shape.
At 14:53, a 1 in the third quadrant will give us a rotation of the first shape (Z).
Nice!
what database are you using? programming language?
It is very moralising for me to see youtubers like yourself who make informative videos, and helping the community to push boundaries of the tech unlike those shitty youtubers who make roast/dank/game stream videos..
Love you brother keep growing
@Gaurav Sen : This is very unlike your other videos. Even the 1st 10 minutes is greek and latin perhaps a much longer video is needed for this topic. Neverthless a very interesting topic.
Thanks for the feedback 🙂👍
How Can I Develop A Database Which Stores Any User Decidede Location Rangewise??
Means 500 meters Around My College.
Have you considered using Radix/Patricia-Trie for proximity. Like Quad-Tree you just explained, it converts lat-lon into 1D by using an open-source library called Geohash.. After converting a lat-lon into a prefix string, we apply the trie. Proximity just becomes natural. I spent some time trying to run algorithm like finding if a point is in Geofence or not. Had some error but had encouraging result.
Hey @Gaurav Sen can you post a link for the location-based databases which give more intuition on top of how these data apps or food delivery apps are based?
Radically, IMPRESSIVE!!!!
Thank you 😁
I’m wondering, does this mean that problem of edge cases have no resolution and can be ignored? So users from regions 29 and 18 never won’t meet because they have distance of 11 in this representation which will exceeds the threshold?
Great presentation, looking forward to seeing more.
For anyone who wants more details on the theory, this is great: arxiv.org/pdf/1710.06384.pdf (The first ~20 pages are actually quite readable without getting proof heavy).
They find neighbor cells exactly by recursively walking up and down the (implicit) quad tree formed by the space filling curve. Thus "... the runtime of the algorithm depends on how far one has to walk up and down the tree to find the neighbor. This concept is later introduced as the neighbor-depth of 𝑣. ... The neighbor-depth allows to characterize the runtime of the algorithm. In Theorem 4.1, we will show that the runtime of the algorithm is in 𝒪 (neighbor-depth) (assuming constant-time arithmetic operations). Using a standard geometric series argument, we will then show that the average neighbor-depth at level 𝑙 is 𝒪 (1) for all “normal” SFCs." (page 14)
Good stuff!
the coolest engineer
hi Gaurav. your videos are awesome- I like how you make things simple to understand. Can you please do videos on elevator system design and parking lot management system.
Hello @Gaurav
Thanks for the nice explanation! I have a question on the partitioning and scalability of the hilbert curve in this solution.
How would you partition the hilbert curve for maintaining scalability?
Great video and concept as always. I have question-
How do we find that node 5 is in close proximity of 57 58 59?
Does the concept of proximity relates with a special form of non-Euclidean geometry called Taxicab Geometry developed by Hermann Minkowski ? As the points of locality are identified up with Hilbert space filling curve, the path seems identifiable with this Taxicab Geometry approach. Correct me, if I am going wrong with this.
10:07 That T Shirt change though 🤣
@4:47, can someone explain how this example works? mapping 5 in range 4 to 7?
anyone? This part is going over my head