# Algorithms

## A presentation on spatial indexing

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 …

## Having a look at vbuckets

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.

## Idea: Automatic theft prevention in public spaces

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 …

## How to read computer science papers

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 …

## If only more people wrote like Lamport

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 …

## Good indian computer science videos on youtube

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 …

## Turning big hard problems into smaller, less hard problems.

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: …