Location-based alert systems let users register standing requests such as "tell me about anything mentioning a road hazard within 2 km of my commute." These are called publish/subscribe (pub/sub) subscriptions: millions of persistent queries sit in memory, and each incoming geotagged post is checked against all of them. Today's fast systems only allow a subscription to be a spatial region plus a conjunction of exact keywords. Users and applications want more. They want "flooding OR water main, but NOT a drill," and they want meaning rather than exact strings, for example "posts semantically close to road hazard," tested by comparing text embeddings (dense vectors from a language model). Adding OR, NOT, and embedding-similarity tests usually breaks the pruning tricks that make these systems fast. Negation in particular is non-monotone: knowing that some subscriptions in a branch share a keyword says nothing about whether a NOT clause will fail.
We propose a matching engine that keeps pruning exact under arbitrary Boolean subscriptions. Every test, whether spatial, keyword, or embedding similarity, is first evaluated cheaply as an interval: an index node's bounding box gives a range of possible distances, and a low-dimensional prefix of the embedding gives a guaranteed range of possible similarities. These intervals are combined with three-valued logic (true / false / unknown). A subscription is resolved at the coarsest level that already decides it. Only subscriptions still "unknown" pay for full-resolution work. The result is a coarse-to-fine cascade, in the sense of a lower-bound-and-prune scheme from vision and parsing, applied to formulas instead of image regions, with zero false negatives by construction.
Core Claim
Coarse-to-fine pruning stays sound for nested AND/OR/NOT subscriptions over spatial, keyword, and embedding-threshold tests if each cascade level returns intervals rather than yes/no answers and those intervals are propagated through Kleene three-valued logic. Combined with a per-subscription "access atom" (a positive test implied by the whole formula, used to place the subscription in a spatial-textual index), this should give throughput close to that of conjunctive-only systems on realistic Boolean workloads, while answering exactly what brute-force full-embedding evaluation answers.
The pruning principle comes from Yuille: a coarsened model yields a rigorous bound on the true cost, so a branch whose bound fails the threshold can be discarded with no false negatives. Learning and Inference for Hierarchically Split PCFGs shows that cascades over increasingly refined models can give a 107x parsing speedup on Penn Treebank without accuracy loss. Our contribution is to carry that principle into logical query evaluation, where negation would otherwise invalidate it.
Why the Gap Is Real
Three hybrid indexes all implement coarse-to-fine filtering for one fixed query shape: a spatial region plus a keyword conjunction.
- The IQ-tree in SOPS stores keyword posting lists inside quadtree nodes and prunes branches by bounding box and local vocabulary.
- The QT-tree in SSTD chooses at each node between a spatial split and a textual split using a cost model.
- The kdt-tree of PS2Stream does the same for distributed dispatch.
All three rely on the fact that a publication failing a node's summary fails every subscription below it. That reasoning is valid only for monotone (negation-free) queries. SSTD also notes that its matching is purely syntactic.
Two adjacent works stop short of this problem:
- Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations names general AND/OR/NOT as open, even for estimating how many objects a query matches.
- IVF$^2$ fuses inverted files with vector graphs for filtered nearest-neighbor search. It is explicitly limited to single labels and two-label AND, and it searches for nearest vectors rather than matching a stream against stored threshold predicates.
The query-theory literature both motivates and constrains the design. Completeness of Queries over Incomplete Databases reduces a semantic guarantee to query containment and shows that adding comparisons and self-joins raises the complexity sharply. We use the same move in a deliberately cheap form. Deciding whether a positive atom is implied by a subscription is propositional implication over a formula of a few dozen atoms, done once at registration. We avoid relational joins or recursion in subscriptions, which that hierarchy warns would make index construction intractable.
Research Program
Registration side. Each subscription is a Boolean formula over three kinds of atoms:
- a spatial atom, such as "inside region R" or "within r of point x";
- a keyword atom, "contains w";
- a semantic atom, $\langle e(p), c\rangle \ge \tau$. Here $e(p)$ is the unit-norm embedding of publication $p$, $c$ is a unit concept vector, and $\tau$ is a threshold.
At registration we compute an access atom: a positive spatial or keyword atom implied by the formula, chosen to be as rare as possible using per-cell term frequencies. The subscription is indexed under that atom in an IQ-tree-style structure. For example, "within 2 km of $x$ AND (flood OR water main) AND NOT drill" is implied by its spatial atom and can be indexed there. Formulas with no implied positive atom go to a small residual bucket. A purely negative formula is one example, and the experiments will measure how common such formulas are.
Probe side. For each publication we compute the full embedding once, then project it with a fixed PCA basis. Writing $e = e_{1:d'} + r$ for the first $d'$ coordinates plus a residual (and likewise $c$ with residual $r_c$), Cauchy–Schwarz gives
$$ \langle e_{1:d'}, c_{1:d'}\rangle - \|r\|\,\|r_c\| \;\le\; \langle e, c\rangle \;\le\; \langle e_{1:d'}, c_{1:d'}\rangle + \|r\|\,\|r_c\|, $$
so every semantic atom receives a guaranteed interval at cost $d'$ rather than full dimension $d$. The residual norms $\|r_c\|$ are stored per concept vector. Spatial atoms receive intervals from node bounding boxes, and keyword atoms are exact.
Intervals become true, false, or unknown and propagate through the formula. NOT swaps true and false; AND and OR follow Kleene's tables. A subscription is emitted or dropped as soon as its root is decided. Unknown subscriptions move to the next level, for example $d' = 16, 64$, and then full dimension. Concept vectors shared across subscriptions are deduplicated, and each publication–concept interval is computed once.
Analysis. We will show that the cascade never changes the answer set relative to exact evaluation; this follows directly from interval soundness plus Kleene monotonicity. We will then characterize the cost per publication as the full-dimension cost multiplied by the fraction of semantic atoms left undecided at each level. That fraction depends on how far typical similarities sit from $\tau$ relative to the residual bound, and we will measure it rather than assume it.
Baselines
Naive reference: exact brute-force evaluation. For every publication, check the spatial atoms of all subscriptions, then compute full-dimension similarities for every surviving semantic atom and evaluate the formula. This is the correctness oracle. It defines the answer set that every other method must reproduce exactly, and the "do nothing" cost.
Strongest existing method: DNF expansion over an IQ-tree index. Each formula is rewritten into DNF (disjunctive normal form: an OR of AND-clauses). Each clause is registered in an IQ-tree index as in SOPS under its positive spatial and keyword atoms. Negated atoms and full-dimension semantic atoms are checked only at the leaves. This is the strongest competitor because it reuses the best published conjunctive index unchanged and handles OR by expansion.
To make the comparison fair, both systems run on one machine with the same encoder, the same precomputed embeddings, the same quadtree parameters (tuned per system with an equal grid-search budget), and the same subscription sets. The distributed variant uses the same worker count with PS2Stream-style routing.
There is no reported throughput on Lacuna for Boolean subscriptions with negation or semantic atoms. For reference, SOPS reports being designed for "20 million subscribe queries over a stream of more than 50 million geo-textual objects per day," SSTD reports "2–4x faster" than Tornado and PS2 on TW14/TW15, and PS2Stream reports throughput improved "up to 30%" on TWEETS-US. Beating the DNF baseline means at least 2x higher sustained publications per second at equal answers and comparable memory, on workloads whose average formula has three or more disjuncts or any semantic atom.
Ablations. Three ablations isolate the key ingredients:
- Cascade without three-valued logic. Bound only positive atoms, and verify any formula containing NOT at full resolution. This isolates the contribution of sound negation handling.
- Cascade without access atoms. All subscriptions sit in a flat list with interval evaluation. This isolates the contribution of indexing.
- Single coarse level versus multi-level cascade. This isolates the value of graded refinement.
Why not just…?
Why not just expand to DNF and reuse a conjunctive index? This is the real threat. For short formulas with few ORs it may match us, which is why it is the main baseline rather than a straw man. It falls short in three predictable places:
- DNF size can grow exponentially with nested ORs, inflating index memory, which PS2Stream already reports as a dispatcher bottleneck.
- Clauses made only of negations or semantic atoms have no positive keyword to index on.
- Semantic atoms still cost full-dimension dot products at the leaves.
The formula-complexity sweep in the experiments settles this question. If DNF wins whenever formulas have two or fewer disjuncts and no semantic atoms, we will report that crossover honestly.
Why not just turn semantic atoms into keyword disjunctions through thesaurus expansion? That converts the problem back into one existing indexes handle. However, Clue-based Spatio-textual Query reports that thesaurus expansion adds significant latency and slightly lowers accuracy. Expansion also changes the answer set, so it does not solve the same problem. We will run it anyway and report both its throughput and its recall against the exact semantic oracle.
Why not just treat each publication as a filtered nearest-neighbor search over concept vectors, IVF$^2$-style? Nearest-neighbor search returns the top matches, not every subscription whose threshold is crossed, and its recall is below 100%. IVF$^2$ reports "over 10x faster than the FAISS baseline at 85% recall" on YFCC-10M, and that recall level would mean silently dropped alerts. It also supports only two-label AND. We will include a threshold-adapted IVF index over concept vectors as a semantic-atom-only baseline and report its missed matches.
Proposed Experiments
Datasets. Publication streams are TWEETS-US (280M tweets) and TWEETS-UK (58M) from PS2Stream, TW14/TW15 from SSTD, and the Yelp Singapore and Foursquare sets from SOPS. No Boolean geo-semantic subscription workload exists in the file. We will therefore generate subscriptions following the published SOPS/PS2Stream practice of sampling keywords and locations from the stream, then add OR, NOT, and semantic atoms with controlled formula depth, disjunct count, negation rate, and threshold. Concept vectors are taken from embeddings of held-out posts.
Metrics. We measure:
- sustained publications per second and 99th-percentile latency;
- index memory;
- the fraction of subscriptions decided at each cascade level;
- false negatives and false positives against the brute-force oracle, which must be exactly zero for our method.
Decisive checks. Three results determine whether the claim holds:
- Throughput versus formula complexity. Plot throughput relative to the DNF baseline as disjunct count and negation rate grow. The claim fails if there is no regime with a 2x gain.
- Decided fraction versus threshold. Plot the fraction decided at $d' = 16$ against $\tau$. If residual bounds are too loose for real embeddings (fewer than half the atoms decided early), the cascade's premise fails.
- Residual bucket size. Measure the share of subscriptions with no access atom under realistic workloads. If that share is large, the indexing half of the design needs rethinking.
We will additionally run the distributed setting with PS2Stream-style routing on TWEETS-US, to check that the gains survive skew and load rebalancing.
References
- Inference and Learning with Hierarchical Shape Models
- Learning and Inference for Hierarchically Split PCFGs
- SOPS: A System for Efficient Processing of Spatial-Keyword Publish/Subscribe
- SSTD: A Distributed System on Streaming Spatio-Textual Data
- Distributed Publish/Subscribe Query Processing on the Spatio-Textual Data Stream
- Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations
- IVF$^{2}$ Index: Fusing Classic and Spatial Inverted Indices for Fast Filtered ANNS
- Completeness of Queries over Incomplete Databases
- Clue-based Spatio-textual Query