A friend of mine, who is the CEO of a company that develops an embedded database, asked me to do a presentation on spatial indexing. This was an opportunity for me to brush up on R-trees and similar datastructures. Download the slides The presentation introduces R-trees and spatial indexing to a technical audience, who are …
A distribution algorithm is used to map keys to servers in a distributed key-value store. There are several different ones, implemented in different systems, and with different properties. In this blog post I’ll briefly cover the best-known key hashing schemes, before I get to vbuckets.
Background When I’m at the library, I’d like to be able to go to the toilet, without collecting all my stuff from the table. Part of the solution is to have a camera installed that films all the tables, but assuming we can hire someone to look at the camera-feeds, that person might not notice …
Idea: Automatic theft prevention in public spaces Read More »
Situation: You have a large pile of computer science papers in front of you. You want to read them all. What to do? My suggestion is that you read the two guides below. They are really short and helpful. I’m one year into my CS PhD, and I still find reading a large pile of …
Here’s a game I like to play. Select two wikipedia pages at random, and find a route from one to the other. I stated a theorem once that: you can get from any page on wikipedia to the page on pollination in 7 steps or less. (it was actually another page, but let’s say it …
Finding a route from one wikipedia page to another Read More »
I’m half way through the Part-time parliament on Paxos article by Leslie Lamport. It is an article that describes a three-phase consensus protocol by telling a story of a (fictional) parliement on the greek island of Paxos, complete with fat priests, busy businessmen, and a vivid description of the parliament hall. The story illustrates how …
While browsing the web for for good videos to help me land a cool job at high profile tech firm, I came across this series from an Indian university. Lecture – 16 Disk Based Data Structures http://www.youtube.com/watch?v=VbVroFR4mq4 You should be able to easily find the other videos in the series through this one. Generally the …
Here I have captured a thought process I had while reading about algorithms for hard graph problems. The thoughts are inspired by MapReduce, distributed merge sort and the more colorful newspapers of the world. Summary of thoughts Given an instance of an problem (think Max Clique, Traveling Salesman or another hard graph problem)… Thought 1: …
Turning big hard problems into smaller, less hard problems. Read More »