hadoop, part 2: jyte cred graph

Following from Part 1 in the series, this article takes a look at an initial application in Hadoop, using a simplified PageRank algorithm with graph data from jyte.com to illustrate a gentle introduction to distributed computing. The really cool part is that this runs quickly on my MacBook laptop, the same Java code can run and scale without modification on Amazon AWS, on an IBM mainframe, and (with minor changes) in the clouds at Yahoo and Google. Source code is available as open source on Google Code at:

http://code.google.com/p/ceteri-mapred/

The social networking system jyte.com provides means for using OpenID as primary identification for participants – at least one is required for login. Participants then post "claims" on which others vote. They can also give "cred" to other participants, citing specific areas of credibility with tags. The contacts API provides interesting means for managing "social whitelisting".

Okay, that was a terribly dry, academic description, but the bottom line is that jyte is fun. I started using it shortly after its public launch in early 2007. You can find a lot more info on their wiki. Some of the jyte data gets published via their API page – essentially the "cred" graph. Others have been working with that data outside of jyte.com, notably Jim Snow's work on reputation metrics.

Looking at the "cred" graph, it follows a form suitable for link analysis such as the PageRank used by Google. In other words, the cred given by one jyte user to another resembles how web pages link to other web pages. Therefore a PageRank metric can be determined, as Wikipedia describes, "based upon quantity of inbound links as well as importance of the page providing the link." Note that this application uses a simplified PageRank, i.e., no damping term in the difference equation.

Taking the jyte cred graph, inverting its OpenID mapping index, then calculating a PageRank algorithm seemed like a reasonably-sized project. There are approximately 1K nodes in the graph (currently) which provides enough data to make the problem and its analysis interesting, but not so much to make it unwieldy. Sounds like a great first app for Hadoop.

The data as downloaded from jyte.com has a caveat: it has been GZIP'ed twice. Once you get it inflated and loaded into the HDFS distributed file system, as "input", the TSV text file line format looks like:

from_openid to_openid csv cred tags

Pass 1 in Hadoop is a job which during its "map" phase takes the downloaded data from a local file, and during the "reduce" phase it aggregates the one-to-many relation of OpenID URIs which give cred to other OpenID URIs. See in the Java source code the method configPass1() in the org.ceteri.JyteRank class, and also the inner classes MapFrom2To and RedFrom2To. The resulting "from2to" TSV text data line format looks like:

from_openid tsv list of to_openids

Pass 2 is a very simple job which initializes rank values for each OpenID URI in the graph – starting simply with a value of 1. We'll iterate to change that, later. See the method configPass2() and also the inner classes MapInit and RedInit. The resulting "prevrank" TSV text data line format looks like:

from_openid rank

Pass 3 performs a join of "from2to" data with "prevrank" data, then expands that into individual terms in the PageRank summation, emitting a partial calculation for each OpenID URI. See the method configPass3() and also the inner classes MapExpand and RedExpand. The resulting "elemrank" TSV text data line format looks like:

to_openid rank_term

Pass 4 aggregates the "elemrank" data to sum the terms for each OpenID URI in the graph, reducing them to a rank metric for each. See the method configPass4() and also the inner classes MapSum and RedSum. The resulting "thisrank" TSV text data line format looks like:

to_openid rank

The trick with PageRank is that it uses a difference equation to represent the equilibrium values in a network, iterating through sources and sinks. So the calculation generally needs to iterate before it converges to a reasonably good approximation of the solution at equilibrium. In other words, after completing Pass 4, the code swaps "thisrank" in place of "prevrank" and then iterates on Pass 3 and Pass 4. Rinse, later, repeat – until the difference between two successive iterations produces a relatively small error.

source: Wikipedia.org

Whereas Google allegedly runs their PageRank algorithm through thousands of iterations, running for several hours each day, I have a hunch that jyte.com does not run many iterations to determine their cred points. Stabbing blindly, I found that using 9 iterations seems to produce a close correlation to the actual values listed as jyte.com cred points. A linear regression can then be used to approximate the actual values:


My analysis here is quite rough, and the code is far from optimal. For example, I'm handling data in-between the map and reduce phases simply as TSV text. There could be much improvement by using subclassed InputFormat and OutputFormat definitions for my own data formats. Even so, the results look pretty good: not bad for one afternoon's work, eh?

I have big reservations about PageRank for web pages, since it assumes that an equilibrium state effectively models attention given to web pages. PageRank provides a mathematical model for a kind of "coin toss", where a user looking at a browser either chooses to navigate to some random URL (with probability 0.15) or they follow one of the links on the current page (with probability 0.85). In practice that implies how some important web pages will experience substantial latency before PageRank begins to "notice" them, since PageRank must wait for (a) other pages to link to the new page, and (b) their web crawlers to visit and analyze those changes. That process can take several days.

A more realistic model of human behavior might take into account that – contrary to Google PageRank assumptions – people do not navigate to some random URL because it is in their bookmarks or is their individual home page. That might have been the general case in 1998, but these days I get my fix of random URLs because of email, IM, RSS, etc., all pushing them out to me. In other words, there is an implied economy of attention (assuming I only look at one browser window at a time) which has drivers that are external to links in the World Wide Web. In lieu of using equilibrium models, the link analysis might consider some URLs as "pumps" and then take a far-from-equilibrium approach.

Certainly, a site such as CNN.com demonstrates that level of network effects, and news events function as attention drivers.

But I digress.



A simplified PageRank analysis based on an equilibrium model appears to work fine enough to approximate jyte.com cred points. It also illustrates how to program within the Hadoop framework. I have ulterior motives for getting jyte cred graph data into Hadoop – which we'll examine in the next part of this series.

a sample chart

Been wanting to try out the recently released Google Chart API. It looks great for implementing things on web pages like Tufte's sparklines.

So here is a sample chart, with my respective ethnicity. Our family is a mixed bag, part which looks like a cross-section of early North America, and part looks like a cross-section of Central Asia, sampled right along the Silk Route. These things happen.

Anywhoo, it took all of about 2 minutes to build a first chart and have it labeled and colored the way that I wanted. All that plus the data is URL-encoded. Nice work, GOOG.

Meanwhile, happy Chinese New Year!

three laws of avatarics

Susan Wu, an associate at CRV, wrote an excellent critique recently in the article Second Life: Incredible innovator, but probably not sustainable:

Their high technical barriers to participation and the fact that SL is a closed standards system ultimately deters them from reaching mass market adoption.

She followed a few days later with an example from the other end of the spectrum:

APIs, like open source, facilitate economies of scale around the development process and create network effects for the core product.

I agree with both points, but I'd like to look in closer detail about why a virtual world suffers by being "closed", and what it means to be "open". First, a little background... It's important to state: we do not live in virtual worlds, rather we project aspects of our persona into these worlds. We engage in interaction with other projected or automated personae - but we do so solely as observers of those worlds. For instance, the avatar sitting next to you at a conference in Second Life is most likely some projected persona of another observer, and the NPC you confront inside World of Warcraft is an automated persona, functioning as a relatively limited observer.

One area of systems theory called autopoiesis seeks to apply rigorous definitions from biology to explore notions of "openness" and "closure" for systems. It also examines projected aspects of observers, sustainability and regulation, and some basis for defining "cognition" in terms of interaction. I'll dive into systems theory in gory detail later, but it seems apropos for a review of Susan Wu's perspective. For now let's make a point that a virtual world can be called a "domain of discourse", and that we as users and businesses involved in a world represent projections of that world's observers.

Let's also note a special term: "personification". I use it to describe how we project our persona, our identity, crossing Edward Castronova's membrane into the many different online worlds. In the sense that "Web 2.0" successes were built on a foundation of "personalization", the successful virtual worlds will likely be those which find effective ways to manage and leverage "personification".

Some interesting conclusions follow from systems theory - issues not usually associated with "virtual reality", "social networks", or media in general, such as implications for how complex behaviors in-world may become computable and perhaps predicted based on cellular automata. More to our point, these open/closed world issues speak to what is permitted as actions by automated systems and intelligent machines. In other words, the relative "openness" of a virtual world such as SL is, according to theory, strongly coupled with what we would permit or require of robots. Not surprisingly, given how recent furor over "CopyBot" has created some of the fiercest philosophical and commercial disputes in SL's history.

***

As the Technical Director of HeadCase Humanufacturing, Inc., a start-up focused on avatars and related technologies, I recently looked online for a term to describe the study of avatars. While there may be several cheesy sites advertising "avatars" as personal icons for chat boards, there seemed to be little in the sense of science or other phenomenology. The fact that so many of us visit virtual worlds such as SL may currently be hot news in the pages of Wall Street Journal or Financial Times; however, what we do with our personifications in those worlds does not yet seem to rate its own name as a branch of academia.

Thinking that "avatars" might be considered analogous to "robots", I tried searching for the term "avatarics". Only one search hit appeared in Google, located in a German entry of Wikipedia (see English translation by its author). That page describes the concept of intellectics as suggested by Wolfgang Bibel:

Intellectics explains human intelligence by designing systems that possess it.

Bibel includes avatarics as a sub-discipline of intellectics, roughly translated as: The science that seeks to design ... anthropomorphic intelligent autonomous agents that act in virtual environments.

Now that we have a name to use, let's return to our point about virtual worlds, openness, and robots. Parallels between avatarics and robotics which Bibel mentions are not new. Many researchers - and several disciplines other than systems theory - have analyzed the overlap of robotics into virtual worlds. As virtual worlds evolve, a large existing body of engineering, sociology, economics, etc., could potentially be carried over from robotics - and vice versa. However, "what we would permit or require of robots" seems particularly interesting.

That got me thinking about Isaac Asimov, who stated his famous Three Laws of Robotics in 1941:

1. A robot may not injure a human being or, through inaction, allow a human being to come to harm.
2. A robot must obey orders given it by human beings except where such orders would conflict with the First Law.
3. A robot must protect its own existence as long as such protection does not conflict with the First or Second Law.

For what it's worth, Asimov "prefixed" another law the following year: A robot may not harm humanity, or, by inaction, allow humanity to come to harm. The first three gained the most notoriety, and let's focus on those.

There have been several variations on Asimov's original theme, popping up throughout literature and science. For example, Mark Tilden took a pass at those Three Laws as:

1. A robot must protect its existence at all costs. ("assert thyself")
2. A robot must obtain and maintain access to its own power source. ("sustain thyself")
3. A robot must continually search for better power sources. ("get thee thither in a whirlwind")

Tilden's view lent a more practical, "life coach" approach for earnest robots. (Elizabethan parentheticals added to track subtext).

***

I tend to agree with elements of both Bibel and Tilden. Though my university studies and 20 years since in the industry have generally focused on "AI", I rarely believe the claims attributed to Strong AI. Bibel's description of "designing systems that possess human intelligence" meshes well with my preferred approach: solutions based on autopoiesis as an area of systems that incorporates a rigorous view of cognition. In other words, I build systems as networks of human interaction, where both the humans and the computers participate together as observers.

As for Tilden's view... When we first began to write specs for HeadCase, we sought technical criteria for rating the effectiveness of the avatar API in a particular online game or virtual world. In our development work, we have found the following three criteria to be helpful in determining the "openness" of various virtual words, with respect to third-party vendors:

1. The world must provide external API for controlling avatars.
2. The world must allow third-party to include code plugin/module.
3. The world must support use of external web services (HTTP, XMPP, etc.)

As a third-party vendor in virtual worlds, I enjoyed how our criteria followed Tilden's pattern of "assert", "sustain", and "thither". I offer these criteria as the Three Laws of Avatarics for evaluating the viability of a virtual world with respect to its broader, external context of social and economic systems. Consider these as preconditions for the network effects that Susan Wu mentioned.

It's clear that SL is lacking (read: broken) in terms of its avatar API and LSL scripting. Much of what could be useful has been disabled, often justified by needs for security. Competing virtual world platforms such as There.com don't even begin to meet the criteria listed above. While there is the excellent Lua scripting language and interesting API support in WoW, it appears that Blizzard has a relatively poor track record when it comes to enabling third-parties and external services (though I'd love to be proven wrong about that). Considering the wealth of "Web 2.0" resources online, both Linden and Blizzard appear to have sequestered themselves into cozy little hideaways. Is that wise?

Intuitively, the answer would seem to be a loud, resounding "No!" Much of what has succeeded on the Internet has worked because of its inherent openness and interoperability. In terms of virtual worlds, however, I wanted to find a more analytic answer.

* * *

Back to our discussion of systems theory, Maturana and Varela stated in their seminal 1980 text on cognition that, "Everything said is said by an observer." (See pp. 38-40, especially...) Considering their discourse, I have a hunch that M&V would have described a virtual world as a "domain of discourse", had such ideas been within their realm of experience; it'd be a fun question to ask Maturana personally.

Randall Whitaker has commented on their work extensively. He paraphrased about observers with:

A cognizing system engages the 'world' only in terms of the perturbations in its nervous system, which is 'operationally closed' (i.e., its transformations occur within its bounds). To the extent that the nervous system recursively interconnects its components (as in our brains), the organism is capable of generating, maintaining and re-engaging its own states as if they were literal re-presentations of external phenomena.

I wouldn't expect many SL or WoW users to endure the post-modern jargon beloved by us systems theory geeks, but the part about "generating", "maintaining", and "re-engaging" makes an interesting callback to our "assert", "sustain", and "thither" criteria for virtual worlds. Whitaker and others describe more detailed properties of complex, sustainable (read: living) systems, including "self-creation", "self-maintenance", "self-reproduction", etc. Fritjof Capra and a few other authors have even managed to craft explanations of complex systems into entertaining texts. While their descriptions may not be quite as tightly packed as the "Three Laws", it looks to me as if Tilden was headed in a good direction.

Whitaker's mention of operational closure deserves a much closer look. Consider that Maturana and Varela had been working in biology - and think about some of the properties of living cells. A cell wall prevents the all-important protoplasmic goo inside from spilling out into its environment. At the same time it allows food to be "captured" and wastes to be "expelled". The system has properties which are both "open" and "closed". In the dynamics of a living cell, this effect provides operational closure as means for using selection to determine what goes in or out... as M&V described, in a process of cognition.

Looking at computer systems, particularly looking at behaviors on large networks, we find a similar property of operational closure at the heart of enterprise network security - at least for any good security practice. This is where Linden and Blizzard miss their mark, in terms of sustainable business models. On one hand, Linden has clamped down on its API and third-party support, ostensibly for the sake of security, and yet they've left SL flying high, wide and handsome when it comes to security breaches - which have nearly become a weekly spectacle. Their operational closure has been "aimed" in the wrong directions. Blizzard, on the other hand, is simply closed - with not much hope for sustainable "protoplasmic goo" there.

In contrast, based on theory reported by Maturana, Varela, Winograd, Capra, Whitaker, et al., I have a hunch that we can determine reasonable estimators to indicate whether or not a virtual world could sustain itself in the long run. In particular, I'd point toward the (relatively obscure) works of former Stanford professor Niklaus Luhmann, who made controversial applications of M&V's autopoietic theory in sociology. Again, be forewarned about profuse jargon, dense texts, and systems theory geekness, but if you can endure it you might gain a sense for an interesting theoretical basis of where and how virtual worlds may evolve. Required reading in the study of avatarics.

***

In my survey of the emerging metaverse, I must give ample credit to Trevor Smith, who articulated a very good set of criteria for Ogoglio City - looking beyond SL toward a next-generation approach. I agree with Susan Wu that APIs, like open source, facilitate economies of scale, since the trajectory of "Web 1.0" and "Web 2.0" seem utterly contingent on that point. From that perspective I highly recommend taking a good look at Trevor's work, along with a few others who seem to get the point. Efforts which follow our criteria also include Croquet, Uni-verse, and the RESTful, Ajax-based Hive7. It looks as if Multiverse could also fit the previously mentioned criteria, though its "60% of revenue" requirement seems questionable as a sustainable practice, albeit in line with their support base in Redmond and Hollywood. It recalls the haphazard form of closure practiced by Linden and Blizzard.

Meanwhile, we're keeping a close watch on avatarics and operational closure as these virtual worlds evolve. We have good company too, considering that IBM appears to be watching for similar properties to emerge.

aws rocks the free world

Amazon Web Services (AWS) is perhaps one of the most fundamental and far-reaching changes in the computer industry ... since perhaps when, recently, SecondLife hit the cover of BusinessWeek magazine. In fact, this news will be the cover story of BusinessWeek next week.

I knew about a friend working on this project a couple of years ago, and helped a little (on the sly) with documenation. So when it came time to provide offsite backup services for HeadCase, we thought it might be good to check out AWS. Price-performance comparisons showed 90% reduction in cost over going to an ISP or other backup service, plus the Amazon approach ("S3") had better reliability and other uses, such as tiered storage.

Overall their "cloud" of grid/utility computing services allows a small technology startup to begin playing with REALLY big scale services - it fits almost perfectly for those of us who share a perspective of REST + SOA. With "S3" as a storage grid, "EC2" as a compute grid (Linux images, Java API), "SQS" as a transaction message queue (somewhat reminiscent of IBM's MQ), and MTurk for the "human computation" and crowdsourcing, this business strategy precipitates a fundamental shift in how to plan for IT infrastructure, how to manage QA resources, etc.

As an engineering manager, I would expect to pay a lot to get access to that kind service - especially giving Amazon's remarkable quality of service. Instead, I pay pennies on the dollar compared with a hosted service - and moreover I don't have to staff up my operations, since Amazon handles that as "outsourcing". And thereby our firm inherits that quality of service, since the Amazon AWS services handle the public-facing aspects of our SOA.

The bottom line here: the fundamental issue with cost of scaling Internet infrastructure is not the processors (thank you very much, Dell or HP) but instead - as IBM knows oh so well - the utilities involved, such as power. Amazon is building out data centers in the Pacific Northwest, located near cheap, plentiful hydroelectric power generation. This has a significant Green effect, optimizing the electrical power generation and usage by collocation, then exporting the "refined" use as data center services.

This almost as major change in the industry as when DNS was invented, or HTTP/1.0 became accepted, or Skype launched. Wall Street is tending to comment that Amazon is not following a core strategy, without clearly understanding that Amazon has just put several big players on notice for substantive business model disruptions: notably IBM, Microsoft, Google, EMC, HP, BMC, (and for what it's possibly still worth) Sun. As the article in BusinessWeek does mention, this is clearly a good strategy for launching a tech startup with vastly reduced capital and substantially enhanced quality and scalability. In other words, in the eyes of VCs, that implies better opportunities to leverage capital.

Here is an example pattern of usage:

1. Design your data model to be stored in the Amazon S3 storage grid. For example, we have requirements for running a Java JSR 170 content management system, which fits well with S3 capabilitities.
   
2. Prepare images for your application servers (Java, PHP, whatever) to run on Amazon EC2.
   
3. Point the client side of your applications, such as Ajax requests, at the Amazon SQS message queue.
   
4. Allocate your server images in the EC2 cloud to pull requests off your SQS queue.
   
5. Your middle tier processes requests within EC2, persisting data out to your S3 storage.
   

You can also run "back office" tasks such as reporting or data mining based on the same pattern - without disrupting customer services.

I've read about people beginning to use this kind of pattern to setup their QA environment for regession testing or load testing - again without disrupting other operations or requiring costly server + network replication.

It would seem to fit quiet well in, say, with Java Server Faces used for an Ajax UI... based on a tech stack that used Seam, clustered JBoss servers, Hibernate for the persistence layer, and clustered MySQL underneath that.

iran, leading the blogosphere

Oh, this is amazing...

Mahmoud Ahmadinejad, president of Iran, has a blog.

As my wife pointed out over my shoulder, now the real political leaders of the world not only have speech-writers, they must have blog-writers.

My paternal family name notwithstanding, I'm no fan of the Imams. Even so, their chess game played on the entire world over the past few decades (during all of my adult life, at least) has been brilliant. They've played the pieces in Iraq, Afghanistan, and now the Levant, pulling in China, Russia, India, and even Europe to argue their side, while cutting a deal with the US under the table. For the punchline, they timed their endgame during a faltering Republican administration.

In comparison, the US has lagging media savvy. Hillary Clinton's blog seems like an f-ing joke, though John McCain's blog at least seems to represent the guy. Guiliani has no clue about blogs, apparently.

Reading the post by Ahmadinejad, admittedly the Iranians who stood up against Iraq - with the US and its "friends" antagonizing from all sides - showed more cojones than have ever been observed in Tel Aviv or Washington, DC. As were those who stood up to the "Shah", which I'm grateful was removed from this world. I guess that after compromising the Bush legacy this way, the next monster in line for Iran to defeat may be Wal-Mart :)

You know, I'm proud to be (half) Iranian, but today in particular I am really proud.

I'm sorry about warfare in the Levant, and especially sorry about the horror brought on beautiful Lebanon - but that horror will never end anyway until the US recognizes Syria, while pulling the pants off Israel, Egypt, and Saudi Arabia. Of course, cutting the US dependency on petroleum will do that anyway. It's only a matter of time.

have software agents declined?

Have efforts toward developing effective software agents declined?

During the 1990s, it seemed as if "personal assistants", "intelligent agents", "bot", - whatever you want to call them - were poised to take over the Internet.

For what it's worth, Wikipedia does a fine job of defining what an "agent" is - or rather, what is not an agent.

Looking at a reference search site, such as Google Scholar, shows thousands and thousands of research papers from one PhD candidate or another who proposes a scheme or an architecture for agent-based simulation, etc. Given such a wealth of plans, where are the commercial successes?

Yet, looking at some of the sites which catalog work on agents, such as UMBC AgentWeb or BotSpot, it seems as if new items tapered off after the year 2000.

What happened? My hunch is that several things happened at once...

• Circa 1997, Pattie Maes and company at MIT Media Lab emphasized having "agent" technology embedded within online communities, with the success of Firefly.


• Circa 2000, the Internet "bubble" burst, but the successful examples among the so-called Web 2.0 firms - such as Google, Yahoo, MSN, Amazon, eBay - leveraged the notion of agency and personalization with their browser-based features and web services.

So far, no nascent "H.A.L." has emerged to handle searches better than Google - at least not for most people. Even so, circa 2006, are there "intelligent agents" on the horizon? Our firm wants to understand this issue better, so we asked the question on Google Answers.

What do you think?

---

tags: agents

first day at the new job

It was my first full day at the new job. Still in stealth, we're making good progress. As the Technical Director, my day starts out with a quick peek through Gmail. What's come in from our Executive Producer in Australia before she called it a night? There's a blurb from Google Calendar, describing my agenda for Skype meetings throughout the day. Any news from LA while I was alseep? A few personal messages, then check through Google Reader for interesting news - maybe I'll forward one or two to my partners. Shut down the iBook, time to spend a while with the kids, feed the chickens and the koi, do a few dishes, clean up my new "office" space in the oven-temperature garage, and then off to my real workplace... Just a short ride away on the mtn bike to park for a few hours in a local coffeehouse. Austin has 40C weather, but early in the day it's not so bad; ozone levels won't peak until much later in the day.

Curling up to a mocha and iBook, it's time to twiddle for a while on the company's network architecture diagram, then get to real work for the day on Second Life, winding my way through LSL. Two aging Boomers at the next table are scamming/being scammed for an investment in a bogus Third World water treatment technology. They stare nervously, trying to detect anyone who's seeking to steal their IP. I have my headset blasting Thirteenth Step to drown out the ambient babble so I may focus. This is how life was meant to be.

After a few espresso shots and plenty accomplished, I put my helmet and cleats back on, and ride back home just about the time the sitter is leaving. At few more dishes done, never enough of that with two toddlers in the house. Watching the younger girl while my wife gets a breather. Later, I'm back in Skype to catch a conf call with our Executive Producer and Creative Director, getting prepared for some video production work.

I have time again. Time to spend with my wife and kids. Time to think about what I'm working to build online, or what I need to write. Time to nurture a small urban farm, to show my daughters the different kinds of trees on our property. Time to cook food, slow food, the kind of food that doesn't cost 4x for convenience while causing excess obesity amongst the population, such as most of Corporate America "enjoys" for lunch. Food that makes me feel healthy, working at full potential. Time to rest. Time to return to my regular practice of yoga, fitness training, and mountain biking. Time to exist in my own personal terroir. Time to become, again.

On one hand, some things about my previous job will be missed dearly: some good friends met (online or in the office) daily, a wonderful developer team in Russia, the health insurance package, ... but not the mainframes. On the other hand, I'm enjoying the entertainment business much, much better already :)

Meanwhile, I tend to judge my quality of life based on a couple of factors: how few times per week I must drive a car, and how many times per day I get to cook my own meal. So far, so good!

---

tags: Second Life, Slow Food, Terroir