Efficient Algorithms for Proportionality in Spatial Keyword Search

Abstract: Contextually enriched geolocation datasets are abundant in the web nowadays, with keyword-based queries being a useful tool to explore them. A proposed way to perform such queries, returning a k-subset of the available locations is by using spatial object summaries, while considering diversification and proportionality can yield a more representative result with respect to the query’s surroundings. In this degree project, efficient algorithmic approaches to the proportionality retrieval problem are studied. An approximate heuristic and as a pruning algorithm based on it are introduced to improve calculation of contextual proportionality scores, as well as a biased sampling approach that serves as an alternative to the previously proposed greedy framework for the problem. Experimental evaluation on queries generated from a real dataset reveals that both the approximate contextual proportionality score and biased sampling algorithm can possibly be used as alternatives to the previously studied methods.