Reddit mentions of Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics)

Yeah, the point quad tree splits at a single point, whereas the kD tree split along one axis, and then makes two independent splits in the sub-trees (which usually won't end up splitting at the same location, and depending on the exact implementation may even split along the same axis again).

This book is amazing: http://www.amazon.com/Foundations-Multidimensional-Structures-Kaufmann-Computer/dp/0123694469/ref=sr_1_1?ie=UTF8&qid=1373259783&sr=8-1

There's approximately 10x more spatial data structures, and variations thereof, then you can even imagine, and that book covers basically all of them.

Very nice ELI5 for R-trees and such. Can someone suggest a good book to dig deeper, like algorithm to query points in the R-tree given a bounding box when the bounding box spans more than one R-tree 'partition' box?

Cursory search reveals Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics). Can anyone recommend that book or suggest a better one for wanting to finally learn to code up, say, an R-tree or a BSP tree?

I have to say linux profiling has seemed to me to be a fast-moving target, meaning you'll get scattered results if you search. But, there's this which seems up-to-date: http://en.wikipedia.org/wiki/Perf_%28Linux%29

Then there's Ulrich Drepper's 'What every programmer should know about memory' (long series, but worth skimming at least, if your code is memory intensive. At least read about cache-coherency and cache-lines): http://lwn.net/Articles/250967

But the biggest thing is to get the algorithms right. Sounds like you want image-processing books. Also, GPUs are just absolutely the right place to do this stuff, and there are probably libraries already out there for it; speaking of which, did you know about OpenCV? It even has some stuff implemented on the GPU (as CUDA). I root for OpenCL, but the fact is, almost everything out there, libraries, and books, is written for CUDA.

> All the software is written in C++: I am interested in unlearning bad habits and writing better and easier to maintain code.

I suggest Effective C++ if you haven't read it yet. Also, Herb Sutter's 'Exceptional C++' series (a 'digest' version is C++ Coding Standards: 101 Rules, Guidelines, and Best Practices).

Never read it myself, but I hear 'Code Complete' is good. Maybe, too, Martin Fowler's Refactoring book - it shows lots of little awkward, problematic patterns and what to do about them, with good discussion. Each cleanly separated out - it will refer back and forth, but you can read the bits one-at-a-time. Good bathroom reading :)

Re: algorithms: Ugh, I don't know. It sounds like you'll want some metric data structures, dealing with space as you do. There's http://www.amazon.com/Foundations-Multidimensional-Structures-Kaufmann-Computer/dp/0123694469, and I don't know what else, maybe some Knuth? But probably, you should learn undergraduate-level data structures and algorithms, Big O stuff. Any used CS Data Structures + Algorithms book should help with that.

Do not fear spending money, as a former boss said, "books are free" ie they pay for themselves if they save you an hour's debugging later. Good luck!