John Glaser on Healthcare Information Technology

I recently sat in on a lecture for Professor Peter Szolovits’s Biomedical Computing course. The lecture was open to a greater audience, given the prominence of the speaker. As a non-expert, I found it to be a useful look into the current state of healthcare IT and the coming legislative and technical challenges facing the industry. My notes are below.

John Glaser, Ph.D.
Formerly CIO of Partners/Brigham And Women’s Hospital
Currently CEO of Siemens Health Services

Free advice: get a healthcare proxy and power of attorney set up. Easier to do now than have someone else guess later how you want to live/die.

Why does Health IT suck?

Not for lack of money put into the system
Not for lack of smart people working on the problem

Current model

Insurance companies/patients pay per volume (per birth, per surgery, etc.) almost regardless of quality
Boards of directors are very conservative. Don’t want to be the board that made an IT decision that made a huge hospital fail.

U.S. Numbers to give context

60% of hospitals are <= 100 beds
Of 500K physicians, majority work in 2-3-doctor practice (not IT-savvy, or modestly interested in IT at best)
2/3 of medical decisions are heuristic/not scientific, and many have a difficult-to-verify outcome
volatile knowledge domain: 700k academic articles have come out in the last (decade?)
20% of doctors are a decade away from retirement, so perhaps newer doctors will bring IT mentality with them?
PricewaterhouseCoopers survey: 58% of (independent?) doctors considering quitting, selling practice, or joining a larger practice
various societies are discussing requirements: to become board (re-)certified (oncology, etc.), you have to show facility in technology.

Health IT Services

huge fragmentation: the 3rd largest health IT services company has 7% of market. if they win every open engagement from now until (?), they will have 11% of the market.
lots of players: 300 electronic health record providers in US, 25% exit and 25% enter per year
engagements are long: bringing up a new hospital IT system takes 2-4 years. from the moment you decide to change IT systems, you will continue to use your old one for the next 4-5 years as you transition.

Affordable Care Act (ACA)

costs are projected to go up 26% in the next decade. ACA stipulates that govt. will compensate 12% more in the next decade: providers have to make up the difference.
to incentivize quality care, govt. will hold on to 10% of payments until you prove treatment was effective (hard to define).
currently, for a single procedure (e.g., total hip replacement) you might get 12 different bills (e.g., surgeon, materials, anesthesia). new system: govt. pays a single provider one bill, with a fixed amount. incentivizes a holistic view.
risk: hospitals go out of business. potential future doctors don’t enter medicine. doctors “fire” bad patients to make their numbers look good.

Consolidation

doctors in small practices joining larger networks to avoid managing the ACA requirements.
single payment requirement will cause groups of doctors to more tightly collaborate (contractually).

Transition challenges

ACA is rolling out over the course of a decade.
need to be careful, since some patients will be handled by old rules, and some by new rules. so do you not apply decision support-based treatment to patients on old rules, or just do fee-for-service? lots of mental overhead for doctors.

Fixed fee challenges

paying a fixed amount per treatment doesn’t work for everything. Diabetes is sort of predictable, but a trauma might range from a broken toe to severe burns on 90% of body.
(Adam’s note) perhaps large pools of insured patients will smooth over the individual spikes in cost of care.

Information Technology needs

systems must span inpatient, outpatient, emergency care, rehab
need revenue cycle + contract management system that handles continuum of care. this is complex: medicare + blue cross might pay diff amounts for “good” diabetes treatment, and “good” might be defined differently.
systems should manage individuals and populations: how did all 100 people w/ respiratory problems do last month? which patients strayed from predicted path? what should have happened? why/why not?
sophisticated business intelligence + analysis: predict who will get worse, etc.
interoperability w/ different providers
rules+workflow engines to ensure followups/next steps/help primary care doctors coordinate care, manage exceptions, follow up properly. also allow this in collaborative care environment w/ lots of specialists checking in and out.
high availability + low total cost of ownership
engage patients

New challenges for primary care physicians (PCPs)

At the moment, PCP moves from one patient to the next every 15 minutes, sees 100s of lab results per day
Only 25% of data from specialists comes back to a PCP within a month
In future, PCPs will be responsible for closing the loop on specialists, tests, etc., with more accountability, but still be given just as much or more information, with similar delays. Workflow management systems are key here!

Interesting technical challenges

filtering patient care notes: 10s of pages of patient care history. No doctor can read them all before seeing patient. how to help doctors find relevant notes across different doctors, annotations, etc.
supporting collaboration between multiple providers
parsing notes to remind providers. e.g., “Ask about patient’s daughter next time.”
cleaning up conflicting medical record data: was it type 1 or type 2 diabetes? was it a heart attack, or just a test for one?

Human-powered Sorts and Joins

(Cross-posted on the Crowd Research Blog)

There has been a lot of excitement in the database community about crowdsourced databases. At first blush, it sound like databases are yet another application area for crowdsourcing: if you have data in a database, a crowd can help you process it in ways that machines cannot. This view of crowd-powered databases misses the point. The real benefit of thinking of human computation as a databases problem is that it helps you manage complex crowdsourced workflows.

Many crowd-powered tasks require complicated workflows in order to be effective, as we see in algorithms like Soylent’s Find-Fix-Verify. These custom workflows require thousands of lines of code to curry data between services like MTurk and business logic in several languages (1000-2000 in the case of Find-Fix-Verify!). If we provide workflow developers with a set of common operators, like filters and sorts, and a declarative interface to combine those operators, such as SQL or PigLatin, we can reduce the painful crowdsourced plumbing code while focusing on a set of operators to improve as a community.

This is not an academic argument: Find-Fix-Verify can be implemented with a FOREACH-FOREACH-SORT in PigLatin, or a SELECT-SELECT-ORDERBY in SQL, resulting in several tens of lines of code. All told, we can get a two order-of-magnitude reduction in workflow code. The task at hand is thus to make the best-of-breed reusable operators for crowd-powered workflows. In our VLDB 2012 paper, we look at two such operators: Sorts and Joins.

Sorts

Human-powered sorts are everywhere. When you submit a product review with a 5-star rating, you’re implicitly contributing a datapoint to a large product ranking algorithm. In addition to rating-based sorts, there are also comparison-based ones, where a user is asked to compare two or more items along some axis. For a particularly cute example of comparison-based sorting, see The Cutest, a site that identifies the cutest animals in the world by getting pairwise comparisons from heartwarmed visitors.

The two sort-input methods can be found in the image below. On the left, users compare five squares by size. On the right, users rate each square on a scale from one to seven by size after seeing 10 random examples.

In our paper, we show that comparisons provide accurate rankings, but are expensive: they require a number of comparisons quadratic in the number of items being compared. Rating is quite accurate, and cheaper than sorts: it’s linear in the number of items rated. We also propose a hybrid of the two that balances cost and accuracy, where we first rate all items, and then compare items with similar ratings.

These techniques can reduce the cost of sorting a list of items by 2-10x. Human-powered sorts are valuable for a variety of tasks. Want to know which animals are most dangerous? From least to most dangerous, a crowd of Turkers said:

flower, ant, grasshopper, rock, bee, turkey, dolphin, parrot, baboon,
rat, tazmanian devil, lemur, camel, octopus, dog, eagle,
elephant seal, skunk, hippo, hyena, great white shark, moose,
komodo dragon, wolf, tiger, whale, panther

The different sort implementations highlight another benefit of declaratively defined workflows. A system like Qurk can take user constraints into account (linear costs? quadratic costs? something in between?) and identify a comparison-, rating-, or hybrid-based sort implementation to meet their needs.

Joins

Human-powered Joins are equally pervasive. The area of Entity Resolution has captured the attention of researchers and practitioners for decades. In the space of finance, is IBM the same as International Business Machines? Intelligence analysis runs into a combinatorial explosion in the number of ways to say Muammar Muhammad Abu Minyar al-Gaddafi’s name. And most importantly, how can I tell if Justin Timberlake is the person in the image I’m looking at?

We explored three interfaces for solving the celebrity matching problem (and more broadly, the human-powered entity resolution problem). The first is a simple join interface, asking users if the same celebrity is displayed in two images. The second employs batching, asking Turkers to match several pairs of celebrity images. The third interface employs more complex batching by asking Turkers to match celebrities arrayed in two columns.

Simple Joins, Naive Batching, and Smart Batching

As we batch more pairs to match per task, cost goes down, but so does Turker accuracy. Still, we found that we can achieve around a 10x cost reduction without significantly losing in result quality. We can achieve even more savings by having workers identify features of the celebrities, so that we don’t, for example, try to match up males with females.

We’re Not Done Yet

We now have insight into how to effectively design two important human-powered operators, sorts and joins. There are two directions to go from here: bring in learning models, and design more reusable operators.

Our paper shows how to achieve more than order-of-magnitude cost reductions in join and sort costs, but this is often not enough. To further reduce costs while maintaining accuracy, we’re looking at training machine learning classifiers to perform simple join and sort tasks, like determining that Cambridge Brewing Co. is likely the same as Cambridge Brewing Company. We’ll still need humans to handle the really tricky work, like figuring out which of the phone numbers for the brewing company is the right one.

Sorts and joins aren’t the only reusable operators we can implement. Next up: human-powered aggregates. In groups, humans are surprisingly accurate at estimating quantities (jelly beans in a jar, anyone?). We’re building an operator that takes advantage of this ability to count with a crowd.

For more, see our full paper, Human-powered Sorts and Joins.
This is joint work with Eugene Wu, David Karger, Sam Madden, and Rob Miller.

I’m a (STEM) Graduate Student: Please Tax Me

Over the past month, a petition has been circulating asking the Obama administration to bring graduate student stipends back to their pre-1986 tax-exempt status. I urge you to not sign this petition, as it is misguided and damaging to our image. If you believe graduate student researchers are more valuable than their compensation, then demand more compensation, not a tax loophole.

First, the caveat: I can only speak for the STEM fields. In these fields, a combination of government, corporate, and university grants support research-track students in the lab and classroom. This compensation usually comes in the form of full tuition coverage and a stipend in the range of $1500-$2500 per month, and sometimes includes health coverage.

Our stipends put our yearly income at $18,000-$30,000/year. Compare this to a poverty threshold of $18,530 for a family of three, or $29,990 for a family of six. In computer science, you can double your income with a summer internship, placing you above the median 2009 household income. At first glance, it seems like we are reasonably compensated before we take into account the education, advising, networking, and travel opportunities our life decision has earned us.

Of course, the argument in the petition is more nuanced than one of unreasonable taxation. The petition speaks to the value of our “innovative, cutting-edge thinking” relative to “bankers, lobbyists, or hedge-fund managers.” The comparison is certainly timely, but sweeps under the rug other valuable fields, like Nursing or Carpentry. Both of these fields earn more than the median graduate student in STEM, but optimistically, we are in a position of higher upward mobility once we graduate.

Perhaps a better comparison is what we could earn if we had not chosen graduate studies. With a B.S. in Computer Science, my undergraduate colleagues at large technology firms and startups are earning 3-5x what I earn through my stipend. Am I more valuable as a researcher than I would be in their shoes? This seems like a good conversation to have.

This is a discussion one of relative value. In the absolute sense, graduate students in STEM are not poor, and should pay taxes in whatever tax bracket we fall. Perhaps we’re not compensated enough for what we provide to society. I would like to believe that STEM’s contribution to social and economic development is significant. If we’re seeing a dirth of STEM researchers and our value to society is high, the market failure should be supplemented by the government. Not in the form of yet another tax break, but as an increase in the number of stipends or the amount of compensation distributed per researcher.

STEM is under attack. We should elevate its image by discussing how valuable our work is, not by asking for pity. Demand what you are worth, but remember how lucky you are.

Database papers at CHI

There is little I like more than a fine cheese and fresh-baked bread. Still, to fill the rest of my day without expanding my waistline, I go for a mix of databases and human-computer interaction. That’s why I was excited to see several database-oriented papers presented at CHI. While many papers contained some amount of data, I’ll stick to the three that are unquestionably of interest to the databases community.

The first paper was for the social scientist in all of us. Amy Voida, Ellie Harmon, and Ban Al-Ani presented Homebrew Databases: Complexities of Everyday Information Management in Nonprofit Organizations. Nonprofits are arguably some of the most difficult database users to design for. They have minimal resources, rarely employ fulltime technical staff, and solve non-core problems as they show up. This practice leads to homebrew, just-functional-enough solutions to many data management problems. The authors provide an interesting qualitative study of how nonprofits manage volunteer demographic and contact information. They provide descriptions of the homebrewed, often fractured collections of data stored in several locations. Reading this paper, I couldn’t help but think of how perfectly these homebrewed databases resembled Franklin, Halevy, and Maier’s dataspaces.

Sean Kandel presented Wrangler, a project he’s been working on with Andreas Paepcke, Joe Hellerstein, and Jeff Heer. Wrangler lets users specify transformations on datasets by example. Each time a user shows Wrangler how to modify a record (or line of unstructured text), Wrangler updates its rank-ordered list of potential transformations that could have led to this modification. Wrangler borrows concepts such as interactive transformation languages from Vijayshankar Raman and Joe Hellerstein’s Potter’s Wheel. Its interface has a taste of David Huynh and Stefano Mazzocchi’s Refine as well as Huynh’s Potluck. Wrangler’s novelty comes in combining the interfaces and transformation languages with an inference and ranking engine. Since Wrangler is hosted, it is also capable of learning which transformations users prefer and improving its rankings over time!

The last slot goes to our own Eirik Bakke, who presented Related Worksheets along with David Karger and Rob Miller. Related worksheets make foreign key references a first-class citizen in the world of spreadsheets. Just as spreadsheets secretly made every office worker capable of maintaining a single-user, single-table relational database, Eirik has secretly enabled those workers to make references between spreadsheets without having to program. While adding foreign key references to a spreadsheet requires a simple user interface modification, its implications on how to display multi-valued cells in the spreadsheet are significant. Read the paper to see Eirik’s hierarchical solution to this problem!

Keep it up, data nerds! Soon we’ll be able to start a data community at CHI!

Evening Project: What Would Hacker News Say?

What Would Hacker News Say (WWHNS) is a bookmarklet that allows you to see if there is a Hacker News (HN) discussion about a page you are currently viewing.

I often find a link through a feed reader or Twitter and want to know if there is an HN thread discussing the link. This happens more often now that I have moved over to following @newsyc20 on Twitter rather than visiting the HN website directly. I batch up a bunch of stories to read at once, and lose context of which HN thread pointed to that page.

The WWHNS bookmarklet, when clicked, looks the current page up in Ronnie Roller’s wonderful HN API, and adds a link to the top right of the current page to any existing HN comment threads.

I tested it in Chrome and Firefox. Let me know if it works in other browsers.

Caveat: This bookmarklet will work for links you followed by way of HN or another source which replicates it. It may not work if you arrived at a page from a source outside of HN, since that link might be slightly different from the one posted to HN.

To use WWHNS

Easy

Drag this WWHNS bookmarklet to your bookmark toolbar.
For any page, click on the WWHNS button in your bookmark toolbar.

Hard

Check out the WWHNS git repository
Type make
Open wwhns.html in a browser
Copy the WWHNS link to your bookmark toolbar
For any page, click on the WWHNS button in your bookmark toolbar

To edit the bookmarklet

Fork this git repository
Edit wwhns.js
Type make
Open wwhns.html in a browser
Copy the WWHNS link to your bookmark toolbar
For any page, click on the WWHNS button in your bookmark toolbar
Push the changes back to me. I’d love to see what you do with it!

License

BSD

Shoutouts

Ben Alman—For the jQuery bookmarklet HOWTO
Ronnie Roller—For an awesome HN API
YUI Compressor—Makes JavaScript small
Hacker News—For having comment threads worth reading

Comments as content: The medium hinders the message

When articles were published in hard-copy newspapers, reader response was left to the ultimate in asynchronous communication: letters to the editor for differences of opinion, and corrections when a mistake was discovered. As brick-and-mortar newspapers moved into the digital realm, the static publishing model initially stuck, albeit with an easier method for correcting mistakes.

When we digest a story published by a large newspaper, be it in digital or dead tree form, we assign the strongest signal to the content of the article. In exchange for giving the journalist our full attention, we expect that the news organization has put significant effort to researching, writing, and editing the story. Newspapers rarely put uncurated content front-and-center because they trust their own vetted content more, and in part to justify the expense that went into their refined content.

Along the path from single-source hard copies of stories to the everyone-gets-a-voice world of microblogging, we got comments. Blogs frequently display discussion threads following each entry, and sites such as Digg, Reddit, and Hacker News provide us with another forum to chat with the community about articles we find interesting.

Many blogging outfits, including those run by organizations as large as the New York Times, now employ comment systems beyond their purpose as a meta-article discussion medium. One often finds blog entries that end with prompts such as “What has your experience been? Let us know in the comments!” Or “If you know more about this late-breaking story, leave a comment below!” In the same way that live-blogging has taken blog entries from static entities to up-to-the-minute documents, comments sometimes become a necessary part of the stories which they adjoin. Slashdot sometimes takes this one step further: when a topic of wide interest appears, the editors open an essentially content-free story with the express purpose of leaving a place for comments.

If comments can sometimes be the content of a story, then why are they always relegated to the bottom of the story? What is the user interface for displaying articles where readers are assigned a reporter’s role? How do we assign prominence to the most informative fragments of story and user-generated content? Flickr and Facebook have figured this out to some extent—you can annotate photos and witness the result in situ. Youtube lets users embed annotations in videos. How do we apply this concept to text media? What tools already do this, and what ideas do you have for improvement? Leave your comment below!

Twitter Papers at the WWW 2010 Conference

This past week at WWW 2010 has resulted in quite the spread of Twitter papers. Topic included systems, novel uses, and studies of tweets and users. I’ve made an attempt to provide a taste of each paper/presentation I experienced. Feel free to comment if I missed anything!

At the web science conference on Monday, we saw two presentations on Twitter. Devin Gaffney presented a paper entitled #iranElection: quantifying online activism. Devin collected around 766,000 worth of tweets across nearly 74,000 users around the time of the #iranElection. He first showed that there was a spike in signups around the time that #iranElection became a trending topic with the seeming purpose of adding #iranElection updates to the tweet stream. A retweet analysis showed that as more users became interested in the #iranElection, users with influence (as measured by follower count or retweet count) lost influence relative to the entirety of relevant users.

Panagiotis Metaxas presented the other paper at the Web Science workshop, entitled From Obscurity to Prominence in Minutes: Political Speech and Real-Time Search. In this work, the authors studied the recent Massachusetts special election between Scott Brown and Martha Coakley through the lens of Twitter. Metaxas presented the notion of twitterbombing, where, similar to googlebombing, sneaky twitter users abuse various mechanisms to appear in the relatively prominent real-time search results that search engines have recently added. 32% of tweets were repeated several times by the same account, presumably in an attempt to increase the ranking of their tweets’ content by naive real-time ranking algorithms. The authors described how they identified Republicans and Democrats through follower and retweet analysis, and showed an example where twitterbombing was used to lead searchers to a page designed to dissuade voters from voting for Coakley.

Next, at the Linked Data Workshop, Joshua Shinavier presented Real-time #SemanticWeb in <=140 characters. Joshua’s goal is to extract structured data from tweets using his TwitLogic system. Instead of extracting data from all tweets, Joshua’s system looks for tweets that follow a format called nanotations and are identified by hashtags. It is unclear what sort of adoption this format will see, but the value in such annotations (as well as those in the up-and-coming twitter annotation system) is that with precise structure, the extracted data can be a far more rich data source for the linked data web.

Moving into the main WWW2010 presentation tracks, Yi Chang and his colleagues at Yahoo! presented Time is of the essence: Improving Recency Ranking using Twitter Data, which studied how to turn relevant and popular tweets into search results. Crawling for real-time content is typically resource-intensive on search engines which have to frequently revisit many sources of such content, and belabors the servers of the content providers if recrawled too frequently. The authors of this paper studied how to use streaming Twitter results to discover URLs and avoid having to actively recrawl for new content. In a 5-hour sampling of tweets, Chang and team found 1M URLs, and after cleaning these results to avoid spam, adult content, or self-promoting tweets, approximately 5.9% of the URLs remained. From here, the authors describe how various features including tweet content, retweets, and social network topology can be used to rank the discovered URLs. Finally, the authors found that they can use the tweet text describing a URL in much the same way that search engines traditionally use the contents of anchor text linking to a webpage to index discovered URLs.

Next, Haewoon Kwak presented What is Twitter: Social Network or News Media? One impressive contribution of this work is the large dataset that the authors collected, featuring 41.7M user profiles, 1.47B following relations, 4262 trending topics, and 106M tweets mentioning these trending topics. The authors presented some interesting network structure statistics. Twitter has an asymmetric following model, and only 22% of user pairings are symmetric, compared to a symmetric follower rate of around 70-85% on other asymmetric social networks. This should not suggest that Twitter is more a news medium than a social network. For example, Twitter may be a different medium to different users, and the high rate of updates might discourage users from following everyone that follows them. Other interesting factoids presented by the authors included that 96% of retweet trees are of height 1, 35% of retweets occur within 10 minutes of the original tweet, and 55% occur within 1 hour.

Finally, Takeshi Sakaki presented Earthquake Shakes Twitter Users:
Real-time Event Detection by Social Sensors, which described how to build an earthquake detection and location system with the tweetstream as its input. The authors passed all tweets with the term ‘earthquake’ or ’shaking’ to a classifier, and showed which features of tweets helped classify positive and negative instances of tweets relating to an earthquake. They then built a temporal model to identify when the earthquake-positive tweets strayed from the norm. Finally, they compared several spatial methods for using geotagged tweets to determine the epicenter of an earthquake. The authors point out one weakness in their location logic: their algorithms have a hard time identifying an accurate location of earthquakes which have an epicenter in the ocean.

A summary of the Twitter analysis papers would not be complete without a hat tip to danah boyd, who gave a wonderful keynote which touched on the intersection of big data analysis and privacy. boyd pushed researchers with access to content outside of the context in which it was created, such as a message sent to a friend or a tweet directed at a tight social network, to be ethical with their handling of that data. Doing her talk justice would take a blog post of its own, so I will just mention one point that danah made toward the beginning of her talk. When confronted with a large dataset, big data hackers sometimes equate aggregate statistics to facts that need not be backed or understood by social models, and sometimes fail to think about the limitations of their population samples. Little things matter: sampling 5% of all tweets biases toward users that tweet more frequently. Similarly, sampling 5% of twitter accounts does not properly account for people with multiple accounts/identities or lurkers with no accounts. Social streams are a wonderful data source for data scientists, but we should ford the streams responsibly.

256 colors in your xterm!

Have you ever used emacs or vim from the command line in GNU/Linux and been offended by the horrible color scheme you saw? I’m embarrassed to admit that I’ve been through tons of vim color schemes and have never been able to understand why the colors did not show up as desired.

Yang’s blog post has changed my life. See here for more notes on which color schemes work well for vim. I’ve been enjoying wombat256.

On Ubuntu on my laptop, I added “export TERM=xterm-256color” to the end of my “~/.bashrc”—You will have to re-open another terminal to see the results after saving your bashrc, or type “source ~/.bashrc” in your current terminal if you’re too antsy.

Notes from NoSQL Live Boston 2010

I was excited to sit in on NoSQL Live Boston today. Thanks to 10gen for hosting and all of the speakers for putting the time in!

The NoSQL community is an interesting one. I was pleased to see Dwight Merriman suggest that the community look past its awkward and misleading name when figuring out how to define itself, and instead find other commonalities: removing the emphasis on joins, focusing on horizontal scalability, and building out non-relational data models. There was no consistent theme to the community, which is the point—if the era of one-size-fits-all solutions is over, you will be hard-pressed to easily define the movement.

There are some special treats in here: numbers from deployments at LinkedIn, StumbleUpon, and Twitter. Take a look at the “Scaling w/ NoSQL” panel for that.

Without further ado, here are my notes. I’ve found that these are often filled with typographical errors, so anything you offer up as a fix would be greatly appreciated.

Dwight Merriman (CEO at 10gen)

What is NoSQL? Look beyond the name, we’re stuck with it
- No joins in-app + light transactional semantics => horizontal scalability
Questions to ask of different offerings
- What is your data model?
- What is your consistency model?
- What are the functional differences in operations, querying, etc.?

Tim Anglade (CTO GemKitty)

General idea: what’s the future of NoSQL, how to get more adoption

European nosql conference—nosqleu.com

We’re currently at the stage where makers took prototypes from academia, turned into hobby projects. Startups adopted as side-projects. Now VC-backed developers do work on nosql dbs full-time.

How to see adoption+support going forward?

more development
marketing
education—currently it’s easy to only learn about relational model, sql. Need that model for nosql ecosystem.
certification—because RDBMSs are more standardized, certifications are easier, so it’s easier to hire junior developers and engage lots of vendors.
branding—“SQL” currently gets more searches than “mysql,” “oracle,” or “sql server.” For “NoSQL” its the opposite—less searches than for the nosql products (mongo, redis, couchdb, etc.)
references—need a nosql book of reference. What is a document-oriented store, or Key/value (K/V) store?
industry group that interfaces w/ industry, academia, and education. Runs conferences.

Panel: Scaling w/ NoSQL

Speakers

Mark Atwood—Gear6 (memcached support)
Alex Feinberg—Voldemort developer at LinkedIn—simple get/put/delete K/V store.
Doug Judd—Hypertable (bigtable implementation in c++, on top of HDFS)
Ryan King—Twitter, which is replacing MySQL w/ Cassandra
Ryan Rawson—HBase developer at Stumbleupon

How does each system scale?

memcached—completely shared-nothing. Facebook has several TBs of memory pooled in memcached.
Voldemort—based on dynamo’s consistency model, so completely symmetric. Largest LinkedIn cluster does 7k req/sec on the client, which results in 14k req/sec on each server in the pool (read quorum = 2).
Cassandra—also symmetric based on dynamo’s consistency model (eventual consistency) but uses bigtable data model. Twitter currently stores all data in mysql, but cassandra is repeating all writes and they are currently testing reads live but not displaying the read results to users. Biggest benefit of scale—memcache helps scale reads, but cassandra, due to eventual consistency, scales writes nicely.
Hypertable is based on HDFS, which is replicated, highly scalable.
HBase is also based on HDFS. ZooKeeper helps master nodes run elections and lets new nodes take over tablets easily.

What’s life like for operations folks?

Voldemort—easy to deploy, no single point of failure, and backups are built in through replication. Workload is expectable—no long-running queries, unlike SQL. Thus, little babysitting.
Cassandra—currently, the engineering team are the operations folks. Numerous failure cases don’t require waking someone up at night. Cluster managed membership/rounting. Upgrade==rolling restart. mysql/memcache is harder to add capacity (data consistency issues)/change configs.
Hypertable is easy to deploy, but hadoop’s HDFS is harder to get right.
Rawson points out that HBase is easy, and handles drastically varying row sizes. Config changes require rsyncing configs to all machines, which doesn’t scale well. King points out that some combination of capistrano and ‘murder,’ a twitter open source project, help deploy config changes.
Feinberg points out that configuration is always more of a dark art once data on disk > data in memory.

Use cases/deployment in the wild

memcache—lots of use cases, but most popular are sessions and prebaked HTML
voldemort—scalable writes, UI settings, e-mail system, rate-limiting, shopping cart (original dynamo paper use case).
cassandra—King points out Twitter’s use is simple. Some stats: 45 nodes, 9-10B rows. Avg tweets/sec: 600-700 (50M daily) with highly skewed spikes. When deployed, reads will need to be 100k/sec against the cluster.
Hypertable—only listed analytics workloads: virus sitings (500M events/day), spam classification, site access statistics. No online/live query access stories.
HBase—at stumbleupon, they have several uses. Numbers: 12K requests/sec in production cluster of 15 nodes. Reqs/sec are uneven—some nodes have 100’s reqs/sec, others have up to 2.4K reqs/sec. Separate cluster to handle analytics: 20 machines handle 7M rows/sec in mapreduce. If they double to 40 machines, they see ~15M rows/sec in mapreduce, so linear scaleup in mapreduce. Bulkloads on this cluster result in ~1M rows/sec insert speeds, and add up to 700GB compressed on disk.

Random discussion

HDFS not designed for lots of random reads (Yahoo! experiment). But HBase does aggressive caching to avoid hitting disk, so in practice the HBase/Hypertable folks don’t think it’s a big issue.
Hypertable vs. HBase: Judd says c++ makes for more efficient memory and cpu footprint. Rawson points out that as an apache software foundation project, HBase benefits from lots of contrib projects, such as HIVE/Pig query languages.
Voldemort is persistent key-value store, whereas memcache is not persistent.
CAP theorem mini-argument (yay!). For the uninitiated: (C)onsistency, (A)vailability, (P)artition tolerance. Brewer’s theorem (proved later by Lynch et al.) is that you can only have two of these in your system. In any real networked system w/ packet loss, Partitions are a given, so tradeoff is between Consistency (will you be able to read the value you just wrote) and Availability (will parts of the system become unavailable/see latency spikes if a node dies). Voldemort/Cassandra==eventual consistency in exchange for high availability. Bigtable copies (HBase/Hypertable) give give up on availability guarantee in exchange for straightforward consistency. King points out that in real system with caching layers and dropped messages, you have to handle read repairs and inconsistency anyway, so embrace it in favor of high availability! Feinberg points out that Voldemort (+ Cassandra) let you demand strong consistency by forcing reads to come from consensus group anyway, so you get what you want.
BigTable folks point out that range scans suck in all other systems. Automatic partitioning (at least in Cassandra) needs some love as well. memcache has no good notion of dynamic scalability—add more nodes and you might get some inconsistency.

Panel: NoSQL in the Cloud

Participants

Benjamin Day—consultant speaking on behalf of MSFT Azure platform
Jonathan Ellis—works for rackspace, is lead of Cassandra development for apache project.
Adam Kocoloski—cloudant, works on CouchDB cloud hosting offering.
Daniel Rinehart—Allurent—startup which is using AWS for a lot, specifically SimpleDB.

Offerings

Azure—offers SQL in the cloud (hosted sqlserver). Also offers blog/queue/KV cloud store.
Rackspace offers cloud sites (like appengine for php)—handles multitenancy in mysql (host multiple users on a mysql install). Also offers cloud files (like Amazon S3) and cloud servers (like amazon AWS but with dedicated physical hard drives per cloud server).
Cloudant—CouchDB cloud hosting. Have developed their own sharding layer on top of CouchDB.
SimpleDB—nice since amazon handles scale for you. recently added consistent reads, conditional puts (had previously relied on eventual consistency).

Why do cloud + nosql relate?

Ellis was contrarian here—cloud is nice, obviously. But for databases, cloud is good if you are storing something really small (and want to provision fraction of a machine), or to handle spiky traffic. But for data, you usually don’t see spikes like you see web traffic—if you have 20TB today, you will only have more than that tomorrow. So provisioning data storage in the cloud is silly. For things you’re sure you will have to store, provision real hardware that’s optimal for your setup, and keep adding hardware as you grow. Use cloud for more stateless, spiky things.

Blah blah blah—argument about whether there should be a standard “nosql storage” API to protect developers storing their stuff in proprietary services in the cloud. Probably unrealistic. To protect yourself, use an open software offering, and self-host or go with hosting solution that uses open offering.

Interesting discussion on disaster recovery. Since you’ve outsourced operations to the cloud, should you just trust the provider w/ diaster recovery. People kept talking about busses driving through datacenters or fires happening. What about the simpler problem: a developer drops your entire DB. Need to protect w/ backups no matter where you host.

Lightning Talks

Alan Hoffman—CEO of Cloudant: Queries + Views in CouchDB

Each JSON doc in CouchDB has a pkey. View engine lets you build indices.
Indices are defined by map/reduce functions that emit the key/value pairs for indexing.
Common pitfalls: don’t use tempviews—those are just for prototypes. Don’t do filtering or reordering in reduce tasks—just aggregate here.

Les Hill—Hashrocket: MongoDoc

Built Object-Document Mapper for MongoDB in Ruby. Like ORM (object relational mapper), but for document stores like MongoDB.
Not activerecord, but similar
Current MongoDB driver for Ruby looks like JSON, whereas MongoDoc (his ODM) looks like more traditional ORMs.

Flinn Mueller—Tokyo Cabinet

Cares about speed more than scale. TC mmaps disk for speed.
TC has several backing stores
- Hash store for simple Key/Value
- B+Tree for range scans/duplicate keys
- Fixed-length DB for fast access
- Table store—stores tuples/documents. Supports queries w/ conditions, orders, limits, union/intersect/diff.
Says he uses TC like memcache++, and as a queue, atomic counter, and tag cloud. Still uses relational DBs to store data—nosql is more of a utility.

Jim Wilson—Vistaprint: Full-Stack Javascript

Impedance mismatch between business logic (usually object-oriented)/data model (usually relational), and business logic (usually php)/client-side (javascript).
Wants to live in a world where Javascript runs on DB (JSON document stores), server (V8, node.js, etc), and client (the way it is now)

James Williams—BT/Ribbit: MongoDB on Groovy

NoSQL is pot-relational, schemaless. Groovy is post-java, allows metaprogramming.
Makes Mongo + Groovy be a good match in philosophy.

Panel: Schema design and document-oriented DBs

(I missed most of this)

Panelists

Paul Davis—would store patient history in a document store, but would still trust RDBMSs for mission-critical medical applications where strong consistency is required. Represented CouchDB.
Eliot Horowitz—10gen (MongoDB)—advocates doing joins in-app, since Mongo doesn’t have foreign key constraints anyway
Bryan Fink—Basho (Riak)—similar lack of foreign key constraints, also no indices.

Indexing

Riak has no indexes. Use SOLR/Lucene to do full-test index of documents (wtf?)
MongoDB—indices similar to mysql indices. Even have geospatial indexing.
CouchDB does indices by way of mapreduce, as described above.

Foreign Keys for relations

Riak supports links (references) but doesn’t enforce them and doesn’t clean up links to deleted items.
MongoDB—DB references exists to refer to other documents. No constant validation, and deleted objects result in broken links (avoids multisite transactions).

How to lock down schemas/do migrations

Riak—keep version number in the document. Modify schema on read. i.e. handle it in the application.
MongoDB—similar process, but indices break when schema changes. Will add rename functionality soon.
CouchDB—like everything in couchdb, use mapreduce.

Horizontal partitioning

Riak—add machines. consistent hashing + read repair on failure. mapreduces run locally, so adding machines adds cpu power for mapreduce tasks.
MongoDB—shard on range. currently has master-slace replication, but soon replica sets.
CouchDB—-no support—build your own partitioning/hashing scheme in front of couchdb installs.

Consistency

Riak—eventual consistency using vector clocks. In some modes, can get back multiple versions which had conflicts to be solved by application. Like in dynamo paper, claims this is actually easy to solve in most cases.
MongoDB—single master for any shard, so 100% consistent.

Panel: Evolution of a Graph Data structure from research to production

Panelists

Boris Iordonov—HypergraphDB (stores hypergraphs)
Peter Neubauer—Neo4J (stores graphs w/ directed edges and typed nodes that have properties).
Sandro Hawke—Represented W3C RDF model. Some think of it as a directed graph w/ URIs for source nodes and edges, and URIs or literal values for destination nodes.

How do you do schemas

HypergraphDB has schema support at low level and package-level
Neo4J doesn’t—leaves it to higher-level packages
RDF—datatypes borrowed from XML, and RDFs or OWL for schemas

Implementation details

HyperGraphDB offers ACID guarantees and may soon offer MVCC.
Neo4J gives ACID guarantees. Constant-time traversals result in 1000-2000 traversals/msec (I think this is dubious on a DFS of a graph—each traversal would be a disk seek—what benchmark gave this?) Update: this was for in-memory or cached graphs.
RDF is a standard, but in general query languages such as SPARQL are less about node traversal and more about graph pattern matching.

Query Model

HypergraphDB—supports BFS/DFS or “more complicated” traversals. Query language for graph pattern finding as well. Supports SPARQL via a Sail, but no XPath since it’s not expressive enough for hypergraphs.
Neo4J—traversals by way of objects that are represented as Java objects. Also supports SPARQL, XPath.
RDF—lots of libraries in each language for raw graph access. Also, if you prefer, use SPARQL for declarative queries.

Who uses it

HypergraphDB—released 2 months ago. Used for search in miami dade county. Knowledgebase for NLP/information extraction project.
Neo4J—opensourced in 2007, lots of interest in social networking, recommendation engines, GIS/spatial indexing, activity streams, intelligence community.
RDF—defense/intelligence, then health/life sciences picked it up, and now govt. data (data.gov.uk is represented by a bunch of sparql endpoints). govt data demands standards!

Sharding—graphs are hard to slice.

Building a Social Data Commons

(cross-posted on the Haystack blog)

Inspired by Ted’s vision of what he’d like to see happen to data.gov, I decided to have a try at my hopes for it. Ted’s desires for data.gov are all ones that I agree would make the data more accessible. I would now like to discuss what else I might want in a world where such steps were taken: a world in which government data was centralized, versioned, searchable, and accessible.

Now what? Given the large and growing pile of data we will optimistically uncover, we will run into new frustrations. People will claim that the published data formats are not the ones that their analysis tool requires. People will be overwhelmed by dataset size, not knowing where to start. People will unknowingly recreate someone else’s data-munging workflows on the way to repeating analyses of the same data. People will become the next bottleneck if data ever ceases to be.

There’s no one answer to the concerns listed above because everyone has a different goal for the data. To handle these issues, we will need more than a place to find up-to-date datasets—-we will also need a place where it is easy for people to share ideas and strategies for tackling data. We will need a social data commons.

Whereas blogs and wikis help report findings, steps, and missteps, a social data commons can be the place to go to “talk shop” about the available data. Even if people post their solutions using decentralized means, there will be benefit to pooling all of these resources in one place on the web. Here are some tools that will help the data-tinkerers get things done:

Data-munging war stories. The first stage in data analysis is often long and frustrating. One must digest the dataset in the form they received it, and transform, clean, and filter out the subset that they wish to analyze, visualize, or otherwise present. The workflow differs for each dataset and application, but to the extent that people can share tools and instructions for processing each dataset, these should be written up in the form of recipes for baking the data.
Crowdsourced analysis. Datasets can be overwhelming. While many exploration tasks are easily automated, it is often easiest to leave certain tasks (e.g., “Find the interesting pictures”) to humans. Mechanical Turk gives us a hint at what this might look like, and the Guardian provides a wonderful example of crowdsourced public data analysis in action.
Current uses showcases. To spark competition, avoid duplicating work, and inspire follow-on projects, visitors should see a showcase of the current uses of each dataset. Aside from links to sites built around a dataset, the list can include embedded visualizations of finished work.
Analysis wishlists. Given that data released by a government reaches more than just programmers, there will be more people with ideas than people who can implement the ideas. People with ideas should be given an outlet, and passers-by should be asked to vote on these ideas to help data geeks with some free cycles discover the most insteresting unimplemented project.
Data wishlists. If an agency were to dedicate resources to releasing another dataset, which one is in highest demand? As Ted mentioned, governments should let demand drive delivery.
Forums. No set of tools will encompass all use cases for social data analysis. A discussion forum can lead to the formation of interest groups while serving as a catch-all for needs not served by the list above.

The US government might hit a few bumps trying to implement some of these social features. For example, a conflict of interest might arise if the showcase of uses of a dataset includes a site critical of the current administration. Having the executive branch ban spam or abusive comments on a forum draws concern over limitations of free speech. These details are not roadblocks, but they do signal that we can’t expect a social overlay to spring out of data.gov per se—-if we want these features, we may have to build and manage them on a third party.

I’m sure there’s more to the social data commons than I listed here. What did I miss, and where can we seek further inspiration?

Thanks to Ted for reading the first version of this entry.

← Earlier Posts Page 1 of 5

marcua's blog

About Me

Navigate

Subscribe by Email