Константин Елисеев, если честно я не очень понимаю что Вы ждете в ответ.
Общее направление для поиска?
1) Готовимся. Решаем вопросы: будет ли поиск по какому-то конкретному городу или это будет сервис на всю страну. Как решать проблемы приоритетов (например улицу Ленина человек ввел)? Будет ли поиск связан с геолокацией? Делаем прототипы и пытаемся на пальцах понять как это должно работать (нужно именно делать, а не копировать с вышеупомянутых сервисов)
2) На вопросы отвечено, прототип готов, а значит можно уходить в верстку. Отображаем "демо-данные", для этого копаем в сторону JS + HTML + CSS
3) Далее нужно напонять это данными, а для этого нужно уже копать в сторону какого-нибудь полнотекстового поиска (FTS Mysql, Sphinx, Solr, Lucene)
Если pet-проект на 10-20 человек онлайна, то можно просто сделать одну таблицу, куда в спец. поле заносить данные и повесить на нее full-text index. Благо Вадим на Битрикс24.Идея про него много рассказывал (есть запись доклада).