Batch-Enhanced kNN Spatial-Keyword Queries Supporting Negative Keyword Predicates
ACM Transactions on Spatial Algorithms and Systems · 31.12.2026 · 12 (4) · 1-38
DOI: 10.1145/3849802 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Spatial Algorithms and Systems, online erschienen am 29.10.2026. Verfasst von Yiyang Bian und 2 weiteren Autor:innen. Die Arbeit nennt 58 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Division of Information and Intelligent Systems, Google, Microsoft Research.
Abstract (Originalsprache)
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 with the state-of-the-art algorithms, and the batch-enhanced POWER achieved 4× faster compared with our original POWER query processor.
Förderung
- Division of Information and Intelligent Systems
- Microsoft Research
Zitieren
APA
Bian, Y., Liu, Y., & Magdy, A. (2026). Batch-Enhanced kNN Spatial-Keyword Queries Supporting Negative Keyword Predicates. ACM Transactions on Spatial Algorithms and Systems, 12(4), 1-38. https://doi.org/10.1145/3849802
Vancouver
Bian Y, Liu Y, Magdy A. Batch-Enhanced kNN Spatial-Keyword Queries Supporting Negative Keyword Predicates. ACM Transactions on Spatial Algorithms and Systems. 2026;12(4):1-38. doi:10.1145/3849802
BibTeX
@article{Bian2026,
author = {Bian, Yiyang and Liu, Yongyi and Magdy, Amr},
title = {Batch-Enhanced kNN Spatial-Keyword Queries Supporting Negative Keyword Predicates},
journal = {ACM Transactions on Spatial Algorithms and Systems},
year = {2026},
volume = {12},
number = {4},
pages = {1--38},
doi = {10.1145/3849802}
}
EUVIMED