Thursday, 16 April 2009

WPS implementation (nearly)

My WPS system now consists of a ASP.NET application wrapped around a ASP.NET Web Service. The web application takes the input and handles the getCapabilities and DescribeProcess requests. It also, after some error checking passes on the Execute request to the Web Service which processes the request asynchronously.

The WPS getCapabilities response can be seen here:

http://www.gmtu.gov.uk/wps/?service=WPS&version=1.0.0&Request=GetCapabilities

The DescribeProcess response can be seen here:

http://www.gmtu.gov.uk/wps/?service=WPS&version=1.0.0&Request=DescribeProcess&Identifier=DBSCAN

The DescribeProcess output is not yet complete as there is no description of the input and output data format. There is some error trapping so if you enter:

http://www.gmtu.gov.uk/wps/?service=WPS&version=1.0.0&Request=DescribeProcess&Identifier=noProcess

An error message will be returned.

The Execute process should return an XML response document that allows any client to monitor progress. In my implementation, for each request the WPS creates a file nnnnn.xml, where nnnnn is a unique integer. Both the wrapper application and the web service write to this file. When the Execute request has been parsed and all the inputs are present and correct, the wrapper creates the file with a ProcessAccepted message. When the Web Service is called, it overwrites the file with a ProcessStarted message. If there are any errors in processing then a ProcessFailed message is written. Finally a ProcessSucceeded message is written to the ResponseDocument. The idea is that the client can poll this document to check the process of the request.

This is sort of working but I have occasional errors “file being used by another process” when I try to overwrite the file or sometimes when reading it. I think this is due to the web server software (IIS) locking any file it has recently served. I’ll need to think of a way around this.

Monday, 2 March 2009

Final architecture?

After several weeks of exploring different solutions including remoting and using a Windows Service I have settled on using a Web Service.

The service takes as input a value for Eps (in metres) and a url pointing to a WFS service.
Currently I have the web service running on one physical server and the WFS service running on another. The service saves the results in a KML file on the server, which can be accessed via the web. The clustering alogorithm may take several minutes to run (depending on the amount of source data) so the service needs to be called asynchronously.

Firstly, the server code that executes the DBSCAN algorithm has to be encoded as a sub rather than a function since it cannot return a value to the client if we are running asynchronously. The sub definition needs the following attribute set:

SoapDocumentMethod(OneWay:=True)

The timeout has to be increased in the service application, using a setting in the Web.config file:

httpruntime executiontimeout="1200"

The service can be called from a web client. A reference to the service is added to the client and, for the page that calls the service, the sync attribute needs to be set in the @Page directive:

Async="true"

The client can then call the service:

Dim ws As New WPSservice.Service
ws.DBSCANasyncAsync(Eps, Url)


Where ws is a reference to the web service and DBSCANasyncAsync is the sub in the web service.

I’ve got this working as it should. The client calls the service asynchronously and control returns to the client page straightaway whilst the service continues to run in the background. When complete it writes out a results file to the server. This is all well and good, but since the client does not wait for the service to finish, how does the client know when the job has been completed, where the results are, if there are any errors? This is the next stage, I need to setup a mechanism for polling the service for the results and reporting any errors back to the client. I need to start getting my system looking like a Web Processing Service as specified by the OGC.





Tuesday, 3 February 2009

Output to KML file and more thoughts on implementation

So far I have written the results from DBSCAN as INSERT statements to be run against a postgreSQL database. This is not going to be much use for a client application, so for the next step I’m going to generate a KML file showing the clusters (I’m going to omit noise points to keep the output filesize low). KML has now been adopted as a OGC standard and can be used as input to Google Maps and Google earth.

One problem is that my data is in OSGB co-ordinates whereas KML uses WGS84 lat/long. I've used the Grid InQuest co-ordinate translation program which comes with a DLL file that can be used in Visual Studio. My VB.NET application now outputs the results to a KML file. The code for generating the KML file was adapted from here.

Some sample results:

http://www.gmtu.gov.uk/nmg/citycentre.kml
http://www.gmtu.gov.uk/nmg/heatonsnorth.kml

If these urls are pasted directly into the browser, Google Earth will be fired up (if installed). To use the kml files in Google Maps you can paste the URL into the Search Maps text box on the Google Maps page.

Here is the Heatons North data in Google Maps:


View Larger Map

The number on each point is the clusterID (note that noise points have not been included.

As it stands the KML displays the individual points in each cluster. I perhaps need to think about generalization and generate polygons to display the clusters.

How does this fit in with my eventual implementation? My current thinking is this:

To develop An ASP.NET web application that acts as a “wrapper” around a VB.NET service/application. The wrapper is what the client sees and is in effect the WPS. This is the technique as recommended by Michael and Ames in their early evaluation of WPS. They suggest that the geo-processing takes place in a separate process. This will stop a badly performing process from bringing down the entire WPS (On Windows Server I can put the geo-processing tools in a separate application pool). My ASP.NET application will handle the GetCapabilities and DescribeProcess functions. It will also manage the Execute process by calling the necessary geo-processing service. The geo-processing service will take input from the wrapper and write its results to a results file (e.g. a KML file as above) It will also write to a log file, reporting its progress. The log file can be queried by the ASP.NET wrapper (on request of the client) allowing it to check on progress. The relevant section of the OGC WPS specification is:

"The mandatory Execute operation allows WPS clients to run a specified process implemented by a server, using the input parameter values provided and returning the output values produced. Inputs can be included directly in the Execute request, or reference web accessible resources. The outputs can be returned in the form of an XML response document, either embedded within the response document or stored as web accessible resources. If the outputs are stored, the Execute response shall consist of a XML document that includes a URL for each stored output, which the client can use to retrieve those outputs. Alternatively, for a single output, the server can be directed to return that output in its raw form without being wrapped in an XML reponse document.

Normally, the response document is returned only after process execution is completed. However, a client can instruct the server to return the Execute response document immediately following acceptance by the server of the Execute request. In this case, the Execute response includes a URL from which the response document can later be retrieved during and after process execution. The server can be instructed to provide regular updates to a measure of the amount of processing remaining if the process is not complete. This allows the client to determine the process status by polling this URL. "

The response document will be in effect my log file (an XML document), which while processing is ongoing will provide status updates when queried and when processing is complete will contain URLs to any output e.g. a KML file.

I think this method means generating a separate XML document each time the process is called (each file named with a unique reference number) unless I generate the response document dynamically from ASP.NET.

I need to examine further the approaches taken by 52 North and deegree in their WPS implementations.

Wednesday, 28 January 2009

UML Experiments

I'm going to document my implementation using UML since it is prevalent in academia. I've been experimenting with the Poseidon for UML community edition modelling software which was included with Teach yourself UML in 24 hours. The book gets panned on Amazon but I am up to hour 7 and I am fairly impressed so far. The important section for me will be sequence diagrams which I have yet to reach (hour 9).

My first attempt at a (very basic) class diagram:
This is the point class used in my code that implements DBSCAN.

The software has an export function which created the above gif image. However, with the version I've got it puts a watermark on any exports:


Which will not look too good in my thesis.

I'm going to look next at Star UML, an open source tool.

Tuesday, 27 January 2009

More on DBSCAN

To recap, I'm attempting to implement the clustering alogorithm, DBSCAN, as a desktop VB.NET application, reading the accident data from a GML file. I've managed to do this using a modified version of the method described by Tan et al (Algoritm 8.4, p528).

The implementation requires the user to supply a value for Eps. The process is as follows:
  1. read all points into an arraylist of type point (where point is a user defined class)
  2. populate a distance array – containing the distance between each point and every other point
  3. create array for k-dist where k = 4– i.e. for each point what is the distance to the 4th nearest neighbour?
  4. flag core points – i.e. where 4-dist is <= Eps
  5. flag border points – i.e. where the point is within Eps of a core point
  6. by default the remaining points are noise
  7. populate an array of linked core points – i.e. core points within Eps of each other
  8. where core points are linked put them in the same cluster
  9. add border points to same cluster as their nearest core point
(The code then generates INSERT statements that can be run against a postgreSQL database for plotting in QGIS).

The process was run using data from the Heatons North ward using values for Eps of 10m and 20m. The following images focus on a particular section of road:

With a Eps of 10m:

With an Eps of 20m:


The core points are black, border points are yellow and noise points are crosses. The number indicates the cluster ID (the 10m Eps returns 14 clusters, the 20m Eps returns 19 clusters)

With the 10m Eps there is more noise and the cluster is more focussed - at 2 junctions instead of 3. The choice of Eps is critical then.

A large view of the 10m results can be seen here.

Summary
My implementation of DBSCAN will not be the most efficient but that doesn't matter. Its the implementation of WPS that I'm interested in.

The next stage is to implement the algorithm as a WPS. The first step will be to look at the input parameters of the WPS i.e. how can I make the accident data in WFS form available to a web service?


Saturday, 10 January 2009

useful references - GI Days 2008

I came across the GI Days 2008 conference website the other day. There were a good number of papers relating to WPS. In particular:

Towards a Quality Aware Web Processing Service (Donubauer et al) describes a project to develop a web service that gives an indication of the quality of the results based on the quality of the input data. In their forestry use case the process is a polygon overlay. With the source data the accuracy is provided at a line segment (of each polygon) level. The WPS returns the area and standard deviation of the overlay. The accuracy data is passed to the process embedded in metaDataProperty tags in the source GML. Including something similar in my implementation of WPS is probably beyond the scope of my project but it is something I need to at least make reference to.

Web-based geostatistics using WPS (Jorge de Jesus et al) describes the development of a WPS for spatial interpolation, Kriging, in particular. The output from the process is a reference to a geoTIFF document that can be downloaded using a browser. This project has similarities with my own in that it uses point source data. They note that the “verbosity” of XML is a problem when sending thousands of points observations. Another issue is that GML allows for multiple ways of describing the same data which presents a problem to the programmer. They too raise the issue of quality and make reference to the work done with UncertML (original paper).

Providing GRASS with a Web Processing Service Interface (Bruaner) describes how WPS can be integrated with the GRASS desktop GIS. In a discussion on state he notes that each time you read a dataset in a stateless web-based system you process it and then throw it away. He contrasts this with the classic stateful desktop GIS where you load up your data sources and work on them for as long as necessary.

Monday, 5 January 2009

Implementing DBSCAN

The next stage is to implement the DBSCAN algorithm. DBSCAN is an algorithm for discovering clusters in point data. In my case I want to discover accident black spots in my accident dataset.

The algorithm was devised by Ester et al, in a paper A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise.

Tan et al provide a good discussion of DBSCAN in a chapter of Introduction to Data Mining.

My intention is to implement DBSCAN in a VB.NET desktop application using as input a GML file saved from output of my WFS setup. In my actual implementation I will need to develop a web-based implementation of DBSCAN using an actual WFS request as input but I think this is a good starting point (debugging .NET desktop applications is easier than debugging web applications).

DBSCAN requires three inputs:
  • the data source
  • a parameter MinPts - which is the minimum number of points to define a cluster
  • a distance parameter, Eps - a distance parameter - if there are at least minPts within Eps of a point then that point is a core point in a cluster.
Now, Ester et al concluded that MinPts could safely be set to 4 for all 2D datasets. So MinPts is eliminated. The next step is to work out how to calculate Eps. The following was repeated with a number of susbsets of the full dataset:
  • Read in the GML file, saved from WFS, and store the points in an arraylist
  • Create a distance array that holds the distance of each point to every other point in the dataset
  • for each point calculate its 4th nearest point - what is called the 4-dist point
  • sort the 4-dist values in ascending order
  • plot them
This was repeated with three datasets:

  • All accidents in the (Manchester) City Centre ward (3236 points) graph
  • All accidents in the Heatons North ward (398 points) graph
  • All accidents in Greater Manchester in 2008 -up to September 30th (5309 points) graph

The first thing to note (gratifyingly!) is that all three graphs are similar in shape to that displayed in Tan et al. (Note that the graphs are the flipside of that displayed in Ester et al since they order the data in descending order.) The Eps value for a dataset can be estimated as the point where the graph "takes off". This is very much an estimate, but for the City Centre data it is about 50m, for the Heatons North data it is about 70m but for the whole of GM dataset the value is about 700m.

This value has to be provided to the DBSCAN algorithm before it can work out where the clusters are. As Ester et al state it is difficult to calculate this value automatically. So what's to be done? Some options:

  • Do we send the data to the WPS and get it to send back a graph from which we can estimate the value of Eps which we then send back to the WPS for it to calculate the clusters?
  • Do we assume the user "knows" his/her dataset and expect him/her to provide the value of Eps?
  • Can we make some estimate of Eps? If we look at the three graphs - the first two each cover a single ward. I think they are similar in area and have a similar value of Eps. The third graph covers a much larger area (all of GM) and returns a much larger value of Eps. Can this be used to estimate Eps?

Problems with large datasets
I did try with all accidents in Greater Manchester in 2000, 11998 points, but this meant an array of 11998 x 11998 which was too much for VB.NET. I need to have a think about this distance between points array - perhaps look at spatial indexing and doing the query in a spatial database - there's no point in calculating the distances between points that are nowhere near each other.

Conclusion
I don't want to get bogged down in the details of the processing part of the WPS, since the investigation is into the WPS itself, not any particular algorithm. So, I could simply specify that the user has to provide the value of Eps as a parameter for the WPS. However, I'd like to give it more consideration before taking this option - perhaps estimating the value of Eps if it is not supplied by the user.