Abstract
Modern location-based services increasingly rely on Regions-of-Interest (ROIs) rather than simple point data. Finding ROIs that are similar to a query in both spatial extent and textual description is a computationally intensive task. This paper introduces SEAL (Spatio-tExtuAl simiLarity search), a framework that utilizes hybrid signature-based filtering to prune the search space across both dimensions simultaneously. Experimental results demonstrate that SEAL outperforms state-of-the-art methods by several orders of magnitude.
Introduction
Traditional spatial search often focuses on point-to-point proximity. However, many real-world entities—such as neighborhood "active areas" or wildlife habitats—are better represented as regions with associated textual tags. The core challenge addressed by SEAL is the efficient retrieval of ROIs that share significant spatial overlap (measured by Jaccard similarity) and textual relevance (measured by weighted Jaccard similarity) with a query ROI.
As shown in the figure above, objects $o_1$ through $o_7$ are defined by spatial regions $R_1$ to $R_7$ and sets of textual tokens. A query $q$ consists of a target region $R_q$ and a set of keywords. Calculating similarities across millions of such complex shapes and thousands of keywords is a bottleneck for standard indexing techniques like R-trees.
Methodology: The SEAL Framework
SEAL employs a filter-and-verification framework designed to minimize the number of expensive exact similarity calculations.
Hybrid Signature-Based Filtering
The "secret sauce" of SEAL is its hybrid signature. Instead of filtering by text and then space (or vice versa), SEAL hashes tokens and grid cells into a unified signature. This allows for aggressive pruning in both dimensions simultaneously.
Adaptive Grid Selection
The effectiveness of spatial filtering depends heavily on grid granularity. Coarse grids lead to poor filtering (false positives), while overly fine grids increase index size and processing overhead. SEAL addresses this "Goldilocks problem" using a probabilistic cost model and a Grid Tree.
The Grid Tree (shown above) allows the system to automatically determine the optimal grid level ($G^0, G^1, G^2$) for a given dataset, balancing filtering power against index efficiency.
Threshold-Aware Pruning
SEAL utilizes user-defined similarity thresholds ($\tau_R$ for spatial and $\tau_T$ for textual) to skip objects in inverted lists that cannot mathematically meet the criteria. By maintaining upper bounds on similarity, the algorithm avoids processing irrelevant candidates.
Evaluation and Results
The researchers evaluated SEAL using a Twitter dataset (1 million users) and a synthetic USA dataset (1 million objects).
- Performance: SEAL demonstrated significant speedups, often running tens of times faster than IR-trees. For instance, on the Twitter dataset, SEAL processed queries in approximately 5ms, compared to 253ms for the IR-tree baseline.
- Scalability: The system scales sub-linearly with the number of objects, making it suitable for massive, real-world datasets.
- Filtering Efficiency: The hybrid approach consistently produced smaller candidate sets for the final verification step than single-dimension filters.
Discussion and Future Work
A key insight from this work is the importance of incorporating Inverse Document Frequency (IDF) weights, ensuring that rare, highly descriptive keywords contribute more to the similarity score than common terms.
While highly efficient, SEAL leaves room for future exploration. Current models represent user locations as single Minimum Bounding Rectangles (MBRs); future iterations could model "active regions" as clusters of smaller shapes. Additionally, moving beyond weighted Jaccard similarity to semantic models like word embeddings could further enhance textual relevance.
Summary updated