Thursday, July 24, 2008

WHY UNCERTAINTY IN DATA IS GREAT

Background: Uncertain Data

With the advent and growing popularity of several new applications (such as information extraction on the web, information integration, scientific databases, sensor data management, entity resolution), there is an increasing need to manage uncertain data in a principled fashion. Examples of uncertain data are:
  1. Extraction: You extract structure from an HTML table/text on the Web, but due to the inherent uncertainty in the extraction process, you only have some confidence on the result. You extract the fact that John works for Google, but are not entirely sure, so associated a probability 0.8 with this fact.
  2. Human Readings: Let’s suppose people are viewing birds in California (Christmas Bird Count: http://www.audubon.org/Bird/cbc/). George reports that he saw a bird fly past, but wasn’t sure whether it was a Crow or a Raven. He may also attach confidences with each of them: He is 75% sure it was a Crow, and associates only a 25% chance of it being a Raven.
  3. Sensors: Sensor S1 reported the temperature of a room to be 75±5.
  4. Inherent Data Uncertainty: From weather.com, you extract the fact that there will be rain in Stanford on Monday, but you only have a 75% confidence in this.
  5. Data Integration/Entity Resolution: You are mapping schemas of various tables, and are unsure of whether "mailing-address" in one table corresponds to "home-address" or "office-address" in another table. We are de-duplicating a database of names, and are not sure whether "John Doe" and "J. Doe" refer to the same person.
There are many other examples of uncertainty arising in real-world scenarios.

How Do We Deal With Uncertainty

With large volumes of uncertain data being produced that needs to be subsequently queried and analyzed, there is a dire need to deal with this uncertainty in some way. At a high-level, there are two approaches to dealing with data uncertainty:
  1. CLEAN (Approach-C): "Clean" the data as quickly as possible to get rid of the uncertainty. Once the data has been cleaned, it can be stored in and queried by any traditional DBMS, and life is good thereafter.
  2. MANAGE (Approach-M): In contrast, we could keep the uncertainty in data around, and "manage" it in a principled fashion. This involves building DBMSs that can store such uncertain data, and process them correctly, i.e., handle the probabilities, range of values, dependencies, etc.
Let us compare the two approaches. Both Approach-C and Approach-M entail several technical challenges. Cleaning uncertain data is not a trivial process by any stretch of imagination. There has been work in the database community in cleaning uncertain data in various environments. (For one piece of work on cleaning in sensor/RFID networks, check this IQIS 2006 paper.) Once the data has been cleaned, there is no additional effort involved, as it can be processed by any off-the-shelf DBMS. In contrast, with Approach-M less upfront effort is involved. However, processing uncertain data becomes significantly more challenging. I would like to highlight the Trio project (http://infolab.stanford.edu/trio/) at Stanford that is building a system to manage uncertain data along with data lineage (also known as history or provenance). The lineage feature in Trio allows for an intuitive representation (see our VLDB 2006 paper), and efficient query processing (see our ICDE 2008 paper or a short DBClip). I would also like to note that several other database groups are also studying the problem of managing uncertain data.

Why Managing Is Better Than Cleaning

Without going into technical details, I would like to describe why Approach-M is in general better than Approach-C. While Approach-C gives instant gratification by removing all "dirty data," Approach-M gives better long term results. Intuitively, Approach-C greedily eliminates all uncertainty, but Approach-M could resolve uncertainty more accurately later on because it has more information. Another way to look at it is that in Approach-C, the error involved in cleaning the data keeps compounding as we further query the certain data. But in Approach-M, since the uncertainty is explicitly modeled, we don’t have this problem.

Let us take a very simple example to see how uncertainty can be resolved using Approach-M. Consider the Christmas Bird Count described earlier, where people report bird sightings with a relational schema (Observer, Bird-ID, Bird-Name). (Suppose for the sake of this example birds are tagged with an identifying number, and the main challenge is in associating the number with the bird species.) In this extremely simple example, suppose there is just one sighting in our database by Mary, who saw Bird-1, and identified it as being either a Finch (80%) or a Toucan (20%). At this point we know that Bird-1 is definitely a Finch or a Toucan, but we are not sure which one it is; using Approach-C, we would like to create a certain database, and since Mary feels much more confident that Bird-1 is a Finch, we would enter the tuple (Mary, Bird-1, Finch) into the database and forget the information that it could have possible been a Toucan as well.

In Approach-M, we would store Mary’s sighting as is, which could be represented as:
(Mary, Bird-1, {Finch: 0.8, Toucan: 0.2})
Why is this better? Suppose next day we get another independent observer, Susan, reports the sighting of Bird-1, and she thinks it’s either a Nightingale (70%) or Toucan (30%). The following day we get another independent observer’s sighting who says Bird-1 is either a Hummingbird (65%) or Toucan (35%). Clearly when we reconcile all these sightings, the likelihood of Bird-1 being Toucan is quite high. The method of "reconciling" these readings can be quite complicated, and is an important topic of research, but any reasonable reconciliation should indicate the probability of Bird-1 being Toucan quite high since all other sightings are conflicting. However, using Approach-C, all the three observers’ readings of Toucan would have been weeded out.

Uncertainty In Data Integration

For readers who are not convinced by the synthetic example above, here’s a very real application: data integration, which has been an important area of research for several years.

Data integration systems offer a uniform interface to a set of data sources. As argued in our chapter to appear in a book on uncertain data, data integration systems need to model uncertainty at their core. In addition to the possibility of data being uncertain, semantics mappings and the mediated schema may be approximate. For example, in an application like Google Base that enables anyone to upload structured data, or when mapping millions of sources on the deep web, we cannot imagine specifying exact mappings. The chapter provides the theoretical foundations for modeling uncertainty in a data integration system.

At Google, we built a data integration system that incorporates this probabilistic framework, and completely automatically sets up probabilistic mediated schemas and probabilistic mappings, after which queries can be answered. We applied our system to integrate tables gathered from all over the web in multiple domains, including 50-800 data sources. Details of this work can be found in our SIGMOD 2008 paper. We observed that the system is able to produce high-quality answers with no human intervention. The answers obtained using the probabilistic framework was significantly better than any deterministic technique compared against.

Wednesday, January 9, 2008

A Thousand Miles

A thousand miles, so far away,
My heart and soul, there they lie.
Every moment, each passing day,
Like the birds, I long to fly.

How shall I explain to thee,
Without you, what becomes of me
Dried, shrivelled, impotent, full of sorrow
After all, what's a bow without an arrow?

I've heard people say, the world is your oyster,
I give myself to thee, seeking thy shelter,
Well I hope in my oyster, you are the pearl.
My heart smiles a rainbow, so long as you are my girl.

I gaze at that lonely star,
shining bright in the twilight sky,
I know I'll be there, not too far,
but still, why do I always cry?

Let's sail through the vast oceans,
beyond anything anyone ever knew,
Come with me, my dear,
you are the ship, and I am the crew.

Never again shall I leave your view,
Not for the world, mark my promise.
Tell me, thou shalt keep me with you,
Please, please, my pretty little miss?

No, I'm not a writer, not nearly a poet,
Nor am I magician, hidden behind a closet.
I am the best donning cupid's bonnet.
And so I dream, that you shall see...
I'm a fanatic lover, and come embrace me?

A thousand miles, so far away,
My heart and soul, there they lie.
Every moment, each passing day,
Like the birds, I long to fly.

Thursday, October 11, 2007

Weekly Tops

Songs:

- "One Way Ticket" - Eruption
- "From of a Distance"
- "One Last Breath" - Creed
- "Chanda Ke Kiranon Mein": Kishore kumar
- "Unwritten" - Natasha Bedingfield
- "You and Me" - Lifehouse
- "Escape" - Enrique
- "When You Say Nothing At All" - Ronan Keating
- "You took my heart away" - MLTR
- "Kuch to log kahenge" - Kishore Kumar
- "koyi hota jisko apna" - Kishore kumar
- "But it rained" - parikrama
- "Mamma I'm coming home"

Movies:

- Chak de India
- Bourne Ultimatum

Welcome Back!

Welcome back rhapsodic readers; your best-loved blogger is back! Let not my hiatus from blogging, my friends, insinuate my hiatus from fun, work, life, and love. A lot has transpired in the interim and I dare only pen a 20,000 feet executive summary, not doing justice to any of the bullets, lest I fear getting lost in the labyrinth of the glorious summer I've left behind. Not to mention losing my readers bored by the details :-). Hmm... where shall I start. Indeed it has been an amazing summer; the best since I left home, long long ago.

- Undoubtedly, the place to start is update you of my burgeoning love life. Mallika Kumar is her name. I reserve the word "SHE" in the rest of my blog for her, forever. It all started that thunderous full moon night on the 1st of July. And since then, I've never looked back...

- And yes, I was interning at Google. I loved it! Yeah, that does include work, not just food and pool.

- Worth noting is our escapade to Steffi's baby shower. As we walked toward Steffi's apartment, Mallika told me: "And BTW, I didn't tell you the baby shower is technically only for girls" :P. While she was trying to pull a fast one, as we entered, to both our surprise Steffi said: "Uhmmm, Anish, I must warn you, you might be the only guy here". And sure enough, that evening I was with 10 gorgeous women in one room with no reason to complain.

- What else, I bought tickets for my India trip this winter! I'll be off for more than a month in Bangalore. Can't wait to get back home after a long year!

- I've moved on-campus :). EV 86. Stop by for unprecedented hospitality: dirty apartment and no food or soda to offer. J/K.

- Four of us (Atish, Himani, Mallika, and I) made a trip to Orlando, Florida. We saw alligators, parasailed in Daytona, went on the fieriest rides in disney, and much more...

Oh, I almost forgot, I owe you an explantion. Not for the hiatus, but for the return to the dark. SHE said "You write really well! Why have you stopped blogging?" :)

Alright, stay tuned to this column for further posts. In the meanwhile, stay beautiful.

Monday, July 23, 2007

Weekly Tops

Songs:
-------
1) "Because of you - Kelly Clarkson" (looking for mp3)
2) "How Do I Live" - Trisha Yearwood
3) "These Dreams - Heart" (looking for mp3)
4) 'Kandisa" - Indian Ocean
5) "Lay a whisper" - roxette?
6) "Leaving on a jetplan" - John Denver

Movies:
--------
1) Silence of the lambs
2) ...censored...

Poker Party Minutes

Friday, 20th July was a night to remember... a night of fun, frolic, fights, derision, and debauchery.

What: Poker, Games, and more...
Who: Kavya, Ranjit, Aditya Jami, Dilys, Sidjon, VK, Mallika, Atish, Anish

Standings:
1) Winner: Atish
2) Runner up: Anish
3) Third spot: Ranjit

Credits:
- The thinker:
VK (Thought for 5 minutes and folded :)
- First time drinker: Sidjon (drank a glass of vodka+cranberry)
- Teetotallers: Dilys, VK, Mallika
- Most Illustrious player: Ranjit (back after playing the WSO Poker tourney at Vegas.)
- Surprise performer: Aditya Jami (First time player performed really well. Neophyte's serendipty.)
- Drunken Driving: Kavya :P (flunked her driving test next day :( Good luck next time round!)
- The strategist: Mallika (ask her why!)
- From rags to riches: Atish (was penniless in between, then ended up winning eventually)

Free Furniture (first-come-first-served)

Hello,

If you or anyone you know needs furniture, we are giving away furniture for free. The price you have to pay is transport it from our place (749 Stanford Avenue, Palo Alto, CA 94306) by 28th July, or latest 29th July. Call or email ASAP if you are interested in looking at or taking any furniture.

We have the following (in addition to several other smaller things. Drop by or let me know if you are interested in the complete list and I can send it over):

- couch
- 2 convertible beds (foldable to make it a chair)
- coffee table
- wooden dining table with 4 chairs
- side table
- 2 large computer tables
- 2 large chests/drawers for clothes
- small bed table
- modem

All the stuff above is available for free (only because I need to clear my apartment by 29th July :( ). You can also buy the stuff below if you wish:

- Comfortable leather chair ($20)
- Queen size bed + mattres ($40)
- Microwave ($20)