Are there deduplication algorithms that do not work on a metric space?
One option is fingerprinting. If two objects have the same fingerprint, they are probably the same object. Depending the technique used, the fingerprint can not tell about approximate duplicates.