Designing a location database: QuadTrees and Hilbert Curves

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! 🔥
https://interviewready.io

References:
Google S2: https://blog.christianperone.com/2015/08/googles-s2-geometry-on-the-sphere-cells-and-hilbert-curve/
Hilbert Curve: https://www.youtube.com/watch?v=3s7h2MHQtxc
Fractals: https://www.youtube.com/watch?v=gB9n2gHsHN4
System Design Playlist: https://www.youtube.com/playlist?list=PLMCXHnjXnTnvo6alSjVkgxV-VH6EPyvoX
Segment Trees: https://youtu.be/W4KUVTjh8RQ
Z-order curve: https://en.wikipedia.org/wiki/Z-order_curve

You can follow me on:
LinkedIn: https://www.linkedin.com/in/gaurav-sen-56b6a941/
Twitter: https://twitter.com/gkcs_