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 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 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 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 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 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 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  colle ction of a larg e numb e r of  node s an d ro ad  segm ents.  Road n ode 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 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 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 into a direct ed graph i n  memory. Fi gure  sho w 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  set of ed ge 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 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 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 distan ce s to  qp usin (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 qp .e , put  (dp, d(qp,d p ))  int o   Q dp   and p u (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 v x . If  v x  ha alread y existed i n   Q v  and   d ( qp, v x )  i s   small e 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 of the que ry  points  and  data poi nts,  whi c h me an 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 dp  may  also be the  nea rest on e to th 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 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 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 ,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 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 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 cont ains the n e a r es 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 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 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 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 and  Java vi rtua 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 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 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 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 comp ared to th e g a 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 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 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 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 Li, Ji n e  T ang.  N e w K-n e i gh bo 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 an 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 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 on  Spati a 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.