F1 Database from Google: A scalable distributed SQL database

 

This world is a sphere. We keep going round and round. After a great hype around the NoSQL highly distributed databases, now Google presented a paper on how they have implemented a SQL based highly scalable database for supporting their "AdWords" business in 39th VLDB conference.

---

The news item: http://www.theregister.co.uk/2013/08/30/google_f1_deepdive/
and the paper: http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/41344.pdf

---

The key changes I liked:
1. Heirarchically clustered physical schema model: I always thought heighrarchical model is more suited for real life application than a pure relational model. This implementations is proving it.

2. Protocol Buffers: Columns allowing structured types. It saves a lot of ORM style conversions when moving data from a storage to in-memory and vice versa.

---

A quote from the paper's conclusion:

In recent years, conventional wisdom in the engineering community has been that if you need a highly scalable, high-throughput data store, the only viable option is to use a NoSQL key/value store, and to work around the lack of ACID transactional guarantees and the lack of conveniences like secondary indexes, SQL, and so on. When we sought a replacement for Google's MySQL data store for the Ad-Words product, that option was simply not feasible: the complexity of dealing with a non-ACID data store in every part of our business logic would be too great, and there was simply no way our business could function without SQL queries.

So, ACID is needed and SQL is essential for running the businesses! Have a nice weekend!!

Anticipatory Computing and Functional Programming – some rambling…

 

After an early morning discussion on Anticipatory Computing on TCS's enterprise social network - Knome,  I thought of making this blog post linking the aspects of “functional orientation” of complex systems with consciousness.

In the computing world, it is generally widely accepted fact that data can exist without any prescribed associated process. Once the data is stored on a medium (generally called as Memory) it can be put into any abstract process trying to derive some conclusions. (This trend is generally called as big-data analytics leading to predictive and prescriptive analytics)

But,

If I mention that function can exist without any prescribed data to it with multiple outcomes, then it is not easily accepted. Only thing people can think about is completely chaotic random number generator in this. Completely data independent, pure function that returns a function based on its own “anticipation” is what is called consciousness.

This is one of my interest areas in computability and information theory. A complex system behavior is not driven entirely by the data presented to it. Trying to model the complex system purely by the past data emitted by the system is not going to work. One should consider the anticipatory bias of the system as well while modeling.

Functional Programming comes a step near to this paradigm. It tries to define the function without intermittent state preserving variables. In mathematical terms a function maps elements of domain to its range. Abstracting this into an anticipation model we get the consciousness (or free will) as a function of three possible return functions.

1. Will do
2. Will NOT do
3. Will do differently
(I have derived this based on an ancient Sanskrit statement regarding free will – kartum, akartum, anyathA vA kartum saktaH)

The third option above (it is beyond binary, 0 or 1) leads to the recursion of this function of evaluation of alternatives and again at (t+Δt) the system has all the three options. When the anticipatory system responds then “data” starts emitting from it. The environment in with this micro anticipatory system is operating is also a macro anticipatory system.

The ongoing hype around big data is to establish the patterns of data emitted from various micro-systems and establishing the function of macro-freewill. It is easier for a micro-freewill to dynamically model the function which is called “intuition” that is beyond the limits of computability.

Enough of techno-philosophical rambling for this Friday! Have a nice weekend.

Science, Research, Consulting and Philosophy

It was this day 25 years back (08-08-1988) I have joined my Bachelors of Science in Computer Sciences course. The aim at that time is be become a Scientist. As the years passed, I have completed my Masters and joined in Indian Space Research Organization.

Due to various reasons, I could not register for a PhD degree nor could continue my Research career. Instead, I started doing software consulting joining TCS, the largest software services company of India. That took me to various business domains starting with Banking moving into Utilities (Gas Transportation), retail, financial services and insurance. Working as a developer, tester, modeller, designer, architect, pre-sales solution support, offshore delivery manager etc., roles gave me an experience worth of PhD.

Later it was a period of working with Oracle in the core Server Technologies division when we were working closely with the select elite customers of Enterprise Manager product who were monitoring and managing large data centers.

A later period it turned out to be philosophy. Philosophy of data, information, knowledge trying to optimize the end to end information flows using the right strategies for the life cycle of information. Efficient data capture from individual transactions. Supporting the operational requirements with the needed latency, making it available in the right format for its human and other computing systems, transforming and moving around efficiently to derive much needed long term strategic decisions etc.,

Most of my career till date has moved through the highs and lows of information technology hype cycles, peaks, waves and magic quadrants.....

Links to the blog posts that are made around 8-August.....

Last year: http://technofunctionalconsulting.blogspot.in/2012/08/multi-tenancy-and-resource-management.html

Before: http://technofunctionalconsulting.blogspot.in/2011/08/web-age-of-www.html

http://technofunctionalconsulting.blogspot.in/2010/08/8035-days-or-22-years.html

http://technofunctionalconsulting.blogspot.in/2009/08/another-year.html

http://technofunctionalconsulting.blogspot.in/2008/08/quick-recap-of-20-years-8888-till.html

Crisscrossing thoughts around #Cloud and #BigData

While “Big Data Analytics” is running on Cloud based infrastructure with 1000s of (virtual) servers, Cloud infrastructure management has become a big data problem!

Assuming all key availability and performance metrics need to be collected and processed regularly to keep the cloud infrastructure running within the agreed performance service levels and to identify the trends of demand for the cloud services there is an absolute need for the predictive analytics on the collected metrics data.

As the data centers gradually turn into private clouds with a lot of virtualization, it becomes increasingly important to manage the underlying grid of resources efficiently by allocating the best possible resources to the high priority jobs. The integrated infrastructure monitoring and analytics framework running on the grid itself can optimize the resource allocation dynamically to fit the workload characteristics could make the data center more efficient and green.

Taking the same approach to the business services across the organizational boundaries, there could be an automated market place where the available computing resources could be traded by the public cloud providers and the consumers can “buy” needed computing resources in the market and get their processing executed by probably combining multiple providers’ resources on an extended hybrid cloud in a highly dynamic configuration.

The data and processing have to be encapsulated at a micro or nano scale objects, taking the computing out of current storage – processor architecture into a more connected neuron like architecture with billions of nodes connected in a really BIG bigdata.

OR

If all the computing needed on this tiny globe can be unified into a single harmonic process, the amount of data that needs moving comes to a minimum and a “single cloud” serves the purpose.

Conclusion: Cloud management using bigdata, and big data running on cloud infrastructure complement each other to improve the future of computing!

Question: If I have a $1 today, where should I invest for better future? In big data? Or in Cloud startup??

Have a fabulous Friday!

Models of Innovation diffusion in social networks

 

Having seen the trust modeling, centrality in social network, this post is the third and last of the series on social network analysis.

Innovation diffusion, influence propagation or ‘viral marketing’ is one of the most researched subject of contemporary era.

---

Some theory:

Compartmental models studying the spread of epidemics, which have susceptible (S), infected (I) and recovered (R) ‘SIR states’ are used to study the influence propagation in the electronic social networks as well. Initially these are descriptive models to describe a specific behavior of nodes when exposed to new innovation or information each node has an initial probability to adapt to that innovation. As each node adapts to the new innovation it has a specific amount of influence on the nodes connected to it.

Primarily two basic models are used to study the spread in a social network. An initial set of ‘active’ nodes at time t₀ exert influence on the connected nodes and at t₁ some of the connected nodes will become ‘active’ with a probability p(i). Each individual node has a threshold θ_i and when the influence from the neighbors is more than this threshold it becomes active. This model is called ‘Linear Threshold’ model. At each step, the set of nodes till the step – 1 remain active and influence their neighbors with a weightage. In independent cascade model each node is given only one chance to influence its neighbor.

---

Based on the above two diffusion models, the maximization problem is to determine the best set of initial ‘active’ nodes in a network to arrive at a best propagation by maximizing influence for ‘viral marketing’ campaign.

It is a NP-hard problem and this paper - http://pdf.aminer.org/000/472/900/maximizing_the_spread_of_influence_through_a_social_network.pdf discusses some interesting approximation algorithm with a general cascade, threshold and triggering models.

Have a good weekend reading!

On Centrality and Power in social networks

After the last weeks post on 'Trust' - http://technofunctionalconsulting.blogspot.in/2013/06/trust-modeling-in-social-media.html - let us quickly review another important measure of (social) network structure.

---

Centrality is a structural measure of a network that gives an indication of relative importance of a node in the graph / network.
Simplest way of measuring centrality is by counting the number of connections a node has. This is called 'degree centrality'.

Another way of measuring centrality is to see how far a node from all other nodes of the graph is is. This measure is called as 'closeness centrality' as it measures the path length between pairs of nodes.

'Betweenness Centrality' is the measure of number of times the node acting as a bridge on the shortest path of any other two nodes. That gives how important each n ode in connecting the whole network.

To complicate the centrality further, we have a measure called 'eigenvector centrality'. Eigenvector considers the influence for the node in the network. This methods considers the power of the nodes the current node is connected. To explain it simply, if I am connected to 500 other people on LinkedIn is different from Barak Obama connecting to 500 of his friends on the LinkedIn. His 500 connections are more influential (probably) than my 500 connections. Google's page rank is a variant of Eigenvector Centrality.

When an external factor is considered for each node and implement eigenvector centrality to consider an external α it is called 'alpha centrality'

When we move the alpha centrality measure from one node to cover multiple radii to include first degree, second degree and so on.. With a factors of β(i) and measure the centrality as a function of influence of varying degrees, it is called beta centrality.

---

The key problem with centrality computation is the amount of computing power needed to arrive at the beta centrality measure of the social network with millions of nodes. I recently came across this paper - https://www.msu.edu/~zpneal/publications/neal-alterbased.pdf which proposes an alternative approximation algorithm which is computationally efficient to estimate fairly accurate centrality measure. This alter-based non recursive method works well on non-bipartite networks and suits well for social networks.

---

Title of this blog states "power" and whole content did not mention anything about it. Generally centrality is considered as the indicator of power or influence. But in some situations power is not directly proportional to centrality. Think about it.

Trust modeling in social media

 

After last week’s “tie strength” post, this week let me give some fundamentals on importance of modeling TRUST in social media.

What is Trust?
It is difficult to define. But when I ask “Will you loan a moderate amount to the other person?” or “Will you seek a reference or recommendation regarding a key decision?” help understand the term TRUST.

There are two components to TRUST. Some people are more trusting than others. Some quickly establish trust where as others take a long time in establishing the trust. This component is not easy to be modeled. The second component is the credibility of the trusted person.

Measuring Trust:
In social media, the second component can be measured by analyzing the sentiment based on the blogs referenced by others. This is called “network based trust inference”.

This paper http://ebiquity.umbc.edu/_file_directory_/papers/375.pdf describes a model for measuring trust using link polarity.

Have a good weekend reading!

"tie strength" in social media

What is "tie strength”?

When analyzing the social web, we see various edges (ties or relationships) connecting the nodes (individuals or organizations). Theoretically the strength of the edge or relationship is categorized as strong or weak. In 1973 paper titled "The strength of weak ties" - http://sociology.stanford.edu/people/mgranovetter/documents/granstrengthweakties.pdf  Mark Granovetter lays foundations of importance of strength of ties in micro and macro levels of sociology.

---

Predictive model
Recently I came across a predictive model developed using Facebook which considers seven dimensions of "tie strength" They are: Intensity, Intimacy, Duration, Reciprocal Services, Structural, Emotional Support and Social Distance.

32 Predictive variables from Facebook interactions have been used along with a survey deriving 5 dependent variables that fits into the predictive model.
The model uses statistical linier method to predict the strength of a relationship in continuous 0 - 1 Scale.

More on - http://social.cs.uiuc.edu/people/gilbert/pub/chi09-tie-gilbert.pdf

I like the methodology used and practical approach towards predictive modelling. More stronger the tie, better influence....

Data Philosophers and data quality

After data scientists and data artists, another need is for "data philosophers”.
http://www.ocdqblog.com/home/the-need-for-data-philosophers.html made me think about the data philosophers.

So, the data scientists are focusing on the underlying technology to gather validate and process the 'big' data and the artists are using the processed 'big' data to paint and visualize the insights.

In this whole process due to its wide variety and velocity (two 'V's of big data!) are we missing on the rigor of quality of data?

Considering the 36 attributes of data quality in the 1972 paper of Kristo Ivanov - http://www8.informatik.umu.se/~kivanov/diss-avh.html and evaluating today's big data insights, I somehow feel there is a 'big' gap in the quality of 'big data'.

I see some parallels in big data processing and orbit determination. As long as the key laws governing the planetary motion are unknown, whatever is the amount of the data from observation we have, we will not be able to explain the ‘retrograde motion’ of the planets. In the same way, if we do not have a clear understanding of underlying principles of the data streams, we will not be able to explain them. That is where we need the philosophers!

Now, I think I am becoming a “Data Philosopher” already!

Data Artist - A new professional skillset?

In past few days, I have seen at least two blogs talking about "Data Artist"

1. http://www.thetibcoblog.com/2013/05/04/forget-being-a-data-scientist-and-become-a-data-artist/
2. http://www.datasciencecentral.com/profiles/blogs/the-rise-of-the-data-artist-in-business

The trend seems to go towards business centric data visualization of so called "big data".

Definition:
One who can use data as the paint and create art that can represent massive flows of data and visualize the patterns in a way business users are delivered with a lot of “information” in a single glance.

---

It is slightly different from the “Data Scientist” profession. Data Scientists are focused on technical process of collecting, preparing and analyzing the data for patterns where as the Data Artists specialize in visualizing the discoveries in an artistic manner!

"Scientific Artists" and "Artistic Scientists" with Data! Are we complicating the matter too much??