[jira] [Updated] (LUCENE-6422) Add PackedQuadPrefixTree

["David Smiley (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/LUCENE-6422?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

David Smiley updated LUCENE-6422:
---------------------------------
      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

  was:
To conform to Lucene's inverted index, SpatialStrategies use strings to represent QuadCells and GeoHash cells. Yielding 1 byte per QuadCell and 5 bits per GeoHash cell, respectively.  To create the terms representing a Shape, the BytesRefIteratorTokenStream first builds all of the terms into an ArrayList of Cells in memory, then passes the ArrayList.Iterator back to invert() which creates a second lexicographically sorted array of Terms. This doubles the memory consumption when indexing a shape.

This task introduces a PackedQuadPrefixTree that uses a StreamingStrategy to accomplish the following:

1.  Create a packed 8byte representation for a QuadCell
2.  Build the Packed cells 'on demand' when incrementToken is called

Improvements over this approach include the generation of the packed cells using an AutoPrefixAutomaton

    Lucene Fields: New,Patch Available  (was: New)
    Fix Version/s: 5.2
         Assignee: David Smiley
          Summary: Add PackedQuadPrefixTree  (was: Add StreamingQuadPrefixTree)

> Add PackedQuadPrefixTree
> ------------------------
>
>                 Key: LUCENE-6422
>                 URL: https://issues.apache.org/jira/browse/LUCENE-6422
>             Project: Lucene - Core
>          Issue Type: Improvement
>          Components: modules/spatial
>    Affects Versions: 5.x
>            Reporter: Nicholas Knize
>            Assignee: David Smiley
>             Fix For: 5.2
>
>         Attachments: LUCENE-6422-TRUNK.patch, LUCENE-6422.patch, LUCENE-6422.patch, LUCENE-6422.patch, LUCENE-6422.patch, LUCENE-6422_with_SPT_factory_and_benchmark.patch
>
>
> 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



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org