TELKOM
NIKA
, Vol.11, No
.11, Novemb
er 201
3, pp. 6637
~6
644
e-ISSN: 2087
-278X
6637
Re
cei
v
ed Ap
ril 21, 2013; Revi
sed
Jun
e
22, 2013; Accepted July 2
3
,
2013
K Nearest Neighbor Path Queries based on Road
Networks
Lulin Chen
1
, Guofeng Qin
*
2
Dep
a
rtment of Comp
uter Scie
nce an
d T
e
chnolo
g
y
, T
ongji U
n
iversit
y
, 48
00
Cao
an Ro
ad, J
i
adi
ng D
i
strict,
Shan
gh
ai, Chi
n
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: lulinc
h
e
n
1
9
8
9
@1
63.com
1
, g
f
q
i
ng
@y
ah
oo
.co
m
.cn
2
A
b
st
r
a
ct
The Island is
a
k near
est neighbor
query algorith
m
of
moving objects bas
ed on road net
works and
can
effectively
ba
lanc
e th
e
perfor
m
a
n
ce
o
f
query
a
nd
u
pdate. B
u
t th
e
al
gorith
m
d
o
e
s
n
’
t
co
nsid
er t
h
e
directi
on of
mo
ving
obj
ect w
h
i
c
h is re
quir
ed
in
ma
ny
sce
na
rios. It traverses vertexes fr
o
m
a
ll
directi
o
n
s
,
me
an
ing w
a
sti
ng a l
o
t of time in visiti
ng us
eless vert
ex
es. Besides, it d
o
e
sn
’
t
return
qu
ery path. In thi
s
pap
er, w
e
pr
op
ose
an
i
m
prov
ed Isl
and
a
l
gor
ithm w
h
ich
ta
k
e
s ful
l
acc
o
u
n
t
of movi
ng
direction. It takes
best
poi
nt esti
mat
e
and
h
euristic
s
earch
metho
d
,
effectivel
y
re
d
u
cin
g
th
e n
u
m
ber
of travers
a
l vertex
es. At the
same ti
me, w
e
opti
m
i
z
e
th
e d
a
ta structure a
nd let it re
turn t
he qu
ery pat
h. Result
s sh
ow
that the i
m
pr
ov
ed
alg
o
rith
m o
u
tp
erforms th
e or
igin
al
one. Fin
a
lly, w
e
descri
be el
ectric ve
hicle c
har
gin
g
guid
anc
e syst
e
m
base
d
on the i
m
pr
ove
d
Islan
d
alg
o
rith
m.
Ke
y
w
ords
:
ne
arest nei
gh
bor
query, isl
and
al
gorith
m
, he
uris
tic search
Copy
right
©
2013 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
Due
to the
a
d
vances in m
obile
com
m
u
n
icat
io
n a
nd
geog
rap
h
ic in
formation
technolo
g
y,
locatio
n
-b
ase
d
se
rvice
s
a
r
e increa
sin
g
l
y
popula
r
[1]. The k n
earest nei
ghbo
r que
stion is
an
importa
nt cla
ss of qu
ery type [2] among
location
-ba
s
ed se
rvice
s
. It is used to find the nea
re
st k
obje
c
ts from
query obj
ect,
such a
s
“fin
d nearest fi
ve resta
u
ra
nt’s positio
ns f
o
r taxi” [3], “find
nearest
k g
a
s
station’s p
o
sition
s fo
r d
r
ivers” [4
]. T
here
are
so
me qu
ery al
gorithm
s fo
r
static
obje
c
ts b
a
se
d on
roa
d
netwo
rks, li
ke Papa
di
a
s
’s
INE (Incre
mental Network
Expan
si
on)
algorith
m
[5], Kolahdo
uzan’
s VN3 (Vo
r
on
oi-Ba
s
ed
Net
w
ork Nea
r
e
s
t
Neig
hbo
r) al
gorithm
[6]
a
nd
Hua
ng’
s Isl
a
n
d
alg
o
rithm.
By offering fl
exible yet
sim
p
le me
an
s of
balan
cing
re-comp
u
tation
and
pre
-
computati
on, the Isla
nd
algorith
m
is
able to ma
na
ge the tra
d
e
-
off betwee
n
q
uery an
d up
d
a
te
and h
a
s bett
e
r p
e
rfo
r
man
c
e tha
n
oth
e
r
two
metho
d
s
[7]. But the
algo
rithm’s
online
network
-
expan
sion
co
mpone
nt mu
ch like
Dijkstra
algo
rithm.
T
he m
a
in
ch
aracteri
stic i
s
t
he q
u
e
r
y obj
ect
as th
e
cente
r
outward
exp
ansi
on laye
rs, until
k obj
e
c
ts
extende
d. Although
th
e alg
o
rithm
can
get
k
sho
r
t
e
st
dist
a
n
c
e
o
b
ject
s,
it
doe
sn’t
c
o
n
s
ide
r
the dire
ctio
n of moving
obje
c
t whi
c
h is
requi
re
d in m
any scena
rio
s
. What’
s
mo
re, it only
gives ne
are
s
t o
b
ject
s’ po
sitio
n
but not ret
u
rn
query p
a
ths.
This
articl
e d
e
scrib
e
s an i
m
prove
d
Isla
nd alg
o
rithm,
and it optimi
z
e
s
the al
go
ri
thm
from net
work-expan
sio
n
compon
ent an
d data
stru
cture. By usi
n
g be
st point
estimate a
n
d
heuri
s
tic
sea
r
ch metho
d
, the algo
rithm redu
ce
s t
he
numbe
r of traversal verte
x
es to increa
se
query spee
d, mean
while it gives qu
ery p
a
th whi
c
h can
be use
d
in p
a
th navigatio
n.
2. Road Netw
o
r
k Mod
e
l
In
many pra
c
t
i
cal appli
c
atio
ns, su
ch as m
ap
re
sou
r
ce services,
ro
ad n
a
vigation
syste
m
,
the roa
d
net
work i
s
usual
ly repre
s
e
n
te
d as
a
colle
ction of a larg
e numb
e
r of
node
s an
d ro
ad
segm
ents.
Road n
ode
s
ca
n be
divided i
n
to the follo
wi
ng three
ca
ses: (1) th
e int
e
rsectio
n
s of
the
netwo
rk,
(2
) the de
ad e
nd
of a ro
ad
seg
m
ent, and
(3
) the point
s
where
the
cu
rv
ature
of the road
segm
ent ex
ceed
s a
ce
rtai
n thre
sh
old
so that the ro
ad
s
e
g
m
e
n
t
is s
p
lit in
to
tw
o to
p
r
es
er
ve
th
e
curvatu
r
e
pro
perty [8]. Taking the on
e-way street
int
o
acco
unt, we ca
n tran
sfo
r
m the n
e
two
r
k
into a direct
ed graph i
n
memory. Fi
gure
1
sho
w
s
an exam
ple of ro
ad
netwo
rk
and
its
corre
s
p
ondin
g
dire
cted g
r
a
ph.
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No
. 11, Novemb
er 201
3: 663
7 – 6644
6638
Figure 1. Roa
d
Network
an
d its Dire
cted
Grap
h
There are
so
me definition
s
for graph a
s
follows:
Definition
1:
A roa
d
netwo
rk is a
directi
onal
wei
ghte
d
g
r
ap
h
(,
)
GV
E
. It c
o
ns
is
ts
of a
set
of
v
e
rt
ice
s
V
a
nd
a
set of ed
ge
s
E
, where
EV
V
.
Each edg
e can
be rep
r
e
s
en
ted
a
s
e
i,j
=(
v
i
,v
j
,l)
,
e
i,j
∈
E ,i
≠
j
, where
v
i
and
v
j
are the starting
and ending
vertex,
l
is th
e length of the
edge.
Definition
2:
Usi
ng
que
ry point
(qp
)
to
denote
a m
o
ving obj
ect
a
nd
da
ta
po
in
t (
d
p)
to
denote a
static que
ry obje
c
t.
Definition 3: A
locatio
n
o
n
the
ro
ad network
can be de
noted as
loc
=
(e, pos)
, wh
ere
e
is
the edge
on
whi
c
h the lo
cation is lo
cat
ed and
po
s
repre
s
e
n
ts th
e dista
n
ce f
r
om the sta
r
ting
vertex of the edge to
loc
.
W
e
h
a
v
e
tw
o c
o
nd
itio
ns
:
(1)
qp
su
ch as cars
ru
n on a
ro
ad network
and
dp
su
ch as ga
s
station
s
a
r
e l
o
cate
d on
th
e ro
ad
netwo
rk.
(2) The
di
stan
ce m
e
a
s
ure i
s
define
d
a
s
the
sh
ortest
path len
g
th (netwo
rk di
sta
n
ce
) o
n
the
netwo
rk [9]. In Figu
re
2,
e
1,7
=(v
1
,v
7
,5)
,
qp
’s
lo
c=
{(
e
4,
5
,1),
(e
5,4
,3)}
an
d
dp
1
’s
loc =
{(e
1,7
,3), (e
7,1
,2)}
.
Figure 2. Que
r
y Point and Data Point in the Dire
cted
Grap
h
3. Island Algorithm
The
Isl
and al
gorithm co
nsists of
pre-co
mputation
co
mpone
nt an
d
an o
n
line
n
e
twork
expan
sion
co
mpone
nt. Pre-comp
utatio
n com
pone
nt
divides
the netwo
rk
into some are
a
s, we
call th
em i
s
la
nd. Each i
s
la
nd i
s
a
ci
rcl
e
taking
dp
as the
cente
r
a
n
d
a val
ue giv
en in
advan
ce a
s
the radi
us. I
n
ord
e
r to
reco
rd the i
s
l
and info
rm
ati
on, every ve
rtex stores
referen
c
e
s
to
th
e
islan
d
s that cover the verte
x
and the network di
st
an
ce
s from the vertex to
the data points. Wh
en
getting a
qu
ery requi
rem
ent, we
first
nee
d to
ch
eck the
isla
n
d
s th
at the
qp
i
s
in
side
and
maintains the
dp
found in
a prio
rity que
ue, then sta
r
ts
a network
expan
sion to
find bord
e
rs o
f
new i
s
lan
d
s.
The expan
sio
n
pro
c
e
ss te
rminates
whe
n
the prio
rity queu
e ha
s k
element
s [7].
Q
dp
and
Q
v
are pri
o
rity q
u
e
ue for recordi
ng inte
rme
d
ia
te data.
Q
dp
is
us
ed
to
r
e
co
r
d
the
covered
data
points an
d th
eir
dista
n
ces
to
qp
. T
h
e
el
ement
of
Q
dp
is d
enote
d
a
s
(d
p
k
, d(qp,dp
k
))
and its si
ze i
s
limited to
k.
Similarly,
Q
v
re
cords the
can
d
idate
poi
nts an
d thei
r
distan
ce
s to
qp
,
usin
g
(v
x
, d(qp,v
x
))
den
otes elem
ents.
Both queue
s so
rt
eleme
n
ts by the distan
ce and d
on’t
allow d
uplicate data. The al
gorithm
can b
e
descri
bed a
s
follows:
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
K Nearest Ne
ighbo
r Path Queri
e
s b
a
se
d on Ro
ad Networks (L
uli
n
Che
n
)
6639
(1)
For
e
a
c
h
dp
on edg
e
qp
.e
, put
(dp, d(qp,d
p
))
int
o
Q
dp
and p
u
t
(qp.e.v
s
, d
(
qp, qp.e.
v
s
)
,
(qp.e.v
e
, d(qp
, qp.e.v
e
)
into
Q
v
;
(2)
For
ea
ch
dp
, if its island co
vers
qp.e.
v
s
or
qp.e.v
e
,put
(dp, d(qp,dp
))
into
Q
v
;
(3)
If the size of is k, the que
ry
terminate
s
, else sta
r
t network exp
a
n
s
io
n;
(4)
Get
Q
v
’s first
element
(v, d(qp,v))
an
d mark it visited;
(5)
For e
a
ch no
n-visited
adja
c
ent ve
rtex
v
x
of
v
, put
(v
x
, d(qp,v
x
))
into
Q
v
wh
en
Q
v
doe
sn’t
contai
n
v
x
. If
v
x
ha
s
alread
y existed i
n
Q
v
and
d
(
qp, v
x
)
i
s
small
e
r
than the
di
sta
n
ce
sto
r
ed,
update the di
stan
ce to
d(q
p
, v
x
)
, else d
o
nothing;
(6)
Rep
eat step
s 4 and 5 until finding k d
a
ta
points.
4. The Improv
ed
Island Algorithm
Island al
go
rithm’s exp
a
n
s
i
on proc
ess is similar to
Dij
kst
ra’s
sin
g
le
sou
r
ce shorte
st path
s
algorith
m
. De
spite the
high
accu
racy, th
e algo
rith
m d
oesn’t co
nsi
d
er the
sp
ecifi
c
ci
rcum
stan
ce
s
of the que
ry
points
and
data poi
nts,
whi
c
h me
an
s
wa
sting a l
o
t of time in
visiting u
s
el
ess
vertexes. So t
he sea
r
ch
is
blind a
nd in
efficient. We
ca
n use the
be
st point estim
a
te and h
e
u
r
ist
i
c
sea
r
ch metho
d
to cut down
the traversal vertexes an
d spe
ed up the
query.
4.1. Algorith
m
Descrip
tio
n
Con
s
id
er th
e
followi
ng t
w
o facto
r
s: (1) In d
a
ily life, wh
en
ma
kin
g
path
pla
nni
ng a
nd
navigation, if
you want to go s
outh will never go north,
this
i
s
the
habitual
choice; (2) A
strai
ght
line between
two poi
nts is t
he shorte
st. T
he shorte
st
p
a
th between t
w
o p
o
ints o
n
the actu
al ro
a
d
netwo
rk mu
st
be
clo
s
e
r
to
the line. If th
e st
raig
ht line
between
on
e
dp
and
qp
is the
s
h
ortes
t, it
rep
r
e
s
ent
s th
e
dp
may
also be the
nea
rest on
e to th
e
qp
o
n
the
road n
e
two
r
k.
So we
ca
n u
s
e
the function t
o
evaluate
da
ta points arou
nd the
qp
:
()
()
*
(
)
,
(
)
9
0
Ed
p
A
d
p
L
d
p
A
d
p
In the form
ul
a,
A(dp)
represe
n
ts the
an
gle bet
wee
n
the di
rectio
n o
f
qp
’s m
o
vem
ent and
the directio
n
from
qp
to
dp
. The
small
e
r the valu
e of
E(dp)
which
mean
s the
b
e
tter the
dp
t
hat
match the q
u
e
ry expe
ctations. And the
n
sele
ct t
he b
e
st k d
a
ta poi
nts,
but these
data points
a
r
e
not the final result, they just repre
s
e
n
t the forwa
r
d di
re
ction of the search.
After determi
ning the be
st data points,
we ca
n
use the heu
risti
c
strat
egy for se
arching. It
limits the
sea
r
ch
scale
by
an evalu
a
tion
function.
In e
a
ch
step
of searchin
g p
r
o
c
ess, we fin
d
the
vertex with th
e lowest valu
e of the eval
uation
fun
c
tio
n
as th
e next
extensio
n ve
rtex. Here, the
evaluation fu
nction i
s
:
11
()
()
(
)
,
(
)
(
)
..
,
.
.
xx
x
x
KK
ii
ii
f
v
g
v
hv
hv
L
V
d
p
V
d
p
L
at
dp
L
a
t
V
dp
L
o
n
d
p
L
on
In the formul
a,
g(v
x
)
is a
c
tual co
st from
qp
to
v
x
and
h(v
x
)
is the
straig
ht line
distan
ce
betwe
en
v
x
a
nd virtual dat
a point. Virtual data point’
s
longitud
e
is the average
of k best da
ta
points’ lo
ngit
ude
s. Similarly, virtual data point’s
l
a
titude is th
e a
v
erage
of k
best d
a
ta poi
nts’
latitudes. The
algorithm
ca
n be de
scribe
d as follo
ws:
(1)
For
ea
ch
dp
on
e
dge
qp.e
, put
(dp, d
(
q
p
,dp))
whi
c
h i
s
in
the
movi
ng di
re
ction
i
n
to
Q
dp
and
put
(qp.e.
v
e
, d(qp, qp.e.
v
e
)
into
Q
v
;
(2)
For
ea
ch
dp
, if its island co
vers
qp.e.
v
e
,put
(dp, d(qp,
dp))
into
Q
v
;
(3)
If the size of is k, the que
ry
terminate
s
, else sta
r
t network exp
a
n
s
io
n;
(4)
Assu
ming
we
have fo
und
n data
poi
nts, ther
e
are
still m (m=k-n)
data p
o
ints n
eede
d. Use
best
point e
s
timate metho
d
to find
othe
r m o
p
timal d
a
ta point
s a
n
d
to calculate
the virtual
data point.
(5)
Get
Q
v
’s first
element
(v, d(qp,v))
whos
e
f(v
)
valu
e is the small
e
st , and then ma
rk it visited;
(6)
For ea
ch no
n-visited
adj
a
c
ent
ve
rtex
v
x
of
v
, put
(v
x
, d(qp,
v
x
))
into
Q
v
whe
n
Q
v
do
esn’t
contai
n
v
x
. If
v
x
ha
s al
rea
d
y
existed in
Q
v
and
d(q
p
, v
x
)
i
s
smalle
r than the
dist
ance sto
r
e
d
,
update the di
stan
ce to
d(q
p
, v
x
)
, else d
o
nothing;
(7)
Rep
eat step
s 5 and 6 until finding m dat
a points.
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No
. 11, Novemb
er 201
3: 663
7 – 6644
6640
Usi
ng h
e
u
r
isti
c fun
c
tion,
we ma
ke the
search m
o
re i
n
telligent to t
he virtual
dat
a point
so
that it ca
n redu
ce th
e traver
sed ve
rt
ex. Figure 3
is a
n
Isl
and
algo
rithm’s approximate path
extensio
n dia
g
ram a
nd Fig
u
re 4 i
s
the i
m
prove
d
Isla
nd algo
rithm’
s app
roximat
e
path exten
s
ion
diagram.
Figure 3. Isla
nd Algorithm’
s
Approximate Pa
th
Figure 4. Improved Isla
nd
Algorithm’
s
Approximate Path
The figu
re
s show th
at the i
m
prove
d
net
work
traverse
s fewer ve
rte
x
es than
ori
g
inal on
e.
Whe
n
k=1, fo
r exampl
e, su
ppo
se the
sh
ortest
pat
h le
ngth is 2a,
so
the maximu
m se
arch
radi
us
of the Island
is 2a an
d the
major axis o
f
the e
llipse
of improved I
s
lan
d
is 2a.
Search area
a
s
follows
:
The area of ci
rcle:
2
4
Sa
The area of ellipse:
22
1,
/
,
Sa
e
e
c
a
c
a
Whe
n
k=1, I
s
lan
d
algo
rith
m’s maximu
m sea
r
ch a
r
ea is 4 time
s mo
re than
improve
d
Island
alg
o
rit
h
m’s.
Of cou
r
se,
the i
m
proved al
gor
ith
m
is faste
r
which
can
be
verified from
the
followin
g
experime
n
tal dat
a.
4.2. Data S
t
r
u
ctur
e
Island
alg
o
rit
h
m do
es not
retu
rn
que
ry
path
a
nd can’t be dire
ctly
appli
ed to
path
planni
ng
sce
nario
s,
so
it i
s
n
e
cessa
r
y t
o
optimi
z
e th
e data
st
ru
cture.
De
sign
e
d
data
st
ru
cture
is
based on
Jav
a
can b
e
se
e
n
in Figure 5.
Figure 5. Gra
ph Structu
r
e
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
K Nearest Ne
ighbo
r Path Queri
e
s b
a
se
d on Ro
ad Networks (L
uli
n
Che
n
)
6641
We u
s
e the a
d
jacen
c
y list as g
r
aph
storage st
ru
cture
,
meanwhile, usin
g Ha
shM
ap dat
a
stru
cture to spe
ed up th
e sea
r
ch for set of
adja
c
ent ed
ge
s. The detail
s
of grap
h sto
r
age
stru
cture ca
n be se
en in Fi
gure 6.
Figure 6. The
Main Storag
e Structu
r
e
Island
cla
s
s store
s
p
r
e
-
co
mputed
re
sult
s which sto
r
e
d
in file in de
fault and loa
ded into
memory whe
n
need
ed. Th
e stora
ge form of Island cl
ass is
(v
x
, d(v
x
,dp), path)
,
v
x
is the Island
’s
ver
t
ex,
d(v
x
,dp)
is the sho
r
test dista
n
ce from
dp
to
v
x
and
path
store
s
detail
shorte
st pat
h.
Nod
e
RelatedI
slan
d cla
ss
stores ve
rtex’s Island re
fe
rence, if the
vertex
is cov
e
red by Islan
d
,
there
mu
st e
x
ists referen
c
e in
Nod
e
Rel
a
tedIsla
nd
cl
ass. ResultLi
st cl
as
s
cont
ains the n
e
a
r
es
t
data point
s a
nd the sh
orte
st path.
Acco
rdi
ng to
the ab
ove al
gorithm, fi
rst
we
sh
ould
se
arch th
e
Nod
e
Rel
a
tedIsl
an
d cl
ass
to judge
whe
t
her
qp.e.v
e
h
a
s
Is
la
nd
r
e
fe
r
e
nc
es
w
h
ic
h
c
o
ver
it an
d
p
u
t
Is
la
nd r
e
fer
e
nc
es
in
to
Re
sult
Li
st
cl
as
s.
I
f
Re
sul
t
List
.
s
iz
e(
)>
=
k
,
t
he
sea
r
ch termin
ates,
otherwi
se
start the net
work
expan
sion. V
i
sit the g
r
ap
h
and find
qp.
e.v
e
’s
adja
c
e
n
t edge
s.
We re
pla
c
e the
Arc.len
g
th
with
f(v
x
)
an
d p
u
t
the Arc into
t
he p
r
io
rity qu
eue. G
e
t p
r
io
rity queu
e’s f
i
rst
eleme
n
t, remove
it an
d
sea
r
ch the Node
RelatedI
sl
and to judge
whethe
r Arc.EndNod
eId has Isl
and referen
c
e
s
. And
then rega
rd
Arc.End
N
od
e
I
d as th
e nex
t sea
r
ch ve
rt
ex. Repe
at the p
r
o
c
e
ss
u
n
til we fin
d
the k
nearest
data
points. T
he i
d
and
shor
te
st
path
of nea
rest d
a
ta p
o
int
s
can
be fo
u
nd in
Re
sultL
i
st
cla
ss.
The
stru
cture
use
s
a
lot of
Ha
shM
ap a
n
d
Tre
e
Set. HashM
ap a
s
mentione
d be
fore
can
improve
the
se
arch
efficiency. T
r
eeS
et ba
sed
on
Re
d-Bla
c
k
Tree
[10]
which
is the
self-
balan
cing
bin
a
ry se
arch tree.
Its ope
rat
i
on’s
com
p
lex
i
ty is
O(log
2
n)
. We ca
n u
s
e
comp
arato
r
to
make th
e red
-
bla
ck tree m
a
intain
s an o
r
de
rly st
ate. Priority queu
e need
s fre
q
uent insert a
nd
delete
op
erations, so
let TreeSet
a
s
prio
rity
queu
e is a
wise choi
ce. As
can be
see
n
, the
optimize
d
da
ta stru
cture is able to
ret
u
rn t
he
sh
ort
e
st path a
n
d
the com
p
lex
i
ty of improved
Island al
gorit
hm netwo
rk e
x
pansi
on is
O
(
nlog
2
n)
.
4.3. Simulation and An
aly
s
is
T
he expe
rim
ent use
s
Sh
angh
ai roa
d
netwo
rk
. After modeli
ng,
the grap
h contai
ns
2014
740 vert
exes an
d 203
7521 a
d
jacen
t
edges. Hard
ware co
nfigu
r
ation: Intel (R) Co
re (TM
)
2
Duo
CP
U, 2.
0GB mem
o
ry
. Java i
s
a
n
algo
rithm i
m
pleme
n
tatio
n
lang
uag
e
and
Java vi
rtua
l
machi
ne max
i
mum hea
p memory i
s
51
2MB. Query
point and d
a
ta points’ di
stribution a
s
sh
own
in the Figure 7.
The ci
rcle ind
i
cate
s pre-co
mputed a
r
e
a
and a
r
row in
dicate
s the
directio
n of mo
vemen
t
of que
ry p
o
int
.
Add di
re
ctio
n con
s
traint
s
that mea
n
s e
x
clude
{d
p1,
dp8, d
p9, d
p
10, dp
11}
as
th
e
result. We
an
alyze p
e
rfo
r
m
ance fro
m
th
e num
ber
of t
r
aversal ve
rte
x
es a
nd the
executio
n tim
e
.
The re
sult
s are in Figure 8 and Figu
re 9.
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No
. 11, Novemb
er 201
3: 663
7 – 6644
6642
Figure 7. Que
r
y Point and Data Points’
Distri
bution in
Road
Network
Figure 8. The
Numbe
r
of T
r
aversal Ve
rtexes
Figure 9. Executio
n Time
Whe
n
k=2, for example, th
e experim
ent
al para
m
eters are sh
own in
Table 1, and
the results
are in Fig
u
re
10.
Table 1. Algo
rithm Perfo
r
m
ance Com
p
a
r
ison
whe
n
k=2
Name
Execution Time (
M
S)
Tempor
ar
y Node
Number
Result
Improved Island
125
22516
(dp3, 974
4.26)
(d
p7, 9787.76
)
Island
407
13849
(dp3, 854
6.77)
(d
p7, 9735.81
)
Figure 10. Th
e Re
sult wh
e
n
k=2
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
K Nearest Ne
ighbo
r Path Queri
e
s b
a
se
d on Ro
ad Networks (L
uli
n
Che
n
)
6643
In summ
ary, improve
d
Isla
nd algo
rithm
trav
erse
s fewer vertexe
s
t
han o
r
igin
al one a
n
d
more effe
ctive. Although the impr
oved
algorithm
cannot give o
p
timal solutio
n
, it has a h
i
gh
query pe
rformance and m
o
re suitable f
o
r
high
real
-time dema
ndin
g
scena
rio
s
.
5. Applicatio
n Example
The im
prove
d
Isla
nd al
gorithm ca
n b
e
applie
d
in th
e
ele
c
tric vehi
cle
cha
r
gi
ng
guida
nce
system
which
has hig
h
real
-time req
u
ire
m
ent.
No
w
comp
ared to th
e g
a
s
station,
e
l
ectri
c
vehi
cl
e po
we
r di
st
ribution
infra
s
tru
c
ture
resou
r
ces are sca
r
ce a
n
d
unevenly
di
stribute
d
. At
the same tim
e
, ch
argi
ng
station plan
ni
ng
research i
s
still in its infancy at
hom
e and abroad
[11]. It is li
kely that electri
c
vehi
cle in
use
pro
c
e
ss n
e
e
d
s to be re
charg
ed but couldn’t fi
nd the ch
argi
ng
station. On the one h
and
, a
perfe
ct b
a
ttery monitori
ng
techn
o
logy [1
2] is im
po
rta
n
t, on th
e ot
her ha
nd, the
ele
c
tri
c
vehi
cle
route
guid
a
n
c
e is
also very
ne
ce
ssa
ry. T
he gui
dan
ce
sy
st
em mu
st
prov
id
e
re
al-ti
m
e route tip
s
,
or wh
en the vehicl
e away from the loca
ti
on, the given path loss its
meanin
g
.
Figure 11. The Electri
c
Vehicl
e Ch
argi
ng Guid
e System
Whe
n
ele
c
tri
c
vehi
cle b
a
ttery is lo
we
r than the
wa
rning
value, t
he current
G
PS and
power inform
ation will be sent to
the background syst
em
. The background sy
st
em calculates the
path and
se
n
d
s it to the vehicl
e termin
al. And the
terminal g
u
ide
s
the vehicle b
y
voice pro
m
pts
to the n
eare
s
t charging
station. The
b
a
ckgroun
d
system
will
con
t
inue to m
oni
tor the ve
hicl
e,
whe
n
it devi
a
tes from th
e giv
en
drivi
ng route, sy
stem re
-cal
cul
a
tes th
e path
until the ve
hicle
rea
c
he
s the chargi
ng statio
n.
Electri
c
vehicle ch
argi
ng g
u
idan
ce
syst
em
is
k=1 ne
are
s
t neig
hbo
r que
ry probl
em. The
improve
d
Isla
nd alg
o
rithm’
s qu
ery p
e
rf
orma
nce
is shown
in
the
Figure
12. Here we assu
me
Island radiu
s
is 150
0 meters, usin
g the h
a
rd
wa
re environment a
s
de
scribe
d in 4.3
.
Figure 12. Th
e Perform
a
n
c
e whe
n
k=1
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No
. 11, Novemb
er 201
3: 663
7 – 6644
6644
As illust
rated
above, find
the nea
re
st chargi
ng
station in 3
0
KM
scope
uses l
e
ss than
300m
s. If electri
c
vehicl
e
’
s sp
eed is
60KM/h, t
he traveling di
stance of the vehicle in qu
ery
pro
c
e
ss
will b
e
less than 5
meters. So the offs
et is sm
all and meet the real
-time requireme
nt.
6. Conclusio
n
This pa
pe
r prop
oses a
n
improved Island al
go
rith
m. We take
the best d
a
ta point
estimate
an
d
heu
ri
stic
se
a
r
ch
meth
od,
effectivel
y re
duci
ng th
e traversal ve
rte
x
es. Be
side
s,
we
optimize th
e data structu
r
e. The
expe
ri
mental re
sult
s show th
at
the improved
Island al
go
rithm
make
s the q
uery pe
rform
ance more ef
fectivel
y and
can
return th
e nea
re
st nei
ghbo
r path
s
, is
suitabl
e for the high real
-time deman
d
i
ng route
g
u
i
dan
ce ap
plications. Thi
s
pape
r doe
sn’t
discu
ss the
p
r
e-com
puted
Island
radi
us and the al
g
o
r
ithm ba
sed
on stati
c
roa
d
netwo
rk usi
n
g
length a
s
th
e
road
pri
o
rity. The road
pri
o
rity in re
al life
sho
u
ld
also
take th
e d
egre
e
of cong
esti
on
and
roa
d
g
r
ade i
n
to a
ccount. Th
eref
ore, th
e research
emp
h
a
s
is in th
e fu
ture
will
be
the
improvem
ent of the Island
algorith
m
und
er dynami
c
n
e
twork, as
we
ll as the Islan
d
pre
-
comput
ed
radiu
s
dete
r
m
i
ning strategy
.
Referen
ces
[1]
Hu L, Sh
aha
bi
C, Bakiras S.
Spatia
l
Quer
y Integrit
y
w
i
th
Voron
o
i N
e
ig
h
bors.
Know
le
d
ge a
nd D
a
ta
Engi
neer
in
g IEEE Transactio
n
s on
. 20
13; 2
5
(4): 863-
87
6.
[2]
Guobi
n
Li, Ji
n
e
T
ang.
A
N
e
w K-n
e
i
gh
bo
r
Se
a
r
ch Alg
o
r
i
t
h
m
Ba
se
d o
n
Va
ri
ab
l
e
In
crem
en
ta
l D
y
nam
ic
Grid Divisi
o
n
. Comp
utation
a
l Intelli
genc
e
an
d
Desi
gn
(ISCID). Hangz
hou.
201
0; 2: 167-1
70.
[3]
Ya Sun. Desi
gn an
d Imple
m
entatio
n of Near
es
t Neig
h
bor Quer
y in
Spatia
l Net
w
or
k Databas
e
.
Co
mp
uter Scie
nce
. 200
8; 35(
3):73-7
5
.
[4]
Jingfe
ng Gu
o, Hanfe
ng
Liu,
Qian Ma. K
Near
est
Nei
g
h
bor Quer
ies
of Movin
g
Obje
cts Based
o
n
Net
w
orks.
C
o
m
p
u
t
e
r
En
gi
nee
ri
ng
. 200
8; 34
(3): 100-1
04.
[5]
Papa
dias D, Z
han
g J, Mamoulis N.
Query p
r
ocessi
ng in sp
atial n
e
tw
ork databas
e
. Proce
edi
ngs of the
29th Intern
atio
nal C
onfere
n
ce
on Ver
y
Lar
g
e
Data Bases (V
LDB). 200
3; 29
: 802-81
3.
[6]
Kola
hdo
uza
n
M, Shah
abi
C.
Voron
o
i-b
a
se
d
K ne
arest n
e
ig
hbor s
earc
h
for
spatia
l n
e
tw
ork data
bases
.
Procee
din
g
s of
the 3
0
th Inter
natio
nal
Co
nfe
r
ence
on V
e
r
y
Larg
e
D
a
ta Ba
ses (VLDB).
2
004;
30: 8
40-
851.
[7]
Hua
ng
X, S
i
m
onas
S.
T
h
e
Islan
d
s Ap
pro
a
c
h to
Near
est Nei
g
h
bor Q
u
eryin
g
i
n
Sp
ati
a
l N
e
tw
orks
.
Procee
din
g
of
the 9th Int
e
rna
t
iona
l S
y
mp
osi
u
m
on
Spati
a
l
and T
e
mpor
al
Data Bas
e
s (S
ST
D). 2005
:
73-9
0
.
[8]
W
ang H, Z
i
m
m
erman
n
R.
L
o
catio
n
-bas
ed
Query Proc
ess
i
ng
on M
o
vi
ng
Objects i
n
R
o
ad N
e
tw
orks
.
Procee
din
g
s of
the 30th Intern
ation
a
l Co
nfere
n
ce on Ver
y
La
rge Data Bas
e
s (VLDB). 200
7.
[9]
H
y
un
g Ju
C
h
o
,
Chi
n
W
a
n
Ch
ung.
A
n
efficie
n
t an
d sc
ala
b
l
e
a
ppr
oach
to
CNN
Quer
ies
in
a
Ro
a
d
Netw
ork
. Proceed
ings
of the 31th Inte
rn
atio
nal C
onfer
enc
e on Ver
y
L
a
rg
e Data Bas
e
s (VLDB). 200
5
:
865-
876.
[10] Jian
w
e
i
Li,
Yu
bin
Xu, Hon
g
Guo.
Me
mory
Organi
z
a
t
i
on
i
n
a
Re
al-ti
m
e
D
a
tabas
e B
a
se
d
on
R
ed-b
l
ack
T
r
ee Structure
. Intellig
ent Co
n
t
rol and Aut
o
mation. 20
04; 5: 397
1-39
74.
[11]
Han
w
u
L
uo, F
ang Li. A M
e
thod for El
e
c
tric V
ehicl
e O
w
n
e
rsh
i
p F
o
recast Cons
id
erin
g Differe
nt
Econom
ic F
a
ct
ors.
T
E
LKOMNIKA Indo
nesi
a
Jo
urna
l of E
l
ectrical
En
gin
eeri
n
g
.
2
0
1
3
; 11(4): 223
9-
224
6.
[12]
Lei
Lin, Y
u
a
n
K
a
i L
i
u, W
a
n
g
Pi
ng, F
a
n
g
Ho
ng
.
T
he Electric
Vehic
l
e L
i
thi
u
m
Batter
y
M
o
n
i
to
ring S
y
stem.
T
E
LKOMNIKA Indon
esi
a
Jour
nal of Electric
al
Engin
eeri
n
g
. 2
013; 11(
4): 224
7-22
52
.
Evaluation Warning : The document was created with Spire.PDF for Python.