Mailing-List: contact general-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: general@lucene.apache.org
Received-SPF: pass (athena.apache.org: local policy)
MIME-Version: 1.0
In-Reply-To: <c68e39170912291742q6eea1a94o1c03cf9dea3a511b@mail.gmail.com>
References: <1e33aedb0912282125k2f6dc673u98584f8ea24854c3@mail.gmail.com>
	 <1e33aedb0912282349y48628cb8q7ddf9e24d4ad1d77@mail.gmail.com>
	 <24ED15CB-2E08-40E8-BBF7-7ABA758AEABF@apache.org>
	 <1e33aedb0912290854je7e6734m4f8d2d04acd44fba@mail.gmail.com>
	 <20091229183211.GA8740@rectangular.com>
	 <1e33aedb0912291114y75010ac5mf6d3813196346d6e@mail.gmail.com>
	 <20091229202947.GA9132@rectangular.com>
	 <20091229235522.GA9830@rectangular.com>
	 <20091230001324.GB9830@rectangular.com>
	 <c68e39170912291742q6eea1a94o1c03cf9dea3a511b@mail.gmail.com>
Date: Wed, 30 Dec 2009 07:01:01 -0500
Message-ID: <9ac0c6aa0912300401x31faf3b2t72deda9df6ba83d5@mail.gmail.com>
Subject: Re: [spatial] Cartesian "Tiers" nomenclature
From: Michael McCandless <lucene@mikemccandless.com>
To: general@lucene.apache.org, yonik@lucidimagination.com
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Right, NRQ is able to translate any requested range into the union
(OR) of brackets (from the trie) created during indexing.

Can spatial do the same thing, just with 2D instead of 1D?  Ie,
reconstruct any expressible shape (created at query time) as the union
of some number of grids/tiers, at finer & finer levels, created during
indexing?

Spatial, today, seems to do this, except it must also do "precise"
filtering on each matching doc, because some of the grids may contain
hits outside of the requested shape.

In fact, NRQ could also borrow from spatial's current approach -- ie,
create the union of some smallish number of coarse brackets.  Some of
the brackets will fall entirely within the requested range, and so
require no further filtering, while others will fall part inside /
part outside of the requested range, and so will require precise
filtering.  If NRQ did this, it should have much fewer postings to
enum, at the cost of having to do precise filtering on some of them
(and we'd have to somehow encode the orig value in the index).

Mike

On Tue, Dec 29, 2009 at 8:42 PM, Yonik Seeley
<yonik@lucidimagination.com> wrote:
> On Tue, Dec 29, 2009 at 7:13 PM, Marvin Humphrey <marvin@rectangular.com>=
 wrote:
>> ... but for this algorithm, different rasterization resolutions need not
>> proceed by powers-of-two.
>
> Indeed - one way to further generalize would be to use something like
> Lucene's trie-based Numeric field, but with a square instead of a
> line. =A0That would allow to tweak the space/speed tradeoff.
>
> -Yonik
> http://www.lucidimagination.com
>