Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency

Senjuti Basu Roy and Kaushik Chakrabarti

Abstract

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.

Details

Publication typeInproceedings
Published inACM SIGMOD Conference
> Publications > Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency