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 http://www.linkedin.com/in/davidwsmiley On Wed, Oct 1, 2014 at 2:17 AM, parth_n <nagar...@asu.edu> 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: > http://lucene.472066.n3.nabble.com/Lucene-Spatial-Question-Is-a-tree-structure-explicitly-created-in-the-QuadPrefixTree-implementation-tp4162038.html > Sent from the Lucene - Java Users mailing list archive at Nabble.com. > > --------------------------------------------------------------------- > To unsubscribe, e-mail: java-user-unsubscr...@lucene.apache.org > For additional commands, e-mail: java-user-h...@lucene.apache.org > >
