A cake for the new doctor... Raju Balakrishnan's Ph.D. Defense tomorrow (7/19; 10AM, BY528): Trust and Profit Sensitive Ranking for the Deep Web and On-line Advertisements

Dear all:

 Raju completed his defense successfully and is a newly minted "Dr". Please stop by the AI lab to celebrate with cake ;-)

Rao

---------- Forwarded message ----------
From: Subbarao Kambhampati <rao@asu.edu>
Date: Wed, Jul 18, 2012 at 5:36 PM
Subject: Raju Balakrishnan's Ph.D. Defense tomorrow (7/19; 10AM, BY528): Trust and Profit Sensitive Ranking for the Deep Web and On-line Advertisements
To: Rao Kambhampati <rao@asu.edu>

Dear all

 This is a reminder that  Raju Balakrishnan will be defending his PhD dissertation tomorrow (7/19 Thursday). Raju's work on deep web source selection and computational advertisements has garnered him a Yahoo! Key Scientific Challenges award (2009) as well as a WWW best poster award (2010), in addition to several archival publications and a lucrative job. 

You are all cordially invited to his defense.

Sincerely

Rao

Trust and Profit Sensitive Ranking for the Deep Web and On-line Advertisements

By

Raju Balakrishnan

Thursday, July 19, 2012

10:00 am

Brickyard 528

Subbarao Kambhampati, Chair

Yi Chen

AnHai Doan (U. Wisconsin, Madison)

Huan Liu

Abstract

Ranking is of definitive importance to both usability and profitability of web information systems. While ranking of

results is crucial for the accessibility of information to the user, the ranking of online ads increases the profitability

of the search provider. The scope of my thesis includes both search and ad ranking.

I consider the emerging problem of ranking the deep web data considering trustworthiness and relevance. I

address the end-to-end deep web ranking by focusing on: (i) ranking and selection of the deep web databases

(ii) topic sensitive ranking of the sources (iii) ranking the result tuples from the selected databases. Especially,

assessing the trustworthiness and relevances of results for ranking is hard since the currently used link analysis

is inapplicable (since deep web records do not have links). I formulated a method---namely SourceRank---to

assess the trustworthiness and relevance of the sources based on the inter-source agreement. Secondly, I extend

the SourceRank to consider the topic of the agreeing sources in multi-topic environments. Further, I formulate a

ranking sensitive to trustworthiness and relevance for the individual results returned by the selected sources.

For ad ranking, I formulate a generalized ranking function---namely Click Efficiency (CE)---based on a realistic

user click model of ads and documents. The CE ranking considers hitherto ignored parameters of perceived

relevance and user dissatisfaction. CE ranking guaranteeing optimal utilities for the click model. Interestingly, I

show that the existing ad and document ranking functions are reduced forms of the CE ranking under restrictive

assumptions. Subsequently, I extend the CE ranking to include a pricing mechanism, designing a complete

auction mechanism. My analysis proves several desirable properties including revenue dominance over popular

Vickery-Clarke-Groves (VCG) auctions for the same bid vector and existence of a Nash equilibrium in pure

strategies. The equilibrium is socially optimal, and revenue equivalent to the truthful VCG equilibrium. Further, I

relax the independence assumption in CE ranking and analyze the diversity ranking problem. I show that optimal

diversity ranking is NP-Hard in general, and that a constant time approximation algorithm is not likely.

Raju Balakrishnan's Ph.D. Defense tomorrow (7/19; 10AM, BY528): Trust and Profit Sensitive Ranking for the Deep Web and On-line Advertisements

Dear all

 This is a reminder that  Raju Balakrishnan will be defending his PhD dissertation tomorrow (7/19 Thursday). Raju's work on deep web source selection and computational advertisements has garnered him a Yahoo! Key Scientific Challenges award (2009) as well as a WWW best poster award (2010), in addition to several archival publications and a lucrative job. 

You are all cordially invited to his defense.

Sincerely

Rao

Trust and Profit Sensitive Ranking for the Deep Web and On-line Advertisements

By

Raju Balakrishnan

Thursday, July 19, 2012

10:00 am

Brickyard 528

Subbarao Kambhampati, Chair

Yi Chen

AnHai Doan (U. Wisconsin, Madison)

Huan Liu

Abstract

Ranking is of definitive importance to both usability and profitability of web information systems. While ranking of

results is crucial for the accessibility of information to the user, the ranking of online ads increases the profitability

of the search provider. The scope of my thesis includes both search and ad ranking.

I consider the emerging problem of ranking the deep web data considering trustworthiness and relevance. I

address the end-to-end deep web ranking by focusing on: (i) ranking and selection of the deep web databases

(ii) topic sensitive ranking of the sources (iii) ranking the result tuples from the selected databases. Especially,

assessing the trustworthiness and relevances of results for ranking is hard since the currently used link analysis

is inapplicable (since deep web records do not have links). I formulated a method---namely SourceRank---to

assess the trustworthiness and relevance of the sources based on the inter-source agreement. Secondly, I extend

the SourceRank to consider the topic of the agreeing sources in multi-topic environments. Further, I formulate a

ranking sensitive to trustworthiness and relevance for the individual results returned by the selected sources.

For ad ranking, I formulate a generalized ranking function---namely Click Efficiency (CE)---based on a realistic

user click model of ads and documents. The CE ranking considers hitherto ignored parameters of perceived

relevance and user dissatisfaction. CE ranking guaranteeing optimal utilities for the click model. Interestingly, I

show that the existing ad and document ranking functions are reduced forms of the CE ranking under restrictive

assumptions. Subsequently, I extend the CE ranking to include a pricing mechanism, designing a complete

auction mechanism. My analysis proves several desirable properties including revenue dominance over popular

Vickery-Clarke-Groves (VCG) auctions for the same bid vector and existence of a Nash equilibrium in pure

strategies. The equilibrium is socially optimal, and revenue equivalent to the truthful VCG equilibrium. Further, I

relax the independence assumption in CE ranking and analyze the diversity ranking problem. I show that optimal

diversity ranking is NP-Hard in general, and that a constant time approximation algorithm is not likely.

5x7 Folded Card

Dazzling Lime Print 5x7 folded card

Create cute birthday cards, valentines and more at Shutterfly.com.

View the entire collection of cards.

Thanks for all the ballot stuffing ;-)

To 

  The students who took classes with me in 2011-12:

Dear all:

 I have been told by the department that I was voted by the students as the best teacher in CSE for 2011-12 year. 

Assuming that my constituency would have been the students who took classes with me this year, which includes you, I would like to thank you for all the  energetic ballot stuffing ;-)

I am supposed to get the (no doubt very substantial cash)  award on Monday during the CIDSE awards shindig.

Cheers

Rao

 

Re: CSE 598 : IR -- Dating app based on Amazon, Netflix, Spotify, And Facebook Data

Thanks for letting me know!

 Since the lecture with that idea is recorded and is on youtube,

I wonder if I can get these Yokels to fork over some pre-IPO options for me.. 

Rao 

On Wed, Mar 28, 2012 at 7:06 PM, Abhishek Kumar <akumar66@asu.edu> wrote:

Dear Prof,

I took the IR course offered by you last semester.

In one of the lectures related to collaborative filtering, you were talking about an idea that

Amazon can use collaborative filtering to suggest soul mates.

There is a new app, Yoke, which is based on that idea.

http://techcrunch.com/2012/03/28/yoke/ 

Thanks
Abhishek Kumar
Graduate Student
Arizona State University
Mobile: 480-381-0004
 

Streaming videos of cse494 (albeit a bit late for you ..)

Thought this may be of interest to some of you. 

I was able to upload most of the cse494 videos to youtube. They are now linked to the class page http://rakaposhi.eas.asu.edu/cse494 and are streamable and random-accessible. 

Rao

teaching evaluations...

Dear all:

 Hope you had a good (if all too short) break; I certainly did roaming the backwaters of Kerala.

I just got your teaching evaluations for the course and it looks like the course was received  well. 

Thanks to the ~75% of you who took time to provide feedback and comments; 

I will try my best to take them into account (except perhaps for the "the course is hard" variety ;-). 

[And as for the other ~25%, they should be riddled with guilt for not taking part ;-)]

 It is my somewhat quixotic custom to make the complete evaluations--warts and all--available to 

the class students for a limited time.  So, here goes:

http://rakaposhi.eas.asu.edu/cse494/f11-598-evals.htm

http://rakaposhi.eas.asu.edu/cse494/f11-ug-evals.htm

If you have any further comments/questions you need to get off your chest, feel free to email me. Otherwise, this will likely be the last mail on this list.

Wishing you all a great new year..

Rao