Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

BKD-based geo shapes #32039

Closed
21 of 22 tasks
jpountz opened this issue Jul 13, 2018 · 6 comments
Closed
21 of 22 tasks

BKD-based geo shapes #32039

jpountz opened this issue Jul 13, 2018 · 6 comments
Assignees
Labels
:Analytics/Geo Indexing, search aggregations of geo points and shapes >feature Meta Team:Analytics Meta label for analytical engine team (ESQL/Aggs/Geo) v7.16.0

Comments

@jpountz
Copy link
Contributor

jpountz commented Jul 13, 2018

Explanation

LatLonShape indexes shapes by decomposing them into a triangular mesh and indexing each triangle as a 7 dimension point in the BKD Tree (POINTS codec). Below is a graphic demonstrating this decomposition on several US state's political boundaries.

tessellator

This provides a spatial accuracy of ~1e-6 decimal degrees. Whereas accuracy for the legacy inverted index approach (Prefix Trees) depended on the tree_levels, precision, and distance_err_pct parameters.

TODO

@jpountz jpountz added >feature :Analytics/Geo Indexing, search aggregations of geo points and shapes labels Jul 13, 2018
@elasticmachine
Copy link
Collaborator

Pinging @elastic/es-search-aggs

@jpountz
Copy link
Contributor Author

jpountz commented Jul 30, 2018

Add indexing support for points, lines and envelopes

We were discussing geo-shapes with Nick earlier today and I realized that we had been living on different assumptions regarding this item. There are two ways that it could be achieved:

  1. either by tessellating those into triangles as well, points would be a triangle that has the 3 same vertices, and lines would be a flat triangle that has twice the same vertex
  2. or by indexing points, lines, envelopes and polygons in different fields and join results at search time

Both would work, I suspect 1 would be a bit more space-intensive but simpler. Query speed would likely depend on the ratio of indexed shapes that are polygons?

Add an option to index geo_shape fields with BKD trees in 6.x

@nknize suggested that we could add support for this work in a new geo field (#16749) instead of reusing the existing geo_shape field and tell users to migrate their geo_shape fields to it. It would make the transition easier for us since we want this new field to have minimal configuration, it would also help be less surprising to users as this new field makes very different trade-offs and we might not be able to support everything that geo_shape supports today (eg. CONTAINS).

Another part of that discussion was whether geo_point should be folded into that field as well. I think we shouldn't do it, at least not now, because geo points are a very common use-case and having a specialized field allows for optimizations that wouldn't be possible with a field that has to support any shapes.

@nknize What do you think?

@nknize nknize self-assigned this Oct 22, 2018
@nknize nknize added the Meta label Nov 7, 2018
@floggle
Copy link

floggle commented Jul 13, 2019

Is there an ETA for CONTAINS support? The ticket gives ES 7.0 and we're already at 7.2. It's mandatory for use-case so I'm stuck using the slow old indexing.

@jpountz
Copy link
Contributor Author

jpountz commented Jul 15, 2019

It is being worked on but there is no ETA at this point.

@iverase iverase added the v7.8.0 label Apr 9, 2020
@rjernst rjernst added the Team:Analytics Meta label for analytical engine team (ESQL/Aggs/Geo) label May 4, 2020
@pugnascotia pugnascotia added v7.8.1 and removed v7.8.0 labels May 6, 2020
@pugnascotia pugnascotia added v7.9.0 and removed v7.8.1 labels May 6, 2020
@andreidan andreidan added v7.11.0 and removed v7.10.0 labels Oct 7, 2020
iverase added a commit that referenced this issue Apr 30, 2021
With the introduction of BKD-based geo shape indexing in #32039, the prefix tree indexing method has 
been deprecated. From 8.0.0, it will not be allowed to create new mappings using deprecated parameters.
@joegallo joegallo added v7.16.0 and removed v7.15.0 labels Sep 22, 2021
@iverase
Copy link
Contributor

iverase commented Oct 14, 2021

@jpountz in #77856 we moved PrefixTree builders to a module together with the Spatial4j/JTS dependency, are we ok to close this issue?

@jpountz
Copy link
Contributor Author

jpountz commented Oct 14, 2021

+1 to close

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
:Analytics/Geo Indexing, search aggregations of geo points and shapes >feature Meta Team:Analytics Meta label for analytical engine team (ESQL/Aggs/Geo) v7.16.0
Projects
None yet
Development

No branches or pull requests