- Learn
- High Level System Design
- Search, Geo and Specialized Data Structures
HLD-M15
Search, Geo and Specialized Data Structures
The specialized indexes behind search boxes, maps, analytics and AI features: inverted indexes, tries, geospatial cells, probabilistic sketches, time series and vectors.
General-purpose databases answer "give me the row with this key" very well. Many product features ask different questions: which documents mention these words, ranked by relevance? What are the top completions for "sys"? Which drivers are within 2 km? Have we seen this URL before? How many unique visitors today? Which items are most similar to this one? Each needs a data structure designed for that question.
This module covers the important ones from a system designer's point of view: inverted indexes and BM25 ranking for full-text search, tries for typeahead, geohashes, quadtrees and hexagonal cells for location queries, Bloom filters, Count-Min Sketch and HyperLogLog for answering questions approximately in tiny memory, time-series storage with compression and downsampling, and where vector search fits when a system needs semantic similarity.
Lessons
- HLD-15.01 Inverted indexes and full-text search Full-text search engines build an inverted index: for every term, a list of documents that contain it. Intermediate 14 min
- HLD-15.02 Typeahead and autocomplete Autocomplete must answer within tens of milliseconds as the user types. Intermediate 10 min
- HLD-15.03 Geospatial indexing Finding things near a location is hard with plain latitude and longitude indexes. Intermediate 14 min
- HLD-15.04 Probabilistic data structures Probabilistic data structures answer questions approximately using tiny memory. Advanced 14 min
- HLD-15.05 Time-series data Time-series data is mostly appended, queried by time range and aggregated. Intermediate 10 min
- HLD-15.06 Vector search in system design Embeddings turn text, images or users into vectors where similar items are close together. Intermediate 10 min