Skip to content

Short evaluation of neighbor detection using topojson

7. June 2013

This will be only a quick and (maybe) dirty evaluation of the neighbor detection that I’ve implemented: http://wwwpub.zih.tu-dresden.de/~rklammer/html/vorlagen/RKMapping_neighbor_finding.html

I’ve written a simple function that evaluates the neighbors of a feature, by using the ArcGeometries extracted from a topojson file, that I’ve described in previous posts (1, 2).

After that, I found out, that there is also a function for neighbor detection included to topojson.js … but … it seemed to be a bit slower than my version … this has to be analysed!

My method

Pretty simple…just do this for each feature:

  1. loop through the geometry of a feature
  2. extract all arcs (at least only there id’s)
  3. analyse the members of each arc (arc has to have the info about its members included for that)
  4. 1 member = no neighbor – 2 members = a neighbor

Actually, I am a noob JavaScript-programmer and do not understand the syntax of topojson’s neighbor detection to 100%…so I will not try to describe that!

Analysing the performance

The analysis will be a little bit dirty, as I will not calculate an arithmetic mean of many test results. This is possible, as I am more interested in the relative time differences, between datasets of different feature amount, than in their absolute values! As you can see (and test by yourself) in the interactive test scenario, I used:

  • municipalities:
    • clipped –> 2946 features
    • full        –> 11626 features
  • states (full) –> 16 features
  • counties (full) –> 402 features

Now…lets have a look at the table!

 
topojson
.neighbors()
getArcs()
get
Arcs
Of
Neighbores()
States (full)
(16 features
1,164
seconds)

full_states
0,008
seconds
0,058
seconds
0,002
seconds
Counties (full)
(402 features
2,985
seconds)

full_counties
0,185
seconds
0,277
seconds
0,008
seconds
Municipalities (clipped)
(2946 features
3,083
seconds)

clipped_muni
1,005
seconds
0,191
seconds
0,013
seconds
Municipalities (full)
(11626 features
26,638
seconds)

full_muni
18,513
seconds
0,940
seconds
0,016
seconds

Basically, my own function seems to be faster than the topojson function. But I need the ArcCollection for being able to detect the members of each arc…so I have to include the processing time of that too. That is why the table contains a column for the getArcs() as well for the getArcsOfNeigbors() functions.

Processing, only 16 german states, took all together 0,06s which is compared to 0,008s way more processing time. That means topojson is ca. 85% faster than my function.

This seemingly advantage is also detectable for the processing of 402 county features. There we have 0,285s (total) against 0,185s, what is only ca. 35% faster then my function.

I said seemingly, because the next two datasets show the difference in performance between both functions. The processing of the ArcCollection still takes way more time than following neighbor detection, but all in all it takes 0,204s while topojson.js takes 1,005s. Now my function is ca. 80% faster.

This first indication is manifested by the last, hughest dateset (11626 features). Here, topojson.js takes long 18,513s while my function takes only ca. 1s. That is a ledge of ca. 95%…WOW!

But that seems to be a little bit strange. Topojson’s processing time is rising uproportionally and I do not have a clue why. The processing time of my function, in contrast, grows proportionally…at least the getArcsOfNeighbors() function, which processes super fast!

Finally, let’s have alook at the growth:

Number of features:

  • 2512% (16 – 402)
  • 733% (402 – 2946)
  • 383% (2946 – 11626)

Processing time – topojson.neighbor():

  • 2313% (0,008 – 0,185)
  • 543% (0,185 – 1,005)
  • 1842% (1,005 – 18,513)

Processing time – getArcs() + getArcsOfNeighbors():

  • 475% (0,06 – 0,285)
  • – 29% (0,285 – 0,204)
  • 490% (0,204 – 1,000)

There you can also see the unnormal growth of processing time, for the topojson function. It is not associated with the growth of number of features…a growth of 1842% is almost five times the feature growth (383%)!

On the other hand my implementation does has also have an unproportional growth. At least the getArcs() function processes 2946 municipality features faster then 402 county features. It is a fact but not as drastic as this exemplary values indicate…average mean for 10 test processings:

  • Counties (full): 0,157s
  • Municipalities (clipped): 0,148s

That is strange and I have to investigate on that more deeply…

 

Advertisements
One Comment
  1. Hi Ralf. I couldn’t find your email address or Twitter handle, so I thought I’d reply here. I rewrote topojson.neighbors and it is now about two orders of magnitude faster. For example, you can compute the neighbors of a set of 3,600 U.S. counties in about 15 milliseconds (previously ~1.3 seconds). Details here, and thanks for prodding me to look into it:

    https://github.com/mbostock/topojson/commit/e6ffa562ed86e6bbf34286812305f8737397d022

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: