Voice search or 411-service is the task that finds a ranked set of directory listings that match a spoken query, where the target entries in the listing database and the spoken query may differ moderately in their syntactic form. While the conventional paradigm uses a two-box input (location + name), a single-box paradigm to voice search can allow users to provide all the information in a single utterance, thereby increasing query efficiency. Furthermore, the scalability of traditional methods used in the two-box paradigm is infeasible, and alternative strategies that sacrifice accuracy are normally adopted. This work presents a scalable algorithm for directory search over a nationwide database of listings (millions of entries) without compromising recognition accuracy.