B-Trees – Balanced Search Trees for Slow Storage

Another cool, but frequently overlooked, data structure in the tree family is called the B-tree. A B-tree is a search tree, very similar to a BST in concept, but optimized differently.

BSTs provide logarithmic time operations, where the performance
is fundamentally bounded by the number of comparisons. B-trees also
provide logarithmic performance with a logarithmic number of
comparisons – but the performance is worse by a constant factor. The
difference is that B-trees are designed around a different tradeoff. The B-tree is designed to minimize the number of tree nodes that need to be examined, even if that comes at the cost of doing significantly more
comparisons.

Why would you design it that way? It’s a different performance tradeoff.
The B-tree is a da
ta structure designed not for use in memory, but instead for
use as a structure in hard storage, like a disk drive. B-trees are the
basic structure underlying most filesystems and databases: they provide
an efficient way of provide rapidly searchable stored structures. But
retrieving nodes from disk is very expensive. In comparison to
retrieving from disk, doing comparisons is very nearly free. So the design
goal for performance in a B-tree tries to minimize disk access; and when disk access is necessary, it tries to localize it as much as possible – to minimize the number of retrievals, and even more importantly, to minimize the number of nodes on disk that need to be updated when something is inserted.

Continue reading

Petabyte Scale Data-Analysis and the Scientific Method

Once again, there’s a silly article somewhere, and everyone hammers me with requests to write about it. It’s frankly flattering that people see
this sort of nonsense, and immediately think of asking me about it – you folks are going to give me a swelled head!

The article in question is a recent article from Wired magazine, titled “The End of Theory: The Data Deluge Makes the Scientific Method Obsolete”.

Continue reading

"Market based" College Evaluations

I’m a bit late to the party on this, but I couldn’t resist
saying something.

A rather obnoxious twit by the name of Richard Vedder has set up a
front-group called “The Center for College Affordability and Productivity”. The goal of this group is purportedly to apply market-based mechanisms to the problems of higher education
in America. When you take a look at their “research”, you’ll quickly recognize that this is astroturf, plain and simple.

A typical example of this is described in an article Dr. Vedder recently wrote for Forbes magazine about a supposed research study done by his organization on college rankings. According to Dr. Vedder, the popular “US News and World Report” college rankings are no good, and that market-based principles can produce a better, more meaningful ranking. The rationale for this new ranking system is that the standard rankings are based
on the input to the schools: schools are ranked based on the quality of students admitted. Dr. Vedder wants to rank schools based on outcomes: how well the school achieves the goal of
turnings its students into educated, successful people after they
graduate. According to Dr. Vedder, his ranking system tries to rank
schools based on several “output” measures: “How do students like their courses?”, and “What percentage of students graduate?”, “How many awards do the students recieve?”, and “How successful are students after they graduate?”

Continue reading

Friday Random Recipe: Homemade Tonic Water

This is an interesting recipe, in a very unusual vein for me.
Homemade tonic water.

I hate tonic water. I really despise the stuff. But like a lot of
people, I have some strange twitchy muscle ticks, in my legs and my
eyelids. A few years ago, I was talking to my opthamologist about the
eyelid twitch thing, and he said that while there was a prescription
drug that he could give me for it, he’d found that most people got
more relief from just drinking tonic water. The quinine that gives it
its distinctive bitter taste works better than the prescription. So I
gave it a try. It didn’t actually do a whole lot for my eyelid thing,
but it did wonders for my twitchy legs at bedtime. So ever since, I’ve
forced myself to drink the stuff.

Then a few weeks ago, I saw a link to a recipe for homemade tonic
water
. I decided to give it a try. I couldn’t get exactly the
ingredients that were suggested, so I add libbed a bit. The end result
was fantastic. It’s got a strong bitter quinine bite, but
it’s also got a wonderful flavor in addition to the quinine. This
variation is particularly good mixed with a nice white rum or cachaca.
If you leave out the cardamom, it’s great with bourbon. (I know gin is
the traditional addition, but I just don’t like the taste of gin.)

With this, for the first time, I can easily imagine drinking
tonic water even if it didn’t have any useful medicinal qualities.

Here’s my recipe.

Ingredients

  • 1/8 cup powdered chinchona bark.
  • Zest and juice of one orange.
  • Zest and juice of one lemon.
  • Zest and juice of one lime.
  • 1/2 tsp allspice berries.
  • 1/2 tsp cardamom pods.
  • 2 cups water.
  • Pinch salt.
  • Agave syrup; about 1 1/2 cups.
  • Seltzer water.

Instructions

  1. Put the water in a pot on high heat. Add all of fruit and
    herbs.
  2. When it comes to a boil, reduce to a simmer, and let it cook
    for about 20 minutes.
  3. Let it cool. Strain it through a paper coffee filter. (This
    takes a long time, but if you don’t use the paper filter, a lot of
    the chinchona powder will stay in, and you don’t want to get a
    mouthful of it; it’s incredibly bitter.)
  4. Add water to bring the volume back up to two cups.

You’ve now got the basic concentrate for tonic water. You can
either mix the agave in now, or you can do it when you make a glass
of tonic. It’s less work to just add the syrup now, but the
concentrate will keep longer if you don’t. I don’t mix them.

To make the tonic, mix together two tablespoons of concentrate
(more if you like it extra bitter), and about 1 1/2 tablespoons of
agave syrup. Then add one cup of seltzer water.

You can use a basic sugar syrup instead of the agave; the standard
bar mix simple syrup substitutes with roughly the same quantity. But I
think that the agave is better. Agave has a slighly different
mouthfeel than cane sugar, and I think that it sweetens and smooths
out the tonic without cutting too much of the bitterness. Cane sugar
to me either doesn’t taste sweet enough, or kills the edge of the
tonic.

To make a killer rum&tonic, take a nice light rum or cachaca
(Cachaca is a brazilian liquor made from sugar cane juice, rather than
from molasses; it tastes like a mild rum with a bit of grassiness),
and mix it, 1 part rum to 3 parts tonic, and serve over ice.

The one problem with this recipe is that Chinchona bark is kind
of hard to find. The most common source of it is flaky herbal medicine
stores. But some of the really large online spice shops have it. I
bought a bunch from a place called “Tenzing Momo”. They definitely
qualify as “flaky herbal medicine store”, but they also carry a really
good selection of cooking herbs and spices. Chinchona is sold by the
ounce; one ounce is about 1/4 cup.

Friday Random Ten, June 27

I haven’t done a FRT in a while.

  1. Mogwai, “Kids Will be Skeletons”: a typical Mogwai
    track; brilliant post-rock.
  2. The Redneck Manifesto, “Bring Your Own Blood: more
    post-rock in the same general vein as Mogwai. This one is a bit
    up-tempo, with a very cool rythym.
  3. Gogol Bordello, “Dub the Frequencies of Love: an Eastern
    European gypsy punk band doing reggae. Insane, but very cool.
  4. Tony Levin, “Beyond My Reach: A few years ago, the god
    of the Chapman stick finally started recording some of his
    own music. He’s got a surprisingly good voice. The album is
    terrific, ranging from some solid prog tracks, to some fun pop tunes
    to very well done ballads, like this one. Even in a mellow ballad
    like this, he manages to work in some very impressive stick work.
  5. Hawkwind, “Seven by Seven”: very old progressive/space
    rock. I just recently discovered Hawkwind, and was very surprised. I
    thought that I knew about all of the first wave of prog-rockers. And
    yet, these guys are famous and influential, but I somehow totally
    missed out on them. They’re utterly brilliant. They’ve got a lot of
    the typcial hallmarks of the early proggers in their sound – there’s
    some similarity to Van Der Graff Generator, early Genesis, Syd
    Barret era Pink Floyd; but they’re got their own unique distinctive
    sound within that style. Really great stuff. This is a very typical
    Hawkwind track; lots of very spacy sounding stuff, against a
    complex structure. Highly recommended.
  6. IQ, “Red Dust Shadow”: from early prog-rock to neo-prog.
    IQ is a neo-progressive band that got started around the same time
    as Marillion. They’re led by a guy named Peter Nichols, who’s got a
    voice that sounds a lot like Peter Gabriel. They’re a really
    fantastic band.
  7. Marillion, “Tumble Down the Years: more neo-progressive.
    I’m a huge Marillion fan. I started listening to them back in 1985
    or so, and I’ve been a continual fan ever since. This is a sweet
    little romantic song from them. Typically for Marillion, even when
    they do a poppy little sappy song, it’s got some beautiful structure
    interesting harmonies, and great transitions.
  8. Naftule’s Dream, “Free Klez”: Very radical experimental
    Klezmer. Ornette Coleman meets Naftule Brandwien on acid.
  9. Tony Trischka, “Celtic Melody: unaccompanied banjo
    played by my former banjo teacher. (He’s also Bela Fleck’s banjo
    teacher.) Amazing technique. No one can play the banjo like Tony –
    when Tony’s on, not even Bela can match him. This is a medley
    of a couple of very traditional Irish tunes, played with absolute
    perfection.
  10. IQ, “You Never Will: another IQ track, from the same
    album as “Red Dust Shadow”.

Fundies and Limited Deities

So I hear, via the Panda’s Thumb, that Uncommon Descent has a new
poster. And he’s off to a rollicking good start, with a post
explaining why Christians who accept the fact of evolution are
incoherent and deluded. (As usual, I don’t link to UD, due to their rampant
dishonesty in silently altering or removing links.)

I am, perhaps, not the best person to respond to his claim, given
that I’m not a Christian. But his argument is so inconsistent, and so
typical of a type of argument that constantly occurs in fundamentalist
gibberings that it doesn’t take a Christian theistic evolutionist
to point out its glaring errors.

Continue reading

Torah and Relativity: Attack of The Jewish Cranks

UPDATE(9/1): In a move that, frankly, astonished me, the author of the piece that I mocked in this post has withdrawn the article, because he’s recognized its errors. And he didn’t just withdraw it – he came back to this blog to explain the withdrawal. I’ve never seen a fundamentalist writer admit to errors this way. Most
authors of what I consider bad religion/science/math either ignore their errors, or silently pull the erroneous articles and pretend that they never existed. The way that
Mr. Bar-Cohn handled this is an excellent example of how honest people with genuine integrity behave. Mr. Bar-Cohn has earned a great deal of respect for me by doing this.)

Since I’ve been writing GM/BM, I’ve frequently mocked Christian
fundamentalists who make stupid arguments based on bad, or (even
worse) no math. I’ve also taken on some Muslim idiots a couple of
times. But I’ve frequently receieved emails asking why I’ve never done
the same thing to Jewish idiots. (Actually, it’s usually not really
asking, but more making accusations that I go easy on Jewish
arguments because I’m a Jew. Usually as a part of some nasty screed
about how I’m part of the Great Jewish Conspiracy to Take Over the
World.)

The real reason that I haven’t dealt with Jewish fundies before is
just because people don’t send me good links. Until now, I haven’t
known of any particularly good Jewish fundy nonsense to write about.
The only major bit of Jewish bad math that I knew about was the infamous “Torah
codes” or “skip codes”
, which had been well and thoroughly done to
death long before I started blogging.

Then, a few weeks ago, someone sent me a great link to a
relativity denial thing, arguing that the Torah demonstrates the
falsehood of relativity using some really wretchedly bad
math. It managed to combine a bunch of my favorite kinds of lunacy,
all in one hysterical package: religious stupidity, horribly bad math,
relativity denial, gematria, bizzare interpretations passed off as
literalism – it hit pretty much all the buttons! It was glorious, the
kind of stupidity that I really relish! I didn’t immediately write
about it, because I wanted to wait until I had time to do it justice.
A quick off-the-cuff mocking wasn’t enough for such high-grade insanity.
And then, being an idiot, I lost the link!

Yes, I really am an idiot sometimes. I could have sworn that put
that link in my “crackpottery” folder in my Safari bookmarks. But no,
it’s not there. And I only keep one week of history in my browser, so
it’s not there either. I lost one of the best cranky links ever to
come my way! If anyone happens to come across an argument from
gematria on why relativity can’t possibly be true, please
forward it to me. I really want to find that gloriously idiotic
mess!

But fear not – all is not lost. (Looking at this as I’m doing a
final editing pass, I’ve got to say that I’m sounding like Orac lately. But hey,
he’s the guy who inspired me to start GM/BM, so how bad could that
be?) While googling to try to find it, I found something almost – not
quite, but almost – as good. It’s a website run by an organization
called the “Torah Technology Institute”, which features an article by
David Bar-Cohn, called Kehushah and Time
Dilation
, which attempts to argue that there’s a connection
between relativity and the presence of God: they argue that a literal
reading of the Torah shows that the presence of God has a relativistic
time-dilation effect.

Continue reading

Perpetual Motion via Fuel Cell

Via several blogs, including the normally wonderful Making Light comes a link to an obnoxious Reuters’ story that once again demonstrates just how scientifically and mathematically illiterate reporters are.

We have yet another company basically claiming to have invented a perpetual motion machine. From Reuters:

Tired of petrol prices rising daily at the pump? A Japanese company has invented an electric-powered, and environmentally friendly, car that it says runs solely on water.

Genepax unveiled the car in the western city of Osaka on Thursday, saying that a liter (2.1 pints) of any kind of water — rain, river or sea — was all you needed to get the engine going for about an hour at a speed of 80 km (50 miles).

“The car will continue to run as long as you have a bottle of water to top up from time to time,” Genepax CEO Kiyoshi Hirasawa told local broadcaster TV Tokyo.

“It does not require you to build up an infrastructure to recharge your batteries, which is usually the case for most electric cars,” he added.

Once the water is poured into the tank at the back of the car, the a generator breaks it down and uses it to create electrical power, TV Tokyo said.

Whether the car makes it into showrooms remains to be seen. Genepax said it had just applied for a patent and is hoping to collaborate with Japanese auto manufacturers in the future.

Most big automakers, meanwhile, are working on fuel-cell cars that run on hydrogen and emit — not consume — water.

There’s just one problem. This is completely impossible.

Continue reading

The Koranic Speed of Light

A reader sent me a really wonderfully wacko link. It’s a fundamentalist islamic site, which tries to use relativity to argue for the divinity of the Koran. It’s remarkably silly. (I also recently got a link to something similar, but from a Jewish perspective – claiming that the Torah disproves relativity. Alas, I screwed up and lost the link; if whoever sent me that link could re-send it, I’d really appreciate it!)

The claim that relativity proves the Koran is true. See, they claim that the Koran tells you what the speed of light was, and that the real absolute speed of light as described by relativity is stated in the Koran, and that it’s tied to the muslim Koranic lunar calendar.

Continue reading