TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol. 12, No. 12, Decembe r   2014, pp. 81 7 5  ~ 819 2   DOI: 10.115 9 1 /telkomni ka. v 12i12.63 32          8175     Re cei v ed Ma y 26, 201 4; Revi sed Septe m ber  28, 201 4; Acce pted  Octob e r 15, 2 014   The B + -tree-based Method for Nearest Neighbor  Queries in Traffic Simulation Systems      Zhu Song* 1 , Zhiguang Qi n 2 , Wei w ei  Deng 3 , Yuping Zhao 4   Schoo l of Com puter Scie nce  & Engin eeri ng,  Universit y  of E l ectron ic Scien c e and T e chno log y  of Ch in a,  Che ngd u, Chi n *Corres p o ndi n g  author, e-ma i l : toni11 0@1 6 3 . com 1 , zgqin@ uestc.edu.c n 2 , uestcde ng ww@hotmai l .com 3 z y p uestc@ live. com 4       A b st r a ct   Extensive us ed traffic sim u lation system s  are helpfu l in planning and contr o lling the traffic system.   In traffic sim u lation syst em s, the state  of  each v e hicl e is affected  by  that of  nearby  vehic l es, called  nei ghb ors. Ne arest nei gh bor  (NN) qu eries,  w h ich are  mu lti 1-di mensi o n a l an d hi gh ly c oncurr ent, larg el y   deter m i ne the  perfor m ance of  traffic sim u lation system s.  M a jority of existing traffic sim u lation system s use  Link ed l i st b a s ed  meth ods  to process  N N  qu eries.  A l thou gh s i mpl e   and  effective t hey ar e, existi n g   meth ods  are  n e ither sc ala b l e  nor effici ent. In this  p a p e r, w e  pro pos e a B + -tree-base d   meth od to  i m pr ove   the effici ency  o f  NN q ueri e s b y  borrow i n g  i d e a s fro m   me thods used in databases. In   particular, we create a  linke loca l B+ -tree, cal l ed  L L B+ -tree, w h ic h is  a v a ri atio n of Ori g in al  B + -tree, to  mai n tain th e i n d e of  nei ghb ors of e a ch ve hicl e. W e  als o  b u il d a  math e m atic al  mo de l to o p ti mi z e  the  par a m e t er setting  of L L B+ - tree accord ing  to multi p l e  par ameters for lan e s and ve hi cl e s . Our theoretical an alysis sh ow s that the time   compl e xity of   the  meth od  is  O(log N ) u n d e r  the  a ssu mpti on  of ra ndo ml y distri butio of veh i cles.  Our  simulati on res u lts show  that LLB+ - tree ca n outperfor m   Link ed list an d  Origina l  B+ -tree by 64: 2%  an d   12:8%, resp ect i vely.     Ke y w ords   Copy right  ©  2014 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  The traffic si mulation sy stem is a mathem atical modelin g of transportatio n  system throug h the appli c ation of  compute r  software, which leads to b e tter unde rst andin g , plani ng,  desi gning  an d optimizi ng  the traffic  system. N earest neighb or  (NN) q u e r ie s pl ay an impo rt ant  role in t r af f i c simulat i o n  sy st em s,  bec au se ea ch ve hi cle ne ed s to find nea rby vehicl es, calle neigh bors, an d determi ne its state  a c cording to neig h bors’ state s .   It is difficult t o  imp r ove th e pe rform a n c e of  NN  que ries be cau s e NN  qu erie s h a ve  the  followin g  pro pertie s : 1) M u lti 1-dime nsi onal case s: i f  we con s id e r  a lane a s   a 1-dim e n s io nal  ca se, then a  road  with mul t iple lane s ca n be seen a s  infrequ ent m u lti 1-dime nsi onal cases. 2 )   High  con c u r rency: the mo re vehi cle s  e x ist in a  sim u lation, the l a rge r  nu mbe r  of NN que ries  oc cur in e a c h  cy cle.   Exis ting  traffic  s i mulation sys tems Paramic s   [16], Viss im [17], MITSim [18], SUMO [19]  etc, adopt Li nke d  list-b a sed method s to pro c e ss  NN que rie s . Such meth od s, which a r e very  easy to  cre a te and m a int a in, index th e se quen ce  of vehicle s  i n  ea ch lan e . Ho wever, th ose   method are  not  scalabl e ,  becau se th ey nee d to  t r averse  the  Linked li st to  find a  vehi cle.  Videlicet, the time compl e xity of such me thods i s   O ( N ).  In this  pap er,  we  propo se   a B+-tre e-b a s ed  metho d calle d L L B+-tree  (lin ke d lo cal B + - tr e e )  b y  bo rr ow in g id ea s fro m  th os e me th o d s  for  1 o r   2 - d i me ns io n a l NN  qu er ie s in  d a t ab as es In   particula r, we  firstly index  all vehicle s  in  each road  in a same di rectio n, and impleme n t the  bidire ction a orde r of l eaf  node s of  Ori g inal B + -tree.  We th en m a intain lin ks  of neigh bo rs  for  each vehicle  in the same  lane. We also build  a m a thematical model to optimize pa ram e ters  setting for L L B+- tre e . Such a mod e l  cacul a tes t he min value of the expect que ry length   according to  numbe rs of lanes a nd vehi cle s .   Our th eoretical analy s is  shows that th e time  compl e xity of the LLB+-tree  m e thod i s   O (log N ). The  optimal avera ge qu ery len g t h can fu rt he r improve the  perfo rman ce  of the metho d Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 12, Decem ber 20 14 :  8175 – 81 92   8176 Our  sim u lat i o n  re sult sho w  t hat  L L B + -t ree  ca o u tp erform  Lin k e d  list a nd  Ori g inal B + -tree  by  64 . 2% and 1 2 . 8%, resp ect i vely.  Overall, the  main prope rties of  LLB +-tree are li sted  as follo ws:   a)  LLB+-tree   su pport s  m u ltipl e  qu ery type s, inclu d ing  ra nge  que ry a n d  reverse  ne a r est  neigh bor (RNN)  qu ery.   b)  LLB+-tree i s  efficient in NN que rie s  in traffic simulation sy stems. The time   compl e xity of  LLB+-tree b a s ed meth od i s   O (l og N ).   c)  The mainte n ance overh e ad of LLB+-tree is  a c cept able, whi c h i s  simil a r to that of  the Origin al B+-tree.   The  re st of th e pap er is  organi zed  as fo llows. Sectio n  II gives a n  o v erview  of th e rel a ted   work. Section III defines NN qu eries in traffic  si mulation  syst ems and  i n tr oduces the  data  stru cture of LLB+-tree. S e cti on IV pro poses alg o rit h ms for ma n aging LLB +-t r ee. Section V  analyzes the  time compl e xity of the method and o p timi ze s pa ramete rs. Sectio n VI evaluates th perfo rman ce  of LLB +-tre e  thro ugh  b o th expe rim ents  and  st atistical  anal ysis. Se ction  VII  con c lu de s this pap er.       2. Relativ e   Work   In this  se ctio n, we fi rstly  overview met hod s for NN que rie s  in  databa se s.  We th en  descri be met hod s for NN queri e s in traffic simulatio n  system s.     2.1. NN Qu er ies in Data b ases   NN que rie s also kn ow as  proximity  qu erie s,  simil a ri ty querie s o r   clo s e s t point  queri e s,   can b e  divide d into two cat egori e s: the q uery for stati c  and moving  obje c ts.   NN q ueri e s f o r stati c  obje c ts u s e ind e x stru cture s , inclu d ing B-tr ee, B+-tree, quad -tre e   and R-tre e . Rou s sop oulo s  et al. [3] propo se  an in fluential met hod for findi ng the K-ne are s neigh bors  (KNN) u s ing  R-tree; Haibo  Hu et al.  devise EXO-tre e to sp eed  up  NN qu erie s [6]; HV   Jag adi sh et  al. [7] pro p o s a B+-tre e  ba sed  meth od, for K N sea r ch in  a  high-dimen s i onal  spa c e; G R  Hj altaso n et al. [2] devise a g eneral  frame w ork an d alg o rithm s  for p e rformi ng sea r ch  based on di stance; a ran domized alg o rithm for  co mputing ap proximate nea rest neig hbo r is  prop osed by  Arya et al. [8]. Ling Hu  et al. [9 ] prop o s e a  ro ad n e t work KNN q uery verifi cati on  techni que to  prove the int egrity of the query resu lt. Seidl et al. [10] improve a  KNN multi-st e p   algorith m  whi c h is g uarant eed to pro d u c e the minimu m numbe r of can d idate s .   NN  que rie s  f o r movin g  o b j ects mainly  use  si mil a r i ndex st ru ctures, in cludi ng  B+-tree  and TP R-t r ee . Kollios  et al . [1] gene rali ze m o ving o b j ects in a  pla ne, the m o ve ments  of whi c h   are rest ricte d  to a numbe of line se gme n ts, as a  “1.5 -dime n si onal ” ca se [11]. Je nse n  et al. [12]  develop alg o rithm s  fo NN q ueri e s wh ose  pe rform a nce  is bette than TP R-tre e . Tao  et al. [ 1 3 ]   solve the ove r hea d proble m s in  continu ous n e a r e s t neighb or (CNN) que rie s . An algorith m  wh i c h   requi re s o n ly one  data s et  lookup to  d e liver a  co m p lete p r edi cti v e re sult for  CNN q u e r ie s, is   devise d  by  L ee et  al. [14].  Xie et  al. [15 ]  prov id es a  solution  whi c h  su ppo rts different  shape s of  comm only-u s ed impreci s e  regio n s u s in u -bi s e c tor.  Benetis et al.   [11] prop ose  algorithm s f o respon ding  RNN a nd NN q uerie s for mo ving points in  plane.     2.2. NN Qu er ies in Traffic  Simulation Sy stems  NN q ueri e s i n  t r af f i c simu lat i on sy st em s ai m to find  at least 2 neighb ors. Wh en the   vehicle  ha s n o  adja c e n t la ne, it only ne ed to find  2 n e ighb ors in th e local lan e Whe n  the ve hicle   has o ne adj a c ent lan e , it need s to find  4 neighb or s:  2 in the local lane an d 2  in the adjacen lane. When t he vehi cle h a s b o th left and ri ght  adj ace n t lane s,  it need s to find ad ditional  2  neigh bors in the other a d ja cent lan e Although the r e has mi nor  differen c e in t he defin ition  of neighb ors i n  different si mulation  system s (e.g. ,  VISSIM [17] do not co nsi der the  n eare s t followin g  vehicl e in the local la ne a s  a   neigh bor), ex isting traffic  simulatio n   system ad opt  simila r line a r method (Li n ke d list - ba sed  method s) for  NN qu erie s.  Parami cs [16 ], a famou s   software  which supp orts a  simulatio n  ov er  1   million vehi cl es,  store veh i cle s   cu rre ntly in lin ear  qu eue s, rega rdl e ss of lane; While in MIT S im  [18], a simul a tor develo ped  by MIT, vehicle s  a r al so  store d  in  Lin k ed list in  ea ch lane. S U M O   [19], an ope n so urce, hi ghly porta ble ,  micro s c opi c an d contin uou s road traffic sim u lati on   packa ge, ind e xes vehi cle s  in each la ne  in a linear q u eue.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     The B + -tree - b a se d Method  for Nea r e s t Neighb or Qu eri e s in Traffic Sim u lation… (Zhu Song 8177 Those Lin k e d  list-ba se d m e thod s, very che ap in  cre a ting and m a intaining, a r e  suitable  to s i mulate spars e  traffic   c o n d ition s . Howeve r, such  method s a r e not scal abl e be cau s e th ey  need  to trave r se  the  Lin k e d  list to  search a ve hicl e. V i delicet, the  more  vehi cle s  in  a  simul a tion,  the worse p e rforman c e of those method s.      3. Problem Statement a n d Data Struc t ures   In this  se ctio n, we  firstly analyze the   appli c ability  of tradition al  method s fo 1 an d 2 - dimen s ion a l NN qu eri e s i n  traffic simul a tion system s. We then p r opo se forma l  descriptio n s of  s u c h   NN  qu er ie s .  At las t, w e  in tr od uc e   th e  d a t stru cture  of B + -t ree, do uble  Li nke d  li st, LL B+- tree and  com pare the d e tai l s of them.    3.1. Applicabilit y  Anal y s is  We use  an  example  to  explain why tradi tional  m e thod s for 1  or  2-dimen s ional  NN  queri e s a r e n o t suitable for traffic simula tion system s.           Figure 1. 8 vehicle s  in a three-la ne road  segm ent       Figure 1 is a  segm ent of a  road. Th ere  are 8  vehi cle s  dist ribute d  in 3 lane s: vehicle s   and  in lane  1; vehicle s   C an in lane 2; veh i cle s   F an in lan e  3 .  When vehi cl laun ch s a NN que ry, call ed the initiator, it  needs t o  find 6 neig hbors: the ne are s t leadin g  an d   fo llo w i ng  ve h i c l es   a nd  in the  lo cal l ane  (lan e 2 ) and   in th e left adj acen t lane  (La ne  1);   and  in th e right adja c e n t lane (lan e 3).   If we ado pt a  method fo r 1 - dime nsi onal  NN  que rie s , we  con s id er  each lan e  a s   a linea spa c e. In  o r d e r to  find th e  nea re st vehi cle s   in  ea ch  l ane,  we  crea te virtual i n itiators  D   an D ′′   with the sam e  displ a ceme nt of  se pa rately in the  left and right  adjacent lan e s. Thu s , th e   method find t he 2 ne arest  vehicle s  of  D D   and  D ′′   in  the local, left  adja c ent an d  right adj acent  lane s, re sp ectively. Howev e r, the s e ve h i cle s  may  not  be the  corre c t nei ghbo rs. The  2 n eare s vehicle s  of  D ′′   in lane 3 are  and  F , whil e the neigh bo rs a r an H If we use a m e thod for 2 - di mensi onal  NN que rie s , we  con s ide r  a whole road a s   a plane.   Such a meth od ca n find the 6 nea re st vehicle s  of the initiator  D . While the s vehicle s  may  not  be the  n e igh bors  either.  As  sho w n  in   Fi gure  1, th nearest  vehi cles  are  A B C F a nd  H Vehicle  is  m o r e   c l os e r  to   than vehi cle  E , but  is not a corre c t neigh bor.     3.2. Problem Statemen We de note  as the set of  all vehicle s  in a  L -lan es road,    is the  th vehicle. We  can   further u s e two prope rtie s, the displa ceme nt of a  vehicle in th e road  and the lane   whe r e the ve hicle lo cate   to describ e e a ch vehi cle.  That is,    can be  de scribed   in a tuple  . To find nei g hbors of  , we divide  into two  s e ts acc o rding t o  the   displ a cement   . One is the set of leadin g  vehicle s ; The othe r is  the set of fo llowing  vehi cles:  . The  n e ighb ors of  vi  in clu de th nearest lea d i ng and follo wi ng vehicl es in  the local an d  two adja c ent  lanes.   That is, a NN query contain s  followi ng 3  step s:  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 12, Decem ber 20 14 :  8175 – 81 92   8178 1)  We find th e neig hbo rs  of the vehicl e  in t he lo cal l ane. The  nea rest l eadin g  vehicl e of   vi  in the local lane is th e element with the minimize    in the set  : the vehicl e   . The nearest following vehicl e of  vi  in the local l ane is the el ement with t h e   maximize    of  the set  : the vehicl 2) If there exists a left adj ace n t lane, we  find the n e ighb ors in that lane. The  neare s t   leadin g  vehi cle of    in the   left adja c ent  lane i s  th e el ement  with t he mini mize    in the set  : the vehicle  . The nearest following ve hicle of  vi  in  the left adjacent  lane is the el ement with th e maximize    of the set  : th e vehicle  1).  3) If there exi s ts a  rig h t ad jace nt lane,  we  find th e n e ighb ors in t hat lane. T h e  nea re st  leadin g  vehicle of    in the right adja c e n t lane i s  the  element  with  the minimi ze    in the set  : the vehicle  . The ne are s followin g  vehi cle of  vi  i n  the right a d jacent  lane is the el ement with th e maximize    of the set  : th e vehicle  1).    3.3. Data S t r u ctur e of LL B+-tr ee   The LLB +-tre e  (Lin ke d local B+-tree), a  variati on of B + - tree, is a  combinatio n of  B+-tre e   and Lin k e d  list.    Linked li st-b a s ed  metho d s index ve hicl es i n  e a ch la ne, while B + -tree b a sed  m e thod index vehi cle s  in  ea ch  ro a d . Using  an   example  of a  roa d   seg m e n t sh own in   Figure 1,  we   can   build th ree  Li nke d  li sts. As sh own in  Fig u re  2, ea ch  Li nke d  li st sto r es ve hicl es  o r de rly in a  sa me   lane. Fig u re  3 tells the  ma pping  sch e m e  of L L B+-tre e u s ing  the  same  roa d   se gment. Acco rding  to the  displacement  of vehi cle s  in  the  ro ad, we  can  m ap the  di strib u tion of  the  8  vehicl es into  a   1-dim e n s iona l queue:            Figure 2. An example of d ouble Li nke d   list  Fi gure 3. Mapping vehi cle s  into 1-di me nsio nal  c o or d i na te      LLB+-tree  m a inly modifie s  the  structu r es  of  internal  nod es  and  l eaf no de s. In intern al  node s, we i m pleme n t the bidirectio n a l ord e r of  e a ch  node to  facilitate mult i query type s. In   particula r, we  create 2 p o i n ters to lin k t he previo us  and next inte rnal no de s, denote a s     and  , re spe c tively. Each i n ternal  no de  ha   k e y va lu es  an d     + 1 children.  The   stru cture of  e a ch  internal  node  is pri n ted b e lo w, wh ere    de note s  the  i th k e value,  P i   po in ts   the  i th c h ild:         In leaf no de s, we mainta in the thread  of  the nei g hbors  of ea ch entity (veh icle). In   particula r, we  create 2 poi nters in e a ch  entity to  link the vehicle’s neighbo rs in the local lan e denote  a s     an d   . T h us , ea c h  e n t ity has  4 do ma ins :  th e   i th key v a lue  , the   vehicle  data   , neig hbo rs    a nd  . Each  le af nod e i s  fo rmed  by entiti e and   two poi nters:    and    , which  point to the p r evious  and  n e xt leaf node s. The  stru ctu r e   of each le af node is of the form:   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     The B + -tree - b a se d Method  for Nea r e s t Neighb or Qu eri e s in Traffic Sim u lation… (Zhu Song 8179     Usi ng th sample  of th e di stributio n of 8  veh i cle s , the  1 - dime nsi onal  que ue  , we build a L L B+-t ree, sho w n in Figu re  4.        Figure 4. An example of a LLB+-tree       As a combi n a t ion of B+-tre e and Lin k ed  list,  LLB+-tre e  inherit s a lot of advantages: data  points  are  sto r ed o n ly at the leaf  nod es.  These leaf n ode s are simi lar to the first (ba s e )  level  of  an index. Inte rnal n ode s of  B+-tre e corresp ond to the  other level s   of a multileve l index [20]. B+ - tree imple m e n tation retai n s the log a rith mic cost p r op erties fo r op e r ation s  by ke y, but gains the  advantag e of requi ring at  most 1 a c ce ss to  sati sfy  a next operation [21]. Ju st like Lin k ed li st,  LLB+-tree  al so maintain s t he thread s of  the nea re st l eadin g  an d n eare s t follo wi ng nei ghb ors o f   each vehicl e in the local la ne, whi c faci litate NN qu eries in that lan e     4. Algorithm s Optimiza tion  In this sectio n ,  we adopt the repla c em en t of  vehicle in the road a s  its sea r ch key  value  in a LLB+-t r ee. we prop ose three sub-al go rithms for the managem ent  of the LLB+-tree,  inclu d ing  sea r chi ng, inserti ng and d e leti ng.    4.1. Searchi ng  This sub-algo rithm  sea r che s  n e igh bors  o f  a v ehi cle i n   the lo cal l ane  and  adj acent  lane s.  The se arch key value of vehicl i   is  the lane of vehicle  i   is  . In LL B+-tree, data points a r store d  o n ly at  leaf n ode s. T hus,  we  u s a fun c tion   to  impleme n t th e searchi n g   pro c e s s from  root n ode to  the obje c tive  leaf  nod e. T he sub-algo rit h m in clude s t w NN  que ri es:  the NN que ri es in th e adj ace n t lane   and in the lo cal lane  . Neig hbors in  the local lan e s indi cate the nea re st leading vehi cle     and the followin g vehicle     and    are respectively the  nearest l eadi ng an follo wing vehi cle s  i n  the a d ja ce nt  lane.   The su b-al go rithm mainly contai ns follo wing  two  step s: 1) It searches the leaf n ode and  find the neig h bors of a veh i cle in the l o cal lane s;  2) It sea r che s  rel a ted leaf no d e s a nd find t he  neigh bors of  a vehicl e in  the adja c e n t lane if  nee d ed. The p s e udo-co de of  the algo rithm  is  s h ow n  in  Algo r i th m 1 .     Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 12, Decem ber 20 14 :  8175 – 81 92   8180       4.2. Insertin g       Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     The B + -tree - b a se d Method  for Nea r e s t Neighb or Qu eri e s in Traffic Sim u lation… (Zhu Song 8181 This sub-algorithm illustrates the procedure for  inserting a reco rd (vehicle) with  a search  field value    in LLB+-tree. A l gorithm 2  gives a d e taile d  pse udo -code  of the sub a l gorithm.  We  denote    and    as the point ers    and    of the nea re s t   followin g  and  leadin g  vehicl es of  i , res pec tively.  We can furth e r divide this  sub - alg o rithm  into two part s : 1) It create  entry of vehicle  in c o rrec leaf node a n d  update s  relat i ve pointers; 2) It update s  internal n ode s to maintain the right  stru cture of LLB+-t r ee. Wh en a nod e is full it w ill split and when the  parent no de  also b e  full, the  splitting can p r opa gate all  way up to cre a te a new lev e l for LLB+-tree.    4.3. Deleting   This al gorithm illustrates  deleting a  record with a  search field v a lue    from a LLB+- tree. When  d e leting a n  e n try, we  sh ould  alway s   remo ve it from the   leaf level. If the ent ry is i n   an  internal n ode,  we mu st also  remove it fro m  there.   The alg o rith m contai ns th ree p a rts: 1 )   It sear che s  in ternal n ode recursively to find the   path a c cordi ng to th se arch field  val ue  Ki Whe n  the  sea r ch f i eld valu e o c cur in  an  int e rnal  node,  we  use  a left (o rig h t) ent ry to repla c e it;  2 )  It delete s  the  entry of  the  vehicl e in  co rrect   leaf node  a nd upd ates  relative poi nters; 3 )  It update s  the l eaf nod e by mergi ng an d   redi strib u ting  sibling  nod es  when th e r e exist s  no de und erflo w ; 4) Wh en t he me rge a nd  redi strib u te in  leaf no de s l ead s to  an u nderflo w   of a  intern al n o d e , the inte rna l  nod e will  al so   merg e a nd  re distrib u te to   maintain  the  stru cture  of  the L L B+-tre e .  We  give th e  pseud o-cod e  of  the algorith m  in Algorithm 3 .               5. Param e ter s  Optim i za tion  In this se ctio n, we firstly analyze those par amete r s that effect on the hit rate  of NN  queri e s.  We t hen a nalyze  the time cost  of  LLB+-tre e  based m e th od an d buil d   a mathem atical  model to opti m ize the no d e  size of the LLB+-tree.     5.1. Hit Ra te  Analy s is  In a LLB +-t r e e , data p o inte rs  are sto r e d   in  leaf n ode s.  For  better un derstandi ng,  we  call  vehicle s  in a leaf node a s  a  “platoon ”. Un der the  a s su mption of ran domly distri b u tion of vehicl es,  the perfo rma n ce, the  exp e ct qu ery len g th  ϵ   of a  NN qu ery is  d e termin ed by  the hit rate  of a   query  in a   platoon. F u rt her, the  hit ra te  is i n fluen ced  by the  averag e a m oun t of vehicle s  i n  a   platoon  q . Th us, we  comp ute the optimi z ed val ue of  to minimi ze  the expe ct q uery le ngth  ϵ   of a  NN q uery .   To cal c ul ate  P , we assu m e  that there  are  vehi cle s  ra ndo mly d i stribute d  in  lane s.  We ca n use a  matrix  to de scri be  po ssi ble  dist ribution s  of  vehicle s . Ea ch ele m ent i n  t he  matrix is a po ssi ble po sitio n  for a vehicl e. In example,  a ij   is the  i th positio n in the  j th lane.  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 12, Decem ber 20 14 :  8175 – 81 92   8182     Whe n   we  qu ery nei ghb ors of ve hicl a ij   in  adja c e n t lane s, the r exist two  different   situation s  whi l e the road h a s  at least 3 la nes.   The first situ a t ion is, vehicl a ij   is in an edge lan e  of a road (th e    or     whe n   ). It need s to qu ery neighb ors  in the onl a d jacent lan e , that are  vehicle s  in   In this  c a s e we calculate  P A , the possi bility of finding a neigh bo r in the adja c e n t lane of  vehicle  a ij   in the platoon.  We can co m pute the  possible di strib u tions of all oth e   1 vehi cle s   ( e xc ept vehicle  a ij   in the edge lane ) tha t  are not distributed in the adja c ent lane The total  po ssible  di stributi ons of  q 1 veh i c l es  is   . T h us , we   c a n ca lc u l a t P A   u s i ng the  following formula:        The second  situation i s , vehicl aij  is i n  a mid lan e   (the lan e  1  < j <  L  when  L >   2). In  this  case, vehic l a ij   ha s both left an d right a d ja cent lane s. T herefo r e,  we  need to q u er neigh bors in  two a d ja cent lane s,  that are ve hicle s  in    and  We den ote  P B   as th e p r obability of fi nding  neig h b o rs of vehi cl a ij   i n  b o th  adja c ent  lane s. To cal c ulate  P B , we  also define  P B the probability of all o t her    1 ve hicle s  that are not  distrib u ted in  those adja c ent lanes. When we d o  not  con s ide r  distributio ns of  vehicles in  one   adja c ent la n e , The di stri bution s  of v ehicl es  exist  in an other  adja c ent la n e  is:  Acco rdi ng to prin ciple of in clu s ion - excl u s ion,  the ge n e ral form of  which i s  sh own  as follow:         P B   can be given by excludi ng t he overla p distrib u tion       Thus,  we can  compute  PB  as  follow:        In gene ral,  we ca n con c lu de the hit  rate   of a NN q u ery in a d ja ce nt lane s in 3   ca se s: 1)   Whe n  the ro ad ha s only 1 lane, vehicl es do n’t hav e to query n e ighb ors in a d jacent lane s. 2)  Whe n  the ro ad has 2 lan e s, vehicle s   only hav e to query neigh bors in one  adja c ent lane . 3)   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     The B + -tree - b a se d Method  for Nea r e s t Neighb or Qu eri e s in Traffic Sim u lation… (Zhu Song 8183 Whe n  the ro ad has mo re  than 2 lanes, we nee d to  con s ide r  two situatio ns: vehicles in edg e   lane s and in  mid lane s. We list the form ula of  as  follow:         We  also  sum m ari s e th e re lationship  am ong th e hit  ra te  P , avera g e  numb e r of v ehicl es  in a pl atoon   and numb e r of  lane L which i s   sh own  in Fig u re  5.  The o b servati on  sho w s tha t  in   comm on ro a d s condition s, a road with  L lanes 1  < L    10, The rate of converge nce of  is   diminishing  with the incre a s ing of  L     Figure 5. The  relation ship  among  L a nd  P       5.2. Time Cost An aly s is   Being a varia t ion of B+-tre e, we ca n find vehicle  in LLB+-tree sp endin g   O (lo g z  N ) time,  whe r is t he num be r o f  vehicle s  in  the roa d i s  the minimi ze numb e of child ren i n  e a ch  internal n ode.    Whe n  que ryi ng neig hbo rs of vehicle s   in the local la ne, we  can  di rectly obtai n them by  pointers    and  . That is, we can find nei ghbo rs of ve hicle  in the local lane  also in  O (log z  N ) time.  Whe n  que rying neig hbo rs of vehicle  in the adja c e n t lanes, we use the exp e c t que ry  length  ϵ   to  m easure th e ef ficien cy of the que ry. Such  a qu ery se arch nei ghb o r s by traversi ng all  vehicle s  in e a c h pl atoon. T he expe ct qu ery length  of finding a vehi cle in  plato on by traversi ng  is   . The exp e c t que ry len g th of findin g  th e obje c t n e ig hbor in the  lo cal pl atoon  is:    and  in   the next pl ato on i s  . We  can  summ ari z the expe ct query  l ength   ϵ   of fin d ing   the obje c t vehicle in the  k th platoon i s       The nu mbe r   of leaf nod es (platoo n s) in  a LLB +-tree  can  be exp r e ss  by  . We  can  descri be the  expect qu ery length  ϵ   of fin d ing nei ghbo rs in all platoo n as follo w:        We can si mpl i fy the formula usin g following method s:     Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 12, Decem ber 20 14 :  8175 – 81 92   8184     By using geo metric  se ries,  we ca n find:        Thus, the exp e ct que ry len g th  ϵ   ca n be  simplified a s  follow:         For a ce rtain road,   i s  a consta nt,  and   is  rapi co nverge nce to  1  with the  in cre a si ng    of the nu mbe r  of vehi cle s   in the pl atoo q . Fo r a  ce rtain  L , we can  get an accepta b le  with  limited  q . Therefo r e,  is also co nsi d ered a s  a consta nt in this ca se. Thu s , the limitation   , and we can  also  cal c ulate  the limitation of  ϵ       As a  re sult,  we can  also fin d  the  neig hbo r of ve hicl i   i n  the  adja c e n t  lane i n  lo g z  N  time,  unde r the assumptio n  of randomly di stribution  of vehicle s . The rel a tionship am ong the num ber  of lane L , ex pect  (ave rag e )  n u mbe r   of vehicl es in  on e plato on  a nd the  expe ct  que ry le ngth  of  finding nei gh bors in the a d jacent lane ϵ   with an e n ough la rge  (we a dapt  = 100 0 in th is   ca se) i s   sho w n i n  Fi gu re  6. T he  cu rve called   skyli ne i s   a lin con n e c ting  e v ery poi nts, t he  minimum val ue of  ϵ   of all  curve s , sho w s the optim al  c hoi ce a nd th e variation tre nd of  with t h increa sing n u m ber of lan e L     Figure 6. The  relation ship  among  L a nd  ϵ       We al so anal yze the impa ct  of the number of vehicle s   N , our rese arch sh ows that there   exists th re sh old valu es of   fo cert ain p a ir  of a m ount of  lan e a nd  averag e a m ou n t  of  vehicle s  in a platoon  q . When  is la rg er than the threshold value ,  the expect query length  ϵ   for  Evaluation Warning : The document was created with Spire.PDF for Python.