After so much debate, I have concluded that @Bram and @Ktimesg were right; prefix search does not offer a statistically significant improvement.

https://bitcointalk.org/index.php?topic=5539190