[mkgmap-dev] [Patch v3] LocationHook with new Quadtree

Sun Jan 15 09:10:42 GMT 2012

Hi Gerd,

> Hi WanMil,
>
> regarding further optimization of the quadtree (presuming we can correct
> remaining errors):
>
> I think we have two options:
> 1) Create and calculate it at runtime (as it is now) . In this case the
> goal must be to keep the creation time and answering time short

 From my point of view the timings of the LocationHook are great now. 
Improvements can be micro improvements only. Investing the same time to 
other parts of mkgmap would give more benefit.

> 2) Calculate it in BoundaryPreparer and save it in the .bnd files (with
> a new or extended format). In this case we can avoid higher calculation
> time if that means reducing redundancy.
> With precompiled quadtrees the LocationHook just has to create a small
> master-quadtree and load required parts into it.
>
> The quadtree in my patch probably contains a lot of redundant
> information because tiles with admin-level=2 or =4 will cover big parts
> of the tree, and the information is (almost always) already
> contained in the smaller areas because I use the information from the
> lies_in tags.

Mmh, I though the merge step will create non overlapping areas and each 
area contains *all* of its information. So there should be no large 
admin_level=2 area left but lots small areas all containing the 
admin_level=2,3,4,5,6,7,8,9,10,11 information.

>I did not try it, but I expect that the merge() process
> result should be the same if we don't use
> the lies_in information.

If not something is wrong?!

> If we move the quadtree to the preparer, we can omit the calculation of
> the lies_in tags (I think they are not needed elsewhere), but we should
> try to avoid saving redundant information.

The lies_in information is only 80% of the information required for the 
new quadtree. So it might help but is not sufficient to remove the merge 
step.

>
> If we can save the quadtree in a format that can be loaded faster than
> the time that is now needed to load the .bnd files plus calculating the
> quadtree, I'd vote for optimizing it for the preparer.

The preparer would have to do the merge step:
 From the given boundaries create not overlapping areas with all 
location information.
I would not try to store additional quadtree information. You can try 
but I don't expect any measurable improvements by that.

All in all: Please keep the format of the bnd files as simple as 
possible and think about using it for other purposes. e.g. the current 
format could easily be used for coastline processing - one can 
precompile the coastlines and mgkmap could load the sea areas from the 
precompiled sea file. This would be great to have (a big!! performance 
and quality improvement). But someone needs to implement that.

> Does that make sense?

Yes.
Also see my first point: Measure how much time it takes and decide 
yourself if you want to invest a lot of time for micro improvements.

WanMil

>
> Ciao,
> Gerd
>
>
>  > Date: Fri, 13 Jan 2012 22:19:08 +0100
>  > From: wmgcnfg at web.de
>  > To: mkgmap-dev at lists.mkgmap.org.uk
>  > Subject: Re: [mkgmap-dev] [Patch v3] LocationHook with new Quadtree
>  >
>  > Ok, I think I didn't understand your concept:
>  > The basis principle of the tree is that there are non intersecting areas
>  > only so that only one area can be found for one point. And each area
>  > contains all tags of all intersecting boundaries.
>  > I thought merging would be a performance thing only.
>  >
>  > The advantage of this is that you only need one match to get all.
>  > If we implement cutting ways by boundaries there is the disadvantage
>  > that we don't know in the LocationHook which tags are relevant and
>  > therefore ways might be splitted too much.
>  >
>  > WanMil
>  >
>  > > Hi WanMil,
>  > >
>  > > of course it is faster, but how do you solve the problem that the
>  > > information is incomplete?
>  > > Maybe I did not make that clear:
>  > > Without the merge step, you have to travel through the nodeElems until
>  > > information from all areas in combined. If you don't do this, you
> have the
>  > > same result as in trunk when you remove an element from the list
> after it
>  > > was first processed.
>  > >
>  > > Ciao,
>  > > Gerd
>  > >
>  > >
>  > >
>  > >
>  > > WanMil wrote
>  > >>
>  > >> Mmmh, I tested with an without merge using 66 tiles.
>  > >>
>  > >> LocationHook time with merge: 72,7s
>  > >> LocationHook time without merge: 55,6s
>  > >>
>  > >> The times are very different. So I assumed that the GC slowed down the
>  > >> merge variant so I compared the timings of each tile. One tile was 8s
>  > >> slower with the merge variant. So maybe the GC slowed it down.
>  > >>
>  > >> But most of the tiles were quicker with the non merge variant.
> Some are
>  > >> quicker with merging and some are rather equal.
>  > >>
>  > >> Maybe timings can be improved by changing the depth and the nodeNum
>  > >> constraint in the split method but merging does not seem to be an
>  > >> overall improvement.
>  > >>
>  > >> WanMil
>  > >>
>  > >>
>  > >>> Hi WanMil,
>  > >>>
>  > >>> yes, it improves performance because the merge is done only once, and
>  > >>> without the merge it would be needed to do more or less the same
> action
>  > >>> for
>  > >>> each single search. I see no better way to handle the problem
> with those
>  > >>> level=7 areas.
>  > >>>
>  > >>> Ciao,
>  > >>> Gerd
>  > >>>
>  > >>>
>  > >>> WanMil wrote
>  > >>>>
>  > >>>>> > > >
>  > >>>>> > > > * I don't understand why you need a merge() method. Could
>  > >>>>> you
>  > >>>>> explain
>  > >>>>> > > > what you are doing in this method and why it's required?
>  > >>>>> > > The get method() of the tree returns the data for the first
>  > >>>>> area
>  > >>>>> that
>  > >>>>> > > contains the coord.
>  > >>>>> > > This area should contain all tags of the area itself plus those
>  > >>>>> from
>  > >>>>> > > areas intersecting it.
>  > >>>>> > > Maybe this is not correct?
>  > >>>>> >
>  > >>>>> > Sounds wrong. If Area a1 is intersected by a2 only in 10% of its
>  > >>>>> area
>  > >>>>> > then an element located in the 90% that does not intersect would
>  > >>>>> be
>  > >>>>> > tagged with a1 and a2?
>  > >>>>> >
>  > >>>>> The merge() first creates a new nodeElem with the intersection, it
>  > >>>>> merges the tags into this
>  > >>>>> and subtracts the intersection from the others, so only the 10%
> part
>  > >>>>> gets more tags.
>  > >>>>> Thinking again about this I might not need both subtract()
> calls since
>  > >>>>> I
>  > >>>>> move the intersection part
>  > >>>>> before the others .
>  > >>>>>
>  > >>>>
>  > >>>> I doubt that merge improves the performance. It breaks two areas
> into
>  > >>>> three probably with intersecting bounding boxes. So I would
> expect that
>  > >>>> you don't save much contains checks.
>  > >>>> But don't mind about my doubts: Did you measure a noticeable
> performance
>  > >>>> difference?
>  > >>>>
>  > >>>> WanMil
>  > >>>> _______________________________________________
>  > >>>> mkgmap-dev mailing list
>  > >>>> mkgmap-dev at .org
>  > >>>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>  > >>>>
>  > >>>
>  > >>>
>  > >>> --
>  > >>> View this message in context:
>  > >>>
> http://gis.638310.n2.nabble.com/Patch-v3-LocationHook-with-new-Quadtree-tp7181669p7184965.html
>  > >>> Sent from the Mkgmap Development mailing list archive at Nabble.com.
>  > >>> _______________________________________________
>  > >>> mkgmap-dev mailing list
>  > >>> mkgmap-dev at .org
>  > >>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>  > >>
>  > >> _______________________________________________
>  > >> mkgmap-dev mailing list
>  > >> mkgmap-dev at .org
>  > >> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>  > >>
>  > >
>  > >
>  > > --
>  > > View this message in context:
> http://gis.638310.n2.nabble.com/Patch-v3-LocationHook-with-new-Quadtree-tp7181669p7185332.html
>  > > Sent from the Mkgmap Development mailing list archive at Nabble.com.
>  > > _______________________________________________
>  > > mkgmap-dev mailing list
>  > > mkgmap-dev at lists.mkgmap.org.uk
>  > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>  >
>  > _______________________________________________
>  > mkgmap-dev mailing list
>  > mkgmap-dev at lists.mkgmap.org.uk
>  > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev