HQT-TI: An Efficient Hilbert Curve Based Index for Spatial Keyword Queries

This paper introduces HQT-TI, a novel indexing method designed to improve the efficiency of spatial keyword queries. HQT-TI consists of two main components: a Hilbert QuadTree (HQT) based spatial index and a Trie-Inverted index (TI) combined textual index. HQT integrates the Hilbert curve with a Quadtree, establishing a direct relationship between the two. TI combines a trie and inverted index to minimize the intersection cost associated with long lists, thus improving the speed of keyword queries. The HQT based Spatial Query algorithm (HQT-SQ) reduces overlap checks and limits irrelevant object retrieval by employing query drill-down and depth first search with limited breadth expansion in spatial queries. Meanwhile, the Segment List Intersection based Keyword Query algorithm (SLI-KQ), built on TI, efficiently handles segment list intersections for keyword queries. The combination of HQT-SQ and SLI-KQ results in HS-SK, a highly efficient spatial keyword query algorithm. Extensive experimental results demonstrate that HS-SKQ outperforms SFC-Quad by up to two orders of magnitude, achieving up to a 5.46× speedup over the best existing competitors, making it a promising solution for large-scale spatial keyword query processing.