Free stuff!

One of the few economic advantages of going back to school is that people seem much more inclined to give you stuff for free. I can get MS Office for free. I can get legal counseling for free (emotional counseling, too, but I'm hoping it doesn't come to that). There's always some free entertainment going on at campus. One of the best freebies is that I get to ride mass transit for free. Really! Not discounted; totally free. This is a big deal for someone who grew up in an area where public transportation was pretty much the only viable option for getting around.

Today, I rode in to work on the bus. The bus takes the same route I would drive and does it in about the same amount of time. Granted there is a mile on either end getting from the closest stops to my endpoints but, I can just add another mile or so in there and it counts as my morning run. It's still less efficient time-wise than driving in, but it does enable running home from work (running both ways is 17 miles, which is way more than I want to do every day).

Getting from work to school is a bit more problematic. There are multiple transfers involved. The bus route takes an hour whereas I can drive it in 30-40 minutes. At least in that case it is truly door-door service, so I could bring something to read and recover a good bit of the time. The rub would be getting from school to home. It would mean getting home pretty late though, again, I could use the time to read which is obviously not an option if I'm driving.

Potential thesis topic

I'm meeting with my adviser today so I thought I should write down some thoughts on my research. Here's what I've put together:

I'm interested in the application of sampling theory to database queries. The success criteria for a useful method includes the following:

• Run time must be significantly faster than simply pulling the full result directly using all rows available.
• The result must produce not only a point estimate, but a confidence interval on that estimate. Ideally, both 1- and 2-sided intervals are supported.

The first criteria significantly reduces the applicability of pseudo-random sampling at the row level, since pulling individual random rows from a database is a relatively expensive operation. Thus, clustered sampling techniques show more promise. However, adjacent database rows tend to be highly correlated, so the use of clustered techniques widens the resulting confidence interval for a given sample set and introduces complexity into the confidence calculation itself.

Kerry and Bland (1998) indicate that "The main difficulty in calculating sample size for cluster randomized studies is obtaining an estimate of the between cluster variation or intracluster correlation." This problem has led to multi-stage sampling techniques where the inter- and intra- cluster variations are estimated at each stage and used to predict a sample size needed at the next layer of refinement. Several epidemiological studies where attaining a true random sample is prohibitive due to geographical constraints have demonstrated this technique (e.g., Galway et al, 2012)

Such methods have their detractors (e.g., Luman et al., 2007), generally claiming that clustered methods consistently overstate results when the variability between clusters is significantly higher than the variability within clusters. In response to this, the World Health Organization has layered various heuristics on top of the cluster selection method to improve performance of estimates of vaccination coverage (Burton et al. 2009). They concede, however, that reliable power estimates are problematic, if not impossible, under their methodology.

The goal of this research is to develop methods for extracting unbiased clustered samples from large databases while retaining the ability to perform power calculations. Some areas to explore are:

• Using background processes to continually analyze the data to develop better correlation estimates which can be used by subsequent query processing to optimally select clusters.
• Similarly, background processing can be used to extract a row-wise pseudo-random sample database that can be used for exploratory queries.
• Using the convergence of the point estimate as an indicator for a stopping rule. That is, refusing to accept that a confidence interval has been met if the point estimate is still showing greater variability with each query iteration.
• Using the convergence of other correlated characteristics of the data as in indicator for a stopping rule (e.g., if one was estimating the cash flows from of a group of insurance policies, one could consider the more volatile component of projected claims since convergence on that item would imply convergence on the far more stable components of premiums and expenses.

Presumably, a more thorough literature review will turn up lots of other avenues to explore as well; these are just a few things that I've thought of so far.

Cheating

So, today in Algorithms we looked at using recurrence relations to prove the asymptotic bounds on run time. The trick, of course, is guessing the right function to begin with. Sure, there are some patterns that are recognizable but, it seems to me that if you already have the algorithm, the simple way to generate a decent guess for the asymptote would be to simply code the algorithm and time it on a range of data sets. The shape of the curve should be pretty apparent; there aren't too many algorithms so complicated that they don't converge to their asymptotic behavior pretty quickly. Maybe mathematicians think that's cheating.

Publish or perish

I'm thinking I should write a paper. Publishing something would score some big points with the UMSL faculty at a time I really, really, want them to transfer a lot of credits from my Master's work. So, I'm looking at potential topics:

• A method for pulling non-rectangular areas out of an OLAP cube. This one is the most obvious candidate because I've already done the work. I just need to write it up. My current employer can't even get mad about it because most of the research was off hours and they never implemented it (though we certainly had it ready to go). Basically, we put a superstructure on top of all the business attributes that allow us to build a hierarchy where the selection criteria at deeper levels is dependent on the selection already made at higher levels. It's actually pretty kick-ass. I have no idea why our users didn't fund the development because it's exactly what they asked for. Anyway, one of the other architects and I got far enough with the design that I could implement a rough version with probably only around 40 hours of work. That would be enough to collect some metrics on performance (to show that it's better than just running a bunch of independent queries and then trying to tie them together with PowerPivot) and write up the results.
• The Ultrarunner's Guide to Long IT Projects. I know this sounds fluffy, but it's really not. I have a ton of experience in both of these areas and the overlap in successful strategies is no coincidence. The two disciplines require the same mindset. Not sure where I'd publish this, but I've given it a fair bit of thought and I think I could write a pretty good paper in 20-30 hours. Or, I could do a really fun interactive presentation. If I can find an appropriate forum, that might be the way to go.
• Test Driven Design for database programming. TDD is all the rage but, if you're going to enforce the criteria that unit tests can't hit the database, you're pretty much S.O.L. trying to apply this to database programming. I've found some ways to relax that rule that don't violate the other tenets of good unit test design or of TDD in general. I could probably write this one up quicker than the other two, but I'd have to spend a good bit of time making sure that I wasn't repeating what someone else has already said. I haven't seen anything in the literature about it, but I could have easily missed it. 

Asymptotic Convergence vs. Bounded Domain performance

Much of what we're looking at in Analysis of Algorithms is Asymptotic Convergence. This is the traditional way to assess an algorithm's performance. Basically, it's looking at the shape of the bounding curve as the amount of input data goes to infinity. That's all well and good but, in reality, the input data doesn't go to infinity. There's some point at which, either due to the problem itself or limitations of the system, that the data size reaches a bound of it's own.

At work we've exploited this fact and designed systems to be performant within a bounded domain. For example, the system I spend most of my time on is a big ETL engine that takes submissions ranging from a few thousand to several hundred million input rows. The Translate step of the ETL does pretty much the same thing for each row, so the process is O(n). However, we scale out onto a 32-node grid. We chunk the process into groups of roughly 200,000 rows. So, for data sets between 200,000 and 6.4 million rows (200K * 32), we have a constant-time process. Anything less than 200K rows processes so fast, nobody cares about performance, so the only submissions that are affected by O(n) processing are the relatively rare submissions larger than that.

It's not that we don't care about the asymptotic performance; we get submissions as large as 60 billion rows, so we do need to be cognizant of what that does to the system. But, by setting a bound on the data that we wish to optimize and then tuning the system for that, we can deliver performance levels much better than what we could if we had to tune to worst case performance.

Week 1 status

I went to a wedding reception last night and a lot of my friends were there (the bride and groom are both ultrarunners, so a pretty good portion of the guests were folks I know from racing). Naturally, I got a lot of questions about how school was going. I've been fielding such queries at work, too.

The answer, of course, is that it's going fine, but that shouldn't be a surprise after just one week. It reminds me of the early parts of marathons where spectators will cheer you at mile 3 saying, "Looking good!" Well, I should hope so. If you're in trouble at that point, there isn't much chance of even finishing much less doing well.

That said, there is cause for optimism, even at this early stage. I have managed to get the books out every day. I'm up to date on reading and have done every problem at least in my head, if not formally writing it out. The adjustment back to classroom learning wasn't as big as I thought it might be. There's a very long way to go, but so far, so good.

Lead time

Finished reading the chapter on the history of language development this morning. One thing that really hit me was the amount of time it takes to get a language out the door. I realize that designing a language is no small thing and neither is building a good implementation, but I would have thought 5 or 6 years would be enough time to do that. It appears to be closer to 10. Many languages put something out in less time, but the version that gained wide acceptance is usually a decade after the idea got a green light.