apache / apache/lucene

Optimize IsWithin spatial RPT to use a point cache for false-positive removal [LUCENE-4869]

Open
#5,934 1 comment 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Major module:spatial type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

#5709 implemented the "IsWithin" predicate for a RecursivePrefixTree based field. It's slow since it looks across the whole world to ensure it doesn't match docs with data anywhere outside the query shape. It can be configured to only look outside the query shape using a very small buffer distance, and that will filter out documents spanning the query shape boundary, but not indexed shapes comprised of multiple disjoint parts. The solution proposed here is to index a point per disjoint part in such a way that it can be easily retrieved (e.g. DocValues) and then a post-process of WithinPrefixTreeFilter would remove false-positives.

This isn't particularly hard/advanced but it requires some advances in some APIs that aren't quite there yet. Spatial4j's ShapeCollection (aka WKT GeometryCollection or Multi\*) needs to get released, it needs a vertex iterator. There needs to be code to read and write a set of points to a BinaryDocValues field (1/doc). And finally of course WithinPrefixTreeFilter needs to have a mode in which it uses the smallest buffer and then in the end checks the DocValues to remove false-postivies.

---
Migrated from [LUCENE-4869](https://issues.apache.org/jira/browse/LUCENE-4869) by David Smiley (@dsmiley), updated May 02 2013
Linked issues:
- #5709
- #5763

Contributor guide

Open the contributing guide

Research direction

Start with WithinPrefixTreeFilter and the linked issues #5709 and #5763 to understand the existing IsWithin implementation. Review the proposed Spatial4j ShapeCollection vertex iterator and BinaryDocValues support for storing points per disjoint part. Done means the smallest-buffer mode removes false positives using the cached points.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.