Region-Grounded Query Expansion for Spatial Keyword Search

People searching for places rarely use the words a map database uses. Someone asks for "somewhere to fix a leaky pipe near the old library." The database lists a "plumbing contractor" three blocks from a building tagged "municipal archive." Spatial keyword indices are tree structures that store, in every internal node, both a bounding box and a summary of the words found below it. That lets them discard whole regions that fail either the location test or the word test. They are fast because the word test is exact, and the same exactness makes them return nothing when the vocabularies differ. The usual fix is to expand the query with synonyms or language-model rewrites. It works badly here. Every added keyword widens the set of tree branches the search must explore. On a clue-based spatial benchmark, thesaurus expansion made results slightly less accurate and noticeably slower (Clue-based Spatio-textual Query).

We propose to choose expansion terms from the index's own vocabulary, restricted to the region the query is about. A language model first splits a nested request into a location sub-goal and descriptive sub-goals. The location sub-goal is resolved first and produces a geometric envelope. The index then reports which words actually occur in the tree nodes overlapping that envelope, and how often. The user's phrase is matched only against this small local vocabulary, under a budget on how many index entries the chosen terms will touch. Expansion therefore cannot drift to words that exist nowhere nearby, cannot grow without limit, and has a cost known before execution. It also gives an immediate signal when the model has invented a sub-goal: if nothing in the region resembles the descriptive phrase, that sub-goal is sent back to the planner instead of being run as a full search that returns nothing.

Core Claim

Expansion that is conditioned on the region and limited by a budget is the right interface between query rewriting and spatial keyword indices. On queries with vocabulary mismatch, it should recover most of the accuracy of dense semantic retrieval while keeping the node-pruning behavior of exact spatial keyword indices. For the same number of added terms, it should beat expansion drawn from the whole vocabulary on both accuracy and latency. The new element is not decomposition, and not semantic matching by itself. It is that the expansion step reads and is limited by the index's per-node word statistics inside a region the decomposition has already fixed.

Relation to Prior Work

Prior work falls into three groups, each playing a different role here.

Indices we build on. Hybrid indices place spatial bounds and word summaries in the same tree nodes. Examples are the inverted-file quad-tree (Chen et al.), the Rt-tree with representative keyword sets per node (Li et al.), and the learned, workload-aware WISK (Sheng et al.). The motivation for joint pruning comes from the sequential-filtering blow-up described by Ahmad et al. and Lu et al.. These indices supply our physical layer. All of them treat the query as a flat point-plus-keywords tuple matched exactly, and that is the assumption we relax.

Closest attempts at the vocabulary gap. - QDR-Tree (Zang et al.) clusters the dataset's own keywords and copies boundary keywords into neighboring clusters. It never sees words outside the dataset's vocabulary, which are exactly the words users bring. - TASK (Luo et al.) tolerates spelling errors over road networks, which is surface mismatch rather than meaning mismatch. - Tao et al. build a static geoscience ontology linking jargon to places, with no index-level pruning and no handling of nested queries.

Results that constrain the design. The negative thesaurus result above, together with the observation that adding semantic models to spatial keyword engines added noise and hurt precision (Li et al.), rules out open-ended expansion. A 12-index benchmark (Chen et al.) shows that index cost is highly sensitive to keyword count, and that no single index dominates. That is why our budget is expressed in index cost rather than term count, and why the method sits above the index rather than inside one design.

Methods we reuse in the decomposition and rewriting layer. - RoHT (Zhang et al.) builds a decomposition tree with a scheduler that answers a node directly when a backend can, and otherwise falls back. It reaches 46.45 exact match on KQA Pro against TransferNet's 16.80. We reuse the scheduler idea, but our "can this backend answer it" test is a cheap lookup in the local vocabulary rather than a semantic parser. - PLUTO (Huang et al.) pairs plan-and-retrieve decomposition with offline rewriting of tool documentation. On ToolBench this raised Contriever recall from 31.78% to 46.57%. It is the closest combination of decomposition and vocabulary-gap repair, but it has no spatial primitives and no pruning index. - InteR (Feng et al.) alternates language-model expansion with retrieval, reaching 50.0 MAP on TREC DL 2019 against 30.1 for BM25. MINDER (Li et al.) constrains generation to strings that exist in an FM-index, a compressed full-text index that only admits strings present in the corpus. MINDER is the conceptual ancestor of our "only words that exist" rule. We apply that rule locally per region, and with a cost bound, rather than globally.

Research Program

The system has three parts.

The planner. A language-model planner turns a request into a small tree. Its leaves are either location sub-goals ("the library holding 18th-century manuscripts," "within 2 miles of it") or descriptive sub-goals ("somewhere to fix a pipe"). Location sub-goals are resolved first, using the same index with exact or region-grounded matching on the anchor's description. Each one compiles into a bounding envelope $R$.

The index. We use an IR-tree-style hybrid index, augmented so that each internal node stores a frequency table of the terms in its subtree, in the manner of the Rt-tree. For an envelope $R$, we take the frontier $F$, meaning the nodes at a chosen depth whose bounding boxes intersect $R$. This frontier yields a local vocabulary $V(F)$, and for each term $t$ a count $c_F(t)$ of matching entries under $F$.

The selection step. For a descriptive phrase $u$, we choose expansion terms by

$$S^* = \arg\max_{S \subseteq V(F)} \sum_{t \in S} \mathrm{sim}(u,t) \quad \text{subject to} \quad \sum_{t \in S} c_F(t) \le B,$$

where $\mathrm{sim}$ is a frozen text encoder's similarity between the phrase and the term, and $B$ is a budget on index entries touched. This is a knapsack problem, which we solve greedily by similarity-per-cost. If no term clears a similarity floor, the sub-goal is returned to the planner with the top local terms as hints. This is the feedback loop that targets hallucinated sub-goals.

The chosen terms then drive ordinary simultaneous pruning inside $R$, with no change to the index's traversal code. We will analyze two things. The first is how frontier depth trades the cost of reading vocabulary against selectivity. The second is whether $B$ can be set from the node counts alone so that latency stays within a fixed factor of the exact-match query.

Baselines

Do nothing. The naive reference is the same hybrid index with exact keyword matching on the user's words. It shows how much recall is lost to the vocabulary gap, and it sets the latency floor.

Thesaurus expansion. We run WordNet-style synonym expansion into the same index, matching the setting where Liu et al. reported slightly lower accuracy and notably higher latency. That paper gives no exact figure, so we will reproduce the comparison on their Beijing POI data.

Unconstrained rewriting. An InteR-style loop with two rounds of language-model rewriting, the iteration count Feng et al. found best, feeds its keywords into the same index. Combined with our planner, this becomes the two-stage pipeline a reviewer would build first.

Dense retrieval with a spatial filter. We expect this to be the strongest competitor on accuracy. POI names, tags and descriptions are embedded with the same encoder our method uses for $\mathrm{sim}$. The baseline runs in two variants. In post-filtering, every POI inside $R$ is scored by brute force. In pre-filtering, approximate nearest-neighbor search is followed by a distance check.

Workload-aware learned index. WISK serves as the fastest exact backend. Sheng et al. report up to 8x speedup over CDIR-Tree and Flood-T on Foursquare, OpenStreetMap and SLIPO. We include it to test whether our expansion transfers to a learned index whose partitions assume a stable query vocabulary.

Fairness rules. All methods share data, encoder, language model, number of planner calls, and a single tuning budget on a validation split. I found no result on Lacuna for semantic, vocabulary-mismatched spatial keyword retrieval, so there is no published number to beat. Beating a baseline therefore means two things on our held-out queries. Against the dense post-filter, we must match or exceed its recall@10 while being at least several times faster on large envelopes. Against unconstrained rewriting, we must exceed its recall at lower latency.

Ablations. - Global grounding. Choose the same number of terms from the full index vocabulary rather than $V(F)$. This isolates the region conditioning. - No budget. This isolates cost control. - No planner feedback. This isolates the hallucination check.

Why not just…?

Why not just decompose with a language model, rewrite the keywords, and send them to QDR-Tree or WISK? This is our unconstrained-rewriting baseline. The evidence against it is indirect but consistent. Index cost rises steeply with keyword count (Chen et al.). Semantic additions have added noise in spatial engines (Li et al.). A rewriter cannot know which of its words exist near the anchor. Our experiments measure this directly through the number of rewritten terms that match zero entries in $R$, and through latency at equal recall.

Why not just embed every POI and filter by distance? This is a real threat. For small envelopes, brute-force dense scoring inside the region is cheap and handles synonyms well, and it may simply win. Our claim is narrower. As envelopes grow and dense urban regions hold tens of thousands of POIs, the post-filter returns to the scan-everything-in-region cost that hybrid indices were built to avoid, while pre-filtered approximate search loses recall to the distance check. We will sweep envelope size and report the crossover point honestly. If dense post-filtering dominates at all sizes on 25M-POI SLIPO, the claim is wrong.

Why not just use a thesaurus? It has already been tried in exactly this setting and made things worse (Liu et al.). Lay-versus-jargon mismatch is also rarely a one-to-one synonym swap (Pham et al.). We still include it, because reproducing that result on our query set makes it a calibrated reference point.

Why not let a large model with tool calls do everything end to end? Linear reasoning chains carry early errors forward (Cao et al.), and explicit decomposition has repeatedly helped. Examples are the average F1 gains reported by Patel et al. and RoHT's gains on KQA Pro. We test a tool-calling agent with access to the same index and the same call budget, scored on the nested-query subset where anchor errors should show up.

Proposed Experiments

Data and queries. We use Foursquare, OpenStreetMap at 4M POIs, SLIPO at 25M POIs, and the Beijing POI data of Liu et al. No vocabulary-mismatch spatial benchmark exists in the file, so we build one:

  • Single-hop queries. For sampled target POIs, a held-out model paraphrases category and tag text into lay phrasing that shares no content words with the target's indexed text. A human-verified subset checks that paraphrases are correct.
  • Nested queries. Templated queries pair an anchor described indirectly with a distance relation and a paraphrased target.

Metrics. We measure recall@10 and nDCG@10 against the true targets. We also record latency, index nodes visited, entries scored, the number of expansion terms, and the rate of empty results.

Decisive check 1: does region conditioning matter? Compare region grounding against global grounding at matched term counts. If region grounding does not lower the empty-result rate and nodes visited at equal or better recall, region conditioning adds nothing.

Decisive check 2: where is the crossover with dense retrieval? Sweep envelope area and POI density against the dense post-filter to locate the crossover.

Decisive check 3: does planner feedback catch invented sub-goals? Inject deliberately invented descriptive sub-goals and measure how often feedback flags them before execution, compared with the two-stage pipeline.

Decisive check 4: does it transfer to a learned index? Run the method on WISK with a paraphrased query workload. This tests whether bounded, index-vocabulary expansion keeps the learned partitions effective when user vocabulary shifts away from the vocabulary the index was trained on.