[jamra]

Yes that makes it supremely clearer. I also found a FastSS implementation, which uses the same d-deletion neighborhood. Here it is: http://fastss.csg.uzh.ch

I am looking at a python implementation for examples.

[lorenzhs]

nice, that seems to be based upon a similar idea as the paper I mentioned (but earlier and less refined).

[jamra]

The paper you mentioned reduces memory consumption hugely and averages out the query and insertion time. It's a good improvement.