первый вариант, грузите улицы/города и прочее из базы во время построения страницы в массивы js, затем при вводе букв ищете по ним, второй вариант, ajax запросы к серверу с динамической генерацией запроса к базе. первый вариант работает быстро и снижает нагрузку на сервак, но если улиц и прочих данных много, могут получится очень большие массивы и увеличиться нагрузка на браузер, третий вариант мне нравиться больше всего, хотя насчет его кроссбраузерности есть некоторые сомнения. Вкуриваете в HTML5->AppCache, HTML5->Хранилище Web, HTML5->Web Workers, почитать обо всем этом можно здесь
http://www[dot]intuit[dot]ru/department/[dot][dot][dot]ass/free/status/ данные технологии позволят исключить сервер из обработки данных, не перегружать код ненужными массивами больших размеров и снизить нагрузку на сам браузер