<p>I need to implement some kind of metric space search in Postgres(*) (PL or PL/Python). So, I'm looking for good sources (or papers) with a very clear and crisp explanation of the machinery behind these ideas, in such way that I can implement it myself.</p>

<p>I would prefer clarity over efficiency.</p>

<p>(*) The need for that is described better <a href="https://stackoverflow.com/questions/122990/how-to-determine-if-a-record-in-every-source-represents-the-same-person">here</a>.</p>

Especially for geographical data, look at
PostGIS
first to see if you need to implement anything. If you do, start with the papers listed in the
Wikipedia entry on GiST
.
Looking at your link, it seems your metric space is strings with some sort of edit distance as the metric. A nice but oldish overview of some solutions is given by
Navarro, Baeza-Yates, Sutinen, and Tarhio, IEEE Data Engineering Bulletin, 2001
; the related papers on Citeseer could also be useful.
Locality Sensitive Hashing
is a newer technique that might be useful, but a lot of the papers are heavy on math.