I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute r  E ng in ee ring   ( I J E CE )   Vo l.   9 ,   No .   4 ,  A u g u s t   201 9 ,   p p .   2 5 5 6 ~ 2 5 6 3   I SS N:  2 0 8 8 - 8708 ,  DOI : 1 0 . 1 1 5 9 1 / i j ec e . v9 i 4 . p p 2 5 5 6 - 2563          2556       J o ur na l ho m ep a g e :  h ttp : //ia e s co r e . co m/ jo u r n a ls /in d ex . p h p / I JE C E   M o bile  l o ca tion  i ndex ing   b a sed  o n  s y nthet ic  m o v ing   o bject s       T hu   T hu   Z a n ,  Sa ba i P hy u   Un iv e rsi t y   o f   Co m p u ter S t u d ies ,   M y a n m a r       Art icle  I nfo     AB ST RAC T   A r ticle  his to r y:   R ec eiv ed   J u n   20 ,  201 8   R ev i s ed   Dec   2 0 ,   2 0 1 8   A cc ep ted   Mar   4 ,   2 0 1 9       T o d a y ,   th e   n u m b e r  o f   r e se a r c h e s  b a se d   o n   th e   d a ta  th e y   m o v e   k n o w n   a s   m o b il e   o b jec ts  in d e x in g   c a m e   o u t  f ro m   th e   trad it io n a l  sta ti c   o n e .   T h e re   a re   so m e   in d e x in g   a p p ro a c h e s  to   h a n d le  th e   c o m p li c a ted   m o v in g   p o siti o n s.  O n e   o f   th e   su it a b le  id e a s  is  p re - o rd e rin g   th e se   o b jec ts  b e f o re   b u il d in g   in d e x   stru c tu re .   In   t h is  p a p e r,   a   stru c tu r e ,   a   p re so rted - n e a re st i n d e x   tree   a lg o rit h m   is   p ro p o se d   th a t  a ll o w e d   m a in tain i n g ,   u p d a ti n g ,   a n d   ra n g e   q u e ry i n g   m o b il e   o b jec ts  w it h in   t h e   d e sire d   p e rio d .   Be sid e s,  it   g iv e s  th e   a d v a n tag e   o f   a n   in d e x   stru c tu re   to   e a sy   d a ta  a c c e ss   a n d   f a st  q u e r y   a lo n g   w it h   th e   re tri e v i n g   n e a re st   lo c a ti o n s  f ro m   a   lo c a ti o n   p o in t  in   th e   in d e x   stru c tu re .   A   s y n th e ti c   m o b il e   p o siti o n   d a tas e t  is  a lso   p ro p o se d   f o r  p e r f o r m a n c e   e v a lu a ti o n   so   th a t  it   is  f r e e   f ro m   lo c a ti o n   p riv a c y   a n d   c o n f id e n ti a li ty .   T h e   d e tail  e x p e ri m e n tal   re su lt s  a re   d isc u ss e d   t o g e th e r  w it h   th e   p e rf o rm a n c e   e v a lu a ti o n   o f   KD tree - b a se d   in d e x   stru c tu re .   B o th   a p p ro a c h e s  a re   sim il a rl y   e ff icie n t  in   ra n g e   se a rc h in g .   Ho w e v e r,   th e   p ro p o se d   a p p ro a c h   is  e sp e c ial l y   m u c h   m o re   s a v e   ti m e   f o r  th e   n e a re st n e ig h b o r  se a rc h   w it h i n   a   r a n g e   th a n   KD   tree - b a se d   c a lcu lati o n .   K ey w o r d s :   I n d ex i n g   M o b ile  lo ca tio n s   M o v in g   o b j ec t   N ea r est n ei g h b o r   P r eso r tin g   R an g e  q u er ies   Co p y rig h t  ©   2 0 1 9   In stit u te o f  A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e .    Al l  rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   T h u   T h u   Z a n ,   Un i v er s it y   o f   C o m p u ter   Stu d i es,    No . 1 2 9 ,   Z e w a k a  Ho s te l,  Hlain g   C o m p u s ,   Ya n g o n ,   M y a n m ar .   E m ail: t h u th u za n @ u cs y . ed u . m m       1.   I NT RO D UCT I O N   W ith   ad v a n ce s   i n   lo ca tio n - b a s ed   s er v ices  ( L B Ss ) ,   m o b ile  d ev ices  a n d   telec o m m u n icat i o n   s y s te m s   ar e  th e  v ital  s u p p o r t  f o r   th e  p o s itio n i n g   a n d   tr ac k in g   o f   m o v in g   m o b ile  o b j ec ts   [ 1 ] .   B esid es,  th e  in cr ea s i n g   n u m b er s   o f   m o b ile  u s er s   ar e  a lr ea d y   e m er g ed   alo n g   w it h   th e   i m p r o v e m e n t  o f   n e w   tech n o l o g ies.  So ,   u s i n g   th e   m o b ile   p h o n e  i s   t h e  m ai n   f u n c tio n   o n   a  d ail y   r eq u ir e m e n t   w i th   t h e   u s er 's  s ea r ch   q u er ies.   M o s t  o f   th e   r eq u ir ed   q u er ies  o r   in f o r m at io n   i s   u s u all y   b ased   o n   cu r r en t   o r   an tic ip ated   lo ca tio n s .   Fo r   ex a m p le ,   s ea r ch i n g   n ea r est   r estau r an ts ,   v ie w i n g   th e  r o u t e  an d   in q u ir y   r eq u ir ed   in f o r m atio n   ar e  th e  u s er   r eq u ir ed   q u er ies  w h ic h   ar e  s u p p o r ted   b y   p o p   tech n o lo g y   [ 2 ] .   T h is   tec h n o lo g y   n o r m a ll y   b ased   o n   s tatic  d ata  o r   lo ca ti o n s .   I n   ad d itio n ,   t h e   s er v ices  s u c h   as  r ec ei v i n g   wea th er   in f o r m at io n ,   e m er g en c y   aler ts ,   ad v er ti s e m e n t  g etti n g   ac ce s s   to   w h at 's   k n o w n   as  a u to m atic  n o tific ati o n s   ar e  aid ed   b y   p u s h   tec h n o lo g y   [ 3 ] .   T h is   s er v ice  is   u s u all y   b ased   o n   m o v i n g   p o s itio n s   o r   cu r r en t  m o b ile  p o s itio n s .   I n   s u ch   e n v ir o n m e n ts ,   m o b ile  d ev ice s   r eg u lar l y   s en d   t h eir   cu r r e n t   lo ca tio n s   to   a  s er v er .   T h e  s er v er   r ec eiv es  th e  cu r r en t  lo ca tio n s   an d   p r o ce s s es  d esire d   q u er ies  s u c h   as  " w h ich   m o b ile s   ar e  c u r r en t l y   lo ca ted   w it h in   t h e  d esire d   ar ea " .   T o   r ep ly   s u ch   q u er ies   ap p r o p r iat el y ,   t h e  ap p licatio n   s er v er   h as  to   s ea r c h   all  o f   th e  cu r r en t  m o b ile  lo ca tio n s   th a t  ar e  in   th e  d esire d   ar ea .   T h er ef o r e,   an   ap p r o p r iate  s tr u ct u r e  an d   s ea r ch in g   m eth o d   f o r   th e  n ea r est ar e  r eq u ir ed .     Gen er all y ,   th e  n ea r est  s ea r ch i n g   tech n iq u e  ca n   b e  d iv id ed   i n to   t w o   p ar ts :  s tr u ct u r el ess   tec h n iq u e  a n d   s tr u ct u r e - b ased   tec h n iq u e.   F o r   ex a m p le,   a  w ell - k n o w n   t ec h n iq u e  s u ch   as  k   th e  n ea r est  n ei g h b o r   is   a   s tr u ct u r eles s   tech n iq u e  an d   it  is   v er y   ea s y   to   i m p le m e n t.  T h e  g en er al  w o r k   o f   s tr u ct u r eles s   tech n iq u e  is   th a t   d is tan ce   i s   ca lc u lated   f r o m   a ll   n o d es  to   t h e  s er v ice  n o d e  o f   a  q u er y   a n d   t h e  n o d e  w ith   t h e   clo s est  d i s tan ce   is   r eg ar d ed   as  t h e  n ea r est   n ei g h b o r   [ 4 - 5 ] .   T h ese  tech n iq u e s   ar e   v er y   s i m p le   b u t   th e   v alu e   o f   k   a f f ec ts   th e   r es u lt.   T o   p r o v id e  th e  s p ee d   o f   q u er y   a n d   m e m o r y   r eq u ir e m e n t,   a  v ar iet y   o f   tr ee - b ased   i n d ex   s tr u ctu r e s   ca lled   s tr u ct u r e - b ased   tec h n iq u es a r e   ap p lied   in   m a n y   ar ea s .       Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       Mo b ile  lo ca tio n   in d ex in g   b a s e d   o n   s yn th etic  mo vi n g   o b jects ( Th u   Th u   Za n )   2557   I n   s tr u c tu r e - b ased   tech n iq u es ,   m o s t  o f   th e  in d e x in g   s tr u ct u r es  a n d   n ea r est  n ei g h b o r   s e ar ch es  ar e   s ep ar atel y   ta k en   b y   t w o   p ar ts :  b u ild in g   i n d ex   s tr u ctu r e  a n d   s ea r ch i n g   n ea r es t  n e ig h b o r   o f   t h e  d esire d   q u er y   p o in t  p .   I n   t h e  b u ild i n g   o f   a  tr ee   also   in cl u d es  r ele v a n t  s tr u c tu r e  alo n g   w i th   co llect in g   a n d   s to r in g   d ata  p o in ts .   T h en ,   an   ap p r o p r iate  p r o ce d u r e  o r   alg o r ith m   is   u s ed   to   s ea r ch   th e   n ea r es t  p o in t s   f r o m   t h e  d esi re d   q u er y   p o in t  [ 6 ] .   I t  is   to tall y   g o o d   f o r   s tatic  o r   n o n - m o v i n g   o b j ec ts   s tr u ct u r e  b u t  it  m a y   is s u e  in   m o v i n g   lo ca tio n s   o r   o b j ec ts   in d ex i n g .   Mo v i n g   o b j ec t  in d ex   s tr u ct u r e  w it h   t h e  r eg u lar   u p d ate  w ill  also   n ee d   to   co o p er ate  u p d atin g   o f   t h e  n ea r est  p o in t s   s ea r ch i n g   al g o r ith m .   I t  m a y   t h i n k   co n s i s te n c y   b et w ee n   in d e x   s tr u ctu r e  a n d   s ea r ch i n g   alg o r ith m   f o r   d is cr etio n ar y   d at a  p o in ts   q u er y   a n d   s ea r ch   w ill  b e  r eq u ir ed   co n cu r r en c y   co n tr o l.    R ec en t  ad v a n ce s   in   m o v i n g   o b j ec ts   b ased   r esear ch   an d   ap p licatio n s ,   th e  p o s itio n i n g   te ch n o lo g ies   an d   in d ex i n g   b ased   s tr u ct u r es   h av e  co llab o r ated   to g eth er   th u s   it  lead s   to   a  p er f ec t  tech n i q u e  f o r   m ain tain in g   an d   u p d atin g   m o b ile  p o s itio n   in   t h e  d y n a m ic  e n v ir o n m e n t .   No r m a ll y ,   t h e  p u r p o s e  o f   t h e  tr ad itio n al  i n d ex   s tr u ct u r e  is   g e n er atin g   q u er ies  f a s ter   an d   ea s ier   w it h   t h e  r eq u ir ed   in f o r m atio n .   Ho w e v er ,   a  g o o d   m o b ile   o b j ec ts '   in d e x i n g   n ee d s   n o t  th e  o n l y   f aster   q u er y   b u t  als o   ab ilit y   to   u p d ate  r eg u lar l y .   I n   th is   p ap er ,   th e   p r eso r ted - n ea r est i n d ex   tr ee   s t r u ctu r e  is   p r o p o s ed   th at  co m b i n es t h e  co n ce p t o f   t h e  n ea r e s t  n eig h b o r   alg o r ith m   an d   tr ee - b ased   in d ex   s tr u ct u r e.   T h u s ,   it  s u p p o r ts   g e n er atin g   n ea r est  lo ca tio n s   b y   i n d ex   s tr u ct u r e  f r o m   t h e   d esire d   q u er y   p o in t.    I n   th i s   s tr u ctu r e,   al l  o f   th e   lo ca tio n   n o d es  ar e  p lace d   b y   lev el   o r d er   th u s   n o d es  at  a n y  d is tan ce   ca n   ea s il y   f i n d   with o u t   tr av e lin g   th e   w h o le   tr ee   an d   th e   s ea r c h in g   m a y   r ed u ce   g r ea tl y .   I t  is   h ar m o n ized   to   s o lv e   n ea r est  n e ig h b o r   lo ca tio n   q u er ies   s i n ce   t h e  lo ca tio n s   o f   th e   d a ta  p o in ts   ar e  b ased   o n l y   o n   t h eir   r elati v e  d is tan ce s   f r o m   ea ch   o t h er .     I n   r ea lit y ,   t h e  m i llio n s   o f   m o b ile  p o s itio n in g   d ata  ar e  u n av ailab le  f o r   p er f o r m a n ce   ev alu atio n   o f   in d ex   s tr u c tu r e.   I f   t h e  m o b ile  lo ca tio n   d ataset  ca n   cr ea te  s y n th etica ll y ,   it   w o u ld   b e  f r ee   f r o m   lo ca tio n   p r iv ac y   an d   co n f id en tialit y .   I t   ca n   b e  u s ed   to   g et  lo ca tio n   d ata   f o r   p er f o r m a n ce   e v al u atio n   o f   p r o p o s ed   in d ex   s tr u ct u r e.   T h u s ,   t h e  r eq u ir e m en t  o f   g en er at in g   a   s y n th e tic  d ataset  f o r   d y n a m ic   m o b ile   l o ca tio n s   t h at   s ee m   r ea lis tic  i s   a   ch al len g e.   T h er ef o r e,   p r o p o s in g   a   n o v el  p r o ce d u r e  to   p r o d u ce   th e   s y n th e tic  d ataset  w h ic h   i s   b ased   o n   d y n a m ic   t w o - d i m e n s io n al  p o in t s   is   in c lu d ed   i n   t h is   p ap er .   A cc o r d in g   to   e n v ir o n m en tal  n ee d s ,   m an y   d atasets   ar e  g en er ated   s y n t h etica ll y   s u c h   as  an i m al,   m o b ile  u s er ,   b u s ,   Hu r r ican e  d ataset,   an d   s o   o n .     A  s y n th etic   d ataset   u s u a ll y   c o m e s   f r o m   ap p licatio n - d ep en d en t  g en er atio n .   T h er ef o r e,   a  d ataset  g e n er ato r   is   r eq u ir ed   ab o u t th eir   d o m ai n   o f   in ter est b ef o r e  m a k i n g   an y   d ataset  s y n t h etica ll y .     T h is   p ap er   ex p lain s   h o w   to   p r o ce s s   d y n a m ic  lo ca tio n   attr ib u tes  i n   t h e  p r o p o s ed   in d ex   s tr u ctu r e  a n d   an   ap p r o p r iate  p r o ce s s   f lo w   o f   m o b ile  o b j ec t  g e n er ato r   is   b u ilt  to   d ea l  w it h   t h e  o v er all   s y s te m .   As  m o b ile  p o s itio n s   ar e  b asicall y   u s ed   in   th is   s y s te m   s o   th at  it  r eq u i r es  co n tin u o u s   ev al u atio n   as  th e  lo ca tio n   r es u l t   n ee d s   to   v alid   af ter   a  s u itab le   p er io d   o f   ti m e.   W h en   t h e  u s e  o f   in d ex i n g   b ased   o n   lo ca tio n   o r   p o s itio n ,   th e  th r ee   b asic  p o s itio n s   ar e  n o r m all y   an a l y ze d   o n   h is to r ical,   c u r r en t  an d   an ticip ated   f u t u r e  p o s itio n .   T h is   s y s te m   tak es  t h e  s ec o n d   o n e  w h ich   i s   b ased   o n   th e  cu r r e n t  p o s itio n   t h u s   it  h as  to   g e t  its   lo ca tio n   with   t h e  ap p r o p r iate   u p d ate  w ill  b e  th er e.     I t  co m b i n es  Sp r in g   s c h ed u ler   th at  a u to m atica ll y   tak e s   in   all  o f   t h e  u p d atin g   ca s e s   th u s   it  lead s   to   r ed u ce   b o th   s er v er   u p d ate  an d   tr af f ic  co s t  [ 7 ] .   T h e  n ec es s ar y   p er f o r m a n ce s   ar e   test ed   b y   u s i n g   a   J Un it  f r a m e w o r k ,   w h ich   ca n   ap p l y   to   f etc h   a n d   test   r ep ea tab le  au to m ated   tes ts .   T h e  r esu lt s   ar e  u s ed   f o r   ex ec u t io n   ti m e,   u p d ati n g   ti m e  an d   C P U  u s a g e  ti m e  w it h   th e  d if f er e n t n u m b er   o f   m o b ile  d atasets .     T h is   p ap er   is   d escr ib ed   i n to   f i v e  s ec tio n s :  i n d ex i n g   a n d   it s   a p p lied   ar ea s   ar e  in tr o d u ce d   i n   s ec tio n   2 .   A   p r o p o s ed   in d ex   s tr u ct u r e,   p r eso r ted - n ea r est  i n d ex   tr ee   s tr u ctu r e  i s   ex p lai n ed   in   s ec tio n   3 .   A   v ir t u al  m o b ile   d ataset  g e n er atio n   is   p r ese n te d   in   s ec tio n   4   w i th   ar c h itect u r e  an d   a  p r o ce s s   f lo w   o f   m o b il e  o b j e cts  g en er ato r .   Fin all y ,   t h e  ex p er i m en tal  r es u l ts   o f   p er f o r m a n ce   ev al u atio n s   an d   d is cu s s io n s   ar e  co llected   in   s ec tio n   5 .       2.   I NDE XIN G   AND  I T S AP P L I E D  AR E A S   I n d ex i n g   is   a  s p ec ial  d ata  s tr u ctu r e  t h at  a llo w s   h a v i n g   q u ic k   ac ce s s   to   d ata  o r   o b j ec ts   s y s t e m atica ll y .   I n d ex i n g   is   u s u all y   u s ed   f o r   u s er s   to   d i s p la y   r esu lts   th a t  m at ch   t h e  d es ir ed   u s er   cr iter ia.   I n   r ec en t  y ea r s ,   th er e   h as  b ee n   a  s u r v e y   o n   in d e x in g   al g o r ith m s   to g et h er   w it h   t h e   ac tiv it ies  o f   m o v i n g   o b j ec t  d atab ases   to   f a s t  a n d   ef f icien t  p r o ce s s es  [ 8 ] .   No r m al l y ,   in d ex in g   h a s   its   o w n   r elev an t  s tr u ct u r e  th at  n ee d s   ti m e  to   b u ild   it.   I t  is   s av ed   b y   b u i ld in g   th e  s tr u ctu r e  o n l y   f o r   p o in ts   th a t  n ee d   to   r ec eiv e  in f o r m a tio n   a n d   it  ca n   b e  u s ed   in   t h e   m u lticas t  n o ti f icatio n .   No w ad a y s ,   i n d ex i n g   h a s   v ar io u s   t y p e s   an d   f ield w o r k s   to   ap p l y   in   th e  r ea l  w o r ld .   So m e   t y p es  ar e  g o o d   in   q u er y in g   an d   s o m e  ar e  in   u p d atin g .   B ased   o n   th e  t y p es  o f   m o v i n g   o b j ec ts ,   s u ch   as   g eo g r ap h ical l y   d is tr ib u ted   m o v in g   o b j ec ts ,   th er e  is   a  s p ec ial  in d ex   s tr u ct u r e  th at  allo w s   g e n er atin g   r an g e   m o n ito r i n g   q u er ies o v er   co n te n t - m a t ch   a n d   g r o u p - a w ar e  q u er ies [ 9 ] .     So m e  o f   t h e  in d e x es   p r eser v e  o n l y   f o r   a   s p ec i f ic  t y p e  s u c h   a s   t h e  tr aj ec to r y   o f   m o v i n g   o b jects  [ 10 ] .   T h e  co m m o n   i n d ex   f o r   d if f er e n t  t y p e s   o f   q u er y   s p ec ial  is   g r i d   s tr u ct u r e.   W ith   t h e  r ap id   d is tr ib u ti o n   o f   s p atial   m o v i n g   o b j ec ts ,   a  Dis tr ib u ted   Gr id   I n d ex   ( DGI )   w a s   p r o p o s ed   [ 11 ]   th at  ac cu r atel y   i n te r r o g ate  th e  o b j ec ts '  lo ca tio n   b y   u n iq u e  o b j ec t' s   I D .   So m eti m es,  t h e  s p atial  i n d ex   s tr u ct u r e  s u c h   as  R   tr ee   u s ed   t h e  p ar titi o n   o f   g r id   in d ex   t h at  b ec a m e  les s   o v er lap   an d   g ai n ed   in f o r m a tio n   [ 12 ] .   L ik e  th e   g r id   s tr u ct u r e,   a  q u ad tr ee   in d ex   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  9 ,   No .   4 ,  A u g u s t 2 0 1 9   :   2 5 5 6   -   2563   2558   o f f er ed   [ 13 ]   b etter   p er f o r m an ce   r eg ar d less   o f   th e  a m o u n t  o f   m o v i n g   o b j ec ts .   Ho w ev er ,   [ 14 ]   u s in g   a  s i m p le,   u n i f o r m   g r id   i n d ex   w a s   b asic all y   s u p p o r ted   to   q u er y   p r o ce s s i n g   a n d   it  i s   w ea k   in   u p d ate  p er f o r m a n ce .   I n   o r d er   to   b etter   h elp   m o b ile  o b j ec ts '   q u er y   w as  p r o p o s ed   [ 15 ] .   So m e  s u r v e y   p ap er   th o u g h t  u n ce r tai n   d ata  o r   o b j ec t  in d ex   s tr u ct u r es  w er e  n o t  ap p licab le  to   all  ty p es  o f   q u er y   p r o ce s s i n g   [ 1 6 ] .   A s   [ 1 7 ]   d is cu s s ed   th a t  s o m e   tr ee - b ased   alg o r it h m s   s u c h   as  R   tr ee s   ar e  n o t  s u itab le  f o r   h ig h - d i m e n s io n al  d ata  i n   r ea l - li f e  ap p licatio n s .   I n s tead ,   th e y   p r o p o s ed   Gr id - in d ex   al g o r ith m   ( GI R )   t h at  o f f er s   r ev er s e  r an k   q u er ies  w i th   a  litt le  m e m o r y   co s t.   On   t h e  o th er   h a n d ,   [ 1 8 ]   d is cu s s ed   th at  it is   h ar d   to   g et  a n   o p ti m al  r eso l u tio n   o f   in d e x   b ased   o n   g r id   a n d   also   R   tr ee   w it h   th e  s k e w ed   m o b ile  o b j ec ts .   A s   a  r esu l t,  a  q u alif i ed   in d ex   s tr u ct u r e  d ep en d ed   o n   th e  s tr u c tu r e  o f   in d ex ,   t y p e s   o f   m o v i n g   o b j ec ts ,   an d   q u er ies.      So m e  in d e x   f o r   m o v i n g   o b jects  ar e   b ased   o n   q u er ies  r e g ar d less   o f   m o v i n g   p o s itio n s ,   s p ee d   o r   m o v e m e n t  n atu r e  [ 19 ] .   A   s u i t ab le  w a y   o f   i n d ex in g   a n d   q u e r y in g   to   m o v i n g   o b j ec ts   is   h a v in g   a  g o o d   d esig n ,   s u c h   as   a  s p atio - te m p o r al  in d ex in g   u s i n g   k e y - v al u e  s to r e   [ 20 ] .   Du e  to   th e   v ar iat io n   o f   m o v i n g   o b j ec ts ,   th e  co n cu r r en c y   p r o b le m   m a y   o cc u r   in   t h eir   i n d ex i n g   s o   th at   d is tr ib u ted   i n d ex   s tr u c t u r e  t h at  e x p l o its   in   m u ltip le  m ac h in e s   [ 2 1 ] .   A ct u a ll y ,   a n   i n d ex i n g   b ased   s tr u ct u r e  is   v er y   s u itab le  f o r   co n ti n u o u s   q u er ies  w i th in   a   s p ec if ied   t i m e   b y   s e n d in g   m u l ticast   m e s s a g es,   r ep o r ts   o r   n o tif icatio n s .   I t   is   m o r e  s u itab l e  as  lo ca tio n   p o i n ts   ar e  r ec eiv ed   w it h i n   a  r an g e  b y   o n l y   o n ce   t h e  q u er y .   W ith o u t  i n d ex i n g ,   t h e  r a n g e  q u er y   i s   av ailab le  b ased   o n   eith er   a  s ea r ch   ac co r d in g   to   th e  d is ta n ce   o r   o th er   m ea s u r es .   B u t,  it  h as  to   s ea r ch   alo n g   w it h   a  s eq u en t ial  o r   o r d er   m atch   p atter n   b y   ea ch   o b j ec t in   th e  d ataset.   T h er ef o r e,   t w o   is s u e s   ar e  f o u n d   in   t h i s   wa y .   a.   Su c h   a  s ca n n i n g   o f   t h e  lar g e  d ataset  ca n   b e  v er y   h i g h   co s t.   b.   T h e  lo n g er   d ataset,   th e  m o r e  e x ec u t io n   ti m e  is   r eq u ir ed   b y   s eq u en tial  s ea r ch i n g .   E s p ec iall y   f o r   r ep ea tin g   a   s i n g le  r a n g e,   in d e x in g   b a s ed   r an g e  s ea r c h i n g   w ill   b e  f aster   t h an   ea c h   o f   th e  s i n g le  m atc h   o f   r an g e  s e ar ch in g .   A s   [ 2 2 ]   p r o p o s ed   a n   in d e x   s tr u ct u r e  ca lled   T M - R T r ee   b y   p lan n i n g   m o v i n g   o b j ec ts   w ith   d i f f er en t   m o d es  s u c h   as  tr a n s p o r tatio n ,   te m p o r al  an d   s p atial.   T h e y   clai m ed   th at  t h eir   p r o p o s ed   in d ex   s tr u c tu r e  w ell  s u p p o r ted   to   an s w er   q u er ie s   r elate d   to   th e  d esire d   r an g es.       3.   RE S E ARCH   M E T H O D   3 . 1 .   B uil din g   ind e x   s t ruct ure  w it h pre s o rt ing   I f   t h e  d ata  is   ad d ed   b y   s o r ted   lis t,  t h e  cr ea tio n   o f   a n   i n d ex   is   f aster   t h a n   t h e  u s u al  b ec a u s e  i t  d o es  n o t   h av e   to   s ea r ch   f o r   t h e  co r r ec t   s p ac e  to   s to r e  t h e  n e w   v al u e ,   an d   it   s a v es   b o th   I /O  a n d   C P U  co s ts .   T h e  n e w   v alu e   t h at  w i ll a l w a y s   b e  j o in e d   ad j ac en t t o   th e  last   v al u e  th a t  w as   s to r ed .   T h e  in d e x   tr ee   wo u ld   b e  f a s t a s   it   i s   ea s il y   b u ilt  s eq u en tiall y .   I f   a n   in d ex   s tr u ct u r e  th at  i s   b u il t  b y   u n s o r ted   d ata,   it  m i g h t  b e  b ig g er   t h an   th e  i n d ex   s tr u ct u r e  o f   t h e  s o r ted   d ata.   E s p ec iall y   it  i s   g o in g   to   b e  h ar d   to   b u ild   a n d   s to r e  in   a  h u g e  a m o u n t  o f   d ata  s ize.   Or d er in g   o r   s o r ti n g   t h e  d ata  m a y   ta k e  ad d itio n al   ex tr a   ti m e,   b u t   it  w ill  b e  f a s ter   t h an   an y   o t h er   u n s o r ted   s tr u ct u r e  an d   th u s   i t  w ill b r in g   to   b e  a  f ast an d   co m p ac t in d e x .     I n   th i s   p ap er ,   a  p r eso r ted - n ea r est  in d ex   tr ee   is   p r o p o s ed   an d   it  ca n   b e  u s ed   f o r   an y   t y p es  o f   t w o - d i m en s io n al   p o in ts .   A ll  o f   t h e  in co m in g   o b j ec ts   o r   p o in ts   ar e  o r d er ed   b ef o r e  b u ild in g   i n d ex   s tr u ct u r e.   T h e   f o llo w in g   al g o r ith m   is   ab o u t t h e  d etailed   s tr u ct u r e  o f   t h e  p r o p o s ed   in d ex   tr ee .     3 . 2 .   P re s o rt e d - nea re s t   ind ex   t re e   I n p u t c : c en ter   o f   lo ca tio n   q u e r y ,     R [ m ] :  m o b ile  lo ca tio n s   i n   r an g e  lis t s   th a t a r e  s o r ted   b y   latit u d e  an d   lo n g it u d e  o f   ea ch   lo ca t io n ,     m :  m o b ile  lo ca tio n s   Ou tp u t N ea r est lo ca tio n s   in d e x   s tr u ctu r e  f r o m   ce n ter   p o in ts   b y   le v el  o r d er   A l g o r ith m : 2 D - Nea r est I n d ex   T r ee ( c,   R   ( m ) )     if   m   ! =  n u l l th e n   T r ee - >r o o t :=   c;     m i n _ I n d ex   =  0 ;      T r ee - >le f tKe y : = Fin d Nea r es t( c) ;     T r ee - >r ig h tKe y : = Fi n d Nea r est ( c) ;     Gen er ateT r ee ( c) ;   Fin d Nea r est(c ) :     n ea r est :=  No d e[ 0 ] ; m i n d is t=0 ;     f o r   i=1   to   R ( m )     d =  d is tan ce ( c,   n ea r est);     if ( d [ i] <d [ m i n d is t] )     n ea r est=d [ i] ;     r etu r n   n ea r e s t;       Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       Mo b ile  lo ca tio n   in d ex in g   b a s e d   o n   s yn th etic  mo vi n g   o b jects ( Th u   Th u   Za n )   2559   Gen er ateT r ee ( c) :     f o r   d   =  1   to   h eig h t( T r ee )     P r in tGiv e n L ev el  ( T r ee ,   d ) ;     if   le v el  is   1   th e n     p r in t ( T r ee - >c)     else if   le v el> 1   th e n     P r in tGiv e n L ev el  ( T r ee - >le f t K e y ,   lev el - 1 ) ;     P r in tGiv e n L ev el  ( T r ee - >r ig h t Ke y ,   lev el - 1 ) ;   Firstl y ,   t h e  p r o ce d u r e  ta k es   m o b ile   li s ts   ( r an g eM o b iles )   w h ic h   ar e  in   th e   m ax i m u m   a n d   m in i m u m   r an g e  b o u n d ar ies.  T h e  r a n g e   m o b iles   ar e  i n p u t  a s   t w o   s o r ted   ar r ay s .   B o th   o f   th e s e  a r r ay s   ar e  ar r a y s   o f   lo ca tio n s   w h ich   h a v e  th e  s a m e  lo ca tio n   p o in ts   b u t  o n e  i s   o r d er ed   b y   latit u d e  an d   an o t h e r   o n e  is   o r d er ed   b y   lo n g it u d e.     T h e n ,   th e   n ea r e s t   lo ca tio n   tr ee   i s   b u ilt  ac co r d i n g   to   t h e  C en ter P o in t  a n d   s e r v ice  r an g e.   I n   t h is   lo ca tio n   tr ee ,   th e  C en ter P o in t  tak e  p lace   as  th e  r o o t  o f   o th er   n o d es  in   th e  tr ee .   T h en ,   n ea r est  lo ca tio n   p o in ts   ar e  r ec u r s iv el y   lo ca ted   to   th e  r ig h t  a n d   le f t  o f   ea c h   r o o t.  T h e  p o s itio n   o f   lo ca tio n   p o in t s   w il l  b e  p lace d   an d   r etr iev ed   ac co r d in g   to   th eir   le v el  o r d er   in   th e  tr ee   f o r   ea s y   a n d   q u ick   to   ac ce s s   n ea r est   n ei g h b o r   lo ca tio n s .   Fo r   r an g e  q u er ie s ,   t h e  f ir s t  t h in g   is   d eter m i n in g   w h et h er   m o v in g   o b j ec ts   ar e  in   t h e  cir cu lar   r an g e   ar ea   o r   n o t.  T h is   ca n   ea s il y   ca lcu late  b y   b o u n d i n g   co o r d in ates  b et w ee n   t h e  ce n ter   a n d   d esire d   s er v ice  d is tan ce : ( latit u d e,   lo n g it u d e,   d i s tan ce )   in   t h e  f o llo w in g   f o r m u la.   -   m i n L o n g it u d e  =  lo n g it u d e  -   M ath . to Deg r ee s   ( d is ta n ce / R /Ma t h . co s   ( Ma th . to R ad ia n s   ( lat) ) ) ;   -   m ax L o n g itu d e  =  lo n g it u d e  +  Ma th . to Deg r ee s ( d is tan ce /R /M ath . co s   ( Ma th . to R ad ia n s   ( lat) ) ) ;   -   m ax L a tit u d e  =  latitu d e  +  Ma t h . to Deg r ee s ( d is tan c e/ R ) ;   -   m i n L atit u d e  =  latitu d e  -   Ma th . to Deg r ee s ( d is ta n ce /R ) ;       4.   VIRT UAL M O B I L E   DA T A SE T   G E N E RA T I O N   4 . 1 .   M o v ing   o bje ct   g ener a t o r   I n   r ea lit y ,   d if f er en t  d ataset s   h av e  d if f er e n t  ap p licatio n s   a n d   u s a g e.   T h er ef o r e,   all  o f   t h e  r esear ch er s   s h o u ld   th in k   ab o u t  th eir   d o m ain   o f   in ter e s t  b ef o r e  m a k i n g   an y   d ataset  s y n t h etica l l y .   I t  h as  to   co m p ar e  th e  b eh av io r s   an d   f u n ctio n s   o f   r ea l d ata  s o   th at  it see m s   r ea lis tic.   T h e  r eq u ir ed   p h ases   an d   d etai l  ex p lan atio n s   o f   t h is   p r o ce s s   b r in g   a  g o o d   id ea   f o r   m a k in g   an y   o t h er   m o v i n g   o b j ec ts   g e n er ato r .   I n   th is   ar c h itect u r e,   s y n t h etic  m o b ile  u s er s '   d ataset  is   g en er at ed   alo n g   w ith   t h eir   b eh av io r s   a n d   ac tiv it ies.  P r ac ticall y ,   m o b ile  u s er s   ar e  g e n er all y   lo ca ted   at  s tatio n ar y   o r   n o   m o v i n g   t y p e,   s o m eti m es   th e y   d r i v e,   an d   s o m e  ar e  w al k i n g .   E s p ec iall y   f o r   u p d atin g   m o v i n g   d ata,   o n e  o f   t h e  s u itab le  f o r m s   is   u p d atin g   t h eir   p r o ce s s   b ased   o n   th eir   m o tio n s .     As  an   e x a m p le,   a  u s er   w h o   i s   w alk in g   an d   a  u s er   w h o   is   d r iv in g   w ill  n o t  b e  th e  s a m e  m o tio n   as  th e  r eq u ir ed   u p d ate.   T h e  m o r e  d ataset  v ar ies,  th e  m o r e  r esu l t  d if f er e n t,  an d   all  o f   th ese  o u tco m es  w i ll  b e  u s ed   in   p ar t  f o r   in co m i n g   r esear c h .     I n   o r d er   to   b ett er   f in d i n g s ,   v ir t u al   m o b ile  u s er s   ar e  cr ea ted   w it h   d if f er e n t f o r m s   a n d   v er s io n s   a n d   test ed   b y   u s i n g   i n d ex i n g   in   th is   p ap er .   A   s u i tab le  w a y   t h at  ca n   g en e r ate   s y n th e tic  d ataset  i s   d er iv in g   a  m o d el  o r   ar ch itect u r e  w it h   v ali d   p r o p er ties   o f   r ea l  d ata.   An   ap p r o p r iate  an d   v alid   ar ch itect u r e,   a  m o v in g   o b j ec ts   g e n er ato r   is   p r o p o s ed   in   t h is   p ap er .   T h e  f lo w   o f   t h e  p r o p o s ed   m o v in g   o b j ec ts   g en er ato r   is   s h o w n   i n   F ig u r e  1.           Fig u r e  1 .   T h e  ar ch itectu r e  o f   m o b ile  o b j ec t g en er ato r       I n   ea ch   o f   th e   m o b ile   u s er ,   d if f er en t   ac tio n   an d   c h ar ac ter is tic  ta k e  d i f f er en t   lo ca tio n   u p d ate.   T w o   m ain   s tep s   ar e  in c lu d e d   in   i m p le m e n ti n g   t h i s   ar ch itectu r e.   Mo b ile  u s er s '   lo ca ti o n s   ar e  g e n er ated   r an d o m l y   w i th i n   th e  m a x i m u m   a n d   m i n i m u m   b o u n d in g   c o o r d in ates  th at   ar e  in   - 9 0   to   9 0   an d   0   to   1 8 0 .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  9 ,   No .   4 ,  A u g u s t 2 0 1 9   :   2 5 5 6   -   2563   2560   T h u s ,   th e  f ir s t  s tep   is   g e n er at in g   m o b ile  u s er s   ac co r d in g   t o   th e  r an d o m   lo ca tio n   f o r m u l a  th at  is   s ep ar atel y   ca lcu lated   w it h   latit u d e  x   a n d   lo n g it u d e  y   o f   ea ch   u s er   lo ca ti o n .     X= m i n X  +  ( r an d o m   ( ) * ( m ax X - m in X)   +  1 ) ;     Y=   m i n Y  +  ( r an d o m   ( ) * ( m a x Y - m i n Y)   +  1 ) ;     Sin ce   t h e  m o b ile  u s er   lo ca tio n   h as  its   o w n   latit u d e  an d   lo n g it u d e,   ea ch   o f   th e m   i s   ca lcu lated   s ep ar atel y .   Af ter   g ett in g   r a n d o m   lo ca tio n s ,   all   o f   t h ese  ar e   d iv id ed   b y   t h r ee   t y p e s   o f   m o b ile  u s er s   w h o   ar e   w al k i n g ,   d r iv i n g   an d   s tatio n ar y   ac co r d in g   to   th e  ti m e  an d   d is tan ce   t h r esh o ld   v al u es  alo n g   w it h   th e ir   u p d ates   ar e  d o n e  f o r   ea ch .   A t  th e  s e co n d   s tep ,   a  lo ca tio n   u p d ate  p o licy   i s   d r a w n   as  m o b ile  u s er s '   b eh a v i o r s   an d   ac tio n s   ar e  q u ite  d if f er e n t.  I n   t h is   s tep ,   ti m e  an d   d i s tan ce   b a s ed   lo ca tio n   u p d ate  s tr ate g ies  a r e  u s ed   to   s ep ar ate   m o b ile   u s er s '   t y p es.  T h e  o u tp u t  w i ll  b e  a  s y n t h etic  d ata s et  t h at  i n cl u d es  f i n d in g   lo ca tio n s   an d   u p d ati n g   th e m   ap p r o p r iately .     4 . 2 .     P r o ce s s   f lo w   o f   g ener a t i ng   m o bi le  da t a s et   T h e  p r o ce s s   f lo w   o f   t h e  p r o p o s ed   ar ch itectu r e  o n   m o v i n g   o b j ec ts   g en er ato r   is   clea r l y   ex p lain ed   i n   F ig u r e   2 .             Fig u r e  2 .  P r o ce s s   f lo w   o f   m o b ile  o b j ec ts   g en er ato r       T h e  f ir s t  p h ase  is   to   f in d   th e   lo ca tio n   o f   m o b ile  u s er s   s y n th e ticall y   b ec a u s e  it  is   h ar d   to   g et  th e  m illi o n s   o f   m o b ile  lo ca tio n s   i n   r ea lit y   an d   it  i s   also   a  w a y   o f   p r iv ac y   p r o tectio n   f o r   r ea l  w o r ld .   Af ter   g etti n g   th ese  lo ca tio n s   o f   m o b ile  u s er s ,   all  o f   t h e s e  lo ca tio n s   ar e  lo ad ed   f r o m   d atab ase   to   m e m o r y .   T h en ,   t h e   f o llo w in g   t w o   s tep s   ar e  d o n e  b y   Sp r i n g   s ch ed u ler   th at  r u n s   w it h   t h e  h elp   o f   Sp r i n g   B o o t  at  th e  s p ec if ic  ti m e.   T h e  r eq u ir ed   u p d ate  lo ca tio n s   ar e  d o n e  b y   u s i n g   t h e  f o llo w i n g   f o r m u la.   Up d ate   L at   =. asin   ( s in   ( latit u d e) * co s   ( Up d ate Dis ta n ce /R )   +  co s   ( latitu d e) * s i n   ( Up d ateD is tan ce /R ) *   co s ( B ea r in g An g le) ) ;   Up d ate  L o n   =   lo n g itu d e+ ata n 2   ( s in ( B ea r in g An g le) * s i n ( Up d ateD is ta n ce /R ) * co s ( latit u d e) , co s ( Up d ate  Dis ta n ce   /R ) - s i n ( latit u d e) *   s i n ( u p d ateL at) ) ;   Firstl y ,   m o b ile  u s er s   ar e  tak en   o u t  o f   m e m o r y   b ef o r e  d o in g   a n y   p r o ce s s .   Seco n d ,   m o b ile  u s er s '  lo ca tio n s   ar e  u p d ated   b y   m o v i n g   t y p es a f ter   ch ec k i n g   m o b il e  u s er   lis t s   w h ich   ar e  av a ilab le   f o r   p r o ce s s in g .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       Mo b ile  lo ca tio n   in d ex in g   b a s e d   o n   s yn th etic  mo vi n g   o b jects ( Th u   Th u   Za n )   2561   5.   E XP E R I M E NT A L   RE SUL T S   We   m a n a g ed   an   ex p er i m en tal   s ettin g   o n   a  co m p u ter   w it h   a n   I n tel  C o r e  i7 - 4 5 9 0 U  C P U,   8 G  R AM ,   a n d   1 - T B   h ar d   d is k   s to r ag e.   W e  ap p li ed   th e  p r o p o s ed   s y n th etic  d ataset  g e n er ato r   f o r   m o b ile  lo ca tio n s   to   s i m u late   m o v i n g   o b j ec ts   th at   b asicall y   ca m e   f r o m   th e   r an d o m   f u n ctio n   o f   t h r ee   d i f f er e n t   b eh av io r s   s u c h   a s   t h e  ca r ,   w al k i n g   an d   s tat io n a r y .   A l l  o f   t h e  ac tiv a tio n s   o f   t h is   g en er ato r   ar e  d o n e  b y   s p r in g   b o o t   [ 1 7 ] .   I t  is   d esig n ed   ch a s tel y   f o r   all  ap p licatio n s   b ased   o n   s p r in g   d e v elo p m e n t.  I t s   i m p o r tan t   co n c ep ts   ar e  au to m atic   co n f i g u r atio n ,   s tar ter   d ep en d en ce s ,   a n d   t h e  co m m a n d   li n e  in ter p r eter .   Sp r in g   b o o t  p r o v id es  f a s t  a n d   w id e   ac ce s s es  f o r   all  d ev elo p m e n t a n d   p r o v id es n o n - f u n ctio n al  f e atu r es.   I n   o r d er   to   g et  t h e  p er f o r m a n ce   ev al u atio n s ,   w e  te s ted   ab o u t  p r o p o s ed   in d ex   tr ee   co n s tr u ctio n ,   its   r an g e  q u er ies  an d   n ea r e s t  n ei g h b o r   q u er ies  w ith   t h e  co m p ar is o n   o f   u s i n g   KD  tr ee .   Mo r eo v er ,   C P U  tim e  i s   ca lcu lated   an d   n o ted   w it h   th e  in cr ea s i n g   n u m b er   o f   m o b iles .   T o   im p r o v e  p er f o r m a n ce   ev al u atio n s ,   w e  clea r l y   s h o w ed   th e  te s ted   r esu lts   b y   d if f er en t  r a n g e  v al u es  a n d   n u m b er   o f   m o b ile s .   T h e  r eq u ir ed   p ar a m eter s   an d   t h eir   v alu e s   f o r   p er f o r m a n ce   ev al u a tio n s   ar e  d escr ib ed   in   T ab le  1 .       T ab le  1 .   T er m s   an d   v a lu e s   P a r a me t e r s   V a l u e s   S y n t h e t i c   M o b i l e   G e n e r a t i o n   R a n g e   M i n   L a t i t u d e   9 . 6 ,   M a x   L a t i t u d e   2 8 . 5   M i n   L o n g i t u d e   9 2 . 2 ,   M a x   L o n g i t u d e   1 0 1 . 1 7   N u mb e r   o f   O b j e c t s   1 0 0 0   –   1 0 0 , 0 0 0   O b j e c t   T y p e s   C a r ,   W a l k i n g ,   S t a t i o n a r y   B e a r i n g   A n g l e s   0 .    –   3 6 0 .   U p d a t e   D i s t a n c e   0 . 0 0 8 3 2 k m, 0 . 0 1 1 1 2 k m, 0 . 0 1 0 2 k m   S c h e d u l e   F i x e d   R a t e   ( f o r   R a n d o m  M o b i l e   U se r s)   2 0 0 0 mse c   S c h e d u l e   F i x e d   R a t e   ( f o r   B u i l d i n g   T r e e )   1 0 0 0 0 m se c   I n i t i a l   D e l a y   5 0 0 0 mse c       5 . 1 .   T re e  co ns t ruct io n t i m e  co mp a rsio n   T h e  F ig u r e   3   d escr ib es  t h e  r e s u lt s   o f   t h e  e x p er i m e n t  o n   p r eso r ted - n ea r est   i n d ex   tr ee   a n d   KD  tr ee   o v er   tr ee   co n s tr u ctio n   ti m e.     Fo r   th i s   co m p ar is o n ,   t h e  r es u lts   ar e  co n f ir m ed   a f ter   te s ti n g   an   a v er ag e   o f   1 5   ti m e s   w it h   th e  d ata s et  i s   f r o m   1 0 0 0   to   1 0 , 0 0 0   m o b ile  lo ca ti o n s .   I n   th is   e x p er i m e n t,  th e   n u m b er   o f   m o b ile s   i s   g en er ated   b y   p r o p o s ed   g en er ato r   w h ic h   is   i n it ialized   b y   ad d in g   t h e  s a m e  n u m b er   o f   m o v i n g   o b j ec t  ty p es .  I t   ca n   b e  co n clu d ed   t h at   th e   p r o p o s ed   tr ee   co n s tr u ct io n   is   o n e   th ir d   f a s ter   t h an   KD   tr ee .   T h is   i s   b ec au s e  b o t h   co m p ar ati v e  tr ee s   ar e  u n b alan cin g   t w o - d i m e n s io n al   tr ee s   a n d   t h e  p r o p o s ed   tr ee   in p u t  i s   b ein g   in c lu d ed   t h e   o r d er   q u er ies  th at  p r o v id e  to   b e  f ast  i n   tr ee   co n s tr u ctio n .   I n   ad d itio n ,   th e  f o r m   o f   t h e  p r o p o s ed   tr ee   is   alr ea d y   o u t o f   th e ir   n ea r est  n eig h b o r   b y   lev el  o r d er   s in ce   tr ee   co n s tr u ctio n .     5 . 2 .   Ra ng e  s ea rc hin g   T i m e   Co mp a rsio n   T h e  F ig u r e   4   s h o w s   t h e  te s t  f o r   th e  d u r atio n   o f   s ea r ch i n g   ti m e  w ith in   a   d is ta n ce   o f   1 0 0   k i lo m eter s   t o   6 0 0   k ilo m eter s   r an g e  s ea r ch   q u er ies.  T h is   ex p er i m en t   i n cl u d es  a   d ataset   1 0 0 0 0   an d   a  ce n ter   lati tu d e  a n d   lo n g it u d e  t h at  ta k e  as  U n i v er s it y   o f   C o m p u ter   Stu d ie s ,   Ya n g o n   GP S  co o r d in ate.   I t  w a s   n o t  d escr ib ed   th e  test ed   r esu lts   w it h in   a  d is ta n ce   o f   les s   t h a n   1 0 0   k m   r an g e  s ea r ch in g   ti m e   b ec au s e  it  w a s   ta k en   n ea r l y   th e  s a m e  in   ( 1   m illi s ec o n d ) .   A cc o r d in g   to   th e  f i g u r e,   b o th   KD  tr ee   an d   p r eso r ted - n ea r est  i n d ex   t r ee   ar e  ad e q u atel y  s u p p o r tiv e  to   r an g e  s ea r ch i n g .     5 . 3 .   Co m pa riso n o f   Nea re s t   Neig hb o r  Sea rc h w it hin   a   Ra ng e   T h e  F ig u r e   5   s h o w s   th e  co m p ar is o n   r esu l ts   o f   t h e  p r eso r ted - n ea r e s t  in d e x   tr ee   an d   KD  tr e e  th at  ac ts   w it h i n   a  r an g e  o f   m o b ile  lo ca tio n s   f r o m   th e  n ea r est  ar e  m ar k ed   an d   ca lcu lated . .   I n   th is   e x p er i m e n t,  th e   cir cu lar   r an g e  i s   u s ed   f o r   f i n d in g   r an g e  s ea r c h .   T o   u n d er tak e  th e  d u r atio n   o f   t h e  ex p e r i m en t,  th e  m o b ile  lo ca tio n s   ar e  f ir s tl y   c h ec k ed   w it h i n   t h e  r an g e  o r   n o t,  w h ic h   h a s   m ar k ed   t h e  ti m e.   T h en ,   th e  d is p la y i n g   th e   m o b ile   u s er   li s ts   b y   n ea r es t  c alled   n ea r est   n e ig h b o r   s ea r ch   is   te s ted   an d   also   m ar k ed   th e   ti m e.   Su c h   a   q u er y   ca n   b e  u s ed   f o r   n o t  o n l y   s ta t ic  o r   s tatio n ar y   lo ca tio n s   b u t   also   m o v in g   t h e  lo ca tio n   q u er y   th at  r ep ea ted l y   u n d er ta k es  a s   a  co n ti n u o u s   r a n g e   q u er y .   Acc o r d i n g   to   th e   ex p er i m e n tal  r es u lt s ,   t h e  p r es o r ted - n ea r est  i n d ex   tr ee   ex ec u tio n   tak e s   a  h al f   ti m e  in   th e   ex ec u tio n   o f   KD  tr ee .   T h is   is   b ec a u s e   alth o u g h   th e   s ea r ch in g   t i m e   o v er   t w o   co m p ar is o n   tr ee s   ar e  n ea r l y   th e  s a m e,   th e  s tr u ct u r e  o f   p r eso r ted - n ea r est  i n d ex   tr ee  is   al r ea d y   s u p p o r ted   t o   n ea r est n e ig h b o r   w it h i n   t h e  tr ee   co n s tr u ctio n   th u s   it c an   s ea r ch   f o r   n ea r est  n ei g h b o r   w it h in   o n e  m illi s ec o n d .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  9 ,   No .   4 ,  A u g u s t 2 0 1 9   :   2 5 5 6   -   2563   2562       Fig u r e  3 .  P r o ce s s in g   an d   co m p ar is o n   o f   co n s tr u cti n g   ti m e       Fig u r e  4 .  E v alu atio n   o f   r an g e  s ea r ch i n g   ti m e             Fig u r e  5 .  E x ec u tio n   ti m e  b et w ee n   p r o p o s ed   tr ee   an d   KD  tr ee       6.   DIS CU SS I O N   T h e  ca lcu latio n   o f   t h e  p er f o r m an ce   e v al u atio n   o v er   t w o   n o n - b ala n ce d   tr ee s   ( p r eso r ted - n e ar est  in d ex   tr ee   an d   KD  t r ee )   is   b ased   o n   th e  tr ee   co n s tr u ct io n   ti m e,   e x ec u t io n   ti m e  d u r in g   r an g e  s e ar ch es  a n d   n ea r es t   n eig h b o r   s ea r ch e s .   I n   t h is   ca l cu latio n ,   th e  g e n er atin g   o f   th e   latitu d e  a n d   lo n g it u d e  w h ic h   is   t h e  s o u r ce   o f   t h e   s y n t h etic  m o b ile  d ataset   is   t ak en   b y   M y a n m ar   co u n tr y   b o u n d ar ies  w it h i n   t h e  m a x i m u m   an d   m i n i m u m   latitu d es   an d   lo n g it u d es a lo n g   w it h   th e   p r o p o s ed   f o r m u la   to   r etr iev e  a n d   u p d ate.   O n e  p r o m i n en t   c h ar ac ter is tic   w it h i n   te s ts   f o u n d   th at   t h e  p r o p o s ed   tr ee   ( p r eso r ted - n ea r est i n d ex   tr ee )   i s   f aster   in   tr ee   b u il d in g   d u e  to   o r d er ed   d ata  b y   q u er ies   as  th e  in p u t d a ta.   I t c an   b e  f o u n d   t h at  b o th   co m p ar at iv e  tr ee s   ( p r eso r ted - n ea r est in d e x   tr ee   a n d   KD   tr ee )   ar e  c o n v en ien t l y   an d   f ast  in   t h e  r an g e  s ea r ch   w it h o u t  d ela y .   B esid es,  th e  p r o p o s ed   tr ee   p r o v id ed   th e   n ea r est  n e ig h b o r   b y   le v el  o r d er   s in ce   th e  tr ee   b u i ld in g   s o   t h at  it  d o es  n o t  n ee d   to   g i v e  p r iv ate  ti m e  i n   t h e  n ea r est n e ig h b o r   s ea r ch i n g .       7.   CO NCLU SI O N   T h is   p ap er   em p h a s ized   an   e f f i cien t  i n d ex i n g   an d   q u er y in g   s t r u ctu r e  o f   m o b ile  o b j ec ts   o n   a  s y n t h etic  d ataset.   A cc o r d in g   to   th e  d if f i cu ltie s   o f   g etti n g   m il lio n s   o f   m o b ile  lo ca tio n s ,   a  s y n t h etic  m o b ile  d ataset  m o d el  is   p r o p o s ed   alo n g   w i th   th e   r eq u ir ed   f r a m e w o r k   a n d   its   p r o ce s s   f lo w c h ar t.  T h e  p r eso r ted - n ea r est  i n d ex   tr ee   i s   p r o p o s ed   th at  s y s te m atica l l y   ad d r ess ed   an d   u p d ated   th e  lo ca tio n s   o f   m o b ile  a n d   s u p p o r ted   to   d esire d   r an g e   q u er ies  o v er   m o b ile  o b j ec ts .   E x p er i m e n tal  r es u lts   i n d icate   t h e  ef f ic ien c y   o f   u s i n g   p r o p o s ed   in d ex   tr ee   is   m o r e   th an   u s in g   th e  K D  tr ee   s tr u ct u r e  f o r   m o v in g   o b j ec ts .   T h e  v ar iatio n   o f   m o b ile  o b j ec ts   is   h a n d led   b y   p r eso r tin g   in   t h e  p r o p o s ed   tr ee   s tr u ctu r e .   Ho w e v er ,   th e  p r o p o s ed   s tr u ct u r e  w h ic h   i s   p r eso r ted   b y   in p u t  q u er ie s   r esis t  th e   s k e w ed   d is tr ib u tio n s   o f   m o b il e  o b j ec ts .   Mo r e o v er ,   th e  p r o p o s ed   s tr u ct u r e  p er f o r m ed   th e  d esire d   r an g e  q u er ies   an d   n ea r est  n eig h b o r   s ea r ch   with i n   th e  s h o r t e x ec u tio n   ti m e,   esp ec iall y   i n   t h e  lar g e  m o b ile  d ataset.       ACK NO WL E D G E M E NT S     I   w o u ld   li k e  to   ex p r es s   v er y   s p ec ial  t h an k s   to   m y   s u p er v is o r   Dr .   Sab ai   P h y u ,  P r o f es s o r ,   th e   Un i v er s it y   o f   C o m p u ter   St u d ies,  Yan g o n .   I   w o u ld   n o t  b e  ab le  to   co n tin u e  w it h o u t  h e r   s u p er v is io n   an d   v alu ab le   g u id an ce   d u r i n g   p er i o d   o f   th e  r esear ch   s t u d y .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       Mo b ile  lo ca tio n   in d ex in g   b a s e d   o n   s yn th etic  mo vi n g   o b jects ( Th u   Th u   Za n )   2563   RE F E R E NC E S     [1 ]   A .   Dh u m a l,   e t  a l. ,   “ V e h icle   T ra c k in g   S y ste m   u sin g   G P S   a n d   A n d r o id   OS, ”  In ter n a ti o n a l  J o u r n a l  o f  Ad v a n c e d   Res e a rc h   in   C o mp u ter   En g in e e ri n g   &   T e c h n o lo g y   ( IJ AR CET ) ,  v ol /i ss u e :   4 ( 4 ) ,  2 0 1 5 .   [2 ]   Bra ta K .   C . ,  e t  a l .,   “ L o c a ti o n - b a se d   A u g m e n ted   Re a li t y   In f o r m a ti o n   f o r  Bu s Ro u te P lan n in g   S y ste m , ”   In ter n a ti o n a l   J o u rn a l  o f  El e c trica l  a n d   C o mp u t e r E n g i n e e rin g   ( IJ ECE ),   v ol /i ss u e :   5 (1 ),   p p .   1 4 2 - 1 4 9 ,   2 0 1 5 .   [3 ]   S y a f i e   N . ,  e t  a l . ,   “ T h e   De v e lo p m e n t  o f   On li n e   Disa ste r  I n f o rm a ti o n   S y ste m   Us in g   L o c a ti o n   Ba s e d   S e rv ice   L B S   T e c h n o lo g y , ”   In ter n a ti o n a l  J o u r n a l  o f  I n fo rm a ti c s  a n d   C o mm u n i c a ti o n   T e c h n o l o g y   ( IJ - ICT ) ,   v ol / issu e :   3 (1 ) ,   p p .   47 - 5 8 ,   2 0 1 4 .   [4 ]   S.   Dh a n a b a l   a n d   S.   C h a n d ra m a th i,   “ A   Re v ie w   o f   v a rio u s  k - Ne a re st  Ne ig h b o r  Qu e ry   P ro c e ss in g   T e c h n iq u e s, ”   In ter n a t io n a l  J o u rn a l  o f  C o mp u ter   Ap p l ica ti o n s ( 0 9 7 5   – 8 8 8 7 ) ,  v ol / issu e :   31 ( 7 ) ,  2 0 1 1 .   [5 ]   S .   G h o rb a n i,   e t  a l. ,  “ Co n ti n u o u s  M u tu a l  Ne a re st  Ne ig h b o u r  P r o c e ss in g   o n   M o v in g   Ob jec ts  in   S p a ti o tem p o ra l   Da tas e ts, ”   In ter n a ti o n a l   J o u r n a l  o f  In fo rm a t io n   a n d   Ed u c a ti o n   T e c h n o lo g y ,  v ol /i ss u e :   7 ( 5 ) ,   2 0 1 7 .   [6 ]   H .  J .   Ch o ,   “ Eff icie n t  S h a re d   Ex e c u ti o n   P ro c e ss in g   o f   k - N e a re st  Ne ig h b o r  Jo in s  in   Ro a d   Ne t w o rk s, ”  M o b il e   In fo rm a t io n   S y ste ms ,   A rti c le ID  1 2 4 3 2 8 9 ,   2 0 1 8 .   [7 ]   Jo v a n o v ic  Z . ,  e t  a l. ,   “ Ja v a   S p ri n g   Bo o t  Re st  W EB  S e rv ice   In teg ra ti o n   w it h   Ja v a   Artif ici a l  In telli g e n c e   W e k a   F ra m e w o rk , ”   In ter n a ti o n a l  S c ien t if ic Co n fer e n c e .   Ga b ro v o ,   p p .   270 - 2 7 4 ,  2 0 1 7 .   [8 ]   Ay a b a k a n   I .   a n d   Kili m c i  P . ,   “ M o v in g   Ob jec t  Da tab a se s - In d e x in g   A l g o rit h m s, ”   In ter n a ti o n a l  J o u rn a l  o f  Co m p u ter   T h e o ry   a n d   En g in e e rin g ,  v ol /i ss u e :   6 (6 ),   p p .   4 5 5 - 4 5 9 ,   2 0 1 4 .   [9 ]   Ju n g   H .   R . ,  e t  a l. ,   “ Ev a lu a ti o n   o f   Co n ten t - M a tch e d   Ra n g e - M o n it o rin g   Qu e ries   o v e r  M o v in g   Ob jec ts  in   M o b il e   Co m p u ti n g   En v ir o n m e n ts, ”   S e n so rs ,   v ol /i ss u e :   1 5 (9 ) ,   p p .   2 4 1 4 3 - 2 4 1 7 7 ,   2 0 1 5 .   [1 0 ]   P f o se r  D . ,  e t  a l. ,   “ No v e l  A p p r o a c h e s  to   t h e   In d e x in g   o f   M o v i n g   Ob jec t  T ra jec to rie, ”   Pro c e e d in g s  o f  th e   2 6 t h   In ter n a t io n a l  C o n fer e n c e   o n   Ver y   L a rg e   D a ta b a se s ( VL DB'0 0 ) ,   Ca i ro ,   Eg y p t ,  p p .   3 5 9 - 4 0 6 ,   2 0 0 0 .   [1 1 ]   P a rk   K. ,   “ L o c a ti o n - b a se d   g rid - i n d e x   f o r  sp a ti a l  q u e ry   p ro c e ss in g , ”   Exp e rt  S y ste ms   wit h   A p p li c a ti o n s,   El se v ier ,  v ol /i ss u e :   4 1 (4 ),   p p .   1 2 9 4 - 1 3 0 0 ,   2 0 1 4 .   [1 2 ]   Rsla n   E . ,  e t   a l. ,   “ S p a ti a l  R - T re e   In d e x   Ba se d   o n   G rid   Div isio n   f o r  Qu e ry   P ro c e ss in g , ”   In ter n a ti o n a l  J o u rn a l  o f   Da ta b a se   M a n a g e me n t  S y ste ms   ( I J DM S ),   v ol /i ss u e :   9 ( 6 ),   p p .   2 5 - 3 6 ,   2 0 1 7 .   [1 3 ]   Zh a n g   F . ,  e t  a l. ,   “ Re a l - T i m e   S p a ti a l  Qu e ries   f o r  M o v in g   Ob jec ts  U sin g   S to rm   T o p o lo g y , ”   In ter n a ti o n a l  J o u r n a l  o f  Ge o - In fo rm a ti o n ,  v ol /i ss u e :   5 ( 1 0 ) ,   2 0 1 6 .   [1 4 ]   S id lau sk a s D . ,  e t  a l. ,   “ T re e s o r  G r id s?   In d e x in g   M o v in g   Ob jec ts  in   M a in   M e m o r y , ”   T h e   ACM   GIS   ’0 9 .   S e a tt le,  W A,   US A ,   p p .   2 3 6 - 2 4 5 ,   2 0 0 9 .   [1 5 ]   Zi w e i  Z . ,  e t  a l. ,   “ A   V o r - K V G Q  In d e x   S tr u c tu re   o f   M o b il e   Ob jec ts   Ba se d   o n   C o v e Re d   A re a , ”   In ter n a ti o n a l   J o u rn a l  o f  Hy b rid   In f o rm a ti o n   T e c h n o lo g y ,  v ol /i ss u e :   8 ( 5 ),   p p .   1 7 7 - 1 8 6 ,   2 0 1 5 .   [1 6 ]   Jo h n   A . ,  e t  a l .,   “ In d e x in g   a n d   Qu e ry   P ro c e ss in g   T e c h n iq u e s  in   S p a ti o - T e m p o ra l  Da ta, ”   ICT ACT   J o u rn a l  o n   S o f t   Co mp u t in g ,  v ol / issu e :   6 ( 3 ),   p p .   1 1 9 8 - 1 2 7 1 ,   2 0 1 6 .   [1 7 ]   Do n g   Y . ,  e t  a l. ,   “ G rid - In d e x   A l g o rit h m   f o r  Re v e r se   Ra n k   Q u e ries , ”   T h e   2 0 t h   In ter n a ti o n a l   Co n fer e n c e   o n   Exte n d in g   Da ta b a se   T e c h n o l o g y   ( EDBT ) ,   V e n ice ,   Italy ,   2 0 1 7 .   [1 8 ]   P a rk   Y . ,  e t  a l. ,   “ A  F a st  a n d   Co m p a c t  In d e x in g   Tec h n iq u e   f o r  M o v in g   Ob jec ts, ”   1 4 th   In ter n a ti o n a l   Co n fer e n c e   o n   In fo rm a t io n   Reu se   &   In teg ra ti o n   ( IRI )  IEE E ,   S a n   F ra n c isc o ,   CA ,   USA ,   2 0 1 3 .   [1 9 ]   Ka las h n ik o v   D .   V . ,  e t  a l. ,   “ Eff i c ien t  Ev a lu a ti o n   o f   Co n ti n u o u s  Ra n g e   Qu e ries   o n   M o v in g   Ob jec ts, ”   T h e   1 3 th   In t e rn a t io n a l  C o n fer e n c e   o n   D a ta b a se   a n d   Exp e rt S y ste ms   Ap p li c a t io n s ,   p p .   7 3 1 - 7 4 0 ,   2 0 0 2 .   [2 0 ]   L e   H .   V. ,   “ Distrib u te d   M o v in g   Ob jec ts  Da tab a se   Ba se d   o n   Ke y - V a lu e   S t o re s, ”   Pro c e e d in g s  o f  t h e   VL DB  2 0 1 6   Ph . D.  W o rk sh o p ,   Ne w   De lh i,   In d i a ,  2 0 1 6 .   [2 1 ]   L e e   Y .   a n d   S o n g   S . ,   “ Distrib u te d   In d e x in g   M e th o d s  f o r  M o v in g   Ob jec ts  b a se d   o n   S p a rk   S trea m , ”   In ter n a ti o n a l  J o u rn a l  o f  Co n ten ts ,  v ol /i ss u e :   1 1 (1 ),   p p .   6 9 - 7 2 ,   2 0 1 5 .   [2 2 ]   X u   J . ,  e t  a l. ,   “ T h e   T M - R T re e :  a n   in d e x   o n   g e n e ric  m o v in g   o b jec ts  f o r  ra n g e   q u e ries , ”   An   In ter n a t io n a l  J o u rn a l  o n   A d v a n c e s o f  Co m p u ter   S c ie n c e   fo r Ge o g ra p h ic I n fo rm a t io n   S y ste m s ,  v ol /i ss u e :   1 9 ( 3 ),   p p .   4 8 7 - 5 2 4 ,   2 0 1 5 .       B I O G RAP H I E S   O F   AUTH O RS        Th u   T h u   Za n   is  a   re se a r c h   c a n d i d a te  a t  Clo u d   C o m p u ti n g   L a b ,   Un iv e rsity   o f   Co m p u ter  S t u d ies   Ya n g o n .   He r  c u rre n t  re se a rc h   is   b a se d   o n   g e n e ra ti n g   sy n th e ti c   d a tas e t  f o r  m o v in g   o b jec ts,   w irele ss   n e tw o rk   o p e ra ti o n   a n d   c lo u d   c o m p u ti n g .   S h e   is  a ls o   a   m e m b e r  o f   IA EN G   (In tern a ti o n a l  A ss o c iatio n   o f   En g in e e r).         S a b a i  Ph y u   is  a   d e a n   o f   Clo u d   Co m p u ti n g   L a b   a t  Un iv e rsity   o f   Co m p u ter  S tu d ies ,   Ya n g o n   (UCS Y)  M y a n m a r.   S h e   is  in tere ste d   in   v ir tu a li z a ti o n   a n d   c l o u d   c o m p u ti n g .   S h e   c u rre n tl y   w o rk s  a t  th e   S o f twa re   De p a rtme n t,   UCSY  M y a n m a r.     Evaluation Warning : The document was created with Spire.PDF for Python.