[ https://issues.apache.org/jira/browse/LUCENE-6480?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14541933#comment-14541933 ]
Nicholas Knize commented on LUCENE-6480: ---------------------------------------- Its sounds much like the simple morton interleaving I'm using for the 2D case? But since you're using an extra bit for the 3rd dimension you lose precision in the horizontal direction. We could start w/ that as a phase one? Instead of worrying about the sign bit the values in the 2D case are scaled 0:360, 0:180 and divided into 32 bits per lat/lon (see GeoUtils.java). Extending to 3D divide 0:360, 0:180, 0:?? by 21 and extend BitUtil.interleave to the 3 value case. Its super fast since its done by bit twiddling using magic numbers (although the magic numbers will need to be reworked). The question is the max value of the altitude? The larger the value the less precise, but you could conceivably go as far as 3,300 (km) to cover the earth's atmosphere? Maybe that's configurable. As a phase 2 there has been some work in this area for 3 and 4d hilbert order (still using 64 bit), which will better preserve locality. (I mentioned it in a comment in the previous issue). Locality is important since it will drive the complexity of the range search and how much the postings list will actually help (e.g. stepping one unit in the 3rd dimension can result in a boundary range that requires post-filtering a significant number of high precision terms). The more I think about it, this might be efficiently done using a statically computed lookup table (we'd have to tinker)? i.e., one hilbert order for the 3d unit cube is 000, 001, 101, 100, 110, 111, 011, 010, and the order of the suboctants at each succeeding level is a permutation of this base unit cube. For example, the next rotated level (for suboctant 000) gives the binary order: 000 000, 000 010, 000 110, 000 100, 000 101, 000 111, 000 011, 000 001. There's a paper that describes how to compute the suboctant permutation rather efficiently, and it could be statically computed and represented using 1. base unit ordering, 2. substitution list. So for level 2, each suboctant ordering is: base order (000, 001, 101, 100, 110, 111, 011, 010), substitution list (2 8) (3 5), (2 8 4) (3 7 5), (2 8 4) (3 7 5), (1 3) (2 4) (5 7) (6 8), (1 3) (2 4) (5 7) (6 8), (1 5 7) (2 4 6), (1 7) (4 6). Something to think about as an enhancement. I'll try to find the paper. > Extend Simple GeoPointField Type to 3d > --------------------------------------- > > Key: LUCENE-6480 > URL: https://issues.apache.org/jira/browse/LUCENE-6480 > Project: Lucene - Core > Issue Type: New Feature > Components: core/index > Reporter: Nicholas Knize > > [LUCENE-6450 | https://issues.apache.org/jira/browse/LUCENE-6450] proposes a > simple GeoPointField type to lucene core. This field uses 64bit encoding of 2 > dimensional points to construct sorted term representations of GeoPoints > (aka: GeoHashing). > This feature investigates adding support for encoding 3 dimensional > GeoPoints, either by extending GeoPointField to a Geo3DPointField or adding > an additional 3d constructor. -- This message was sent by Atlassian JIRA (v6.3.4#6332) --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org