Hierarchical Information Quadtree: Efficient Spatial Temporal Image Search for Multimedia Stream

Chengyuan Zhang, Ruipeng Chen, Lei Zhu, Anfeng Liu, Yunwu Lin, Fang Huang

Abstract

Massive amounts of multimedia data containing timestamps and geographical information are being generated at an unprecedented scale in many emerging applications, such as photo-sharing websites and social network applications. Due to their importance, a large body of work has focused on efficiently computing various spatial image queries. In this paper, we study the spatial temporal image query, which considers three important constraints during the search: time recency, spatial proximity, and visual relevance. We propose a novel index structure, namely the Hierarchical Information Quadtree (HI-Quadtree), to efficiently insert and delete spatial temporal images with high arrival rates. Based on HI-Quadtree, an efficient algorithm is developed to support spatial temporal image queries. Extensive experimentation with real spatial databases clearly demonstrates the efficiency of our methods.

Introduction

Every day, millions of images are uploaded to platforms like Flickr and Twitter. These images are enriched with metadata, specifically GPS coordinates and timestamps. When a user searches for "recent photos of a specific landmark that look like this query image," the system must perform a Top-$k$ Spatial Temporal Image Query. This requires balancing three distinct constraints:

  1. Spatial proximity: Geographic closeness to the query location.
  2. Temporal recency: How recently the image was captured.
  3. Visual relevance: Content matching based on visual features.

Existing search indexes typically handle spatial-textual or content-based retrieval separately. Attempting to integrate time into spatial indexes (e.g., 3D R-trees) often leads to performance degradation due to overlapping bounding boxes. The HI-Quadtree addresses the need for a unified, high-throughput index capable of handling rapid streaming data while answering complex 3D queries efficiently.

System Architecture and Methodology

The proposed Hierarchical Information Quadtree (HI-Quadtree) combines time-partitioning, space-partitioning, and content-indexing into a single architecture.

System Architecture of the HI-Quadtree framework, showing the flow from multimedia data streams to query interfaces.

The system consists of three primary components:

  • Temporal Segments: Incoming data is chunked into successive time windows. This allows for rapid insertion and expiration of streaming data by simply appending to active segments or dropping old ones.
  • Inverted Quadtree: Within each time segment, spatial data is organized using a Quadtree. Each node contains an inverted file of visual words (Bag-of-Visual-Words) for the images in that geographic sub-tree.
  • Best-First Search: A priority queue traverses the tree using a mathematical lower-bound metric, $MIND_{stv}$, to prune branches that cannot possibly contain a top-$k$ result.

Mathematical Formulation

To rank images, the system balances spatial, temporal, and visual factors using preference parameters ($\omega_1, \omega_2, \omega_3$). The notation used for these calculations is summarized below.

Notation and definitions for spatial-temporal-visual ranking components.

The $MIND_{stv}$ metric is mathematically guaranteed to be a lower bound, allowing the search algorithm to aggressively discard large portions of the database without missing relevant images.

Experimental Evaluation

The system was evaluated using a Flickr Landmark Dataset of over 1 million images. Key results include:

  • High Throughput: HI-Quadtree is nearly 4 times faster at inserting new images compared to 3D-Rtree baselines (STVI), making it ideal for high-velocity social media streams.
  • Query Efficiency: HI-Quadtree consistently outperformed baselines in query response time, maintaining a scalable growth curve even as the dataset size exceeded 1 million images.
  • Effective Pruning: The hybrid indexing approach allows the system to filter out spatially distant and visually irrelevant images simultaneously.

Conclusion

By decoupling time from space, the HI-Quadtree avoids the "Curse of Dimensionality" associated with high-dimensional spatial indexes. While currently relying on the Bag-of-Visual-Words model, future work could involve integrating dense neural embeddings to further enhance semantic retrieval while maintaining the efficiency of the Quadtree structure.

Summary updated

Abstract

Massive amount of multimedia data that contain times- tamps and geographical information are being generated at an unprecedented scale in many emerging applications such as photo sharing web site and social networks applications. Due to their importance, a large body of work has focused on efficiently computing various spatial image queries. In this paper,we study the spatial temporal image query which considers three important constraints during the search including time recency, spatial proximity and visual relevance. A novel index structure, namely Hierarchical Information Quadtree(\hiq), to efficiently insert/delete spatial temporal images with high arrive rates. Base on \hiq an efficient algorithm is developed to support spatial temporal image query. We show via extensive experimentation with real spatial databases clearly demonstrate the efficiency of our methods.
BibTeX
@article{zhang2019hierarchical,
  author = {Chengyuan Zhang and Ruipeng Chen and Lei Zhu and Anfeng Liu and Yunwu Lin and Fang Huang},
  title = {{Hierarchical Information Quadtree: Efficient Spatial Temporal Image Search for Multimedia Stream}},
  journal = {Multimedia Tools and Applications},
  year = {2019},
  url = {https://openreview.net/forum?id=nLyCrzirMo},
}
Figure