Hybrid Indexes for Spatial-Visual Search

Abstract

Due to the growth of geo-tagged images, recent web and mobile applications provide search capabilities for images that are similar to a given query image and simultaneously within a given geographical area. In this paper, we focus on designing index structures to expedite these spatial-visual searches. We start by baseline indexes that are straightforward extensions of the current popular spatial (R*-tree) and visual (LSH) index structures. Subsequently, we propose hybrid index structures that evaluate both spatial and visual features in tandem. A unique challenge of spatial-visual search is that there are inaccuracies in both spatial and visual features. Therefore, different traversals in the same index structures may produce different images as output, some of which are more relevant to the query than the others. We compare our hybrid structures with a set of baseline indexes in both performance and result accuracy using three real world datasets from Flickr, Google Street View, GeoUGV, and a large synthetic dataset. Our comprehensive experimental results demonstrate that our proposed hybrid indexes significantly outperform baselines.