Precise graph-based phrase query with SpanNearQuery
summary
A patch that makes SpanNearQuery matching precise and complete while keeping performance comparable to the current implementation, presented as a proof‑of‑concept that records positionLength and a nextStartPosition lookahead in payloads and targets LUCENE-7398. It builds a linked, circular, resizable-array-backed 2‑D queue with stable node references and a spans wrapper that supports efficient backtracking; GC tuning and object pooling yield roughly 2x–10x better behavior versus naive linked allocations, and the implementation works without exponential expansion.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:42TokenStream structure
- 1:59Latent potential of PositionLengthAttribute
- 3:34LUCENE-7398: nominally about "nested" Span querits
- 4:09Abstraction of the Spans API contract with respect to position order
- 8:17Foundation: a backtracking-capable Spans wrapper
- 10:04Properties of backtracking-capable Spans wrapper
- 11:44Building matches over subclauses
- 13:432-dimensional queue traversal, building word lattice
- 15:28Managing GC for heavily-linked data structure
- 15:58Support for indexed position length
- 16:52startPosition lookahead
- 17:36PositionLength edge cases
- 18:43Common words: the last hurdle
- 19:23Match modes
- 20:09Potential non-text use cases?
related talks
17mA Better Approximation for Interleaved Dyck Reachability
43mPriority Search Queues: 1.5 dimensional Tree Search
21mgoSLP - Globally Optimized Superword Level Parallelism Framework
25mA Semi-Persistent E-Graph with Native AC Canonization and Leapfrog AC Matching.
43mUpdateable Fields and other Fun with Codec API
28mSpEQ: Translation of Sparse Codes using Equivalences
19mSpEQ: Translation of Sparse Codes using Equivalences
42mFrom Linear to Incremental