Being David in the DataManagement World of Goliaths

Sourav S Bhowmick
Nanyang Technological University
SingaporeiDB 2011, Kyoto, Japan

Disclaimer

The opinions expressed in this talk are solelyof the author and does not necessarily reflect
the opinions or beliefs of the community.

David & Goliath – The Story
Hebrew Bible•Saul and Israelites vs Philistines•Goliath of Gath• A giant Philistine warrior whochallenges the Israelites to send out
a champion of their own to decide
the outcome in single combat• David, younger brother of Saul,
accepts the challenge• David went to the battle only with asling and five stones!
• Goliath in armors and shield.
• David hits Goliath’s forehead->Goliathcollapses -> David cut off his head withGoliath’s sword

Davids & Goliaths in DB WorldDavidsGoliaths•Not a descendant of “star”
faculty•Not affiliated to DB-strong
institutes•Not well-connected tofrequent top-tier community• Only has a sling (laptop)
and stones (ideas)•Frequently publishes in
top-tier conferences• Descendant of “Goliaths”• Affiliated to DB-strong
institutes• Strong social network

Being David – Sharing MyExperience•NTU wasn’t DB strong•DB in Singapore =NUS DB•My advisor was not adescendant of “star”• Disconnected fromvisible network

StartedPh.D@NTU

1997

ICDCS
Received
Ph.D.

2001

VLDB

ICDE,TKDE

KDD
WWW
ICDE

2002

2003

2006

Sanjay Madria (MUST)
Mukesh Mohania (IBM)SIGMOD
WWW

ICDE
VLDB

ICDE
ICDE
VLDB
SIGMOD SIGMOD
MMMM

2007

2009

2010

Curtis Dyreson (Utah)
Aixin Sun (NTU)
C F Dewey (MIT)2011

Problem Statement
Top-Tier Acceptance Maximization Problem
Let there be N
slots inin aa conference
conference CC.where
Let R betheNsetof Rk slotsk <<. Letreviewers
Let p beintheof theDavid
D. Thetop-tier
be the set inofC.reviewers
C.paper
Let p bepaperof David
acceptancemaximization
is to findan algorithm
D. The top-tieracceptanceproblem
maximization
problemis to findthatmaximizesfC(pan algorithm
thatmaximizesN) = Pr(pNf|R).
C(pk) = Pr(pk|R).

Assumptions•There are G Goliaths in the community• M slots are taken by G’ GVisual Representation

Characteristics
Theorem 1
The top-tier acceptance maximization problem is NP-Hard.

Solution•Heuristic-based algorithm

Challenges
Hard Issues•Real-world reviewers• No Goliath as co-author•Affiliation of the paper is notDB-strong

Ideal vs Real Reviewers
Real-world Reviewers

Ideal Reviewers•May not be aware of allworks in the field• May not read every
sentence carefully• May be biased to authors
weight and social network• May have a biased viewof a solution• Expert in the field•Reads every line of thepaper carefully• Is not influenced by namesof authors/affiliations• Have solid vision and openmind• Can see through theproposed solution• Not biased to any socialnetwork

Curse of Delta
The work seems to be delta research…

What is delta?
•Different reviewers havedifferent measure of delta• Most papers are based onprior work
• Twig join algorithm lead tomany enhancements

Solution•Not easy as you do not know who will review• Safe solution: propose a new line of research

Lack of Significant Impact
The impact of the work is low…..

How do you know?
•Crystal ball comment• DB community has been wrong inprediction many times• Relational model, B trees, Lorel,Page Rank, ARM….
• Best Paper  10 Years Best Paper

Solution•Intractable problem!

Not “Skyline” Performance
Performance gain is not significant enough…

Delta performance• Can-do-better papers•Improvement by a factor of3 or less
• Weakens the proposedtechnique

Solution•Propose technique that can bring in at least anorder of magnitude performance improvement

Not Enough Experiments!
Not enough experiments…

Performance study• How much is “enough”?
• Controlled by page limit

Solution•Report exhaustive experimental study(~3 pages)• Even report results that are obvious• Highlight the strong results

Too Simple Solution!
Solution is simple…

Simplicity• Simplicity is not a crime• Techniques that can standtest-of-time generally have
simple solution• Interpretation -> No complex
formula/maths, theorems arevisible Solution•Don’t solve this problem• Hope for a better reviewer next time Not Enough Theorems!
The paper don’t have enough theorems …

Theorem problem• Good research  No. oftheorems• Generating large number of
insignificant theorems
obfuscate the main idea

Solution•Don’t solve this problem• Hope for a better reviewernext time Ok..But What About Y?
The paper doesn’t discuss how it can handle …

Interpretation• Often Y = future work
• Comments made without
considering page limit• Often indicates that thereviewer cannot find any otherissue to criticizeSolution•Intractable problem!

Summary
Key Issues•Curse of delta• Lack of significant impact• Not “skyline” performance• Not enough experiments• Too simple solution• Not enough theorems• The Missing YDavid’s PaperRank 1 strategy

Rank 2 strategy Rank 3 strategy

New line ofresearch!

Prove a famouswork wrong!

ProsProsPros•No competition!
•Curse of delta•Lack of novelty•Too simple soln
•Not “skyline” perf.

•Curse of delta•Lack of impact•Too simple soln
• Performance

Cons•Its hard!
•Difficult to get
acceptedCan-do-better paper•Relatively easy
• Pro-performance(at least 1-2 ordersof mag)

ConsCons•Its hard too!
• Can becontroversial•Curse of delta• Novelty• Perf-not-enoughSecret of Great Papers
Secrets to tackle Real-world Reviewers•Story telling (Sell your story in 3 pages)• Understandable without reading the entire paper• Make it readable even if certain sections are skipped•Realistic assumptions & Real problems• Elegant solution• Solid experiments (even obvious ones!)• Know your area well! (Don’t be oblivious to relatedresearch)Heartware of Top-tier Research
Heartware necessary for success•Be driven• Never say die• Be creative (Don’t always believe what you read)• Think deep vs Think fast
• Work hard
• Be a one-man army (David don’t have choice)Post-Relational Reality
Impact of DB researchThen• How to measure?
• Publications in top venues• Citations• Who uses it? How itenhances human lives?

•Data is generated incompanies• Resides in companies• Used by companies• DB-literate users

Now•Data is generated byeveryone• Resides everywhere• Used by everyone• Non-DB literate users

What Areas to Focus?
Parallel & Distributed DB

Cloud data management

semistructured
data management

Data streams

DB+ IRgraphdata management
mobile data management

OO DB
Probabilistic DB

Biggest Impact?
Data aregenerated andconsumed bynon-DB experts
users!

DB Community’s Love Affair

Hard Reality

Hard Reality!
We know the problem
Thirty years of research on query languages can be summarized
by: we have moved from SQL to XQuery. At best we have moved
from one declarative language to a second declarative languagewith roughly the same level of expressiveness. It has been well
documented that end users will not learn SQL; rather SQL isnotation for professional programmers.
The Lowell Database Research Self-Assessment,
Communication of the ACM (May 2005)

Usability
If the user can’t use it, it doesn’t work.
Susan Dray, Distinguished Engineer of ACM

My Favorite Problems
Unifying Theme
Data management for the people, by the people

Future Healthcare

Social media• Data-driven drug targets
discovery• Functional visualization ofmolecular networks• ACM BCB 11• Analyzing social networks• Improving social image search• CIKM[09,10,11], MM[10,11],
VLDB [10]Usable DBs•DB as iPad
•Making XML & graph DBs usable• ICDE [06,09,10], VLDB[10],SIGMOD [10,11]

Towards Usable DBs
Querying without XQuery• User-friendly DB-ignorant GUI (towards iPAD for DB)•Structure and query language independence• ICDE 2010, VLDB 2010
• XMORPH

DB meets HCI•Blending visual query formulation and query processing• Rank 1 strategy (we are the first!)• ICDE [06,09], SIGMOD [10,11]• XBLEND, GBLENDER

A picture is worth a thousand words. Aninterface is worth a thousand pictures
Ben Shneiderman, 2003

Classical Visual Querying Paradigm

Query formulation Query processing

DBCtimeCCCC

Visual Graph Query Formulation
Meets Query Processing
A novel paradigm•Why wait for the complete visual query to be constructed before
initiating query evaluation? How can we blend these two steps?
•By initiating query processing “early”, can we significantly reduce
the system response time?

Query formulation

Query processingtime

Final Thoughts
VLDB/SIGMOD/ICDE• Not be-all-end-all• PageRank, B Trees, Lorel, etc• Solve problem that enhances humanlives• Solve problems that you are passionateabout• Don’t just follow Goliaths• Publish and go beyond by building
prototypes• Always nice to see your ideas
working in real rather than on just apiece of paper • Someday you will be recognized 