Shadow: Answering Why-Not Questions on Top-K Spatial Keyword Queries over Moving Objects

The popularity of mobile terminals has generated massive moving objects with spatio-textual characteristics. A top-k spatial keyword query over moving objects (Top-k SKM query) returns the top-k objects, moving or static, based on a ranking function that considers spatial distance and textual similarity between the query and objects. To the best of our knowledge, there hasn’t been any research into the why-not questions on Top-k SKM queries. Aiming at this kind of why-not questions, a two-level index called Shadow and a three-phase query refinement approach based on Shadow are proposed. The first phase is to generate some promising refined queries with different query requirements and filter those unpromising refined queries before executing any promising refined queries. The second phase is to reduce the irrelevant search space in the level 1 of Shadow as much as possible based on the spatial filtering technique, so as to obtain the promising static objects, and to capture promising moving objects in the level 2 of Shadow as fast as possible based on the probability filtering technique. The third phase is to determine which promising refined query will be returned to the user. Finally, a series of experiments are conducted on three datasets to verify the feasibility of our method.