[LUCENE-6422] Add PackedQuadPrefixTree

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 5.2
• Component/s: modules/spatial
• Lucene Fields: New, Patch Available
• Assignee: David Smiley
• Reporter: Nick Knize
• Created: 14/Apr/15 19:35
• Updated: 28/Aug/22 14:30
• Resolved: 23/Apr/15 04:31

Description

This task introduces a PackedQuadPrefixTree that includes two things:

1. A packed 8 byte representation for a QuadCell, including more efficient implementations of the SPT API than the existing QuadPrefixTree or GeoHashPrefixTree.
2. An alternative implementation to RPT's "pruneLeafyBranches" that streams the cells without buffering them all, which is way more memory efficient. However pruning is limited to the target detail level, where it accomplishes the most good.

Future improvements over this approach may include the generation of the packed cells using an AutoPrefixAutomaton