A Fast Algorithm for Online Multiple Name Searching

G. Ruibin, and K.Y.T. Chan (Singapore)


Information Systems and the Internet, Name Searching, Multiple Name Searching, Phonetic String Searching


Phonetic name searching is used to retrieve name strings that may have similar pronunciation, regardless of their actual spelling. In this paper, we propose a fast online name searching algorithm. It can be realized by using bit parallelism simulation of Non-Deterministic Finite Automata in linear time. The algorithm can be easily extended to a multiple version, which is able to search multiple name strings simultaneously and accelerate the overall processing speed dramatically. Our experiments demonstrate that it is very effective with English surnames, and its multiple version achieves three to five times speedup compared with a sequential searching procedure.

Important Links:

Go Back