Yes, it is possible. Postgres supports custom data types and operators on those data types, and (using the GiST subsystem) you can create indexes using those custom operators.

Unfortunately, there is a caveat: this will more than likely require writing custom C code. I've never tried to implement GiST indexing for a new data type, so I don't know just how much effort would be required.

What kind of distances did you have in mind?

We have a table which essentially represents a shallow graph (rows in the table can have links to to one or more other rows in the table). It would probably be interesting if we could define a distance metric in terms of those links: "find all rows reachable in 3 links from this starting row".

This probably isn't ideally done by this sort of index, as it would be a pretty weird sort of distance metric, if it's even a valid one (most rows aren't connected, meaning the "distance" between most rows would be infinite, and our query would really be "WHERE distance < infinity"). But it's good to know there's some kind of support for it!

Ah, right. For the kNN/GiST support in Postgres, distance has to be defined in such a way that it is computable given only two data values; furthermore, I'm pretty sure it has to be both symmetric and satisfy the triangle inequality in order for the index to produce correct results.