Re: [HACKERS] How to implement a SP-GiST index as a extension module? - Mailing list pgsql-hackers

On Mon, Nov 13, 2017 at 2:09 AM, Alexander Korotkov <a.korotkov@postgrespro.ru> wrote:

Hi!

On Mon, Nov 13, 2017 at 6:47 AM, Connor Wolf <connorw@imaginaryindustries.com> wrote:

Ok, I've managed to get my custom index working. 

 

Good!

It's all on github here: https://github.com/fake-name/pg-spgist_hamming, if anyone else needs a fuzzy-image searching system 

that can integrate into postgresql..

It should be a pretty good basis for anyone else to use if they want to implement a SP-GiST index too. 

I took a look at the code, and I feel myself a bit confused :)

It appears that you're indexing int8 values.  That seems like unrealistic short representation for image signature.

It is a int8, and nope, it's a surprisingly robust and functional signature. There's a document describing the hashing mechanism here:

http://www.hackerfactor.com/blog/?/archives/432-Looks-Like-It.html

Functionally, the procedure is relatively simple:

• Convert to greyscale
• Resize to intermediate resolution (32x32 is common)
• Perform DCT on 32x32 image.
• Crop 32x32 image to 8x8 by throwing away the high-frequency components
• Threshold the 8x8 image by it's average
• Serialize the 64 binary values into a int8

In my case, the actual implementation is here: https://github.com/fake-name/IntraArchiveDeduplicator/blob/master/scanner/hashFile.py#L95-L102

 

Also, name of repository make me think that hamming distance would be used to compare signatures.  But after look at the code, I see that plain absolute value of difference is used for that purpose.

static double

getDistance(Datum v1, Datum v2)

{

    int64_t a1 = DatumGetInt64(v1);

    int64_t a2 = DatumGetInt64(v2);

    int64_t diff = Abs(a1 - a2);

    fprintf_to_ereport("getDistance %ld <-> %ld : %ld", a1, a2, diff);

    return diff;

}

For such notion of distance, you don't need a VP-tree or another complex indexing.  B-tree is quite enough in this case.  Alternatively, distance function is not what it meant to be.

You're looking in the wrong place. 

https://github.com/fake-name/pg-spgist_hamming/tree/master/vptree is the code you sent me, with some simplification to make it only work on single integers. Basically,

before I started on my own stuff, I wanted to make sure I could at least implement a functional index using a much more basic structure.

https://github.com/fake-name/pg-spgist_hamming/tree/master/bktree is the actual BK-tree index, and it does indeed use hamming distance for the search metric:

static int64_t

f_hamming(int64_t a_int, int64_t b_int)

{

/*

Compute number of bits that are not common between `a` and `b`.

return value is a plain integer

*/

uint64_t x = (a_int ^ b_int);

uint64_t ret = __builtin_popcountll (x);

return ret;

}

(see https://github.com/fake-name/pg-spgist_hamming/blob/master/bktree/bktree.c#L38-L58).

 

It would be useful if you provide complete usage example of this extension: from image to signature conversion to search queries. 

Actual usage is done with this project: https://github.com/fake-name/IntraArchiveDeduplicator, which

also has the older in-memory BK tree I've implemented, and it's actually used here. 

I also have unit tests that sit on top of this here (see all the files that are named "Test_db_BKTree...".