The first thing that came to mind when I saw this preso was "What algorithm are they using to find the words?" The problem looks something like: Given a string of characters, find all possible words that start and end like the string of characters and use any number of characters in between.
The best I can come up (after not so much thinking about it) with is using Bloom Filters. Precompute the bit vector for every word in your dictionary, then after they swype, compute a vector for the string of characters and run it up against all the words in your dictionary that start and end with the same letters. Still kind of an expensive linear search, albeit fast (since it's just boolean AND).
You also get a hint from direction changes. As far as I can tell, direction changes almost always indicate that the current letter is in the word, though not every letter gets a direction change.
The first thing that came to mind was "Newton," which used stroke-recognition for recognizing letters. I doubt it's actually computing letters on the fly, I go along with your thought that you precompute vectors for each word in the dictionary. My thought is that the vectors are probably very simple. They may start with a specific letter, but after that I'm guessing they are very forgiving of inaccuracies. A rough direction and distance is probably enough to disambiguate words from each other.
I'm guessing it precomputes a tree for the dictionary. With each stroke, it drills down the tree along the most likely path. If it runs out of nodes, it backtracks and tries a more likely path somewhere,possibly using a precomputed list of vectors most likely to be mistaken for each other.
I doubt they use bloom filters (or any other hash-based algorithm) because hashes by their design are a quick way to reference something well defined. A gesture is anything but and you need something a lot more fuzzy and flexible than hashes.
I'd think that they try to calculate the focus of each direction change and see what letter it landed on, then try a fuzzy match to words that have the smallest hamming distance between their input. After you get a good approximation of all the letters, then you can try hashing techniques.
Also, pivoting on first and last letter of each word isn't fool-proof, as the first and last letters are also not guaranteed to be hit dead-on.
I would have to go with what Natrius said. It's probably based on the stroke directions. The technology is probably very similar to that used to recognize Chinese writing.
The best I can come up (after not so much thinking about it) with is using Bloom Filters. Precompute the bit vector for every word in your dictionary, then after they swype, compute a vector for the string of characters and run it up against all the words in your dictionary that start and end with the same letters. Still kind of an expensive linear search, albeit fast (since it's just boolean AND).