This thesis focuses primarily on constructing voice-only pedestrian guidance systems using spatial database techniques. In the process of doing this we first explored how to use authoring tools to build natural language interfaces over large databases. Specifically we built a natural language interface over the MusicBrainz database of 1.5GB and confronted the resulting scalability issues. We then explored vague querying, specifically spatial queries using `near'. Assuming `language as a set of conventions', we proposed an approach for handling vagueness by defining contexts that are compiled to crisp SQL view definitions. In our recent work, as partners in the Spacebook project (http://www.spacebook-project.eu), we have focused on how to build reliable, scalable and extensible text-to-speech (TTS) based navigation systems for pedestrians. Technical aspects we have worked on include building the system Janus (http://janus-system.eu), with sensor reports and bidirectional voice channels. Experimental work has been mostly focused on measuring accuracies and latencies with available hardware. We have also, very recently, started human usability experiments. Our theoretical work has been in defining models for how a system can interact with pedestrians over high latency data links with poor GPS quality using prediction of pedestrian positions and scheduling utterances to mask latencies. To allow for scalable deployment, we have only used standard smart phones and inexpensive servers.