Users often search spatial databases like yellow page data

using keywords to find businesses near their current loca-

tion. Such searches are increasingly being performed from

mobile devices. Typing the entire query is cumbersome and

prone to errors, especially from mobile phones. We address

this problem by introducing type-ahead search functional-

ity on spatial databases. Like keyword search on spatial

data, type-ahead search needs to be location-aware, i.e.,

with every letter being typed, it needs to return spatial ob-

jects whose names (or descriptions) are valid completions

of the query string typed so far, and which rank highest in

terms of proximity to the user's location and other static

scores. Existing solutions for type-ahead search cannot be

used directly as they are not location-aware. We show that a

straight-forward combination of existing techniques for per-

forming type-ahead search with those for performing prox-

imity search perform poorly. We propose a formal model

for query processing cost and develop novel techniques that

optimize that cost. Our empirical evaluations on real and

synthetic datasets demonstrate the effectiveness of our tech-

niques. To the best of our knowledge, this is the first work

on location-aware type-ahead search.

PDF file

In  ACM SIGMOD Conference

Details