Luc, Will,

I've checked in a version that captures the requirements as I see them. It
includes a method to identify sets of segments (I've called them
SpatialRegions) that can be rolled up.

http://perforce.eigenbase.org:8080/@...src/main/mondr
ian/util/SpatialValueTree2.java

I have re-introduced the distinction between 'segment requests' (called
SpatialRegionRequest; for each dimension, the set of values to retrieve) and
'segments' (called SpatialRegion; the actual set of values).

For performance, I have made all kinds of constraints, e.g.
SpatialDimensions are created by the tree itself, have contiguous and unique
ordinals; values implement Comparable; arrays of values are sorted and
unique and the client will not modify them. We can add more constraints, if
it improves performance.

Conversely, if there are things in this API that mondrian does not need,
let's remove them.

There are other general design notes in the javadoc comments at the head of
the class.

Developers,

I would like to have this discussion in a public forum, so we might as well
start now. Briefly, this is what we are trying to achieve...

The goal is to design a data structure that will allow us to manage
thousands, possibly millions, of segments containing cell values. Currently
mondrian stores segments in a linked list for each dimensionality (e.g. all
segments for (year, month, nation) are in the same list). But that won't be
tenable when we (a) have an external cache with many thousands of segments,
(b) we want to answer a cell request by rolling up coarser granularity
segment(s). Our design process is to (a) propose an API, (b) write unit
tests for functionality, performance and thread-safety, (c) write several
implementations of the API, and may the best one win.

Julian


_____

From: Luc Boudreau [mailto:lboudreau (AT) pentaho (DOT) com]
Sent: Monday, April 18, 2011 9:05 PM
To: Will Gorman; Julian Hyde
Subject: Spatial index



As discussed, I've sketched a first draft at a proposed spatial index.



http://perforce.eigenbase.org:8080/@...src/main/mondr
ian/util/SpatialValueTree.java
<http://perforce.eigenbase.org:8080/@...src/main/mondr
ian/util/SpatialValueTree.java>



If you could give it a quick read and tell me if there is anything I might
have missed or overlooked, I could then start writing a bunch of unit tests.



Thanks!



Luc


_______________________________________________
Mondrian mailing list
Mondrian (AT) pentaho (DOT) org
http://lists.pentaho.org/mailman/listinfo/mondrian