Bed-tree: an all-purpose index structure for string similarity search based on edit distance.

Zhenjie Zhang, Marios Hadjieleftheriou, Beng Chin Ooi, Divesh Srivastava

Browse the full SIGMOD paper archive.