Cache-oblivious data structures

In most data structure and algorithms classes, the model used for basic analysis is the traditional RAM model: we assume that we have a large, random-access array of memory, and count the number of simple reads/writes needed to perform the algorithm. For example, selection sort takes about n(n-1)/2 reads and 2n writes to sort an…

10

K-nearest neighbor spatial search

I apologize to everyone for the hiatus – I realise a post is more than a little overdue and will try to be more regular in the future. I appreciate the support that I’ve received for the blog and continuing it. Consider the following problem: you’re starting a website for a chain of restaurants, and you…

7