Genius hour

Mildly off-topic post tonight.

My daughter's grade did their "Genius Hour" presentations this evening. They basically get an hour a week in school to research whatever subject interests them and then they put together a display of their results for perusal by the parents. Many of them were quite good. Yaya's presentation was on LGBT rights in general and gender identity specifically. It's a subject she's been wrestling with and she did a pretty fair job of framing it. (No, I'm not outing my daughter; she may be conflicted, but she's sure not shy about it).

Anyway, one of the other kids had a presentation on why learning to write code is such a great thing. His argument basically boiled down to "you're guaranteed a job."

Well, I certainly wasn't going to debate him on that point because it seemed that he really did think programming was fun and, if that's true, you pretty much are guaranteed a job. Unfortunately, there still are way too many young folks picking majors who believe that the skill without passion is all that's required.

I do know a few uninspired programmers who manage to get enough done that their employers find it easier to keep them on than go through the hassle of firing them. Most leave on their own volition (or switch to non-programming roles within the same organization). However, employers are increasingly using right to hire contracts to make sure that programmers are able to cut it before making a perm offer. I wouldn't think you'd have to bomb out on too many of those before contracting firms would get sick of placing you. Simply put, if you don't love this stuff, you probably won't last. And, even if you do hold onto a job, you won't be well paid. Junior programmers really don't make that much and you won't get promoted unless you show some initiative.

In 1990, I had a student at Mount Union who seemed to be of average intelligence, but was doing terribly in a programming class I was teaching. I asked her why she was majoring in Computer Science since it didn't appear to interest her much. She said her dad had pushed her into it so she could get a good job. That's just sad and it's still going on today.

I turns out, she did have a passion for a subject; it just had nothing to do with Computer Science. She switched her major to Art and, upon graduating, got a job as a graphic designer. I don't know if that worked out or not, but I do know that she left school eager to get at it and such individuals tend to succeed.

I wish Yaya's classmate success. But mostly I wish for him what I wish for all kids (and adults, for that matter): that he finds what he loves.

Goin' it alone

I'm pretty much out of people to ask for help this summer. Seems like all the faculty who would be qualified to help with my research are otherwise disposed. That may not be a terrible thing. I'll have my life back for a couple months. It does lessen the chance I'm done in three years.

I won't be completely dead in the water. Aside from the Q preparation, much of the planned research is actual implementation and I certainly don't need guidance on how to do that. Getting projects from whiteboard to production is what I do for a living.

Dynamic Block Partitioning with BIRCH Clustering

Here's the slide deck for my presentation in Data Mining:

Dynamic Block Partitioning using BIRCH clustering.

Outline for BIRCH presentation

Recalling, of course, that this isn't really a presentation on BIRCH, but rather the concepts from BIRCH that will be relevant to my work this summer (and/or possibly fall).

Introduction: Partitioning as a form of clustering

• Show a simple example of how partitioning cuts down on query time
• Optimal partitioning has blocks where all or no rows are included
• Also need a way to know without reading the block - attribute tagging

Building the initial data set partitions

• Since we have no real query data, use surrogate partitioning
• Weight attributes by expected query use
• Insert entries into CF tree as per BIRCH except that we use hard partition lines rather than closeness when splitting a node. That is, an attribute is chosen to yield the best split and then the values are divided according the that attribute only.
• Label each block with appropriate attribute tags

When querying keep track of key metrics:

• Actual attribute slices.
• Percentage of rows are actually used when a block is read.
• Percentage of queries where the attribute tags allow the block to be skipped entirely.

Dynamic repartitioning

• Rank the blocks based on the effectiveness of their attribute tags
• Good blocks are either skipped entirely or return a high percentage of rows.
• Remove underperforming block(s)
• Re-insert data, using attribute partition weights updated from actual use

Why that won't work

• Even with updated weights, most of the re-inserted data is going to flow to the same spot on the CF tree.
• Insert a step between the deletion of the bad blocks and re-insertion of data where a new CF Tree is created using only blocks (not the individual rows in the blocks).
• This will sufficiently re-shuffle the CF tree so that the re-inserted data goes to new (presumably better) locations.

Implementation details to be sorted out through empirical testing

• Exact distance metric given query history
• Block ranking metric
• Fixed or dynamic number of blocks to delete on each iteration
• Maintaining stability during the reshuffle operation (system needs to be continuously available for query and new data loads).

Next big thing

Tons to do before the current paper is ready for publication, but it's not too early to think about what's next. My main priority this summer will be to make sure I'm ready for the Q. I'm not worried about Analysis, that's always been a really strong subject for me. I've already gone through Linear Algebra, so that's "just" practice (I use quotes because I think it will be quite a bit of practice to get that really sharp). That leaves the two stats courses. I don't know the exact content of those courses, but it appears to be fairly standard upper-undergraduate level stuff. As with Algebra, it's just a matter of doing enough problems to bring it all back the the surface.

I've got about 20 weeks to work with and I'd think 100 hours of working problems should be enough, so that's 5 hours a week. That leaves at least 10 hours a week for getting real research done. If I can tie it in with our re-platforming efforts at work, I could probably double that to 20. Subtract out this coming month which needs to be dedicated to finishing off this semester (and my CISS paper) and I've got somewhere between 200 and 300 hours. A lot can be done in that amount of time.

There are two possible paths with respect to dissertation work. One would be to continue on the implementation road by working on adding dynamic partitioning to the stratification. The other would be to dig into understanding the mathematical properties of heavy tailed distributions and the implications for processing financial data. The latter is a fairly active line of research right now, which means there's probably a lot less low hanging fruit for publication. However, it also means that cracking a tough nut could lead to a dissertation with some real significance.

My gut is telling me to take the first route since that will be much easier to fit in with activities at work. We're currently spinning up scalable environments for our larger analytics databases and dynamic partitioning would play right into that.

To that end, I spoke with my Data Mining prof about the presentation that's due this Tuesday. The assignment is to present the BIRCH algorithm. Well, with all six grad students presenting the same paper, the undergrads are going to be pretty bored by the end of class (this is a mixed grad/undergrad course). However, my thoughts on dynamic partitioning are pretty close to how BIRCH works. Optimal partitioning is really just a clustering problem where the distance metric is whether or not two rows show up in the same query. Furthermore, I was already going down the b+tree path for managing the splits, which is how BIRCH does it as well. So, I convinced him that I should present my forward looking view, that is, what ideas I'm going to use from BIRCH rather than the algorithm itself. It was actually a rather easy sell; I think he was somewhat dreading hearing six more or less identical presentations on a topic he already understands.

Now there's just the trivial matter of getting all my thoughts together and trimming it to a 10-minute presentation in two days.

2011 "Double" Chubb

Next week I'll be running the Double Chubb Single Edition so I figured this week's off-day throwback race report should be to my previous run of the 1-lap course.

Run April 16, 2011

Perhaps it's a case of familiarity breeds contempt. I run the Chubb trail once or twice a month. It's a great trail. The half-marathon distance makes it a good intermediate run and it's easy to add distance using connecting trails if you want to go long. The hilly and technical portion through Tyson drains well and can be run in almost any conditions. When it's dry and the Meramec River is below flood stage, the bottoms section is fun, fast singletrack. The gravel road through Lone Elk is less than inspiring, but it's only a mile long.

And yet, I've never run Double Chubb.

Now in its 13th edition, the Double Chubb is arguably the most anticipated trail race in Missouri. No other trail event fills faster (10 hours this year). Some of this is a consequence of logistics. Most of the trail is singletrack and it's an out-and-back course. Therefore, the SLUGs (St. Louis Ultrarunners Group) have wisely held the field limit low to keep head-on traffic manageable. Also contributing is the fact that there is a non-ultra distance offered (the 25K "single" Chubb) which expands the appeal to a broader range of runners. But, mostly, it's a great race on a great trail.

Falling just two weeks before I'm scheduled to run the Illinois Marathon, I decide to enter the single. Even at a training pace, a 50K would be too much so close to a marathon. My plan is to run the race at marathon effort (that is, the pace I can hold for three hours), which should have me done in just under 2 without destroying my legs. As that's a reasonably competitive master's time, I leave open the option of kicking it a bit in the last few miles if there's an age group win on the line.

Due to a minor informational snafu on the SLUG website, I end up missing packet pickup the night before. While that's not a problem itself, it leaves me not knowing what time to show up the next morning. I decide to arrive at 6, which turns out to be a bit on the early side. Only Race Directors David and Victoria White are there. I offer some assistance in getting the registration tent set up and then take a nap in my car. By 6:45, the registration area is hopping. While standing around chatting with my friends sounds appealing, the damp, chilly morning has me shivering a bit so I get started on my warmup. I don't want to start with my feet all gooped, so I jog easily on the road for half an hour, then change into my orienteering shoes for the race. While just a bit heavy for trail racing, my hope is that the open tread on the O-shoes will shed the mud we'll be running through along the river.

At the gun, Andy Koziatek and Ben Creehan bolt off up the steep road to the trailhead at a pace I reserve for track work. Ben's in the 50 and I've never come close to beating Andy at any distance, so I don't concern myself with them. Behind, a pack of six quickly forms including Chad Silker, Joel Lammers, David Frei, Jeff Sona, Mitch Faddis (all in the 50K) and me. While it's nice to be leading the masters in the 25K, it's still way too early to assume I won't get a push from behind.

David sets the pace for about a mile at which point I decide to up the tempo a bit. Only Chad follows, but David comes blasting by when we go down the first descent. "Your quads will remind you of that in about three hours," I tell him. "It's free speed!" he responds. Yeah, free just like charging things on a credit card is free. He'll pay, but that's his problem. As we start the big climb to the picnic table (the high point on the course), I resume the lead and, again, only Chad matches the effort. By the time we're heading back down the other side, we are clear of the rest of the field.

Despite the heavy rains of the preceding week, the footing on the rocky descent to the river is fine. We get to the aid station at the train tracks in 24:27. Though I have run the opposite direction (which is slightly tougher) a minute faster during tempo workouts, I'm a bit surprised we're that quick. The pace feels right, but just to be sure, I strike up a conversation with Chad to keep myself from overcooking it.

Turns out, Chad doesn't need much encouragement. He talks nearly continuously all through the river section. I don't get in too many comments myself, but it's enough to keep the pace in check. The mud isn't nearly as bad as feared (even the big culvert crossing can be taken without resorting to hands and knees), but it seems reasonable to expect that to change once the entire field has splashed through. Along the gravel road, I intentionally run through some of the puddles to clean my shoes for the climb up to the turnaround.

As we start the climb, Chad decides to back off a bit. After all, he does have lap two to think about. At the top of the hill, I meet Andy coming back the other way and still looking quite strong. Ben is a couple minutes behind him having obviously thought the better of trying to match Andy's pace when he has twice the ground to cover. I arrive at the turnaround in 55:22. I don't really have a context for that split since the turnaround is beyond the trailhead, but it seems like I'm still moving at about the right speed.

One of the nice things (perhaps the only nice thing) about out-and-backs is that you get to see what your competition is up to. Clearly, Andy is going to win, but the Master's prize is still up for grabs as Bob Fuerst is less than a minute behind me. I may have to push that last stretch through Tyson after all. The top two 25K women, Mary White and Laura Scherff, have a tight battle going and are putting away nearly all the men in the process. Joe, David, and Mitch are still running well in the 50 but Jeff looks like he might be off his game today. Travis Liles has worked his way into the mix and looks quite fresh. I make it back to the gravel road before hitting the bulk of the field, which makes passing easy.

The mud has certainly gotten worse on the flood plain, but it's still not as bad as I was anticipating. About half way through it, Chad catches back up to me. I worry that maybe I'm slacking off the pace and letting Bob back into the race, but we hit the midway aid station at 1:25:46 which is within a minute of our split time heading out. I can't see Bob behind me, but just in case he is closing, I decide to firm up the pace a bit. Chad takes some time to get food at the aid station so I'm left on my own to push up the ridge away from the river.

I've run the Tyson section from the tracks to the trailhead at tempo pace so many times, the added pace feels quite natural. I don't quite match my normal tempo effort, but I'm not slow by much, hitting the trailhead at 1:49:56 for a 24:10 split. Having found my groove, I keep it going through the final loop on the Chinkapin trail to finish at 1:55:13. Andy's been done for over ten minutes, but as he's a young pup, I get the 40+ win. Chad comes through a couple minutes later looking relaxed for lap 2. Bob finishes at 1:58:43. While he may have missed the Master's prize, he does win Senior as he turned 50 last year. I put my finisher's medal and winner's plaque (both quite nice) in my car and then head back out for a few easy miles. Joel and Mitch have already come through. David is just starting his second lap, so I run with him for a while. He admits he took it out too fast, but he's still moving well enough that after about half a mile I let him go. He says he really wants to try to beat Mitch who is less than a minute up the trail. David always saves his best efforts for beating his friends. I consider it something of an honor that many of his best performances have come in the process of handing me a loss.

I plod along easily, internally debating the wisdom of going all the way to the aid station. Travis comes by at a pace indicating he's saved himself for lap two. At the picnic table, I rest for a few minutes and then decide to head down to the aid station to say hi to the volunteers. I'll walk back if I have to. At the base of the descent, Jeff catches me and we jog into the aid station together. He's not feeling great, but doesn't expect to have any trouble finishing.

I hang at the aid station for a few minutes, chatting it up with the volunteers and passing runners. All I ate during the race was a single packet of Gu, so I take this opportunity to down some of the refreshments. As usual, the SLUGs have a fine spread - their aid stations are among the best.

It's turning into a longer run than planned and I don't want to put myself too far in a hole for Illinois, so I go back to the start straight through the woods, which is not only a mile shorter, but also a softer surface. I've done enough navigation training at Tyson that I have no trouble doing this without map or compass.

I get back barely in time to clean up and change clothes before Ben comes in, winning the Double in 3:56:19. He looks pretty fresh for having just finished an ultra. Given that his second lap was nearly a minute per mile slower than his first, I have to assume he got off the gas when he realized he wasn't going to be challenged for the win. Chad takes second in just over 4 hours, then there's a pretty good gap back to Joel in third (winning Masters). Travis follows just a couple minutes ahead of David who admits that the thought of catching and then staying ahead of Mitch had a lot to do with holding onto a decent lap 2 for a 50K PR of 4:21:47.

While the cool, misty conditions may have been a bit uncomfortable for the volunteers, the runners all seem to agree it was a great day to be out on trail, even with the mud along the river. Personally, I would have loved to run a second lap hard. It was definitely a day to shoot for breaking 4 hours (my PR for a trail 50K is 4:06). My intention is to run Boston next year, so I won't likely try the double until 2013, but I'm already looking forward to it.

Green light

Reviewed results with my adviser yesterday and the verdict is "go". Biggest task is framing the result in the context of current research. To that end, here's my bibliography so far:

Why heavy tailed distributions show up and why they are a problem:

Mandelbrot, Benoit. “The Pareto-lévy Law and the Distribution of Income”. International Economic Review 1.2 (1960): 79–106. Web...

Nolan, J.P. Stable Distributions — Models for Heavy Tailed Data. Birkhauser, Boston, 2015. Note: In progress, Chapter 1 online at academic.2.american.edu/~jpnolan. This is a book that is still a work in progress, but just ch1 is good background info. The author has a good page on Stable Distributions.

No Stable Distributions in Finance, Please! I'm not sure if this one's been published or not. It seems to raise some valid points about the overuse of Stable distributions. Worth a read just because the English is comically bad (certainly better than my Czech, but it's still funny)

L. B. Klebanov, G. M. Maniya, and I. A. Melamed, A Problem of Zolotarev and Analogs of Infinitely Divisible and Stable Distributions in a Scheme for Summing a Random Number of Random Variables Theory Probab. Appl., 29(4), 791–794. I couldn't find the full text online at any site I have access to so I'll have to track down a hard copy in a library. If I can't get this one in St. Louis, I know I can read it at Cornell when I visit my folks in June because we used to have this journal in the OR department.

Stratified sampling:

Anderson, Paul H.. “Distributions in Stratified Sampling”. The Annals of Mathematical Statistics 13.1 (1942): 42–52. Classic background on stratified sampling.

Shahrokh Esfahani, Mohammad; Dougherty, Edward R. (2014). "Effect of separate sampling on classification accuracy". Bioinformatics 30 (2): 242–250. Discusses bias issues arising from stratified sampling when the ratio of data between strata is not known.

Two texts I should probably read; hopefully I can find them in a library cuz they're REALLY EXPENSIVE. Fortunately, my family is in Ithaca and Kate's is in Champaign, so I'm regularly making trips that land me near two of the world's best mathematics libraries.

Heavy-Tailed Distributions in VaR Calculations. Chapter in Springer Handbooks of Computational Statistics.

Svetlozar T. Rachev & Stefan Mittnik, Stable Paretian Models in Finance