Module 3 Capstone: Picking the Right Algorithm
Concept. Choose the data structure and algorithm that fit each workload.
Which join algorithm should I use?
-
Non-equi joins: use BNLJ.
-
Equi-joins: use the equation sheet to calculate BNLJ, HPJ, and SMJ costs. Choose the cheapest.
Do the math.
Which lookup index should I use?
Figure: Choose the key, then the indexWords and IDs can be indexed directly. Embeddings can be full keys for exact matches or mapped to LSH codes for similarity candidates. Locations can be mapped to spatial codes. Hash indexes support equality; B+ trees also support ordered key ranges.
Figure 1. Choose the key, then the index. Smaller keys fit more entries per page.
How should writes be handled?
| B+ tree / hash index | LSM tree |
|---|---|
| Update the relevant pages | Buffer updates in memory |
| Split pages or buckets; reorganize as needed | Flush sorted SSTable files |
| Scattered page writes can become expensive | Batch writes, then merge files through compaction |
| Pay for page updates as writes arrive | Reads may check multiple files; compaction adds work |
Update pages now, or batch writes and compact later.
Design from the workload
Use the workload to choose a structure, then explain the key, value, and tradeoff.
Tools to consider: hash index, B+ tree, LSH, LSM tree, Bloom filter. You may combine them; they serve different roles.
Your design: key, value, read/write path, and one tradeoff.
Try-afterward questions are optional; no submission is required.
Finding the right data
Finding the Right Data
1. How do you find upcoming shows in your ZIP code?
Find upcoming shows in one exact ZIP code. Return artist, venue, and date.
Hint
Use a hash index. What is the lookup key?
One possible design
Key/value:zip_code → show records with artist, venue, and date.
How it works:find the ZIP’s records, filter out past shows, and sort by date.
Tradeoff:the ZIP lookup is fast; filtering and sorting still take work.
Try Afterward: Search a date range
What if users search a ZIP code and a date range, with many shows per ZIP?
Hint
Consider a B+ tree on (zip_code, date).
One possible answer
Use a B+ tree on (zip_code, date). Seek to the ZIP and start date, then scan until the end date or a different ZIP. This avoids scanning every show in the ZIP.
2. How do you show an artist’s listening trends?
Show daily listen totals after a release for one artist and city over a date range. Updates may lag by 1 hour.
Hint
Store daily aggregates with a B+ tree. What comes before the date in the key?
One possible design
Key/value:(artist_id, city, date) → daily listen count.
How it works:Update daily totals hourly. Seek to the first date and scan the range.
Tradeoff:Keep raw events for questions the daily totals cannot answer.
Try Afterward: Query all cities
What changes if the dashboard requests all cities for a date range?
Hint
Think about the order of fields in the composite key.
One possible answer
Use (artist_id, date, city) for this access pattern, or scan the date range separately for each city with the existing index. Choose based on the common queries; a second index costs storage and writes.
Handling updates and combining results
3. How do you keep listen time per song up to date?
Each listen adds listen time. Handle 100,000 events per second. Totals may lag by 1 minute.
Hint
Use an LSM tree with an additive merge rule. Choose the key and value.
One possible design
Key/value:(song_id, date) → partial sum of seconds.
How it works:accumulate in memory, flush sorted files, and add partial sums during reads and compaction.120 + 80 + 100 = 300 seconds
Tradeoff:Compaction still costs I/O.
Try Afterward: Handle duplicate events
What if the same event is delivered twice?
Hint
Adding the same increment twice changes the answer. What identifies an event?
One possible answer
Give events stable IDs and deduplicate before adding their seconds. The duplicate check and aggregation must be coordinated so a retry cannot count twice. An ordinary Bloom filter alone cannot safely discard events: false positives could lose valid contributions.
4. How do you maintain average listen time per song?
New listens keep arriving. Maintain the overall average without rereading every listen.
Hint
Keep the LSM design. What two numbers can you add independently?
One possible design
Store:(total_seconds, listen_count) per song and date.
Combine:add the seconds and counts.
Read:divide total seconds by listen count.
Try Afterward: Combine medians
Can the same approach calculate the median by storing each batch’s median and count?
Hint
Can different batches have the same median and count but different values?
One possible answer
No. A median and count do not preserve enough information to recover the combined median. An exact answer needs additional distribution information, potentially the values themselves; an approximate answer needs a different summary.
5. How do you avoid reading unnecessary files?
A song’s totals may appear in several SSTables. How can you skip files that definitely do not contain its key?
Hint
Use a Bloom filter per SSTable. Which keys should each filter summarize?
One possible design
Keys summarized:each SSTable’s (song_id, date) keys.
How it works:Definitely absent → skip the file. Possibly present → check its index and data.
Tradeoff:filters use RAM; false positives cause unnecessary reads.
Try Afterward: Look up a date range
Can the same Bloom filter answer “all dates in this month”?
Hint
A standard Bloom filter tests membership of a specific key.
One possible answer
Not directly. Use file key ranges and sorted indexes to find and scan the relevant dates.
Finding similar data
6. How do you find 20 album covers similar to this one?
Given a cover or cover ID, find 20 similar images among 10 million covers. Their embeddings are indexed using LSH. Approximate results are acceptable.
Hint
Use LSH for candidates, then score them. What belongs in each bucket?
One possible design
Key/value:LSH_code → cover IDs, within each LSH table.
How it works:get the cover’s embedding, compute its LSH codes, and probe matching buckets. Deduplicate candidates, score by cosine similarity, and return the closest 20 candidates.
Tradeoff:the true closest matches may be missed. Probing more buckets improves coverage but adds work.
Try Afterward: Find matches outside the first buckets
What if some good matches fall into different buckets?
Hint
Can you change candidate retrieval without changing the final similarity calculation?
One possible answer
Try more hash tables or probe additional buckets, then rerank the candidates with the same cosine calculation. Measure recall and latency on held-out queries. More candidates generally mean more scoring work.
Takeaway: Choose the key and operation before choosing the structure. Explain what your design makes cheaper and what it makes more expensive.