The Data Structures and Algorithms Problem

Here's a snippet of an email

In big data / data science, the curse of dimensionality keeps showing up over and over. A good place to start is the wiki article “curse of dimensionality.” The issue seems to be that a lot of these big data / data science people have not taken the time to study fundamental data structures.

There was more about Foundations of Multidimensional and Metric Data Structures by Hanan Samet being too detailed. And Stack Overflow being too high-level.  And more hand-wringing after that, too.

The email was pleading for some book or series of blog posts that would somehow educate data science folks on more fundamental issues of data structures and algorithms. Perhaps getting them to drop some dimensions when doing k-NN problems or perhaps exploit some other data structure that didn't involve 100's of columns.

I think.

I'm guessing because -- like a lot of hand-waving emails -- it didn't involve code. And yes, I'm very bigoted about the distinction between code and hand-waving.

If there is a lack of awareness of appropriate data structures, the real place to start is The Algorithm Design Manual by Steven Skiena.

I harbor my doubts that this is the real problem, however. I think that the broad spectrum of computing applications leads to a lot of specialization. I don't think that it's really prudent to try and think of generalists who can handle deep data science issues as well as algorithm design and performance issues. No one expects them to write JavaScript and tinker with CSS so that the web site which presents the results looks good.

I actually think the real problem is that some folks expect too much from their data scientists.

In fantasy land the rock stars are full stack developers who can span the entire spectrum from OS to CSS. In the real world, developers have different strengths and interests. In some cases, "full stack" means mediocre skills in a lot of areas.

Here's a more useful response: Bridging the Gap Between Data Science and DevOps. I don't think the problem is "big data / data science people have not taken the time to study fundamental data structures". I think the problem is that big data is a cooperative venture. It takes a team to solve a problem.

The Users Just Want "Search" -- What's So Hard?

Great article on "Search" from back in '08 in Forbes. "Why Google Isn't Enough", by Dan Woods. He's talking about "Enterprise Search": why in-house Google-style search is really hard and often unsatisfying.

Here's the cool quote.

enterprise search systems also index and navigate information that may reside in databases, content management systems and other structured or semi-structured repositories. The contents may include not only text documents, but also spreadsheets, presentations, XML documents and so on. Even text documents may include some amount of structure, perhaps stored in an XML format.

Everyone thinks (hopes) that the mere presence of data is sufficient. That fact that it's structured doesn't seem to influence their hopes.

The complication is simple -- and harsh. Many enterprise databases are really bad. Really, really epically bad. So bad as to be incomprehensible to a search engine.

Explanations

How many spreadsheets or reports "stand alone" as tidy, complete, usable documents?

Almost none.

You create a budget for a project. It seems clear enough. Then the project director wants to know if the labor costs are "burdened or unburdened". So the column labeled "cost" has to be further qualified. And "burdened" costs need to be detailed as to which -- exact -- overheads are included.

So a search engine might find your spreadsheet. If a person can't interpret the data, neither can a search engine.

Star Schema Nuance

You can build a clever star schema from source data. But what you find is that your sources have nuanced definitions. Each field isn't directly mappable because it includes one or more subtleties.

Customer name and address. Seems simple enough. But... is that mailing address or shipping address or billing address? Phone number. Seems simple. Fax, Voice, Mobile, Land-line, corporate switch-board, direct? Sigh. So much detail.

Of course the users "just want search".

Sadly, they've created data so subtle and nuanced that they can't have search.

A Limit to Reuse

We do a lot of bulk loads. A lot.

So many that we have some standard ETL-like modules for generic "Validate", "Load", "Load_Dimension", "Load_Fact" and those sorts of obvious patterns.

Mostly our business processes amount to a "dimensional conformance and fact load", followed by extracts, followed by a different "dimensional conformance and fact load". We have multiple fact tables, with some common dimensions. In short, we're building up collections of facts about entities in one of the dimensions. [And no, we're not building up data individual consumers. Really.]

Until, of course, someone has a brain-fart.

Overall Application Design

An overall load application is a simple loop. For each row in the source document, conform the various dimensions, and then load the fact. Clearly, we have a bunch of dimension conformance objects and a fact loading object. Each object gets a crack at the input row and enriches it with some little tidbit (like a foreign key).

This leads us to pretty generic "Builder" and "Dimension Builder" and "Fact Builder" class hierarchy. Very tidy.

Each new kind of feed (usually because no two customers are alike) is really just a small module with builders that are specific to that customer. And the builders devolve to two methods

• Transform a row to a new-entity dict, suitable for a Django model. Really, just a simple dict( field=source['Column'], field=source['Column'], ... ) block of code.
• Transform a row to a dimension conformance query, suitable for a Django filter. Again, a simple dict( some_key__iexact= source['Column'] ).

The nice thing is that the builders abstract out all the messy details. Except.

Hard-to-Conform Data

We're now getting data that's not -- narrowly -- based on things our customers tell us. We're getting data that might be useful to our customer. Essentially, we're processing they're data as well as offering additional data.

Cool, right?

But... We lack the obvious customer-supplied keys required to do dimensional conformance. Instead, we have to resort to a multi-step matching dance.

Limiting Factors

The multi-step matching dance pushed the "Builder" design one step beyond. It moved from tidy to obscure. There's a line that seems to be drawn around "too much" back-and-forth between framework code and our Builders.

Something as bone-simple as a bulk loader has two candidate design patterns.

• Standard loader app with plug-in features for mappings. This is what I chose. The mappings have been (until now) simple. The app is standard. Plug a short list of classes into the standard framework. Done.
• Standard load support libraries that make a simple load app look simple. In this case, each load app really is a top-level app, not simply some classes that plug into an existing, standardized app. Write the standard outer loop? Please.

What's wrong with plug-ins?

It's hard to say. But it seems that a plug-in passes some limit to OO understandability. It seems that if we refactor too much up to the superclass then our plug-ins become hard to understand because they lose any "conceptual unity".

The limiting factor seems to be a "conceptually complete" operation or step. Not all code is so costly that a simple repeat is an accident waiting to happen.

Hints from Map-Reduce

It seems like there are two conceptual units. The loop. The function applied within the loop. And we should write all of the loop or all of the mapped function.

If we're writing the mapped function, we might call other functions, but it feels like we should limit how much other functions call back to the customer-specific piece.

If we're writing the overall loop -- because some bit of logic is really convoluted -- we should simply write the loop without shame. It's a for statement. It's not obscure or confusing. And there's no reason to try and factor the for statement into the superclass just because we can.

Information Technology -- It's all about Decision-Making

Check this SD Times article out: Future of data analysis lies in tools for humans, not automatic systems.

"Andreas Weigend... said that “data is only worth as much as the decisions made based on that data."

This is the entire point of IT: IT Systems Support Decision-Making. The job is not to "automate" decision-making with a bunch of business rules. The job is to create systems to support decision-making by people. Buying a tool that allows "end-users" to drag and drop icons to create workflows and business rules misses the point. Automating everything isn't helpful.

Information should be classified and categorized to facilitate decision-making.

People need to be in the loop.

Management by exception can only happen when people see the data, can analyze, categorize, summarize and -- by manipulating the data -- discover outliers and unusual special cases.

Too many systems attempt to leave people out of the loop.

Business Rules

A canonical example of business rule processing is credit checks or discounts in an order processing system. This requires integrating a lot of information, and making a decision based on ordering history, credit-worthiness, etc., etc.

In some cases, the decision may be routine. But even then, it is subject to some review to be sure that management goals are being met. Offering credit or discounts is a business strategy decision -- it has a real dollar-valued impact. A person owns this policy and needs to be sure that it makes business sense.

These decisions are not just "if-statements" in BPML or Java or something. They are larger than this.

One good design is to queue up the requests, sorted into groups by their relative complexity, so a person can view the queues and either make (or confirm) the automated decisions. It's a boring job, but they're doing management by exception. They own the problems, the corner cases, the potential fraud cases, the suspicious cases. They should have an incentive payment for every real problem they solve.

You give up "real-time" because there's a person in the loop. For small value, high-volume consumer purchases, you may not want a person in the loop. Most of us, however, are not Amazon.com. Most of us have businesses that are higher value and smaller volume. People will look at the orders anyway.

All IT Systems must facilitate and simplify manual review. Even if they can automate, the record of the decisions made should be trivial to review. Screen shots or log scraping or special-purpose audit/extract programs mean the application doesn't correctly put people into the process.

"Automated" Data Mining

In most of the data warehousing projects I've worked on, folks have been interested in the idea of "automated data mining" discovering something novel in their data. For example, one of the banks I worked with was hoping for some kind of magical analysis of risk in their loan portfolio.

Data Mining is highly constrained by the implicit causal models that people already have. There's a philosophical issue with attempting to correlate random numbers in a database and then trying to reason out some theory or model for those correlations. The science of going from observation to theory requires actual thinking. There's a long analysis here: http://theoryandscience.icaap.org/content/vol9.2/Chong.html.

Indeed, the only possible point of data mining is not to discover something completely unexpected, but to confirm the details of something suspected but hidden by noise or complexity. People formulate models, they confirm (or reject) them with tools like a data warehouse with some data mining analytics.

Sometimes the universe appears multidimensional -- but isn't

Had a knock-down drag-out fight with another architect recently over "status" and "priority".

She claimed that the backlog priority and the status where the same thing. I claimed that you can easily have this.

Priority: 1, Status: Not Started

Priority: 2, Status: In Process

Priority: 3, Status: Completed

See? It's obvious that they're independent dimensions.

She said that it's just as obvious that you're doing something wrong.

Here's her point:

• If you have priority 1 items that aren't in process now, then they're really priority 2. Fix them to honestly say priority 2.
• If you have priority 2 items that "somehow" jumped ahead of priority 1 items, they were really priority 1. Fix them to say priority 1. And don't hand her that "in the real world, you have managers or customers that invert the priorities". Don't invert the priorities, just change them and be honest about it.
• The only items that are done must have been priority 1, passed through an "in-process" state and then got finished. Once they're done, they're not priority 1 any more. They're just done.
• Things that hang around in "in-process, not done" have two parts. The part that's done, and some other part that's in the backlog and not priority 1.

She says that priority and status are one thing with the following values.

• Done.
• Priority 1 = in process right now.
• Priority 2 = will be in process next. Not eventually. Next.
• Priority 3 through ∞ = eventually, in order by priority.

Any more complex scheme is simply misleading (Priority 1 not being done right now? Is it a resource issue? A priority issue? Why aren't you doing it?)

The world is multidimensional? Really?

I cannot believe that people still consider top-down, uni-dimensional, taxonomic hierarchies useful.

This Stack Overflow question (REST: How to Create a Resource That Depends on Three or More Resources of Different Types?) repeats an assumption. Essentially the confusion comes from assuming that "URI's map directly to a hierarchy".

I think it's over-exposure to the Windows file system where hard links are a rarity.

Perhaps it's also from over-exposure to hierarchical site-maps that simply repeat the menu structure without adding information.

Someone who is reading Everything is Miscellaneous suggested I read up on "faceted classification" as if that was something new or different.

What's interesting in Weinberger’s book is (1) recognizing this and (2) taking some concrete action.

What To Do?

What's perhaps the most important thing is this

Stop Forcing Things Into Hierarchies

I sat in a multiple hour meeting where we debated the file-system structure for artifacts created during a development project. Each artifact has several dimensions.

• Phase of the project (Inception, Elaboration, Construction, Deployment)
• Deliverable type (DB Design, Application Programming, Web Site, etc.)
• Status (Work in Progress, Waiting UAT, Completed, Rework, etc.)
• Calendar (Year, Quarter, Month the work started, as well as ended)
• Team (DBA's, Batch/Backend, Web/Frontend, ETL, etc.)

Sigh.

Since the data is multidimensional, no single taxonomic hierarchy can ever "work". Each alternative (and there are 5!=120 ways to permute five dimensions) appears equally useful.

If you want, you can enumerate all 5! permutations to see which is more "logical" or "works better for the team". What you'll find is that they all make sense. They all make sense because the dimensions are all peers -- equally meaningful.

Alternatives

One alternative is to do this.

1. Create a relatively flat structure. Define all your things in this flat structure. In a Relational Database context, this means assign surrogate keys to everything, "natural" keys are more problem than solution. In a content management context, just throw documents anywhere.

2. Create "alternative" indices via hard links to the flat structure. Do not limit yourself to a few alternative orderings of the dimensions. There are n! permutations of your dimensions. Expect to create many of these for different user consituencies.

Remember, Search Exists

Recognize that highly structured metadata fields in a database are usually a waste of time and money. Search exists. Much data is unstructured or semi-structured and search functions exist that handle this nicely.

If you stop force-fitting hierarchies, you find that you have now have several dimensions. Each dimension has a set of reasonably well-defined tags. Each document or database fact row is a point in multi-dimensional space.

A single SQL-style query among these multiple dimensions is a pain in the neck. Search, however, where the dimensions are implied instead of stated, is much, much nicer.