Answering Why-Not Questions on Top- <i>k</i> Social Image Search Services

Social images shared on social media are often associated with geo-tagged information and text descriptions. Given a set of keywords and a spatial location, geo-tagged social image search can retrieve top-k image objects that best match query parameters in terms of spatial distance and tag similarity of social images. However, due to improper parameter settings, users may notice that some expected images are missing and wonder why these objects do not appear in the query results. This paper studies the why-not top-k social image search question and proposes efficient query refinement algorithms, aiming to minimally modify users' initial queries to reintroduce missing objects. We first develop a baseline algorithm that traverses each possible query parameter sequentially to find the best refinement parameters. Then, we propose a fast search algorithm with two optimization strategies named lower ranking nodes pruning and early stop pruning, which can improve performance by quickly removing low-ranking social images. In addition, we propose an efficient boundary search algorithm that can determine the ranking of missing images at a low time cost. We also extend the proposed techniques to handle multiple missing images. Extensive experimental results demonstrate that the proposed solution is two orders of magnitude faster than baseline and is effective in a wide range of settings.