The End of an Architectural Era?

Stonebraker et al have an interesting paper pointing out the antiquity and consequent limitations of the classic relational database architecture in today's world of massive disk/cycles/core.

If they are correct (and in spite of the recent MapReduce blunder Stonebraker has made a lot of great calls in the DB world), the world of data management is going to get awfully interesting in the coming years. The DBA's & DA's of this world have been living a relatively comfortable existence compared to those who are wandering across the stormy badlands of the middle tier. But Stonebraker postulates at least 5 radically variant database architectures to address specific use cases of data management. This would seem to lead to a much more complex world for data architects. But maybe a windfall for the consultants who find their niche?

Quote of the Day

Java - learn once, write anywhere

"From my personal experience, that is quite true. I started programming in Java in 1997, and since then I have built web applications, database applications, mobile applications for Palm and Pocket PC, an application server for CTI applications, CORBA-based distributed applications, network management applications, server-side business components for application servers, fat-client business applications, an IDE, a Rich Client Platform, a modeling tool among other kinds of software. All that across different operating systems and using similar products by different vendors.

Of course I had to learn something new for each kind of "application style", but the programming language and core class library were always there for me. That is a huge thing. Before Java, it was really hard to move from one domain to another, or even move from vendor to vendor. Sun has my eternal gratitude for bringing some sanity to the software development industry."

- Rafael Chavez

The Paradoxically Poor Power of Visual Programming

I've just been reading about TextUML, which is a language and IDE for textually defining UML diagrams by a start-up company called abstratttechnologies.

This seems like both a stroke of brilliance and painfully obvious. It makes me wonder why UML isn't already defined in terms of a serializable language. The big advantage of this I think would be the ability to have a clearly defined semantics. In the past when reading about UML I've been quite frustrated by an apparent lack of rigour in the definition of the various UML concepts and diagrams. It's always seemed to me that a metalanguage like UML is more in need of fully-defined semantics than application languages. Most (all?) application languages after all are executable, which gives provides a final authority for the meaning of a program written in them - run it and see what happens. AFAIK UML isn't really (or not conveniently) executable in the same way.

Which brings me to the paradox promised in the title of this post. One of the claims for TextUML is that it is easier to write and express complex models in than a purely diagram-based UML tool. I can easily believe this - developing a complex model by diagrams seems cumbersome and limited compared to writing a textual description. And I think this generalizes to the concept of visual programming in general. We've had easy access to powerful graphics capabilities for over 20 years now, culminating in today's basically unlimited in graphical capabilities. In spite of this, text-base programming still rules the roost when it comes to expressiveness, flexibility and speed.

So the paradox is: why is a 1-dimensional representation more powerful than a 2-dimensional representation? To put this another way, why does a 1D representation seem less "flat" than a 2D representation?

For further study: would the same apply to a 3D representation? Or would a move to 3D jump out of some sort of planar well, and end up being more expressive than 1D?

By the way, abstratt is right here in l'il ol' Victoria, and the lead designer (and CEO) Rafael Chavez is giving a talk at VicJUG in March. I'm definitely going to attend - I suspect he may have an interesting take on this issue.

New Buffer Styles in JTS 1.9

JTS allows specifying styling parameters to control the appearance of generated buffer polygons.

End Cap styles have been available for a while. End caps can be Round (the default), Flat, or Square. For Round caps, the Quadrant Segments parameter controls the degree of approximation to a true circular arc.

End Cap Styles: Round, Flat, Square

JTS 1.9 adds the ability to specify the Join Style. The Join style controls how the offset curves for consecutive line segments are joined together. The Join type can be Round (the default), Mitre, or Bevel. If Mitre is specified, a further Mitre Limit parameter is provided to control how long mitred joins can be before they are beveled off. The maximum length of a mitred corner is equal to the Mitre Limit multiplied by the buffer distance.

Join Styles: Mitre (limit = 10), Mitre (limit = 1), Bevel

The JTS TestBuilder has been enhanced to allow specifying all of these parameters, so it can be used to experiment with the visual effects of the various styles.

Hey What's That - Terrain Panoramas Mashup

Here's a nifty mashup using Google Maps. It computes a skyline terrain panorama from a given location.



The computed skyline isn't bad, although a bit optimistic (I'm pretty sure you can't see the Olympics from downtown Vancouver!). I think this particular query is ignoring earth curvature (although apparently you can choose to take it into account.)

The site uses it's own SRTM dataset. The gazetteer is impressive - not sure how they get that information.

Cross-Border issues with Google Maps terrain

So GM now has terrain - yay! But they seem to have short-changed half the continent. Check this screenshot from the border just south of Chilliwack. Notice the American Border Peak - but where's the Canadian one? And what's with that crazy-looking border swathe?


I assure US viewers that Canada isn't normally this blurry. And no, it isn't proof that we really do have a year-round 4 ft snowpack!

Ok, I know - never satisfied. Really, this is a very nice feature. I just hope Google gets their north-of-the-border vision lasered real soon...

Enumerating permutations using inversion vectors and factoradic numbering

Permutations are a fundamental concept in discrete mathematics, and crop up in numerous places in computer science. The set of all possible permutations of n items is usually denoted S_n (since the set forms a group which is isomorphic to the Symmetric group of order n). The number of permutations in this set is n!.

This apparently simple concept poses some unexpected challenges. For instance, the following useful operations are messy to compute via the brute-force way of enumerating successive permutations:

• List all the permutations in S_n (in lexicographic order)
• Find the i'th permutation in S_n

This would be straightforward if there was a way of effectively enumerating all permutations; i.e. a mapping between S_n and the integers {1, 2, ..., n!}.

It turns out that this can be done using a pair of ingenious concepts known as the inversion vector and factoradic numbering. These can be used to provide an enumeration of S_n, conveniently in lexicographic order. (Inversion vectors are also known as inversion tables and Lehmer codes - the term vector seems to me to be most appropriate for the nature of the structure.)

A permutation can be written as a sequence of numbers

P = (p₁ p₂ ... p_n) where p_i is in {1, 2, ..., n}

An inversion is a pair (p_i, p_j) where i < j but p_i > p_j. We define d_i to be the number of inversions in the sequence where the first element is p_i:

d_i = | { p_j : i < j , p_i > p_j } |

Then the inversion vector for the permutation is the sequence

D = (d₁, d₂, ..., d_n) (d_i is in the range {0, 1, ..., n-i})

It is fairly straightforward to recover the original permutation from the inversion vector. This paper gives a definition of the forward and reverse mapping algorithms.

There are n! possible sequences D. They are in one-to-one relationship with the set of permutations S_n, and their natural order gives a lexicographic ordering of S_n. So we're halfway to the enumeration that we are looking for.

Inversion vectors can in turn be mapped to the integers in {1, ..., n!} by using the concept of factoradic numbering. A factoradic number is a number made up of a sequence of digits where the radix for digit d_i is (n-i)!. This Wikipedia article explains the concept in detail.

Here's an example:

P = (4 6 2 5 3 1 8 7) is a permutation in S₈.

Its inversion vector is L(P) = [3,4,1,2,1,0,1,0].

The factoradic representation of this is

3×7! + 4×6! + 1×5! + 2×4! + 1×3! + 0×2! + 1×1! + 0×0! = 18175

So inversion vectors and factoradic numbering provide an elegant way of enumerating permutations. But what does this have to do with geospatial processing? That will be a subject for another post...

If programming languages attended computer conferences

If you're a language geek, this post by David Rupp is hilarious!

Fast polygon merging in JTS using Cascaded Union

A common requirement in spatial processing is to union a set of polygons together. Depending on the use case, the polygons may either be a coverage or be overlapping. Up until recently, there were two techniques for accomplishing this in JTS:

• Iterated Union: Iterate over the polygons and union them one-by-one into a result polygon
• Buffer Union: Collect the polygons into a GeometryCollection and run buffer(0) on the collection

The first one is straightforward, but quite inefficient for large input sets. The second technique is more efficient in many cases, but still tends to fail for large or complex data.

Since this is such a common operation, I've been keen to find a faster and more robust approach. An alternative strategy is to use a concept I call Cascaded Union. The idea is to union small subsets of the input together, then union groups of the resulting polygons, and so on recursively until the final union of all areas is computed. This can be thought of as a post-order traversal of a tree, where the union is performed at each interior node. If the tree structure is determined by the spatial proximity of the input polygons, and there is overlap or adjacency in the input dataset, this algorithm can be quite efficient. This is because union operations higher in the tree are faster, since linework is "merged away" from the lower levels.

This picture shows the algorithm in action:


Handily, the spatial indexes already in JTS can be used to determine an appropriate tree structure. Currently the Sort-Tile-Recursive packed R-Tree index is used - this seems to produce an effective tree (although I suspect that the algorithm is not very senstive to the precise spatial tree used)

It turns out that Cascaded Union can be much more efficient than Iterated Union. On a test dataset with 30,000 small polygons with a high degree of overlap, the performance results were:

Cascaded Union: 20 sec
Iterated Union: 3 hours 40 min !

Not bad - well worth the effort of coding... Also, it's more robust than Buffer Union, and often much faster as well.

This will be provided via the Geometry.union() (Unary union) method in JTS 1.9.

Implementations of Polygon Overlay algorithms

Occasionally people ask about the algorithms used in JTS's overlay operations. I don't have a good answer for this, since I basically made it up (in an informed kind of way), and haven't had time to document it to the level I'd like (thank goodness for self-documenting code... 8^)

I recently came across this web site from back in 1998, which is happily still around. It has a good list of implementations of what it calls Polygon Boolean operations. (This is the same thing as the JTS overlay operations - I chose to use a different term to avoid confusion with the spatial predicates). Perhaps some of these sites have done a better job of documentation! There's also some useful references to academic papers covering aspects of the issue.

The bible of Spatial Indexing

The Bhagavad Gita of Multidimensional Access Methods...
The Koran of Quadtrees...

One of the people I met at ACM GIS 2007 was the conference chair, Hanan Samet. He's published a series of highly useful books on spatial indexing methods, which are certainly the most comprehensive and detailed in this field. His latest work is Foundations of Multidimensional and Metric Data Structures and is surely his magnum opus. It could also be called Everything you wanted to know about Spatial Indexes (but were afraid to code). Recommended reading for spatial geeks, especially if you're looking for some reading to tide you over during your next year off.

His first book on the subject, The Design and Analysis of Spatial Data Structures, is also worth looking at, especially since it's a bit more bite-sized. However, it's out-of-print, and expensive when you do find a copy (local plug: I found mine through ABE) If you really can't find a copy you might try contacting Hanan directly.

Hanan has a clear preference for quadtree structures over R-trees, but both approaches are covered well (including pseudo-code - yay!)

Conference Review: ACM GIS 2007

I just got back from ACM GIS 2007, over in Seattle. This is the first time I've attended this conference - or even known about it! It was a good year to go, since there was a lot of energy in the air due to this being the first year that the conference has been held as an independent event in its own right (which may be one reason I haven't heard of it before). One reason for doing this is to catch the building geospatial wave - more on this below.

The conference was very well attended (about 200 people). The bulk of attendees seemed to be from US universities - but hailed from all over the globe. Microsoft was there in force, as you might expect, and Google was very prominent too (a running joke at the conference was that every talk was connected to or given by someone tied to MS or Google). The omnipresent Michael Jones gave a good motivational talk about some of the technologies which are challenges for Google and would be fruitful research areas. Clearly the big guns of the GeoWeb are investing heavily in geospatial research, and this in turn is injecting a lot of cash and relevancy into this field.

Some of the presentations which stood out for me were:

• Using Constraint Programming to conflate address data to urban imagery. Constraint programming is a well established "AI" technique with a lot of mature effective algorithms, and it seems like a promising approach for other kinds of conflation problems as well (such as road network conflation)
• A guy from Google talked about conflating vector road networks to ortho imagery (surprise, surprise - this is a big use case for them). His approach seem to take place mostly in the raster domain (using edge detection and signal isolation), which I found interesting
• A talk by Andrew Danner about building massive TINs and extracting drainage patterns from them. Having just tackled a very similar problem (in both domain and data size) I was interested to see his approach - which was a fair bit more clever. His group has a novel external memory algorithm for building TINs on huge datasets. This seems like an important focus for research, since data gathering bandwidth is outpacing RAM growth.
  
• A couple of talks on approaches for compressing surface models and extracting varying levels of detail. Nice because they used some elegant mathematical concepts such as Morse-Smale codes.

There were lots of other talks - and a HUGE bonus was that the conference proceedings were provided to you at registration time (not 2 months later). So you could read ahead to get a good idea of what was coming up - or use downtime to get a more in-depth understanding of a previous talk.

Speaking of which, this is the first conference I've been to which had a single track of presentations. This made for pretty full days, and was probably only barely possible due to the size of this conference, but it certainly made for a more satisfying, less stressful, and more inclusive experience. No need to agonize on which one of 5 presentations might be the most interesting and then rush madly around repositioning during the 5-min break between talks. And it gave you time to catch up on your reading if the subject wasn't of total interest.

Next year the conference is in Irvine, CA. The organizers are keen to get more industry participation, so don't be shy - check it out.

Workaround to Google 4 Black Screen Of Death problem

Ever since I upgraded to Google Earth 4, I've had the extremely annoying problem that tilting to an oblique view produced a completely black screen. The only way to get the screen view back was to restart GE. Time to dust off that ol' BSOD acronym...

I just found a thread which provides a clue to why the problem occurs, and gives a workaround (which doesn't 100% remove the annoyance, since it only works for that one session).

Apparently the problem is caused by the use of a dual core AMD Athlon processor. The solution is to set the processor affinity to use only a single core for the GE process. (TaskManager, Processes Tab, rightclick process 'googleearth.exe', 'Set Affinity', select 1 processor only). I haven't yet found a way to persist this setting - anyone have any ideas?


Update: After a few milliseconds more browsing, I found that you can use the imagecfg.exe utility to permanently set the processor affinity for a load image. Running the following command in the Google Earth directory does the trick:

imagecfg -a 0x1 googleearth.exe

Virtual nautical sightseeing around Victoria

The great thing about living on an island in the Pacific Ocean is that you're surrounded by... well, ocean. And the great thing about oceans is that there's always something going on. So much goes on, in fact, that Google manages to capture some of it on their infrequent satellite flyovers. Here's a couple of interesting events:

• A nuclear submarine on its way home to Bangor. I'm happy to see that it's clearly making pretty good time, so if one of those warheads did happen to tip over it might be far enough away that we'd only hear the bang and get a bit of a suntan. And according to Google's yellow line it's keeping to its side of the street, which is a good thing too - a head on collision with a container ship would probably substantially lower the property values in my neighbourhood.
• An apparently sinking ferry. No surprises really, we've had a bit of that going around recently. Hopefully everyone made it off this one, so as not to spoil B.C. Ferries' almost perfect record for the last two years. Never mind, we'll get the Germans to build us another one.

You have to really like this neogeography stuff, it's such a time-saver - I no longer have to walk two blocks to watch for nuclear submarines. And maybe take the ferry less often too, which is also good for the health!

Geometry Safari - Squircles, Supercircles, and Superellipses

Everyone knows that the equation of a circle is the beautifully simple:

x² + y² = C

An obvious generalization of this is to allow higher values for the exponent:

|x|ⁿ + |y|ⁿ = C : n >= 2

This produces a family of nicely rounded closed curves which are asymptotic to squares. For n = 4 the curve looks like this:

x⁴ + y⁴ = C

It turns out this geometric shape has been given a cute name: squircles (Who said geometry has to be dull?) The entire family is known as supercircles. And of course, there is a analogous generalization for ellipses known as superellipses. (I don't think there's a "sqellipse", however - and maybe that's just as well).

This page allows you to generate supercircles for different values of n. (Incidentally it uses Walter Zorn's very slick jsGraphics library for generating pixel & vector graphics on web pages).

Useful? Sort of - Wikipedia has a few examples, mostly in the decorative arts. And I'm betting that a concept this elegant is bound to turn up in lots more places. So maybe I should add this to JTS, just to - ahem - get ahead of the curve.

En l'an 2000

The Bibliotheque Nationale de France has an online exhibition of a vision of the world in the year 2000 - published in the year 1910. It's interesting to see what the artist got right, and what he got wrong. Air-Sea Rescue - but also radium fireplaces. He correctly predicted that electric power would replace human labour - but he didn't foresee that the biggest impact would be from automating thought rather than muscle.

He also didn't see that the fashions of 1910 would not be a la mode in 2000. But it's an appealing vision... I'm still hoping for my personal monoplane to get me to work.

Bursa-Wolf transformations explained

.. courtesy of Adrian Custer on the OpenJUMP mailing list:

> > just one question .. what is this bursa wolf parameter option?

> My impression is that this is scary math I never quite understood.




Well, Bursa was a 9 year old bicyclist from the Alps and...no, no, no, i
lie. Actually it's not particularly scary math and quite easy to
understand. All you really need to remember is that no one has ever been
to the center of the earth.



So everyone started surveying (mostly so the repressive central
governments could exploit taxes from people and have lots of jolly wars
where people could slog through the mud and kill each other so they'd be
blood and suffering for all). Each group started from some random place
on the surface of the earth. Right away, it becomes obvious to everyone
that euclidean rules don't work so well. Some didn't care so much since
taxes are basically arbitrary anyway and getting serious about it means
you'd have to walk through fields and woods and get lots of mud on your
shoes. Others kept at it and resorted to spherical geometry. Once you
start doing that precisely and at continental scales you realize that
doesn't really work either so you decide to try the next hardest thing,
an ellipsoid of rotation. Now how do you know which one to choose? Well
you pick one that minimizes your squared errors. All good and nice but
(1) you are surveying the ground which is anything but an ellipsoid
since it has all those ditches you keep falling into and that keep
getting your clothes covered in mud and (2) you are not perfect
especially with all that mud on your paper. So you have a bunch of
errors. Well everyone that does this comes up with lots of different
ellipsoids that work really nice for their data and everyone is sure
they clearly have found the 'one true ellipsoid' and they decide to use
that for all their work. Then everyone guesses where they actually are
on each of their particular ellipsoids which involves lots of going
outside at night and looking up from the mud at the stars. But then it's
not like the edges of each survey was nice and level on these ellipsoids
either --- think of the eastern USA. You can start nice and clean and
warm and dry at an inn in Boston on the edge of the sea drinking clam
chowder and having a good time but a few months later it will be bitter,
bitter cold in that tiny town of Denver because you are somewhere like a
mile high up in the air and you're wet and covered in mud from slogging
through the plains in a snowstorm. So you've got a pretty good idea that
your data is on a major slant but, well, you'll do your best to make up
for it but it really doesn't help the effort any, especially what with
all that mud that's still itching in your hair. So your errors may be a
wee bit big but hey it's all right: it's good enough to wage lots of
good wars with lots of mud and blood and to keep collecting lots of
taxes so no one cares too much.



Fast forward to more recent times where some people want to talk to lots
of different governments and work with lots of different data. They take
everyone's guess and try to line them up. Well it turns out, when you
try to line everything up, that the center points of all the different
ellipses aren't really the same points and even the orientation of the
three axes are all a bit off because of how everyone guessed where their
were on their ellipsoids. So now, to go from one data set to another so
they line up "the best," you need estimates of how much to rotate each
of the axes and how to shift the center point around; all this beyond
even the obvious stuff of changing between the different definition of
all those "one true" ellipsoids.



When you do this mathematically, you need a bunch of parameters: these
now have the names of the wolf and the bursa. Generally, you can only
come up with good parameters if you have lots of data to compare and
some good software to do the comparing. That's what the EPSG did for
everyone. The guys in the pickup trucks that went out looking for oil
kept falling into ditches along the way and getting mud on their faces
but when they got back to the office they had a good sense of what lined
up with what and could say: "yep, that hill there is the same as this
squiggle here and there's this big ditch right here that cost us our
third flat tire and..." So they collected as much data as they could and
compared it and came up with a database of parameters by which you go
from one data set to another. So that's it. That's why we use their
data; we don't have to fall in any ditches and can avoid getting mud on
our clothes. They give us their parameters and we can mostly line up
data from one survey against data from another. But you do need some
good parameters because the earlier folk had a harder time of the mud
and the data they created don't just line up the way we would like them
to.



Actually doing the math is a bit harder but the concept is pretty
straight forward: geographic data all ultimately gets tied into points
on the earth surface and that requires estimating where the points
really are and how they line up on the estimated ellipsoid being used.
That in turn means none of ellipsoids quite line up and we need
parameters to move between them.



--adrian

Office 2.0

Office 2.0 is an index of Web-hosted applications. The entire list is pretty overwhelming, but more immediately interesting is the list of Web apps that the site's creator uses as his "everyday applications"

Maybe there's something to this Web thing after all...

Late notice: Waterfall 2006 conference on Project Management

Here's an important conference which unfortunately I missed last year. But no matter - the content is timeless, so no doubt it will be held over and over again with exactly the same presentations.

Quote of the day - C. A. R. Hoare

There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.

- C. A. R. Hoare