Batch-Enhanced kNN Spatial-Keyword Queries Supporting Negative Keyword Predicates

The rapid growth of spatio-textual data has driven the need for efficient query processing frameworks to support spatial-keyword queries. Among these, the k-Nearest Neighbor (kNN) spatial-keyword query, which retrieves the top-k objects based on both spatial and textual proximity, is fundamental and widely used. However, existing kNN query frameworks lack support for negative keyword predicates, such as retrieving tweets containing Chipotle but not Chipotle sauce . Additionally, they require specialized indexing structures for different types of kNN queries, limiting their generality. To address these challenges, we propose U-ASK , a unified architecture for spatial-keyword queries supporting negative keyword predicates. U-ASK includes an indexing framework named TEQ (Textual-Enhanced Quadtree) and a query processor POWER ( P arallel b o ttom-up search w ith incr e mental p r uning) that handles various forms of kNN spatial keyword queries with negative keyword predicates. To further enhance the query processing performance, we propose two novel spatio-textual grouping strategies to categorize individual queries into different query batches to be processed collectively according to their similarities. Based on this, we introduce BPOWER (Batch-Enhanced POWER), which identifies shared access patterns across batched queries and minimizes redundant I/O operations, significantly reducing latency. The experimental evaluation on real tweet datasets demonstrates up to 80 × faster runtime compared to the state-of-the-art algorithms, and the batch-enhanced POWER achieved 4 × faster compared to our original POWER query processor.