Author_Institution :
Shanghai Key Lab. of Multidimensional Inf. Process., East China Normal Univ., Shanghai, China
Abstract :
Spatio-textual queries retrieve the most similar objects with respect to a given location and a keyword set. Existing studies mainly focus on how to efficiently find the top-k result set given a spatio-textual query. Nevertheless, in many application scenarios, users cannot precisely formulate their keywords and instead prefer to choose them from some candidate keyword sets. Moreover, in information browsing applications, it is useful to highlight the objects with the tags (keywords) under which the objects have high rankings. Driven by these applications, we propose a novel query paradigm, namely reverse keyword search for spatio-textual top-k queries (RSTQ). It returns the keywords under which a target object will be a spatio-textual top-k result. To efficiently process the new query, we devise a novel hybrid index KcR-tree to store and summarize the spatial and textual information of objects. By accessing the high-level nodes of KcR-tree, we can estimate the rankings of the target object without accessing the actual objects. To further improve the performance, we propose three query optimization techniques, i.e., KcR*-tree, lazy upper-bound updating, and keyword set filtering. We also extend RSTQ to allow the input location to be a spatial region instead of a point. Extensive experimental evaluation demonstrates the efficiency of our proposed query techniques in terms of both the computational cost and I/O cost.
Keywords :
database indexing; query processing; tree data structures; I/O cost; RSTQ; computational cost; high-level nodes; hybrid index KcR-tree; information browsing applications; keyword set filtering; lazy upper-bound updating; location-based services; query optimization techniques; query paradigm; reverse keyword search; spatial information; spatial region; spatio-textual top-k queries; target object rankings; textual information; Estimation; Indexes; Keyword search; Mobile radio mobility management; Query processing; Tagging; Upper bound; Location-based Services; Reverse Queries; Reverse queries; Spatio-Textual Queries; Top-k Queries; location-based services; spatio-textual queries; top-k queries;