Month: July 2006

I was thinking about the problem of corruption and how systems of accountability tend to reduce corruption. I then thought of how this relates to the patent system. Part of the problem with the patent system is a lack of accountability.

Originally I came up with a list of 10 steps to fix the patent system, but this doesn’t fix the underlying problem, which is the patent lawyers themselves. So here’s a simpler version that will do a better job.

How to fix the patent system in 3 easy steps

1. Patent lawyers make minimum wage.
2. Every patent granted pays a bonus of $10,000, 10% as an end-of-year bonus and the majority after the patent expires.
3. If a patent is overturned in court, the legal fees incurred to overturn the patent are reinbursed to the challenger and come out of the bonus.

So there you go. If the patent lawyers do their jobs and only grant meaningful, non-obvious patents they can make a great wage. If they do the job they are currently doing they make squat, which with the current state of the patent system is what they deserve. Companies win because the cost to fight frivolous patents comes from those responsible for granting them in the first place.

In RakNet, when I sent a message I put it on a queue. When an acknowlegment arrives, I look at the head of the queue and assuming that acknowlegement matches what is there, I pop the queue. Most of the time that works great – O(1) both ways. But there is a problem – with large blocks lost, you get the folloowing bug:

(assuming I missed out on elements 0-1000)
Search through a 1000 element list for element # 1001
Search through a 1000 element list for element # 1002
Search through a 1000 element list for element # 1003
Search through a 1000 element list for … 2000

Assuming the list went from 0 to 1000, this is 1 million iterations because in the worst case I did a linear search through the queue.

This rarely happened because usually acknowlegements came in the order I did sends, so 99.99% of the time there wasn’t a problem and it was O(1). But I needed a data structure that, given input not in the set, would still do a relatively fast find. However, it also had to do fast insertions and deletions (which was why I used a queue to begin with).

I could have used my AVL Balanced binary tree. It’s a binary tree that automatically rebalances after every insertion and deletion. It’s pretty good for unsorted data – finds, insertions, and deletions are all Log2(n). However, I wrote it back in college so it wasn’t as efficient as it could be. The main problem was that there was a lot of node creation and destruction.

I also wrote a B Tree and a BPlus tree in college. A BPlus tree is an n-way tree of order o where each node contains o keys and o+1 children. Each leaf contains an ordered list of key/data pairs. The leftmost child of a node points to the subtree where all keys are less than node key 0, the child o+1 is the value of the lowest key of that subtree, and so on. All leaves are linked in a linked list. In essence, it’s an ordered list divided up among leaves with the branches of the tree pointing into that list.

I thought it would be a one day at most project since that’s about how long it took me in college. However, I did two things differently:
1. I didn’t remember how to do it. Thinking it would be easy, I started coding without full understanding of the data structure.
2. I wanted something very optimal so went to extreme lengths to make it so.

So it took a week 🙁

Anyway it’s done now and it’s a good data structure. If you need an ordered list where insertions, deletions, and searches are all fast, and/or you want to linearly traverse the list, a B+ is the way to go. If you need fast insertions, deletions, and searches but your data doesn’t have to be ordered and you don’t need linear traversals very often, an AVL tree is slightly more efficient.

It’s in RakNet as the file DS_BPlusTree.h.