Monday, August 25th, 2008

If you claim high scalability…

Filed under: Academia/Research — Daniel Lemire @ 14:56

I just reviewed a paper where the authors come up with a nice highly scalable algorithm. And it is really scalable too! But to prove just how fast it is, they process 2,000 data points.

This is correct, strictly speaking. Their algorithm runs in O(n) time, so to know how long it would take to process 1000 times more data, just multiply by 1000.

But where is the fun in that?

2 Comments »

  1. Their algorithm runs in O(n) time, so to know how long it would take to process 1000 times more data, just multiply by 1000.

    Is that even true? It ignores memory hierarchy effects.

    Comment by D. Eppstein — 25/8/2008 @ 15:38

  2. But where is the fun in that?

    What do you mean?
    Not trusting a “proof” over only 2000 datapoints?

    Comment by Kevembuangga — 26/8/2008 @ 2:22

RSS feed for comments on this post.

Leave a comment

Warning: When entering a long comment, please ensure that you make copy of your text prior to submitting it. If the server should fail or if you hit a bug, you might lose your work. I am not responsible for your lost effort.

To spammers: I carefully review every single post and make sure that spam gets deleted. You are wasting your time if you are manually entering spam using this form. Read my terms of use to see what I consider to be abusive.

Example: I + II + IX= XII. Yes, you have to enter a roman numeral. (Answer must be in upper case.)

« Blog's main page

30 queries. 1.156 seconds. Valid XHTML

Powered by WordPress

© 2004-2008, Daniel Lemire (lemire at acm dot org). This work is licensed under a Creative Commons License.

Subscribe to this blog in a reader or by Email.