Internati
o
nal
Journal of Ele
c
trical
and Computer
Engineering
(IJE
CE)
Vol
.
4
,
No
. 5, Oct
o
ber
2
0
1
4
,
pp
. 81
0~
81
6
I
S
SN
: 208
8-8
7
0
8
8
10
Jo
urn
a
l
h
o
me
pa
ge
: h
ttp
://iaesjo
u
r
na
l.com/
o
n
lin
e/ind
e
x.ph
p
/
IJECE
Issues and Challenges in
Advertising on the Web
Deep
thi G
u
rr
am,
B.
Vijaya
Babu,
Vid
y
ull
a
th
a
Pellakuri
CSE Department, KL Univer
sity
, Vaddeswaram, Guntur,
Andhra Pradesh,
Ind
i
a.
Article Info
A
B
STRAC
T
Article histo
r
y:
Received Aug 1, 2014
Rev
i
sed
Sep 2, 20
14
Accepted
Sep 20, 2014
One of the big s
u
rpris
e
s
of the 2
1
s
t
centur
y
h
a
s
been th
e abi
lit
y o
f
all s
o
rts
of
inter
e
sting Web applications to
s
upport themselves through advertising
,
rather
than subs
cription
.
W
h
il
e
radi
o and
television have managed to use
advertising as th
eir prim
ar
y
r
e
venue source, most media – n
e
wspapers and
magazines, for
example – have had to use a h
y
b
rid appro
ach
, combining
revenue from ad
vertising and su
bscripti
ons. A venue for on-lin
e advertising
has
been s
ear
ch,
and m
u
ch of the effe
ctiv
enes
s
of s
earch adv
e
rt
is
ing cam
e
from the “adwords” model of
matching
s
e
arch
queries
to adv
e
rtis
em
ents
.
This paper presents the algorithm
s
for
optimizing
the way
of matching search
queries to
adver
tisements
is done. Th
e algo
rith
ms discussed ar
e of unusual
t
y
p
e
; th
e
y
ar
e
greed
y and
the
y
a
r
e on-l
i
ne w
h
ich ar
e us
ed t
o
tack
le th
e
adwords problem.
Keyword:
Ad
w
o
r
d
s
Gree
dy algorit
h
m
Match
i
n
Off-lin
e
On-lin
e
Copyright ©
201
4 Institut
e
o
f
Ad
vanced
Engin
eer
ing and S
c
i
e
nce.
All rights re
se
rve
d
.
Co
rresp
ond
i
ng
Autho
r
:
Deept
h
i Gurra
m
,
Depa
rt
em
ent
of C
o
m
put
er
Sci
e
nce &
E
ngi
ne
eri
n
g,
KL Uni
v
er
sity
,
Vad
d
es
waram
,
G
unt
ur
(
D
t
)
,
An
d
h
ra
Pra
d
es
h,
I
ndi
a.
Em
a
il: d
eep
ug2
110
@g
m
a
il.c
o
m
1.
INTRODUCTION
The
W
e
b
of
fer
s
m
a
ny
way
s
for a
n
ad
vert
i
s
e
r
t
o
s
how th
eir ad
s to
po
ten
t
i
a
l cu
sto
m
ers. So
m
e
sites,
suc
h
as
eBay,
Craig’s
List
or auto tr
ad
ing
si
tes allo
w adv
e
rtisers to
po
st t
h
eir a
d
s
directl
y
, either
for free, for
a fee, or a co
m
m
i
ssi
on. A
d
vert
i
s
ers
pay
f
o
r t
h
e di
s
p
l
a
y
at
a fi
xed rat
e
per i
m
pressi
on
(one
di
spl
a
y
o
f
t
h
e ad
with
th
e do
wn
l
o
ad
o
f
th
e p
a
ge b
y
so
m
e
user).
Norm
ally, a
second downl
o
ad
of the pa
ge, even
by the same
u
s
er, will resu
l
t
in
th
e d
i
sp
lay
o
f
a d
i
fferen
t
ad
and
is a seco
nd
im
p
r
ession
. Search
ad
s are p
l
aced
am
o
n
g
t
h
e
resul
t
s
o
f
a se
arch
que
ry
. A
dve
rt
i
s
ers
bi
d
[1
0]
fo
r t
h
e ri
ght
t
o
hav
e
t
h
ei
r ad sh
o
w
n i
n
res
p
onse t
o
cert
a
i
n
q
u
e
ries, bu
t they p
a
y
o
n
l
y if
th
e ad
is clicked
o
n
. Th
e
pa
rticular ads to
be shown are
se
lected by a
c
o
m
p
lex
pr
ocess
,
i
n
vol
vi
n
g
t
h
e s
earc
h
t
e
rm
s t
h
at
t
h
e a
dve
rt
i
s
er
has
bi
d
fo
r, t
h
e am
ount
o
f
t
h
ei
r
bi
d,
t
h
e
o
b
ser
v
e
d
p
r
ob
ab
ility th
at th
e ad
will b
e
click
e
d
o
n
, an
d
th
e to
tal b
u
d
g
e
t th
at th
e ad
v
e
rtiser h
a
s offered
fo
r th
e serv
ice
[5]
.
Whe
n
a
d
vertis
ers ca
n place a
d
s
directly, suc
h
as a
fre
e
ad
on Crai
g’s
List or t
h
e “
buy it now”
feature
at eBay, there are seve
ral problem
s
that the site
m
u
st d
eal
with
. Ad
s are disp
layed
in
resp
on
se to
q
u
ery
ter
m
s,
e.g., “a
partm
e
nt Palo
Alto.”
The
Web
site can use an i
n
v
e
rt
ed
i
n
de
x of wo
rd
s, ju
st
as
a searc
h
engine doe
s
and ret
u
rn those ads that contain all the
words in th
e q
u
e
ry. Altern
ativ
ely, o
n
e
can ask the advertiser to
specify
param
e
ters of t
h
e a
d
, which are
stored in a
da
ta
base [10]. For i
n
stance
, a
n
a
d
for a
used car could
speci
fy
t
h
e m
a
nu
fact
u
r
er
, m
o
del
,
col
o
r, a
n
d
y
ear from
pul
l
-
d
o
w
n
m
e
nus,
so o
n
l
y
cl
earl
y
unde
rst
o
o
d
t
e
rm
s
can be use
d
. Queryers
ca
n us
e
the
sam
e
m
e
n
u
s
of term
s in
th
eir
qu
eries.
1.1
We
b ad Placement
There
are
som
e
vital fact
ors
for we
b a
d
plac
e
m
ent that we
state below:
Po
sition
i
ng
. Th
e po
sitio
n
o
f
th
e ad
on
a p
a
g
e
greatly in
fl
u
e
n
c
es its
click
ab
ility. Th
e click
prob
ab
ilit
y
decrease
s
e
x
ponentially as th
e
position/se
que
nce inc
r
eases
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 4
,
N
o
. 5
,
O
c
tob
e
r
20
14
:
810
–
8
16
8
11
Sim
ilarity to the use
r’s
searc
h
que
ries.
The
ad
attractiveness
correlates
with th
e
q
u
e
ry term
s.
Specialized media (topic
ori
e
nted
m
a
g
azines/ b
l
og
s
with
a h
i
gh
ad
s click
-
t
h
ro
ugh
rate).
Statistics p
r
ov
e
t
h
at
use
r
s
d
o
pr
efer a
we
b
pa
g
e
rel
e
va
nt
a
d
ra
t
h
er t
h
an
u
n
rel
a
t
e
d m
e
ssy
st
uff.
U
s
er r
e
lev
a
n
t
. Th
e w
e
b
m
e
d
i
a use th
e adv
a
n
t
ag
e
o
f
h
a
v
i
ng
so
m
e
in
fo
r
m
atio
n
about th
e
u
s
er. This
enables
them
to c
h
oose t
h
e
‘right’ ad for
‘the
use
r
’. Statistically an
d
cu
mu
lativ
ely o
n
e
may d
e
termin
e a
visitor
’
s inte
re
st fo
r ce
rt
ai
n t
h
i
ngs
, f
o
r e
x
am
pl
e:
o
search
qu
eries (correlates with
p
o
i
n
t
2)
o
soci
al
net
s
a
n
d
rel
a
t
e
d
gr
ou
ps
o
em
ai
l
cont
ent
e
x
cha
n
ge
(
b
ei
n
g
use
d
e
x
t
e
nsi
v
ely by
Google - et
hicalness
is not quite clear)
o
Bo
ok
m
a
r
k
s and
b
ack lin
ks
1.2
Iss
ues for
Display Ads
Th
is fo
rm
o
f
ad
v
e
rtisin
g
on
th
e
W
e
b
m
o
st resem
b
les ad
v
e
rtisin
g
in
trad
itio
n
a
l m
e
d
i
a. An
ad
for
a
Ch
evro
let run
in
th
e
p
a
g
e
s
o
f
th
e New Yo
rk
Ti
m
e
s is a d
i
s
p
lay ad
, an
d
it
s effectiv
en
ess is li
mited
.
It may b
e
seen by
m
a
ny
peo
p
l
e
, b
u
t
m
o
st
of t
h
em
are
not
i
n
t
e
re
sted
in
bu
yin
g
a car, j
u
st bou
gh
t a car
, d
on’
t d
r
i
v
e, or
h
a
v
e
ano
t
h
e
r
go
od
reaso
n
to
i
g
nore th
e ad
[8] .Yet th
e co
st
o
f
prin
ting
th
e
ad
was still bo
rn
e
b
y
th
e
n
e
wsp
a
p
e
r
and
hence by
t
h
e adve
rt
i
s
er.
An im
pressi
o
n
of a si
m
i
l
a
r ad on t
h
e Ya
ho
o
!
hom
e page [9]
i
s
goi
n
g
t
o
be
relativ
ely in
effectiv
e fo
r essen
tially th
e same reaso
n
. Th
e
fee for
placing s
u
ch an
ad is ty
pically a fraction of a
cent
pe
r i
m
pressi
on
.
An
ad
f
o
r g
o
l
f
cl
u
b
s
on
spo
r
t
s
.y
a
h
o
o
.c
om
/
gol
f has
m
u
ch
m
o
re val
u
e per
i
m
pressi
o
n
t
h
a
n
doe
s t
h
e sam
e
ad o
n
t
h
e Ya
h
o
o
!
h
o
m
e
page or an ad
fo
r C
h
ev
r
o
l
e
t
s
on t
h
e Yah
o
o
!
g
o
l
f
page
[9]
.
H
o
w
e
ver
,
th
e web
o
f
fers an
op
portun
ity
to
d
i
sp
lay ad
s i
n
su
ch
a way th
at it is p
o
ssib
l
e to
u
s
e in
formatio
n
abou
t th
e u
s
er
t
o
det
e
rm
i
n
e whi
c
h a
d
t
h
ey
sh
oul
d
be s
h
o
w
n
,
re
ga
rdl
e
ss
of
w
h
at
page
t
h
ey
are l
o
o
k
i
n
g
at
.
Here
rai
s
es t
h
e
issu
es o
f
pr
iv
acy.
Fi
gu
re 1.
Wor
k
fl
o
w
of di
s
p
l
a
y
i
ng
a
d
vert
i
s
em
ent
s
The chal
l
e
n
g
e
of effect
i
v
e web a
dve
rt
i
s
em
ent
pri
m
ari
l
y
i
nvol
ve
s pl
a
c
i
ng rel
e
vant
ads o
n
use
r
requested
we
b page
s. T
hose a
d
s m
u
st be relevant to a pa
ge
receiver t
h
at is relevant
to the
page c
onte
x
t and/
or
d
i
rectly to
th
e
u
s
er [10
]
.
2.
RELATED WORK
Wh
at al
go
rithm
s
are to
b
e
ap
p
lied in p
l
acin
g
ad
s in
m
o
d
e
rn
web busin
ess
?
Th
e
alg
o
rith
m
s
fo
r
getting a
d
s
,
that
are rele
vant
to searc
h
queri
e
s, m
u
st
be
of
th
e on
-line n
a
t
u
re. Strictly, on
-lin
e al
go
rithm
s
are
th
o
s
e wh
ere data in
pu
t is
fed
in
t
o
the algorith
m
,
with
ou
t h
a
v
i
ng
the entire in
pu
t av
ailab
l
e fro
m
th
e
start. It
very m
u
ch looks like signal
proces
sing (DSP),
whe
r
e the
in
pu
t stream
is
n
o
t
ev
i
d
en
t from th
e start. In
pu
t d
a
ta
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Issue
s
an
d C
h
a
l
l
e
nges i
n
A
d
ve
rt
i
s
i
ng
on
t
h
e
Web
(
D
ee
pt
hi
Gur
r
a
m
)
81
2
st
ream
m
i
ght
al
so be s
o
fast
,
t
h
at
t
h
e pr
oce
ssi
ng l
a
t
e
ncy
i
s
of m
u
ch hi
g
h
er i
m
port
a
nc
e com
p
ared t
o
st
at
i
c
p
r
esen
ted d
a
ta
in
pu
t.
‘On
-
lin
e’
h
e
re refers to
t
h
e
n
a
ture
o
f
th
e
alg
o
rith
m
,
an
d shou
ld
no
t be con
f
u
s
ed
wi
th
‘on
-
lin
e’
meaning
‘on the Internet
’ [10].
Using off-line
algorithm
s
for ad placem
ent, we just
obse
rve searc
h
que
ries for a tim
e
peri
od, and
consider t
h
e
bids a
dve
rtisers
made on searc
h
term
s,
as well as th
eir adv
e
rtisin
g
bu
dg
ets for th
e tim
e p
e
riod
.
Thus the algori
thm can then assign a
d
s to the que
ries in
a way
t
h
at
m
a
xim
i
zes bot
h t
h
e
reve
nue t
o
t
h
e
search
engi
ne and the
num
ber of impressi
ons
that each advertiser gets. But sinc
e
users
who is
sue queries ca
n’t wait
fo
r the
ag
g
r
ega
t
e results,
o
n
-li
n
e alg
o
r
ithm
s
enter i
n
here
.
W
i
t
h
on
-l
i
n
e al
go
ri
t
h
m
s
we m
a
y
use
past
dat
a
fo
r c
o
m
put
i
n
g (l
i
k
e cl
i
c
k-t
h
ro
u
gh
rat
e
)
,
y
e
t
we ca
nn
ot
assu
m
e
h
a
v
i
ng certain
qu
eries or ev
en
ts i
n
the fu
tu
re.
2.
1 O
n
-L
i
n
e
A
l
gori
t
hms
M
a
t
c
hi
ng a
dve
rt
i
s
em
ent
s
t
o
search
que
ri
es i
s
refer
r
ed
to
as “o
n-lin
e”, an
d th
ey g
e
n
e
rally in
vo
lv
e an
approach
called”gree
dy”. A prelim
in
ary exa
m
ple of an
on-line
gree
dy
alg
o
rith
m
fo
r
a sim
p
ler p
r
ob
lem:
m
a
xim
a
l
m
a
t
c
hi
n
g
i
s
s
h
ow
n
[
10]
.
2.
2 O
n
-L
i
n
e
a
nd O
f
f
-
L
i
ne
A
l
gori
t
hms
Th
e
work
fl
ow
o
f
t
h
e typ
i
cal alg
o
rith
m
s
i
s
as fo
llows.
All th
e
d
a
ta need
ed b
y
t
h
e
alg
o
rith
m
is
presented initially. The
algorith
m
can access the data i
n
any order.
At the end, the al
gorithm
produces its
answer. Such a
n
algorith
m
is called
off-lin
e.
Th
er
e is an extr
em
e f
o
r
m
o
f
str
eam
p
r
o
cessin
g
,
wh
er
e w
e
m
u
st r
e
sp
ond w
ith
an
o
u
t
p
u
t af
ter
each
stream
ele
m
ent arri
ves.
We thus m
u
st
decide
about eac
h strea
m
ele
m
ent kno
wing
no
th
ing
at all o
f
th
e
fu
ture.
Algo
rith
m
s
o
f
th
is class are called
on
-lin
e alg
o
rith
m
s
[4
].
As the case i
n
po
in
t,
selectin
g
ad
s t
o
sh
ow
with
search
q
u
e
r
i
e
s
wo
ul
d
be
rel
a
t
i
v
el
y
si
m
p
l
e
i
f
we c
oul
d
do
i
t
of
f-l
i
n
e
.
We
w
oul
d see
a m
o
n
t
h’s
w
o
rt
h
of
s
earch
que
ri
es, a
nd l
o
ok at
t
h
e
bi
ds
adve
rt
i
s
ers m
a
de o
n
searc
h
t
e
rm
s, as wel
l
as t
h
ei
r ad
vert
i
s
i
ng
bu
d
g
et
s f
o
r t
h
e
m
ont
h, an
d
we
co
ul
d
t
h
e
n
ass
i
gn a
d
s
t
o
t
h
e
que
ri
es i
n
a
way that m
a
ximized
bot
h t
h
e re
venue t
o
t
h
e s
earc
h
engi
ne and the
num
ber of im
pressi
ons that each advertis
er got. The
probl
em
with o
ff-li
n
e algorithm
s
is that
m
o
st q
u
e
ryers
d
on’t wan
t
to
wait a m
o
n
t
h
t
o
g
e
t th
eir search
resu
lts.
Thu
s
,
we m
u
st u
s
e an on-lin
e alg
o
rith
m
to
assig
n
ads
to se
arch queries
.
T
h
at
is, when
a search
que
r
y
arrive
s, we m
u
st select the ads to
sh
ow
wi
t
h
t
h
at
que
ry
im
m
e
di
at
el
y
.
W
e
can use information about the past
,
e.g
.
, w
e
do
n
o
t
h
a
v
e
to
sh
ow
an
ad if
th
e adv
e
r
tiser’
s
b
udget h
a
s alr
e
ad
y b
een
sp
en
t, and
w
e
can
ex
amin
e th
e
click
-
th
rou
g
h
rate (fractio
n
of th
e tim
e th
e ad
is click
e
d
o
n
wh
en
it is
d
i
sp
layed
)
t
h
at an ad
h
a
s
ob
tained
so
far.
3.
GREEDY AL
GORITHMS
Many on-line
algorithm
s
are of t
h
e
gree
dy a
l
gorithm
type. These al
go
rithm
s
mak
e
th
eir
d
ecision
in
resp
o
n
se t
o
eac
h i
n
p
u
t
el
em
ent
by
m
a
xim
i
zi
ng s
o
m
e
funct
i
o
n
of
t
h
e i
n
p
u
t
e
l
em
ent
and
t
h
e
past
.
Exam
pl
e 1:
A m
a
nufact
ure
r
A o
f
re
pl
i
ca ant
i
que f
u
r
n
i
t
u
re
has bi
d 10 cent
s
on the sea
r
c
h
ter
m
“chesterfield”.
A m
o
re co
nve
nt
i
onal
m
a
nufa
c
t
u
rer B
has
bi
d 2
0
ce
nt
s o
n
b
o
t
h
t
h
e
t
e
rm
s “chest
er
fi
el
d” a
nd “
s
o
f
a.” B
o
t
h
ha
v
e
m
ont
hl
y
bu
dge
t
s
of
$
1
0
0
,
a
n
d t
h
e
r
e a
r
e
no
ot
he
r
bi
d
d
ers
on
ei
t
h
er
o
f
t
h
ese t
e
rm
s. It
i
s
t
h
e
begi
nni
ng
of
t
h
e
m
ont
h, an
d a
s
earch
q
u
ery
“
c
h
est
e
r
f
i
e
l
d
”
ha
s j
u
st
a
rri
ve
d
[
10]
.
Fo
r t
h
e d
a
ta of th
is ex
am
p
l
e,
wh
at will h
a
p
p
en
is th
at th
e first 5
0
0
“sofa” o
r
“ch
esterfiel
d
”
qu
eries
will b
e
assig
n
e
d
to
B. At th
at
ti
m
e
,
B ru
n
s
ou
t o
f
bud
g
e
t and
is assig
n
e
d
no
m
o
re q
u
e
ries. After th
at, the n
e
x
t
1000 “c
hesterfield” queries
a
r
e assi
gne
d t
o
A, and “sof
a”
queries
get
no a
d
a
n
d
the
r
e
f
ore ea
rn the
s
earch
engi
ne
n
o
m
o
n
e
y
.
The
w
o
rst
t
h
i
n
g t
h
at
can
h
a
ppe
n
i
s
t
h
at
5
0
0
“c
hest
erfi
el
d”
qu
eri
e
s a
rri
ve,
f
o
l
l
o
we
d
b
y
50
0
“so
f
a”
qu
er
ies. A
n
o
f
f
-
lin
e al
g
o
r
ith
m
co
u
l
d
o
p
tim
all
y
assig
n
th
e f
i
r
s
t 50
0
to
A
,
ear
n
i
n
g
$5
0, and
th
e
n
e
x
t
500
t
o
B
,
earni
ng
$
1
0
0
,
or a t
o
t
a
l
of
$1
5
0
. H
o
we
ver
,
t
h
e g
r
eedy
al
gori
t
h
m
wi
l
l
assi
gn t
h
e fi
rs
t
500 t
o
B
,
ear
ni
n
g
$
100
, and
th
en h
a
s no
ad
f
o
r
t
h
e
n
e
x
t
50
0, ear
n
i
n
g no
th
i
n
g.
3.
1 T
h
e
M
a
tc
hi
ng
Pro
b
l
em
A
pr
o
b
l
e
m
i
s
di
scuss
e
d
w
h
i
c
h i
s
a
si
m
p
l
i
f
i
e
d
versi
o
n
of
t
h
e p
r
o
b
l
e
m
of
m
a
t
c
hi
ng
[2]
a
d
s t
o
sea
r
c
h
que
ries. T
h
is
problem
,
called “m
axim
al
m
a
tching,” is a
n
a
b
stract
proble
m
invol
ving
bi
partite graphs
(gra
phs
with
two
sets of nod
es
–
left an
d ri
g
h
t
–
with all ed
g
e
s
co
nnectin
g
a
no
d
e
in
th
e left set to a nod
e in th
e
rig
h
t
set).
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 4
,
N
o
. 5
,
O
c
tob
e
r
20
14
:
810
–
8
16
8
13
3.
2
Matches
and Per
f
ect Matches
Sup
p
o
s
e
we are g
i
v
e
n
a b
i
p
a
rtite g
r
aph
[3
] [6
]. A m
a
tch
i
n
g
is a su
b
s
et
o
f
t
h
e edg
e
s su
ch
th
at no
nod
e
i
s
an e
n
d
o
f
t
w
o
or m
o
re e
dge
s. A
m
a
t
c
hi
ng
i
s
sai
d
t
o
be
pe
rfect
i
f
e
v
e
r
y
n
ode
ap
pea
r
s i
n
t
h
e m
a
t
c
hi
ng.
Not
e
t
h
at
a
m
a
t
c
hi
ng can o
n
l
y
be per
f
ect
i
f
t
h
e l
e
ft
and ri
ght
se
ts are of the sa
me size. A
mat
c
h
i
ng
th
at is as larg
e
as an
y
o
t
h
e
r match
i
n
g
fo
r th
e
g
r
aph
in qu
estio
n is said to
b
e
m
a
x
i
mal.
Fig
u
re
2
.
A Bip
a
rtite grap
h
Th
e set o
f
ed
ges {(a, 1), (b
, 2), (c,
4
)
} is a match
i
n
g
fo
r t
h
e b
i
p
a
rtite g
r
ap
h
[3
] [6
] o
f
Fi
g
u
re 2. Each
me
m
b
er o
f
th
e set is an
ed
g
e
o
f
th
e
b
i
p
a
rtite g
r
ap
h,
and
no
no
de app
ears
m
o
re th
an
on
ce. Th
e set o
f
ed
g
e
s
{(
a,
3
)
,
(b
,
2
)
, (c, 4)
, (d
, 1)
} is
a p
e
rf
ect m
a
tc
h
i
ng
,
r
e
pr
esen
ted
b
y
h
e
av
y lin
es in
Figu
r
e
3. Ev
er
y nod
e ap
p
e
ar
s
ex
actly o
n
c
e.
Th
ere is a so
le p
e
rfect m
a
tch
i
n
g
fo
r t
h
is
g
r
ap
h,
wh
ereas some b
i
p
a
rtite grap
hs h
a
v
e
m
o
re th
an
one
per
f
ect
m
a
t
c
hi
ng
[2]
.
T
h
e m
a
t
c
hi
ng of Fi
gu
re 3 i
s
al
so
m
a
xim
a
l, si
nce eve
r
y
per
f
ect
m
a
t
c
hi
ng i
s
max
i
m
a
l.
3.3 The
Greedy
Algorithm
for Maxim
a
l Matching
In
pa
rt
i
c
ul
ar,
t
h
e
gree
dy
al
g
o
ri
t
h
m
[7]
f
o
r
m
a
xi
mal
m
a
t
c
h
i
ng
work
s as fo
llo
ws.
We con
s
id
er th
e
edge
s i
n
w
h
at
e
v
er
o
r
de
r t
h
ey
are
gi
ve
n.
Wh
en
we c
onsi
d
er
(x
, y
)
, a
d
d
t
h
i
s
ed
ge t
o
t
h
e
m
a
t
c
hi
ng i
f
ne
i
t
h
er
x
no
r y
a
r
e e
n
d
s
of
any
e
d
ge sel
ect
ed f
o
r
t
h
e
m
a
t
c
hi
ng
s
o
fa
r.
Ot
he
rwi
s
e,
s
k
i
p
(x
, y
)
.
Let
us
co
nsi
d
er a
gr
eedy
m
a
t
c
h fo
r t
h
e
g
r
ap
h
of
Fi
gu
re
2.
S
u
p
p
o
se
we
or
de
r
t
h
e
no
des
l
e
xi
cog
r
a
phi
ca
l
l
y
, t
h
at
i
s
, by
or
der
o
f
t
h
ei
r l
e
ft
n
o
d
e,
br
eak
i
ng t
i
e
s
by
t
h
e
ri
g
h
t
no
de.
T
h
en
we
co
nsi
d
er t
h
e
edge
s i
n
t
h
e or
der
(
a,
1)
,(a,
3
)
,(
b,
2)
,(c,
2
)
,(c
,
4
)
,
(
d
,
1
)
. T
h
e fi
rst
edge, (
a
, 1
)
, b
ecom
e
s part
of
t
h
e
m
a
t
c
hi
ng.
The
second e
d
ge, (a, 3), ca
nnot be chosen, beca
use
node a al
re
ady appears i
n
the m
a
tchi
ng.
The t
h
i
r
d e
d
ge,
(b
, 2
)
,
is selected, because neither node
b nor node 2 appears in
the
m
a
tching so far. Edge (c, 2) is rej
ected
for the
match because
2 is alrea
d
y
matched,
but t
h
en
(c,
4) is
a
dde
d t
o
the m
a
tch beca
use
ne
ither c
nor 4 has bee
n
m
a
t
c
hed so fa
r
.
Fi
nal
l
y
, (d
, 1)
i
s
reject
ed
bec
a
use 1 a
p
p
ears
i
n
t
h
e m
a
t
c
h. Thus
, t
h
e m
a
t
c
hing
pr
o
duce
d
b
y
t
h
e
gree
dy
al
g
o
ri
t
h
m
for t
h
i
s
or
de
ri
n
g
of t
h
e e
d
g
e
s i
s
{(a
,
1),
(
b
, 2
)
,
(c,
4
)
}.
Th
i
s
m
a
t
c
hi
ng i
s
not
m
a
xim
a
l
.
Fi
gu
re 3.
The
onl
y
per
f
ect
m
a
t
c
hi
ng
f
o
r
t
h
e
gra
p
h of Fi
g
u
r
e
2
a
b
c
d
1
2
3
4
a
b
c
d
1
2
3
4
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Issue
s
an
d C
h
a
l
l
e
nges i
n
A
d
ve
rt
i
s
i
ng
on
t
h
e
Web
(
D
ee
pt
hi
Gur
r
a
m
)
81
4
4.
THE ADWORDS PROBL
E
M
The fundam
e
ntal problem
of search a
d
vertis
ing,
which we term
the
“adwo
rds
problem
,
”
because it
was
first en
coun
tered
in th
e
Go
og
le
Adwo
rds syste
m
[1
]
[
1
0]
. O
f
c
o
urse
, t
h
e
deci
si
o
n
re
g
a
rdi
n
g
w
h
i
c
h
a
d
s t
o
sh
ow m
u
st b
e
mad
e
on
-lin
e.
Th
e
on
-lin
e
algo
rith
m
s
for so
l
v
ing
th
e adwo
rd
s
p
r
ob
lem
are as fo
llows.
•
Gi
ve
n:
1.
A set
o
f
bi
ds
by
a
dve
rt
i
s
ers
fo
r sea
r
ch
q
u
e
r
i
e
s.
2.
A cl
i
c
k
-
t
h
ro
ug
h
rat
e
f
o
r ea
ch a
dve
rt
i
s
er-
q
uery
pai
r
.
3. A
budget for each adve
rtiser.
W
e
s
h
all assum
e
budgets
are for a m
onth, although a
ny unit of tim
e
coul
d be
use
d
.
4.
A l
i
m
it
on t
h
e n
u
m
b
er o
f
a
d
s t
o
be
di
spl
a
y
e
d
wi
t
h
eac
h se
arch
q
u
ery
.
• Resp
ond
to each
sear
ch qu
er
y w
ith
a set
of advertisers
s
u
ch that:
1
.
Th
e size of t
h
e set is
no
larg
er th
an
th
e limit o
n
th
e
nu
mb
er of ad
s
p
e
r
q
u
e
ry.
2.
Each adverti
s
er
has
bid on t
h
e sea
r
ch que
r
y.
3
.
Each adv
e
r
t
i
s
er
h
a
s eno
ugh bu
dg
ets lef
t
t
o
p
a
y
f
o
r
th
e ad
if
it is click
e
d
u
pon
.
Much of
the effective
n
ess of
s
earc
h
a
d
v
e
rt
i
s
i
ng c
o
m
e
s fr
om
t
h
e “ad
wo
rd
s” m
odel
of
m
a
t
c
hi
ng
search
que
ries
to adve
rtisem
e
n
ts. Searc
h
ads
are placed
among the res
u
lts of a sear
ch
query. Adve
rtisers bid
for th
e righ
t to h
a
v
e
th
ei
r ad
sh
own
in
respo
n
s
e to
certain q
u
e
ries, bu
t they p
a
y o
n
l
y if th
e ad
is click
e
d
on
.
The
particular
ads to
be s
h
own are se
lecte
d
by a com
p
lex
process
,
which we
consi
d
er in this post. It e
m
braces
search term
s that the advertise
r
ha
s bi
d for, t
h
e am
ount
of
t
h
eir
bid, the st
atistical
proba
bility that the ad will
b
e
click
e
d
on
,
an
d th
e t
o
tal bu
dg
et th
e adv
e
rtiser
h
a
s
o
f
fered
for th
e serv
i
ce.
4.1 The
Greedy
Appr
oach
to the
Adw
o
rds
Problem
Sin
ce on
ly an
o
n
-lin
e algo
rit
h
m
is su
itab
l
e
for th
e a
d
words [1] problem
, we should
first
exam
ine the
per
f
o
r
m
a
nce of t
h
e o
bvi
ous
gree
dy
al
go
ri
t
h
m
.
Supp
ose t
h
ere are t
w
o a
dve
rt
i
s
ers A a
nd B
,
an
d o
n
l
y
t
w
o
pos
sible que
r
ies, x a
n
d y. Advertiser
A
bids
only on
x,
while B bids on
bot
h x a
n
d y.
The
budget for each
adve
rtiser is
2. Let the seque
n
ce of
que
ries
be xxyy.
T
h
e
greedy algorithm is able to
allo
cate th
e
first two
x’s
t
o
B
,
whe
r
eu
p
on t
h
e
r
e i
s
no
one wi
t
h
a
n
une
x
p
en
de
d b
u
d
g
et
t
o
pay
f
o
r t
h
e t
w
o y
’
s
.
The re
ven
u
e
fo
r t
h
e
g
r
eed
y
algo
rith
m
in
th
is cas
e is th
u
s
2. Howev
e
r,
th
e
op
ti
m
u
m
o
ff-lin
e
alg
o
rith
m
will
allo
cate th
e x
’
s to
A
and the y
’
s to
B, achie
vi
n
g
re
ven
u
e o
f
4[
10]
.
4.
2 Com
p
eti
t
i
v
e Ra
ti
o
Co
m
p
etit
iv
e ratio
is th
e min
i
m
u
m rate o
f
th
e on
lin
e al
g
o
rith
m
co
m
p
ared
to
th
e
op
ti
mu
m
o
ff-line
al
go
ri
t
h
m
s
for
t
h
e sam
e
case/
pr
obl
em
ove
r al
l
possi
bl
e
in
pu
ts (esp
ecially th
e wo
rst
case). c = effi
ciency
(on
lin
e)/efficien
cy (offlin
e) in th
e worst case. Th
rou
g
h s
o
me calculation one m
a
y prove that generally for the
g
r
eed
y
algo
rit
h
m
[7
] in
ad
s pro
b
l
em
th
e co
m
p
etitiv
e ratio
is no
t less th
an
1/2
.
4.
3 B
a
l
a
nce
Al
gori
t
hm
Bu
t th
ere
are
oth
e
r th
an
g
r
eedy alg
o
r
ith
m
s
, giv
i
n
g
b
e
tter a co
m
p
etitiv
e rati
o
.
Besi
d
e
s th
e
max
i
m
u
m
prese
n
t
r
e
ve
n
u
e
bal
a
nce
,
t
h
e
bal
a
nce al
go
ri
t
h
m
consi
d
e
r
s also
th
e
greatest rem
a
in
in
g
b
u
d
g
e
t
of an
advertiser
in
o
r
d
e
r to
d
e
cid
e
wh
ich
ad
to
sho
w
. Its u
ltimate co
m
p
etit
i
v
e ratio
(sim
p
lified
adwords
m
o
d
e
l) will g
o
clo
s
e
to
0.63
as th
e
n
u
m
b
e
r
of
b
i
dd
er
s and
qu
er
i
e
s g
r
ow
.
Howev
e
r it do
es no
t wo
rk
op
timally in
so
m
e
e
x
trem
e
cases.
Exam
ple: In this exam
ple
we
co
m
p
are th
e si
m
p
lified
situ
atio
n
for off-line and greedy on-line
algorithm
s
in ad
placem
ent.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 4
,
N
o
. 5
,
O
c
tob
e
r
20
14
:
810
–
8
16
8
15
Fi
gu
re
4.
Exa
m
pl
e of com
p
ari
s
o
n
of
o
f
f
-
l
i
n
e an
d
gree
dy
o
n
-l
i
n
e
al
g
o
ri
t
h
m
s
.
Ad
ve
rt
i
s
er ‘
A
’
has
bi
d
1
0
ce
nt
s
on t
h
e sea
r
ch t
e
rm
“choc
ol
at
e”. A
d
vert
i
s
er
B
has
bi
d
20
cent
s
o
n
bot
h t
h
e t
e
rm
s “cho
c
ol
at
e” a
nd “
b
e
rry
”. B
o
t
h
ha
ve m
ont
h
l
y
bu
dget
s
o
f
$1
0
0
.
We
hav
e
no
past
st
at
i
s
t
i
c
s on
ei
t
h
er o
f
t
h
e
s
e
t
e
rm
s. W
e
pr
esu
p
p
o
se t
h
at
onl
y
one
ad i
s
t
o
be t
o
o
di
s
p
l
a
y
e
d
wi
t
h
o
n
e
que
ry
. T
h
e
ob
vi
o
u
s
th
in
g to
d
o
is t
o
d
i
sp
lay B’s
ad
,
b
ecau
s
e they b
i
d
m
o
re (greed
y ap
pro
a
ch
). Howe
v
e
r, su
ppo
se th
ere
will b
e
lo
ts o
f
search
q
u
e
ries th
is mo
n
t
h
fo
r
“b
erry
” b
u
t
v
e
ry
few
for “cho
c
o
l
ate.” Th
en
A
will n
e
v
e
r sp
end
its $
100
b
udg
et,
wh
ile
B will sp
en
d its fu
ll bu
dg
et ev
en if
we
g
i
v
e
th
e qu
ery to
A.
The
worst ca
se
that ca
n
happen is t
h
at
500
“berry” qu
e
r
ies arrive, followed by
500 “c
hoc
olate”
que
ries (see
th
e figure b
e
l
o
w,
at
righ
t).
Th
e gr
eed
y
algorith
m
will assi
g
n
t
h
e fi
rst 500
ads to
B, earn
i
ng
$
100
, and th
en
h
a
s
no
ad
for t
h
e
n
e
x
t
50
0, earn
i
n
g no
th
i
n
g.
Th
e co
m
p
etitiv
e ratio
i
n
th
is case is equ
a
l
2
/
3.
5.
CO
NCL
USI
O
N
These basic theses
and the sim
p
li
fied example have s
h
own the cha
llenge and also an
ele
m
entary
approach (gre
edy,
on-
line
)
t
o
a
d
placem
ent related t
o
se
arch qu
e
r
ies. The data
m
i
ning algorithm
s
for a
d
placem
ent in r
e
sponse to a s
earch
que
ry or large
r
documents (e
m
a
ils)
are on-line greedy or ge
ne
ralized
bal
a
nce
al
g
o
ri
t
h
m
s
on t
h
e m
a
t
c
h
gra
p
h
s
.
Th
e com
p
l
e
x
que
ry
/
b
i
d
m
a
t
c
hi
n
g
pr
ocess
i
s
t
o
be
d
one
wi
t
h
h
a
shi
n
g
set
s
-o
f-
wo
r
d
s t
a
bl
es wi
t
h
t
h
e
co
nseq
ue
nt
m
a
t
c
hi
ng
o
f
ra
re
to u
n
rare
w
o
rd
o
r
de
r in
o
r
der t
o
fi
nd
the
total
m
a
t
c
h of
t
h
e
bi
d set
i
n
t
h
e
d
o
c
u
m
e
nt
.
REFERE
NC
ES
[1]
A Mehta, A Sa
beri, U Vazir
a
ni, and
V Vaziran
i
. “Adwords and generalized
o
n
-line m
a
tch
i
ng
”. IEE
E
S
y
m
p
. on
Foundations of
Computer
Scien
ce. 2005: 264–2
73.
[2]
Bala Kaly
an
asundaram and Ki
r
k
R. Pruhs. An
optimal d
e
ter
m
inistic
algorithm for online
b-matching. Th
eor.
Comput. Sci., 20
00; 233(1-2):319
-325.
[3]
RM Karp,
UV Vazirani,
and VV Vazirani.
An
optimal algorit
hm for on-line
bipartite mat
c
hi
ng
.
I
n
ST
OC
'
90:
Proceedings of
t
h
e twen
t
y
-secon
d
annua
l ACM s
y
m
posium
on
T
h
eor
y
of
com
put
ing. 1990
: 352-3
58.
[4]
Aran
y
a
k Mehta, Amin Saberi, Umesh
Vazirani,
and Vijay
Vazi
r
a
ni. Adwords and gener
a
lized
on
line matching
.
J.
ACM
. 2007
; 54(
5): 22.
[5]
P Rusm
evichien
tong and DP William
s
on. An ad
aptiv
e algor
ithm
for selecting pr
o
fi
table k
e
y
w
ord
s
for s
earch bas
e
d
advertising services.
In
Se
ven
th
ACM Conf
er
enc
e
on
El
ectr
oni
c
Commer
c
e
. 200
6.
A
dver
t
ise
r
A
Bu
dge
t $1
0
0
/m
ont
h
10 c
e
n
t
s
b
i
d f
o
r
searc
h
term
“c
h
o
c
o
l
at
e”
A
dver
t
ise
r
A
Bu
dge
t $1
0
0
/m
ont
h
20 c
e
n
t
s
b
i
d f
o
r s
earc
h
term
“
c
hoc
ol
ate
”
or
“b
e
r
r
y
”
Bot
h
50
0
“
c
hoc
ola
t
e
”
an
d
50
0 “
b
erry
”
queries ar
e
p
l
ac
ed
wi
th
ad
s
from
A
(
$50) a
n
d
B($1
00
)
Firs
t 50
0
“c
h
o
c
o
l
at
e”
queries ar
e given
w
i
t
h
B’
s ad
s.
T
h
e
ne
xt 50
0
“
b
erry
”
queries ar
e not
su
p
por
te
d w
i
th
any
ads, s
i
nce
B’
s bu
dg
et
is
ov
er.
500 “chocolate
”
queries ar
rive,
f
o
llowe
d b
y
500
“
b
err
y
”
q
ue
ries
500 “chocolate
”
queries ar
rive,
followed b
y
500
“berr
y
”
q
ueri
es
Off-line
a
lgo
rithm
Greedy On
-
line algorit
hm
$
150
$100
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Issue
s
an
d C
h
a
l
l
e
nges i
n
A
d
ve
rt
i
s
i
ng
on
t
h
e
Web
(
D
ee
pt
hi
Gur
r
a
m
)
81
6
[6]
Chinmay
K
a
ran
d
e, Ar
an
y
a
k Mehta, and
Pushkar Trip
athi. Online bipar
tite
matching with unknow
n distributions. I
n
STOC
. 2011.
[7]
Hochbaum DS, A Pathria. “Analy
sis of th
e greed
y
approach
in pr
oblems of
maximum k-coverage”.
Nava
l R
e
s
e
ar
ch
Logistics
. 1998
;
45: 615-627.
[8]
Revenue Science http://www.
re
venuescience.
com
/
advertisers/
advertiser_solutions
.asp
[9]
Ya
hoo! Sma
r
t A
d
s http://a
dve
r
tis
i
ng.y
a
hoo.
c
om/ma
rke
ting/sma
r
ta
ds/
[10]
Anand Rajaraman, Je
ffr
ey
Dav
i
d
Ullman.
“
Mining of Ma
ssive Data
se
ts”.
Evaluation Warning : The document was created with Spire.PDF for Python.