Location-aware type ahead search on spatial databases: Semantics and efficiency

Senjuti Basu Roy, Kaushik Chakrabarti

Research output: Chapter in Book/Report/Conference proceedingConference contribution

43 Scopus citations

Abstract

Users often search spatial databases like yellow page data using keywords to find businesses near their current location. Typing the entire query is cumbersome and prone to errors, especially from mobile phones. We address this problem by introducing type-ahead search functionality 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 objects 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 performing type-ahead search with those for performing proximity 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 techniques. To the best of our knowledge, this is the first work on location-aware type-ahead search.

Original languageEnglish (US)
Title of host publicationProceedings of SIGMOD 2011 and PODS 2011
Pages361-372
Number of pages12
DOIs
StatePublished - Jul 11 2011
Externally publishedYes
Event2011 ACM SIGMOD and 30th PODS 2011 Conference - Athens, Greece
Duration: Jun 12 2011Jun 16 2011

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078

Other

Other2011 ACM SIGMOD and 30th PODS 2011 Conference
Country/TerritoryGreece
CityAthens
Period6/12/116/16/11

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems

Keywords

  • type ahead search

Fingerprint

Dive into the research topics of 'Location-aware type ahead search on spatial databases: Semantics and efficiency'. Together they form a unique fingerprint.

Cite this