Efficient indexing and querying of geo-tagged mobile videos

We are witnessing a significant growth in the number of smartphone users and advances in phone sensor technology. More recently, driven by the advances in control engineering, material science and sensor technologies, drones are becoming significantly prevalent in daily life (e.g., event coverage, tourism). Consequently, an unprecedented number of both smartphone videos (i.e., ground videos) and drone videos (i.e., aerial videos) are generated and consumed by public users. In such a large repository, it is difficult to index and search the mobile videos in an unstructured form. Content-based and tag-annotation-based video management suffer from the efficiency and scalability problems. However, due to the rich sensor instrumentations in smartphones and drones, both ground videos and aerial videos can be geo-tagged (e.g., GPS locations and compass directions) at the acquisition time, providing an opportunity for efficient management of aerial videos by exploiting their corresponding spatial structures. Ideally, each ground (aerial) video frame can be tagged by the spatial extent of its coverage area, termed ground Field-Of-View (i.e., ground-FOV, aerial-FOV for aerial videos). This provides an opportunity for efficient management of mobile videos by exploiting their corresponding geo-metadata. ❧ My thesis tackles the challenges of large-scale mobile video data management using spatial indexing and querying of their corresponding FOVs. Unlike the traditional spatial objects (e.g., points and rectangles), ground-FOVs are shaped similar to slices of pie and contain both location and orientation information, and aerial-FOVs are shaped in irregular quadrilaterals. Therefore, conventional spatial indexes, such as R-tree, cannot index them efficiently. Additionally, the distribution of user-generated mobile videos is non-uniform (e.g., more FOVs in popular locations). Consequently, even multilevel grid-based indexes have limitations in managing the skewed distribution. Moreover, since user-generated mobile videos are usually captured in a casual way with diverse setups and movements, no a priori assumption can be made to condense them in an index structure. ❧ To overcome the challenges, I propose a class of new index structures called OR-trees and a new index structure called TetraR-tree for efficiently indexing ground and aerial videos, respectively. The key idea of both index structures is that maximally harnessing the corresponding geographical properties of ground-FOVs and aerial-FOVs. OR-trees effectively harness ground-FOVs’ camera locations and orientations, by taking both of them into consideration during index construction to optimize the combination of location closeness and orientation proximity. TetraR-tree effectively captures the geometric property of quadrilaterals by indexing their four corner points. Based on the proposed indexes, I present novel search strategies and algorithms for efficient spatial queries on ground and aerial videos. Experiments using both real-world and large synthetic datasets (over 30 years’ worth of videos) demonstrate the scalability and efficiency of the proposed indexes and search algorithms.