EUVIMEDObjevte EUVIMED
Open access · CC BY 4.0

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

Yiyang Bian, Yongyi Liu, Amr Magdy

ACM Transactions on Spatial Algorithms and Systems · 2026-12-31 · 12 (4) · 1-38

DOI: 10.1145/3849802 ↗

At a glance

Journal article in ACM Transactions on Spatial Algorithms and Systems, published online on 2026-10-29. Written by Yiyang Bian and 2 co-authors. 58 references. The full text is freely available (open access, CC BY 4.0). Funded by: Division of Information and Intelligent Systems, Google, Microsoft Research.

AbstraktBibliografické údajeCiteRelated studies

Abstract (original language)

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.

Funding

  • Division of Information and Intelligent Systems
  • Google
  • Microsoft Research

Cite

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}
}
Start for free →