The Shape of Data

Last week I attended a San Francisco Bay Area ACM Chapter event at Pivotal Labs, which now occupies one of the former HP Labs buildings up on Deer Creek Road. The speaker was Gunnar Carlsson and the topic was algebraic topology analytics. I was waiting to write this post until the slides would be posted, but they never materialized—maybe the fancy rendering of a coffee mug metamorphosing into a topologically equivalent donut broke the system.

I must admit that what attracted me the most to attend was to see how Gunnar Carlsson would give a presentation on a very arcane topic requiring intimate familiarity with Betti numbers, functional persistence barcodes, simplicial complexes, and Vietoris-Rips complexes to the 244 registered attendees, probably mostly lacking the necessary mathematical background. I was also curious to see if he would reveal some of the fast algorithms which he must have invented to perform the very complex calculations involved.

He did a superb job! After the demonstration that for mathematicians coffee mugs and donuts are equivalent, he had everybody's attention. He then showed some examples of how conventional methods for regression and cluster analysis can fail and lead to completely incorrect conclusions, leaving the task of understanding topological pattern recognition for point cloud data as an exercise.

Gunnar Carlsson started by noting that big data in not about "big" but about complexity in format and structure. Data has shape and shape matters. Therefore, the task of the data scientist is not to accumulate myriad data, but to simplify the data in a way that the shape is easily inferred.

Consider for example the point cloud on the left side of the figure below. You can import it in your favorite analytics program and perform a linear regression. This simplifies the data to two parameters: a slope and an intercept. However, if you look more carefully, you see that this an incorrect representation of the data. Indeed, the point cloud is on two intersecting lines, therefore, the green cross at the right is a more accurate representation of the data's shape.

A second example is the confusion between recurrent data and periodic data. People tend to equate them and then use Fourier analysis on recurrent data that is not periodic, getting meaningless results. Recurrence is a concept from chaos theory and does not imply regular cycles, like the El Niño Southern Oscillation (ENSO).

The solution is to use topological modeling, like in the figure. If you are older, you need to revisit topology, because the field has started to study point clouds only in the last 20 to 15 years.

The first step in a project is to determine a relevant distance metric. Examples include Euclidean distance, Hamming distance, and correlation distance. The distance metric should be such that it is sensitive to nearby events but not so much to far away events because the interesting stuff happens close by: consider for example a distance metric based on the statistical momenta.

The output of an algebraic topology analysis is not a set of algebraic formulæ but a network.

For exercising, Carlsson recommends the World Values Survey, which contains a lot of interesting data. When you play with the data, it is often useful to consider a topological model of the space of columns rather than the rows in a data set.

Adapting to street lighting

Although in Switzerland light pollution is a fraction of what it is in American urban areas, in an interesting study, Florian Altermatt from Zurich and Dieter Ebert from Basel have shown experimentally that moths have adapted to light pollution. They reared moths from 10 different populations from early-instar larvae and experimentally compared their flight-to-light behavior under standardized conditions. Moths from urban populations had a significant reduction in the flight-to-light behavior compared with pristine populations.

This adaptation has direct consequences for ecosystems, because as moths avoid light pollution they will fly less and will pollinate fewer flowers.

If you delve into data science, beware that correlation does not predict causality: if Americans have become couch potatoes and move less than the Swiss, this is not due to the difference in light pollution :-)

Citation: Florian Altermatt, Dieter Ebert: Reduced flight-to-light behaviour of moth populations exposed to long-term urban light pollution, Biol. Lett. 2016 12 20160111; DOI: 10.1098/rsbl.2016.0111. Published 12 April 2016.

How to pronounce LIRE

One of the difficulties of the English language is that it is often not clear, how to correctly pronounce words. For example, Edinburgh, Gloucester, and Leicester are often mispronounced. Fortunately, a dictionary will teach you how to pronounce a word correctly, and if you do not find it there, you can try the Wikipedia.

The situation is a little more hairy in the case of acronyms. Often there is a pun, which can guide you in guessing the pronunciation, but sometimes it is a genuine acronym, and therefore impossible to guess.

In the age of big data, the default approach to crack this riddle is to crowd-source the answer on a social network. Blast the question on Twitter, write a small R program using twitterR, and calculate the statistical mode. You can even get creative and use the PBSmapping package to plot the locations of the responders.

Unfortunately, the crowds are not wise and they might never have crossed path with the acronym, so they just guess. This is a classical case of garbage-in, garbage-out. In German, this process is also known with the expression "mit Kanonen auf Spatzen schiessen."

People were debating how one might pronounce LIRE, a Java library that provides a simple way to retrieve images and photos based on color and texture characteristics. LIRE is an acronym for Lucene Image Retrieval and is used to build content based image retrieval (CBIR, rhymes with cyber) systems.

Nothing is easier than shooting a one-line email to the creator Mathias Lux in Klagenfurt (do not fear, the Lindwurm is made of stone and will not byte you) and you get the correct answer, no need for confidence intervals: "Ich persönlich gehe von der italienischen Sprechweise aus"— it is pronounced the Italian way: li like liberty plus re like record.

Big Dada

If you mistyped and where searching for "big data," try this other post. Here we are on 5 February 1916 in the Cabaret Voltaire on the Spiegelgasse, just a few steps from the apartment where Lenin was living in exile and not far from where I lived for a couple of years under a gaslight.

Dada represents the total doubt about everything, the absolute individualism and the destruction of ideals and norms hitherto cast in concrete. For example, in Hugo Ball's Lautgedichte (sound poetry) the utterances are decoupled from semantics. This is how a century later naive users misuse Internet search engines and then wonder their queries just return millions of dada, much to the chagrin of the computational linguists trying to design semantic search engines. This is dada. No, it is a trigram. Can a second order Markov model help? Not for this trigram: Google Books thinks, it does not exist. Coming up with a new sentence is so dada.

The dadaists were displeased with science, which they judged to be elitist and far from any comprehensibility and sensuality. Maybe they were not completely right, considering what was happening in theoretical physics around that time. But certainly, today science is more dada, when fresh laureates dance their Ph.D. You can win a trip to Stanford and visit me, just a few steps away, under an LED lamppost.

bottom-up vs. top-down

Last week I wrote about systems of autonomous components, also dubbed as bees vs. the bee hive. In management, there is the somewhat related concept of bottom-up vs. top-down management.

Bottom-up used to be popular in engineering companies. Engineers work in small groups that push beyond the bleeding edge of technology and invent new product concepts. As the product evolves, more people are recruited and the product is polished by UX experts, manufacturability experts, marketing and sales teams, etc.

In a top-down company, the leader of the company is an expert visionary who has a new technology idea. A team of second level executives is assembled, which repeats the process for the next level, etc., down to the worker bees who develop the product. This was the basis of the utopian concept described in Tommaso Campanella's Città del Sole.

The preference for one paradigm or the other oscillates with time. Both are viable. Things only go wrong when a mediocre person becomes the head honcho of a bottom-up company and transforms it to top-down. In a bottom-up company, the management's role is mostly to take out of the way the obstacles that slow down the engineers. Typically their nature is more that of a facilitating person than that of a leader.

When the polarity of a company is switched from bottom-up to top-down, the management layers typically fail. With a mediocre person at the top, the company is doomed. It can take decades, but in the end, there is no escape from the spiral of death.

systems of autonomous components

In the discussions about big data and scalability, we learned how Gunther's universal scalability law suggests scaling out.

Another way to look at vertical vs. horizontal scaling is to compare a whale to a fish school. A school of small fish has the same biomass as a blue whale. A whale takes about 5 minutes to turn 180º. On the other hand, a school of small fish switches direction in an instant. The blue whale has no escape when under attack!

Leo Lionni's 1963 picture book スイミー (Swimmy) is particularly popular in Japan because it conveys the message that together we are strong, even though we are small. This is related to the concepts of synergy and emergent property.

In the case of big data and scalability, the morale of the story is that you do not want a rigid powerful central authority, but a plurality of autonomous components orchestrated to play the same symphony, with a minimum of coherency overhead. This resonates with Industry 4.0.

scale-up and scale-out

In the post on big data we mentioned Gunther's universal scalability model

In this model, p is the number of processors or clusters nodes and S_p is the speedup with p nodes. σ and κ represent the degree of contention in the system, respectively the lack of coherency in the distributed data. An example for the contention is waiting for message queueing (bottleneck saturation) and an example for incoherency is updating the processor caches (non-local data exchange).

When we do measurements, T_p is the runtime on p nodes, and S_p = T₁ / T_p is the speedup with p nodes. When we have enough data, we can estimate σ and κ for our system and dataset using nonlinear statistical regression.

The model makes it easy to understand the difference between scale-up and scale-out architectures. In a scale-up system, you can increase the speedup by optimizing the contention, for example by adding memory or by bonding network ports. When you play with σ, you will learn that you can increase the speedup, but not the number of processors where you have the maximum speedup, which remains at 48 nodes in the example in Gunther's pape.

In a scale-out architecture, you play with κ and you learn that you can additionally move the maximum over the number of nodes. In Gunther's paper, they can move the maximum to 95 nodes by optimizing the system to exchange fewer data.

This shows that scale-up and scale-out are not simply about using faster system component vs. using more components in parallel. In both cases, you have a plurality of nodes, but you optimize the system differently. In scale-up, you find bottlenecks and then mitigate them. In scale-out, you also work on the algorithms to reduce data exchange.

Since the incoherency term is quadratic, you get more bang for the bucks by reducing the coherency workload. This leads to adding more nodes instead of increasing the performance of the nodes, the latter usually being a much more expensive proposition.

In big data, scale-out or horizontal scaling is the key approach to achieve scalability. While this is obvious to anybody who has done GP-GPU programming, it is less so for those who are just experienced in monolithic apps.

big data

A few years ago, when "big data" became a buzzword, I attended an event from a major IT vendor that was about the new trends in the sector. There were presentations on all the hot buzzwords, including a standing room only session on big data. After the obligate corporate title slide, came a slide with a gratuitous unrelated stock photo on the left side, while the right side was taken up by the term "big data" in a font size filling the entire right half of the slide. Unfortunately, the rest of the presentation only contained platitudes, without any actionable information. My takeaway was that "big data" is a new buzzword that is written in a big font size.

After the dust settled, big data became associated with the three characteristics data volume, velocity, and variety proposed in 2001 by META's Doug Laney as the characteristics of "3-d data management" (META is now part of Gartner). Indeed, today Gartner defines big data as high-volume, high-velocity and/or high-variety information assets that demand cost-effective, innovative forms of information processing that enable enhanced insight, decision making, and process automation.

Volume indicates that the amount of data at rest is of petabyte scale, which requires horizontal scaling. Variety indicates that the data is from multiple domains or types: in a horizontal system, there are no vertical data silos. Velocity refers to the rate of flow; a large amount of data in motion introduces complications like latencies, load balancing, locking, etc.

In the meantime, other 'V' terms have been added, like variability and veracity. Variability refers to a change in velocity: a big data system has to be self-aware, dynamic, and adaptive. Veracity refers to the trustworthiness, applicability, noise, bias, abnormality and other quality properties in the data.

A recent understanding is the clear distinction between scale-up and scale-out systems with a powerful model called universal scalability model dissected in a CACM paper: N. J. Gunther, P. Puglia, and K. Tomasette. Hadoop superlinear scalability. Communications of the ACM, 58(4):46–55, April 2015.

This model allows us to state that Big Data refers to extensive data sets, primarily in the characteristics of volume, velocity, and/or variety, that requires a horizontally scalable architecture for efficient storage, manipulation, and analysis, i.e., for extracting value.

To make this definition actionable, we need an additional concept. Big Data Engineering refers to the storage and data manipulation technologies that leverage a collection of horizontally coupled resources to achieve nearly linear scalability in performance. Now we can drill down a little.

New engineering techniques in the data layer have been driven by the growing prominence of data types that cannot be handled efficiently in a traditional relational model. The need for scalable access to structured and unstructured data has led to software built on name–value / key–value pairs or columnar (big table), document-oriented, and graph (including triple–store) paradigms. A triple-store or RDF store is a purpose-built database for the storage and retrieval of triples through semantic queries. A triple is a data entity composed of subject-predicate-object, like "Bob is 35" or "Bob knows Fred."

Due to the velocity, it is usually not possible to structure the data when it is acquired (schema-on-write). Instead, data is often stored in raw form. Lazy evaluation is used to cleanse and index data as it is being queried from the repository (schema-on-read). This point is critical to understand because to run efficiently, analytics requires the data to be structured.

End-to-end data lifecycle categorizes the steps as collection, preparation, analysis, and action. In a traditional system, the data is stored in persistent storage after it has been munged (extract, transform, load, followed by cleansing; a.k.a. wrangling or shaping). In traditional use cases, the data is prepared and analyzed for alerting: schema-on-write. Only afterward the data or aggregates of the data are given persistent storage. This is different from high-velocity use cases, where the data is often stored raw in persistent storage: schema-on-read.

Veracity refers to the trustworthiness, applicability, noise, bias, abnormality and other quality properties in the data. Current technologies cannot assess, understand, exploit, and understand veracity throughout the data lifecycle. This is a big data characteristic that presents many opportunities for disruptive products.

Because in big data systems IO bandwidth is often the limiting resource, yet processor chips can have idle cores due to the IO gap (the number of cores on a chip is increasing, while the number of pins is constant), big data engineering seeks to embed some local programs like filtering, parsing, indexing, and transcoding in the storage nodes. This is only possible when the analytics and discovery systems are tightly integrated with the storage system. The analytics programs must be horizontal not only in that they process the data in parallel, but operations that access localized data, when possible, are distributed to separate cores in storage nodes, depending on the IO gap size.

With this background, we can attempt a formal definition of big data:

Big Data is a data set(s), with characteristics (e.g., volume, velocity, variety, variability, veracity) that for a particular problem domain at a given point in time cannot be efficiently processed using current / existing / established / traditional technologies and techniques in order to extract value.

Big data is a relative and not an absolute term. Big data essentially focusses on the self-referencing viewpoint that data is big because it requires scalable systems to handle, and architectures with better scaling have come about because of the need to handle big data.

The era of a trillion sensors is upon us. Traditional systems cannot extract value from the data they produce. This has stimulated Peaxy to invent new ways for scalable storage across a collection of horizontally coupled resources, and a distributed approach to querying and analytics. Often, the new data models for big data are lumped together as NoSQL, but we can classify them at a finer scale as big table, name–value, document, and graphical models, with the common implementation paradigm of intransigent distributed computing.

A key attribute of advanced analytics is the ability to correlate and fuse the data from many domains and types. In a traditional system, data munging and pre-analytics are used to extract features that allow integrating with other data through a relational model. In big data analytics, the wide range of data formats, structures, timescales, and semantics we want to integrate into an analysis presents a complexity challenge. The volume of the data can be so large that it cannot be moved to be integrated, at least in raw form. Solving this problem requires a dynamic, self-aware, adaptive storage system that is integrated with the analytics system and can optimize the locus of the various operations depending on the available IO gap and the network bandwidth at every instant.

In big data, we often need to process the data in real-time or at least near-real-time. Sensors are networked and can even be meshed, where the mesh can perform some recoding functions. The data rate can vary over orders of magnitude in very short time intervals. While in communications technologies, streaming technology has been perfected over many decades, in big data, the data flow and its variability are still largely unexplored territory. The data rate is not the only big data characteristic presenting variability challenges. Variability refers also to changes in format or structure, semantics, and quality.

In view of the recent world events—from Edward Snowden's leaks to Donald Trump's solicitation on Bill Gates to close the Internet—the privacy and security issues for big data are stringent but also in great flux due to the elimination of the Safe Harbor framework. According to a 2015 McKinsey study, cybersecurity is the greatest risk for Industry 4.0, with 50 billion € annual reported damage to the German manufacturing industry caused by cyberattacks.

With all these requirements, it is not surprising that there is only a handful of storage products that are both POSIX and HDFS compliant, are highly available, cybersecure, fully distributed and scalable, etc.

Architecture vs. baling wire and chewing gum

Over thirty years ago, I was working in the Dragon project. The full-custom VLSI chips were so complex, that we were not able to use the commercial tools of the time. Thus, part of the team was working on the development of a set of tools design the chips; I was working on the design rule checker.

Since we were concomitantly writing the tools, designing the chips, writing the compiler, and porting the operating system, we all had to work in parallel. For the tools, this was made possible by having each tool have its own file format and the data was moved from one workflow step to the next in a file. For example, the design rule checker parsed in the layout file and emitted the files for the logic and time simulators.

The challenge was, that this was not really a development project but a research project: we were inventing the algorithms while we were implementing the tools using them. One consequence was, that the file formats kept changing and this broke the parsers. This was painful, especially because we had hard deadlines with the MOSIS service we were using.

One day, during another no-so-happy meeting, I asked the question: "why are we using files at all, we are just dealing with different representations of the same chip. There should be just one data structure and the design tools should decorate it, analyze it, or render it."

The idea stuck and two colleagues designed and implemented the Core data structure. The layout editor would add geometry to the Core data structure and the various design rule checkers and simulation programs would analyze the data structure elements and add their own decorations. Almost immediately, a designer added a schematics editor and we wrote a program to generate the documentation by traversing the Core.

In a way, the original system with the parsers was built with baling wire and chewing gum, while the Core data structure introduced a sophisticated architecture. The various programs became simpler and so we were able to do nightly builds of the entire system. The entire design process became much more efficient and the tools more powerful.

Today, it has become very easy to quickly rig up a system based on open source software. A large number of powerful libraries is available and many produce very compelling eye candy.

Not too long ago, I had to build a prototype where a user could take a mobile phone picture of a store receipt and see on the display the receipt with the prices of a competing store. Since the demo for the customer was imminent, I had to work like a beaver to set up an OCR server, figure out how to get through the firewall, build a price translation table for the two stores, and set up a website to display the doctored receipt.

It took me two weeks and the wabi-sabi result looked like a prototype. Concomitantly, over a weekend, a bunch of young programmers rigged up an app that took a picture, replaced the top quarter with the bitmap of the top of the competing store's receipt to change the store block, leaving the item list unchanged, and displayed the result. This was even worse than bailing wire and chewing gum. However, they spent time making the GUI look slick.

At the end of the day, they got lot of compliments, but since there was no architecture, they would never have been able to implement a working system. In particular, doing the price translation is difficult. They would not have been able to build a real system.

Unfortunately, today's plethora of libraries makes it not only possible to write good applications, but also to quickly rig something up without understanding what is going on. There is much less interest in well-architected powerful software than used to be. Fortunately, the economy works in waves and the next downturn will flush out the system. The smart samurai does not fight his enemy: he patiently sits downstream the river to wait for the body of his enemy to float by.

Industrie 4.0

In our post on the Fourth Industrial Revolution last January, we showed a table from the World Economic Forum. It had 1784 as the date for the first industrial revolution, 1870 for the second, 1969 for the third, and a big question mark for the fourth.

Indeed, technology breakthroughs can rarely be pinned to a single date. In a post on a color scientist's role I had written that discoveries are in the air or ether. Discoveries happen when the time is ripe for them, and at that time, many people will have the same insight with a time interval of a few weeks or months. Research is very expensive, it is a high-risk investment. Timing is everything, otherwise, you lose your investment.

With that, I meant that technologies emerge over an interval of time. The widespread adoption of a revolutionary technology takes an order of magnitude longer than its emergence—giving a precise date is not possible.

When the industry was still artisanal, the force was supplied by waterwheels, donkeys, or indentured labor. Although this allowed mechanical production equipment, the force generation was unreliable and limited. In the first industrial revolution, steam allowed a steady supply of considerable mechanical force. It became possible to build factories with elaborate mechanical force distribution systems based on rods and belts. The layout of a factory floor was dictated by the force distribution system.

In the second industrial revolution, the electric motor made the design of the factory floor layout much easier, because what was distributed was the electricity, while the mechanical force was generated independently and locally at each workstation by electric motors. This allowed the distribution of labor, conveyor belts, and true mass production.

The third industrial revolution was the digitization of the entire design and production process through the use of CAD/CAM tools. Engineers could use interactive software to design new products. The design consisting of a software program meant that the program could be executed to generate simulations. It was not only possible to design smoother products with Bézier curves: the simulation could verify if a part was manufacturable by a CNC lathe and how long the process took. CAD/CAM programs were able to generate the control program for the CNC lathe, thus automating the entire manufacturing process.

If we have to put dates and names to the birthing of the fourth industrial revolution, it would be Kristen Nygaard (1957) and Ole-Johan Dahl (1962). When he was a visiting scientist at Xerox PARC, Nygaard told me how a newspaper trade union came to him for help with stressed out newspaper workers. The newspapers were introducing digital layout systems, which were supposed to be much more ergonomic that the old system of comps and rubylith. As a professor for operations research, he conducted research on planning, control, and data processing to sleuth the source of the stress.

The corollary was in 1962 Simula I, a superset of Algol 60, for simulating typesetting (discrete event networks). This was refined in Simula 67 with objects, classes, subclasses, virtual methods, co-routines, discrete event simulation, and garbage collection. In a first visit from Oslo to Palo Alto, this begat Smalltalk.

In 1973 came Hewitt & co-worker's extension to exploit massively parallel computers with the concurrent execution of objects. Communication was by message passing, decoupling the communication from the sender. The key new concept is that of an actor, a computational entity that, in response to a message it receives, can concurrently 1) send a finite number of messages to other actors, 2) create a finite number of new actors, and 3) designate the behavior to be used for the next message it receives.

In the actor model, messages are simply sent, there is no buffering, no synchronous handshaking, no ordering—FIFO requires explicit queue actor. Everything is local. These ideas were influenced by packet switched networks. The power comes also from the fact that a message can contain another actor, e.g., resumption, (a.k.a. continuation, stack frame) to which the recipient sends a response, enabling a variable topology.

This technology is also known as functional programming because the behavior is that of a mathematical function to express what an actor does when it processes a message.

To build the bridge to industry, the actor is a model for a machine or workstation. Variable topology means that each workstation can autonomously adapt the workflow depending on external factors (sensors). This requires refining the concept of modeling.

Modeling is the act of representing a system or subsystem formally. From a mathematical point of view, it is a set of assertions about properties of the system such as its functionality or physical dimensions. The constructive counterpart defines a computational procedure that mimics a set of properties of the system, also called executable mode or simulation.

With this, we can define design as the act of defining a system or subsystem. Usually, this involves defining one or more models of the system and refining the models until the desired functionality is obtained within a set of constraints.

Embedded software is software that resides in devices that are not first-and-foremost computers. A key feature of embedded software is that it engages the physical world, and hence has temporal constraints that desktop software does not share.

Executable models are constructed under a model of computation, which is the set of ``laws of physics'' that govern the interaction of components in the model. A set of rules that govern the interaction of components is called the semantics of the model of computation.

In the example of a printing plant, each actor can be a PDF transformer that performs the step of a workstation (e.g., imposition, folding, or trimming) by performing the corresponding operation on a PDF file. By combining the actors in a workflow, we can simulate the set of all print jobs in the printing plant and assert correctness. When timing information is collected, the simulation can find bottlenecks and deadlocks. Because rush jobs increase the profit, the simulation allows the workflow topology to reconfigure itself locally dynamically to maximize the profit function. Also, if there is a breakdown, e.g., a jam, the other workstations can reconfigure their use of queues.

An example of a work station is the raster image processor. We can change the algorithm for the black skeleton, gamut mapping, or halftoning. The actor can use simulation to select the most efficient algorithms. It considers the corresponding ICC profiles for the printer and can simulate giving the printer a virtual Farnsworth-Munsell 100-hue test, as shown in this diagram of the workflow in physical respectively simulation mode.

Returning to the concept of the fourth industrial revolution, in Germany, the brand name for this initiative is Industrie 4.0. They use slightly different terminology based on the concept of the twin. They would write:

Four aspects drive the future of manufacturing: modularity, connectivity, autonomy, digital twin. A digital twin of an autonomous system is a very realistic model of the current state of the process and its own behavior in interaction with its environment in the real world. It is a notion where the information created in each stage of the product lifecycle is seamlessly made available to subsequent stages.

The digital twin approach is the next wave in modeling, simulation and optimization technology. Simulation is extended to all life cycle phases as a core product or system functionality.

The concept of using “twins” is rather old. It dates back to NASA’s Apollo program, where at least two identical space vehicles were built to allow mirroring the conditions of the space vehicle during the mission. One vehicle remaining on earth was called the twin. NASA definition: A digital twin is an integrated multiphysics, multiscale simulation of a vehicle or system that uses the best available physical models, sensor updates, fleet history, etc., to mirror the life of its corresponding flying twin. At Airbus, a digital twin is called an iron bird.