Reverse Keyword Search for Spatio-Textual Top-kQueries in Location-Based Services

Reverse Keyword Search for Spatio-Textual Top-kQueries in Location-Based Services

Abstract— Reverse Keyword Search for Spatio-Textual Top-k Queries in Location-Based Services. 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-kresult set given a spatio- extual 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 applciations, 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-kqueries < Final Year Projects 2016 > RSTQ. It returns the keywords under which a target object will be a spatio-textual top-kresult. 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 RST Q 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.