[Jts-topo-suite-user] JTS and Parallel Computing

[Kay, Jim]

I am starting to think about dipping my toe in the water of Java parallel computing; possibly using JCuda for gpu calculations, or PJ2 for everything, or possibly MPJ-Express.
Has anybody got any experience or advice of using JTS in a parallel Java world?

Our application principally uses a lot of basic Polygon operations (union, intersection, distance between geometries).
Can anybody provide any useful pointers as to which core Geometry routines might benefit from speedup by being rewritten to use parallel methods?

Thanks.

Jim

Jim Kay
Principal Engineer
Tel: [phone]
Mob: [phone]
Email: ***@snclavalin.com



[cid:***@01D12B4A.A300ADC0]
interfleetgroup.com<http://www.interfleetgroup.com/> | snclavalin.com

[Martin Davis]

I've given parallel computation with JTS only some casual thought, but one
thing that occurred to me is that there's two ways to parallelize geometry
computation with JTS. The first is what I'll call *external* parallelism.
In this scenario JTS itself runs sequentially, but the invoking process is
parallelized. In many cases the client process is easily parallelizable,
so this provides improved throughput for low effort.

The other approach is *internal* parallelism, in which JTS algorithms are
reworked to offer some degree of multi-execution. This sounds like what
you're thinking of. Is it the case that the frameworks mentioned can only
improve performance for internal parallelism? (In which case I'm curious
to know why this is - and to what extent it's in fact possible.)

For internal parallelism, the obvious place to look is at the major loops
in the processes. In the case of overlay operations, this would be the
noding phase. Ironically, the algorithms which provide best performance in
the sequential case often are not ones which parallelize. For instance,
currently overlay uses a sweepline algorithm for noding
(SimpleMCSweepLineIntersector), which is inherently sequential. To
parallelize this it would be better to use something like MCIndexNoder,
which iterates over a set of unordered chains.

In the case of distance, the current (inefficient) algorithm iterates over
a set of unordered geometry "facets", so this should be easily
parallelized. However, there's a much more efficient approach which is to
use a Branch-and-Bound algorithm over two spatial indexes. Perhaps this
would be harder to parallelize?

Another operation which uses a recursive tree structure is
CascadedPolygonUnion. This should be fairly easy to make parallel, I think.

One worthy goal would be to generalize the code so that it is easy to
switch between parallel and sequential execution modes. How hard would
this be?

On Mon, Nov 30, 2015 at 12:44 AM, Kay, Jim <***@snclavalin.com> wrote:

> I am starting to think about dipping my toe in the water of Java parallel
> computing; possibly using JCuda for gpu calculations, or PJ2 for
> everything, or possibly MPJ-Express.
>
> Has anybody got any experience or advice of using JTS in a parallel Java
> world?
>
>
>
> Our application principally uses a lot of basic Polygon operations (union,
> intersection, distance between geometries).
>
> Can anybody provide any useful pointers as to which core Geometry routines
> might benefit from speedup by being rewritten to use parallel methods?
>
>
>
> Thanks.
>
>
>
> *Jim*
>
>
>
> *Jim Kay*
>
> *Principal Engineer*
>
> Tel: [phone]
>
> Mob: [phone]
>
> Email: ***@snclavalin.com
>
>
>
> [image: line]
>
>
>
> interfleetgroup.com <http://www.interfleetgroup.com/> | snclavalin.com
>
>
>
>
> ------------------------------------------------------------------------------
> Go from Idea to Many App Stores Faster with Intel(R) XDK
> Give your users amazing mobile app experiences with Intel(R) XDK.
> Use one codebase in this all-in-one HTML5 development environment.
> Design, debug & build mobile apps & 2D/3D high-impact games for multiple
> OSs.
> http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts-topo-suite-***@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>

[Kay, Jim]

“Another operation which uses a recursive tree structure is CascadedPolygonUnion. This should be fairly easy to make parallel, I think”

Exactly the same one I was thinking of! (and just started to look at). The new concurrent classes in JDK 8 look promising, in particular the RecursiveTask and ForkJoinPool.

Jim


From: Martin Davis [mailto:***@gmail.com]
Sent: 30 November 2015 17:41
To: Kay, Jim
Cc: jts-topo-suite-***@lists.sourceforge.net
Subject: Re: [Jts-topo-suite-user] JTS and Parallel Computing

I've given parallel computation with JTS only some casual thought, but one thing that occurred to me is that there's two ways to parallelize geometry computation with JTS. The first is what I'll call *external* parallelism. In this scenario JTS itself runs sequentially, but the invoking process is parallelized. In many cases the client process is easily parallelizable, so this provides improved throughput for low effort.

The other approach is *internal* parallelism, in which JTS algorithms are reworked to offer some degree of multi-execution. This sounds like what you're thinking of. Is it the case that the frameworks mentioned can only improve performance for internal parallelism? (In which case I'm curious to know why this is - and to what extent it's in fact possible.)

For internal parallelism, the obvious place to look is at the major loops in the processes. In the case of overlay operations, this would be the noding phase. Ironically, the algorithms which provide best performance in the sequential case often are not ones which parallelize. For instance, currently overlay uses a sweepline algorithm for noding (SimpleMCSweepLineIntersector), which is inherently sequential. To parallelize this it would be better to use something like MCIndexNoder, which iterates over a set of unordered chains.

In the case of distance, the current (inefficient) algorithm iterates over a set of unordered geometry "facets", so this should be easily parallelized. However, there's a much more efficient approach which is to use a Branch-and-Bound algorithm over two spatial indexes. Perhaps this would be harder to parallelize?

Another operation which uses a recursive tree structure is CascadedPolygonUnion. This should be fairly easy to make parallel, I think.

One worthy goal would be to generalize the code so that it is easy to switch between parallel and sequential execution modes. How hard would this be?

On Mon, Nov 30, 2015 at 12:44 AM, Kay, Jim <***@snclavalin.com<mailto:***@snclavalin.com>> wrote:
I am starting to think about dipping my toe in the water of Java parallel computing; possibly using JCuda for gpu calculations, or PJ2 for everything, or possibly MPJ-Express.
Has anybody got any experience or advice of using JTS in a parallel Java world?

Our application principally uses a lot of basic Polygon operations (union, intersection, distance between geometries).
Can anybody provide any useful pointers as to which core Geometry routines might benefit from speedup by being rewritten to use parallel methods?

Thanks.

Jim

Jim Kay
Principal Engineer
Tel: [phone]<tel:%2B44%20%280%29%201332%20223229>
Mob: [phone]<tel:%2B44%20%280%29%207715%20536828>
Email: ***@snclavalin.com<mailto:***@snclavalin.com>



[cid:***@01D12B97.4DF80150]
interfleetgroup.com<http://www.interfleetgroup.com/> | snclavalin.com<http://snclavalin.com>


------------------------------------------------------------------------------
Go from Idea to Many App Stores Faster with Intel(R) XDK
Give your users amazing mobile app experiences with Intel(R) XDK.
Use one codebase in this all-in-one HTML5 development environment.
Design, debug & build mobile apps & 2D/3D high-impact games for multiple OSs.
http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140
_______________________________________________
Jts-topo-suite-user mailing list
Jts-topo-suite-***@lists.sourceforge.net<mailto:Jts-topo-suite-***@lists.sourceforge.net>
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user

[Martin Davis]

Definitely a good spot to dip a toe in the water. Please post to let us
know how it works out.

On Mon, Nov 30, 2015 at 9:52 AM, Kay, Jim <***@snclavalin.com> wrote:

> *“Another operation which uses a recursive tree structure is
> CascadedPolygonUnion. This should be fairly easy to make parallel, I think*
> ”
>
>
>
> Exactly the same one I was thinking of! (and just started to look at). The
> new concurrent classes in JDK 8 look promising, in particular the
> RecursiveTask and ForkJoinPool.
>
>
>
> Jim
>
>
>
>
>
> *From:* Martin Davis [mailto:***@gmail.com]
> *Sent:* 30 November 2015 17:41
> *To:* Kay, Jim
> *Cc:* jts-topo-suite-***@lists.sourceforge.net
> *Subject:* Re: [Jts-topo-suite-user] JTS and Parallel Computing
>
>
>
> I've given parallel computation with JTS only some casual thought, but one
> thing that occurred to me is that there's two ways to parallelize geometry
> computation with JTS. The first is what I'll call *external* parallelism.
> In this scenario JTS itself runs sequentially, but the invoking process is
> parallelized. In many cases the client process is easily parallelizable,
> so this provides improved throughput for low effort.
>
>
>
> The other approach is *internal* parallelism, in which JTS algorithms are
> reworked to offer some degree of multi-execution. This sounds like what
> you're thinking of. Is it the case that the frameworks mentioned can only
> improve performance for internal parallelism? (In which case I'm curious
> to know why this is - and to what extent it's in fact possible.)
>
>
>
> For internal parallelism, the obvious place to look is at the major loops
> in the processes. In the case of overlay operations, this would be the
> noding phase. Ironically, the algorithms which provide best performance in
> the sequential case often are not ones which parallelize. For instance,
> currently overlay uses a sweepline algorithm for noding
> (SimpleMCSweepLineIntersector), which is inherently sequential. To
> parallelize this it would be better to use something like MCIndexNoder,
> which iterates over a set of unordered chains.
>
>
>
> In the case of distance, the current (inefficient) algorithm iterates over
> a set of unordered geometry "facets", so this should be easily
> parallelized. However, there's a much more efficient approach which is to
> use a Branch-and-Bound algorithm over two spatial indexes. Perhaps this
> would be harder to parallelize?
>
>
>
> Another operation which uses a recursive tree structure is
> CascadedPolygonUnion. This should be fairly easy to make parallel, I think.
>
>
>
> One worthy goal would be to generalize the code so that it is easy to
> switch between parallel and sequential execution modes. How hard would
> this be?
>
>
>
> On Mon, Nov 30, 2015 at 12:44 AM, Kay, Jim <***@snclavalin.com> wrote:
>
> I am starting to think about dipping my toe in the water of Java parallel
> computing; possibly using JCuda for gpu calculations, or PJ2 for
> everything, or possibly MPJ-Express.
>
> Has anybody got any experience or advice of using JTS in a parallel Java
> world?
>
>
>
> Our application principally uses a lot of basic Polygon operations (union,
> intersection, distance between geometries).
>
> Can anybody provide any useful pointers as to which core Geometry routines
> might benefit from speedup by being rewritten to use parallel methods?
>
>
>
> Thanks.
>
>
>
> *Jim*
>
>
>
> *Jim Kay*
>
> *Principal Engineer*
>
> Tel: [phone]
>
> Mob: [phone]
>
> Email: ***@snclavalin.com
>
>
>
> [image: line]
>
>
>
> interfleetgroup.com <http://www.interfleetgroup.com/> | snclavalin.com
>
>
>
>
>
> ------------------------------------------------------------------------------
> Go from Idea to Many App Stores Faster with Intel(R) XDK
> Give your users amazing mobile app experiences with Intel(R) XDK.
> Use one codebase in this all-in-one HTML5 development environment.
> Design, debug & build mobile apps & 2D/3D high-impact games for multiple
> OSs.
> http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts-topo-suite-***@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>
>

[Daniel Baston]

For what it's worth, here's an example of parallelizing CascadedPolygonUnion using JDK8 parallel streams:

https://gist.github.com/dbaston/6b32fcb8c70d4d58775b

Cheers,
Dan

________________________________________
From: jts-topo-suite-user-***@lists.sourceforge.net <jts-topo-suite-user-***@lists.sourceforge.net>
Sent: Monday, November 30, 2015 12:52 PM
To: jts-topo-suite-***@lists.sourceforge.net
Subject: Jts-topo-suite-user Digest, Vol 70, Issue 6

Send Jts-topo-suite-user mailing list submissions to
jts-topo-suite-***@lists.sourceforge.net

To subscribe or unsubscribe via the World Wide Web, visit
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
or, via email, send a message with subject or body 'help' to
jts-topo-suite-user-***@lists.sourceforge.net

You can reach the person managing the list at
jts-topo-suite-user-***@lists.sourceforge.net

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Jts-topo-suite-user digest..."


Today's Topics:

1. Re: Regarding Query from the STRtree (Martin Davis)
2. Re: JTS and Parallel Computing (Kay, Jim)


----------------------------------------------------------------------

Message: 1
Date: Mon, 30 Nov 2015 09:51:13 -0800
From: Martin Davis <***@gmail.com>
Subject: Re: [Jts-topo-suite-user] Regarding Query from the STRtree
To: Saurav Ranjit <***@gmail.com>
Cc: "jts-topo-suite-***@lists.sourceforge.net"
<jts-topo-suite-***@lists.sourceforge.net>
Message-ID:
<CAK2ens14axx_9KRJbfjyZ2Y4me2fLq-***@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"

The reason for the multiple results is that the STRtree queries based on
the envelopes of the indexed geometries. (This is known as a "primary
filter" in spatial querying [1]). You need to implement a "secondary
filter" to execute the actual spatial test you want to perform.

In the case of testing whether a point "belongs" to a line segment you will
need to decide whether you want a precise geometric test, or (more likely)
a test based on distance between the point and the linestring. For the
first case use Line.covers(Point), for the second use Line.distance(Point).



[1]
https://books.google.ca/books?id=8shsCQAAQBAJ&pg=PA405&lpg=PA405&dq=geometry+primary+filter&source=bl&ots=ziVSr9mspm&sig=dr55bdT8yt9nYyqI5ePW4HykJqY&hl=en&sa=X&ved=0ahUKEwjQmZqP2rjJAhUVfYgKHZEPAuMQ6AEINDAF#v=onepage&q=geometry%20primary%20filter&f=false

On Sun, Nov 29, 2015 at 6:14 AM, Saurav Ranjit <***@gmail.com>
wrote:

> Hi everyone,
>
> I am new to the jts. I am trying to query in which line segment the gps
> point belongs to using the STRtree. I created the STRtree using the WKT
> format of linestring. I am able to perform the query using "List<Object[]>
> search_result = index.query(search);". But in many case the it produced
> multiple result.
>
> For example for the point "13.7127, 100.52007", the query is giving me 3
> result of different line segments.
>
> LINESTRING (100.51997 13.71225,100.52005 13.71278,100.52009 13.71366)
> LINESTRING (100.52007 13.71224,100.52012 13.71263,100.52019
> 13.71351,100.52021 13.71375)
> LINESTRING (100.5196 13.71037,100.51978 13.71085,100.52001
> 13.71153,100.52017 13.71211,100.52021 13.71233,100.52026 13.71263,100.52033
> 13.71335,100.52035 13.71374,100.52035 13.71377,100.52033 13.7145,100.52023
> 13.7155,100.52023 13.71558,100.52023 13.7156,100.52023 13.71596)
>
> I would like to know exactly in which line segment the point belongs to. I
> have also attached the image of the point and the line segment here.
>
> Please let me know regarding my questions.
>
> Thank you very much for the help
>
> Regards,
> Saurav Ranjit
> Master's in Engineering of Remote Sensing and Geographic Information
> Systems (RSGIS)
> School of Engineering and Technology (SET)
> Asian Institute of Technology (AIT)
> Thailand
> Mobile: [phone]
> Skype: sauravranjit
>
>
> ------------------------------------------------------------------------------
> Go from Idea to Many App Stores Faster with Intel(R) XDK
> Give your users amazing mobile app experiences with Intel(R) XDK.
> Use one codebase in this all-in-one HTML5 development environment.
> Design, debug & build mobile apps & 2D/3D high-impact games for multiple
> OSs.
> http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140
> _______________________________________________
> Jts-topo-suite-user mailing list
> Jts-topo-suite-***@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>
-------------- next part --------------
An HTML attachment was scrubbed...

------------------------------

Message: 2
Date: Mon, 30 Nov 2015 17:52:01 +0000
From: "Kay, Jim" <***@snclavalin.com>
Subject: Re: [Jts-topo-suite-user] JTS and Parallel Computing
To: Martin Davis <***@gmail.com>
Cc: "jts-topo-suite-***@lists.sourceforge.net"
<jts-topo-suite-***@lists.sourceforge.net>
Message-ID: <***@SLI2126.sli.bz>
Content-Type: text/plain; charset="utf-8"

?Another operation which uses a recursive tree structure is CascadedPolygonUnion. This should be fairly easy to make parallel, I think?

Exactly the same one I was thinking of! (and just started to look at). The new concurrent classes in JDK 8 look promising, in particular the RecursiveTask and ForkJoinPool.

Jim


From: Martin Davis [mailto:***@gmail.com]
Sent: 30 November 2015 17:41
To: Kay, Jim
Cc: jts-topo-suite-***@lists.sourceforge.net
Subject: Re: [Jts-topo-suite-user] JTS and Parallel Computing

I've given parallel computation with JTS only some casual thought, but one thing that occurred to me is that there's two ways to parallelize geometry computation with JTS. The first is what I'll call *external* parallelism. In this scenario JTS itself runs sequentially, but the invoking process is parallelized. In many cases the client process is easily parallelizable, so this provides improved throughput for low effort.

The other approach is *internal* parallelism, in which JTS algorithms are reworked to offer some degree of multi-execution. This sounds like what you're thinking of. Is it the case that the frameworks mentioned can only improve performance for internal parallelism? (In which case I'm curious to know why this is - and to what extent it's in fact possible.)

For internal parallelism, the obvious place to look is at the major loops in the processes. In the case of overlay operations, this would be the noding phase. Ironically, the algorithms which provide best performance in the sequential case often are not ones which parallelize. For instance, currently overlay uses a sweepline algorithm for noding (SimpleMCSweepLineIntersector), which is inherently sequential. To parallelize this it would be better to use something like MCIndexNoder, which iterates over a set of unordered chains.

In the case of distance, the current (inefficient) algorithm iterates over a set of unordered geometry "facets", so this should be easily parallelized. However, there's a much more efficient approach which is to use a Branch-and-Bound algorithm over two spatial indexes. Perhaps this would be harder to parallelize?

Another operation which uses a recursive tree structure is CascadedPolygonUnion. This should be fairly easy to make parallel, I think.

One worthy goal would be to generalize the code so that it is easy to switch between parallel and sequential execution modes. How hard would this be?

On Mon, Nov 30, 2015 at 12:44 AM, Kay, Jim <***@snclavalin.com<mailto:***@snclavalin.com>> wrote:
I am starting to think about dipping my toe in the water of Java parallel computing; possibly using JCuda for gpu calculations, or PJ2 for everything, or possibly MPJ-Express.
Has anybody got any experience or advice of using JTS in a parallel Java world?

Our application principally uses a lot of basic Polygon operations (union, intersection, distance between geometries).
Can anybody provide any useful pointers as to which core Geometry routines might benefit from speedup by being rewritten to use parallel methods?

Thanks.

Jim

Jim Kay
Principal Engineer
Tel: [phone]<tel:%2B44%20%280%29%201332%20223229>
Mob: [phone]<tel:%2B44%20%280%29%207715%20536828>
Email: ***@snclavalin.com<mailto:***@snclavalin.com>



[cid:***@01D12B97.4DF80150]
interfleetgroup.com<http://www.interfleetgroup.com/> | snclavalin.com<http://snclavalin.com>


------------------------------------------------------------------------------
Go from Idea to Many App Stores Faster with Intel(R) XDK
Give your users amazing mobile app experiences with Intel(R) XDK.
Use one codebase in this all-in-one HTML5 development environment.
Design, debug & build mobile apps & 2D/3D high-impact games for multiple OSs.
http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140
_______________________________________________
Jts-topo-suite-user mailing list
Jts-topo-suite-***@lists.sourceforge.net<mailto:Jts-topo-suite-***@lists.sourceforge.net>
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user

-------------- next part --------------
An HTML attachment was scrubbed...
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 853 bytes
Desc: image001.jpg
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image002.png
Type: image/png
Size: 12533 bytes
Desc: image002.png

------------------------------

------------------------------------------------------------------------------
Go from Idea to Many App Stores Faster with Intel(R) XDK
Give your users amazing mobile app experiences with Intel(R) XDK.
Use one codebase in this all-in-one HTML5 development environment.
Design, debug & build mobile apps & 2D/3D high-impact games for multiple OSs.
http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140

------------------------------

_______________________________________________
Jts-topo-suite-user mailing list
Jts-topo-suite-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user


End of Jts-topo-suite-user Digest, Vol 70, Issue 6
**************************************************

[Martin Davis]

Nice, thanks.

What is STRtree.itemsTree() ?

On Mon, Nov 30, 2015 at 9:58 AM, Daniel Baston <***@maponics.com> wrote:

> For what it's worth, here's an example of parallelizing
> CascadedPolygonUnion using JDK8 parallel streams:
>
> https://gist.github.com/dbaston/6b32fcb8c70d4d58775b
>
>

[Daniel Baston]

Hi Martin,


STRtree.itemsTree() is being called to pull out the list of lists that forms the internal representation of the tree (the method is implemented in AbstractSTRtree.java). This is in line with what CascadedPolygonUnion is doing.


It's been a while since I looked at this code, so I scratched my head a couple of times when reading it. I added some comments just now.


Thanks,

Dan

________________________________
From: Martin Davis <***@gmail.com>
Sent: Monday, November 30, 2015 1:48 PM
To: Daniel Baston
Cc: jts-topo-suite-***@lists.sourceforge.net
Subject: Re: [Jts-topo-suite-user] JTS and Parallel Computing

Nice, thanks.

What is STRtree.itemsTree() ?

On Mon, Nov 30, 2015 at 9:58 AM, Daniel Baston <***@maponics.com<mailto:***@maponics.com>> wrote:
For what it's worth, here's an example of parallelizing CascadedPolygonUnion using JDK8 parallel streams:

https://gist.github.com/dbaston/6b32fcb8c70d4d58775b

[Martin Davis]

Ah right - I'm losing track of the JTS API!

Good stuff about the comments...

I really should start a list of useful JTS code snippets & extensions...

On Mon, Nov 30, 2015 at 11:30 AM, Daniel Baston <***@maponics.com>
wrote:

> Hi Martin,
>
>
> STRtree.itemsTree() is being called to pull out the list of lists that
> forms the internal representation of the tree (the method is implemented in
> AbstractSTRtree.java). This is in line with what CascadedPolygonUnion is
> doing.
>
>
> It's been a while since I looked at this code, so I scratched my head a
> couple of times when reading it. I added some comments just now.
>
>
> Thanks,
>
> Dan
>
> ------------------------------
> *From:* Martin Davis <***@gmail.com>
> *Sent:* Monday, November 30, 2015 1:48 PM
> *To:* Daniel Baston
> *Cc:* jts-topo-suite-***@lists.sourceforge.net
> *Subject:* Re: [Jts-topo-suite-user] JTS and Parallel Computing
>
> Nice, thanks.
>
> What is STRtree.itemsTree() ?
>
> On Mon, Nov 30, 2015 at 9:58 AM, Daniel Baston <***@maponics.com>
> wrote:
>
>> For what it's worth, here's an example of parallelizing
>> CascadedPolygonUnion using JDK8 parallel streams:
>>
>> https://gist.github.com/dbaston/6b32fcb8c70d4d58775b
>>
>>