Hi Andrea,
Thank you for your views.
More of the answer between lines :
2007/7/6, Andrea Aime <[EMAIL PROTECTED]>:
Christophe Rousson ha scritto:
> Hi Ian and Andrea,
>
> I wrote down my plan for using a quadtree to cache features :
>
>
http://docs.codehaus.org/display/GEOTOOLS/SoC+2007+Caching+data#SoC2007Cachingdata-ideasquadtree
> <
http://docs.codehaus.org/display/GEOTOOLS/SoC+2007+Caching+data#SoC2007Cachingdata-ideasquadtree
>
>
> Could you have a look at this ?
I looked at the description, did not have enough time for the code sorry.
The idea looks good, I have a few questions thought:
* does a non leaf tile contain geometries? If not, where do you
put geometries that cover more than one tile? What if your
map has shorelines or isolines that span most of the map?
non leaf tiles should reference in some way features contained in the tile
but that don't fit in subnodes. This is already the way the insertion
algorithm works, but I have to make some adjustement so that nodes contain a
list of features rather than only ids (though we could store features in
another hashmap, but this has an extra cost)
As for wide-extent features, most queries are likely to yield them. So this
is not a problem if they are cached in the upper levels of the tree. But
this leaves less room for local features. However query coverage will be
recorded at the minimum containing tile. So upper level tiles don't have to
be complete, but this requires to maintain unique references in the list of
features bounded to these tiles.
* what do you do if there are many partial nodes under the
same node, that is, if the situation is not clear cut?
Do a lot of queries? At a certain level you should stop
and reload a few of the features in order to execute less
queries, since query setup and latency have a price too.
I've been aware of that problem : "To minimize the number of quadrants to
fetch, each quadrant should yield less than a maximum number of quadrants,
possibly depending on the level of the quadrant." A node containinig leaves
(level=1) will yield only one extent to query from source picked in {one of
the leaves, on of the halves, extent of the node, none}. On higher levels, a
node should decide wether to load part of its children or reload whole
children, depending of the number of parts to fetch.
* This somehow has consequences on eviction... a good eviction
policy will try to keep the holes in the tree big and square
instead of generating a crossword like picture
good point.
* I think eviction search should not be that expensive if you
are able to keep the tree relatively small (level wise)
and you update the last updated time from the leaf up to
the root for each access. It would also be interesting to
have an estimate of how many megabytes of stuff are there
under each node (down to the leaves) so that you can decide
where you have enough stuff to evict to gather back the
space you need to load the missing parts
It will be easy to record in nodes summary statistics such as number of
features (that is
number of features hold in the node and subnodes). I still don't know how to
evaluate actual size of features without serializing, but we can use
estimate, eventually with an estimator by level.
* when a query has only partial match, I guess you should first
lock the nodes that answer part of the query (minus those
that you may reload due to query grouping) and then evict
those that are not locked.
good point, too. I will depends on the eviction strategy, LRU will not
require this, but LFU will.
I will also have to make my implementation thread safe. But Jody and Martin
discussion will give me materials to do that !
Cheers, and thanks again.
Christophe
-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
Geotools-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/geotools-devel
