lucene-java-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "" <>
Subject Re: Lucene Spatial Question: Is a tree structure explicitly created in the QuadPrefixTree implementation?
Date Wed, 01 Oct 2014 17:19:34 GMT
Hi Parth,

Lucene’s “terms dictionary” (an inverted index) is the physical
instantiation of the actual PrefixTree/Trie for numeric and spatial data.
It doesn’t know it is — it’s just a sorted list of keys pointing to
matching documents — it just so happens that the keys aren’t textual words
in this case, they are encoded prefixes.  SpatialPrefixTree (base class of
QuadPrefixTree and some others) encodes points and other spatial regions
into one or more prefixes that get indexed during indexing, and which that
are looked up during search.  The “Cell” class (aka a node) are indeed used
during spatial processing in an iterator-like way.  The index & search time
processing iterates the prefixes.  It’s not typically fully materialized
into a tree structure of Cells.

Thanks for the MX-Quad tree pointer; the “MX” notion is new to me.  It
appears that any prefix-tree/trie is also in effect an MX-tree as well,
making Prefix-Tree/Tries a particular case of MX trees.

~ David Smiley
Freelance Apache Lucene/Solr Search Consultant/Developer

On Wed, Oct 1, 2014 at 2:17 AM, parth_n <> wrote:

> Hi everyone,
> I have a question regarding the quadtree implementation of the spatial
> module of Lucene. Does the quadtree implementation (QuadPrefixTree)
> explicitly build a tree structure and store this information? I have gone
> over the QuadPrefixTree class, but from what I understand it mainly uses
> the
> spatial prefix partitioning strategy of the MX-quadtree (but not the
> internal nodes).
> Are the internal nodes (e.g. for a 4-level tree prefix ABDA, are the
> spatial
> regions of ABD and/or AB) of the quadtree used during query processing?
> Any replies are much appreciated.
> Thanks!
> Parth
> --
> View this message in context:
> Sent from the Lucene - Java Users mailing list archive at
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message