I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute E ng in ee ring   ( I J E CE )   Vo l.   8 ,   No .   4 A u g u s t   201 8 ,   p p .   2 2 6 1 ~ 2 2 7 1   I SS N:  2 0 8 8 - 8708 DOI : 1 0 . 1 1 5 9 1 / i j ec e . v8 i 4 . p p 2 2 6 1 - 2271          2261       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   Spectral  Cluster i ng  and Va ntag e P o int  Index ing   f o Efficien Da ta Ret ri ev a l       R.   P us hp a la t ha 1 ,   K .   M ee na ks hi Su nd a ra m 2   1 De p a rtme n o f   Co m p u ter S c ien c e ,   Ko n g u   A rts  a n d   S c ien c e   Co ll e g e   (A u to n o m o u s),  Na n jan a p u ra m ,     Ero d e ,   T a m il   Na d u ,   In d ia   2 De p a rtme n o f   Co m p u ter S c ien c e ,   Ero d e   A rts  a n d   S c ien c e   Co ll e g e   (A u to n o m o u s),  Er o d e ,   T a m il   N a d u ,   I n d ia       Art icle  I nfo     AB ST RAC T   A r ticle  his to r y:   R ec eiv ed   J an   24 ,   2 0 1 8   R ev i s ed   Mar   2 5 ,   2 0 1 8   A cc ep ted   A p r   8 ,   2 0 1 8     Da ta  m in in g   is  a n   e ss e n ti a p ro c e ss   f o id e n ti fy in g   th e   p a tt e rn in   larg e   d a ta se ts  th ro u g h   m a c h in e   lea rn in g   tec h n iq u e a n d   d a tab a se   sy ste m s.   Clu ste rin g   o f   h ig h   d im e n sio n a d a ta  is  b e c o m in g   v e r y   c h a ll e n g in g   p ro c e ss   d u e   t o   c u rse   o f   d im e n sio n a li ty .   In   a d d it io n ,   s p a c e   c o m p lex it y   a n d   d a ta  re tri e v a p e rf o r m a n c e   wa n o im p ro v e d .   I n   o rd e t o   o v e rc o m e   th e   li m it a ti o n ,   S p e c tral  Clu ste rin g   Ba se d   VP  T re e   In d e x in g   T e c h n iq u e   is  i n tr o d u c e d .   T h e   tec h n iq u e   c lu ste rs  a n d   in d e x e th e   d e n se ly   p o p u late d   h ig h   d im e n sio n a d a ta  p o i n ts  f o e ffe c ti v e   d a ta r e tri e v a b a se d   o n   u se q u e ry .   A   No r m a li z e d   S p e c tral  Clu ste rin g   A lg o rit h m   is  u se d   to   g ro u p   sim il a h ig h   d im e n sio n a d a ta  p o in ts.   Af ter  th a t,   V a n tag e   P o in T re e   is  c o n stru c ted   f o i n d e x in g   th e   c lu ste re d   d a ta  p o i n ts  w it h   m in im u m   sp a c e   c o m p lex it y .   A t   las t,   in d e x e d   d a ta  g e ts  re tri e v e d   b a se d   o n   u se q u e ry   u sin g   V a n tag e   P o in T re e   b a se d   D a ta   Re tri e v a A l g o rit h m .     T h is  in   tu rn   h e lp to   im p ro v e   tru e   p o siti v e   ra te  w it h   m in i m u m   re tri e v a ti m e .   T h e   p e rf o r m a n c e   is  m e a su re d   in   term o f   sp a c e   c o m p lex it y ,   tru e   p o siti v e   ra te  a n d   d a ta  re tri e v a ti m e   w it h   El   Nin o   w e a th e d a t a   se ts   f ro m   UCI  M a c h in e   L e a rn in g   Re p o sito ry .   A n   e x p e ri m e n tal  re su lt   sh o ws   th a th e   p ro p o se d   tec h n i q u e   is   a b le  t o   re d u c e   th e   sp a c e   c o m p lex it y   b y   3 3 %   a n d   a lso   re d u c e th e   d a ta  re tri e v a ti m e   b y   2 4 %   w h e n   c o m p a re d   to   sta te - of - th e - a rt - w o rk s.   K ey w o r d :   C lu s ter i n g   Data   m i n i n g   Data   r etr iev al   Hig h   d i m e n s io n al  d ata  p o in ts   I n d ex ed   d ata   Van ta g p o in t r ee   Co p y rig h ©   2 0 1 8   In stit u te o 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 rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   K.   Me en ak s h i Su n d ar a m   Dep ar t m en t o f   C o m p u ter   Scie n ce ,     E r o d A r ts   an d   Scie n ce   C o lle g ( Au to n o m o u s ) ,     E r o d e,   T am il Na d u ,   I n d ia .   E m ail:  lect u r er k m s @ y ah o o . co m       1.   I NT RO D UCT I O N   C lu s ter i n g   is   m aj o r   task   to   g r o u p   th s i m ilar   h i g h   d i m e n s io n al  d ata  i n   d ata  m i n in g   a n d   u s ed   in   lar g n u m b er   o f   r ea l a p p lica ti o n s   s u c h   a s   s u c h   a s   w ea t h er   f o r ec ast,  s h ar tr ad in g ,   m ed ical  d ata  an al y s i s ,   ae r ial   d ata  an al y s is   a n d   s o   o n .   Data   m i n in g   ( DM )   i s   u s ed   to   ex tr a ct  u s e f u i n f o r m atio n   f r o m   lar g a m o u n o f   d ata.   Hig h - d i m e n s io n al  d ata   ar w i d e - r an g in g   in   s e v er al  ar ea s   o f   m ac h i n lear n i n g ,   s i g n al  a n d   i m a g e   p r o ce s s in g ,   co m p u ter   v is io n ,   p atter n   r ec o g n itio n ,   b io in f o r m atic s   a n d   s o   o n .   T h h i g h - d i m e n s io n alit y   o f   t h d ata  i n cr ea s e s   th co m p u tatio n a ti m a n d   m e m o r y   r eq u ir e m en t s   a n d   als o   s ig n i f ican tl y   c h a n g e s   t h eir   p er f o r m a n ce   d u to   i n ad eq u ate  n u m b er   o f   s a m p le s .   T h er ef o r e,   g r ea d e m an d   i n   h i g h   d i m e n s io n al   d ata  h an d l in g   i s   to   c lu s ter   t h e   d ata  alo n g   w i th   t h eir   u s er   r eq u ir e m e n t s .   T h s ev er al  d ata  m i n in g   tech n iq u h as  b ee n   d ev elo p ed   to   s h o w   th e   m aj o r   is s u es i n   t h f ie ld   o f   h i g h   d i m e n s io n al  d ata  clu s ter in g .       L o ca lit y   s en s iti v h as h i n g   ( L SH)   tech n iq u es  w as  d e s ig n ed   in   [ 1 ]   ad d r ess ed   n ea r - n ei g h b o r   s ea r ch   is s u es  f o r   h i g h - d i m en s io n a d ata.   Ho w e v er ,   th tr u p o s itiv r ate  w as  n o i m p r o v ed   u s i n g   L SH  tec h n iq u es .   An   i n cr e m en tal  s e m s u p er v i s ed   clu s ter in g   e n s e m b le  ap p r o ac h   ( I SS C E )   w a s   i n tr o d u ce d   in   [ 2 ]   w it h   g ai n   o f   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.  8 ,   No .   4 A u g u s t 2 0 1 8   :   2 2 6 1     2 2 7 1   2262   th r an d o m   s u b s p ac tec h n iq u an d   t h co n s tr ain t   p r o p ag atio n   ap p r o ac h   to   p er f o r m   t h h i g h   d i m e n s io n al  d ata   clu s ter i n g .   B u t,  th d ata  r etr iev al  p r o ce s s   w as  n o t c ar r ied   o u t in   ef f icie n m a n n er .   A   d is cr i m i n ati v e m b ed d ed   clu s ter i n g   f r a m e w o r k   w as  i n tr o d u ce d   in   [ 3 ]   f o r   clu s ter in g   th h ig h   d i m en s io n al  d ata  t h at  j o in s   s u b s p ac lear n i n g   a n d   clu s ter i n g .   T h o u g h   f o r m u lated   n o n c o n v e x   o p ti m izat io n   is s u es  w er ad d r ess ed ,   th f r a m e w o r k   w a s   n o s u itab le  i n   s u p er v is ed   ca s es.  A   s tr atif ied   s a m p lin g   m et h o d   w a s   p r esen ted   in   [ 4 ]   f o r   g en er ati n g   s u b s p ac co m p o n e n d ata s ets.  B u t,  th s p ac co m p lex i t y   w as  n o r ed u ce d   u s i n g   s tr ati f ied   s a m p li n g   m et h o d .   A   n e w   r an k i n g - b ased   h a s h i n g   f r a m e w o r k   w as  i n tr o d u ce d   in   [ 5 ]   m ap s   t h e   d ata  f r o m   v ar io u s   m o d alit ies  in to   h a m m in g   s p ac w h er cr o s s - m o d al  s i m ilar it y   ar ca lc u lated   b y   h a m m i n g   d is tan ce .   T h o u g h   th s p ac co m p lex i t y   w as  r ed u ce d ,   th d ata  r etr iev al  p r o ce s s   w a s   co m p li ca ted .   A   n e w   f u zz y   c - m ea n s   ( FC M)   m o d el  w it h   s p ar s r eg u lar izat io n   w a s   i n t r o d u ce d   in   [ 6 ]   th r o u g h   r ef o r m u lati n g   th FC M   o b j ec tiv f u n ctio n   i n to   w e ig h t ed   b et w ee n - clu s ter   s u m   o f   s q u ar f o r m   a n d   r eq u ir ed   th e   s p ar s r eg u lar izatio n   o n   w e ig h t s .   B u t,  d ata  r etr iev al  ti m w a s   n o r ed u ce d   u s i n g   F C m o d el.   I n ter est in g   S u b s p ac C l u s ter i n g   ( I SC )   alg o r it h m   w as  p r ese n te d   in   [ 7 ]   u til ized   th a ttrib u te  d ep en d en c y   m ea s u r f r o m   R o u g h   Set   th eo r y   to   r ec o g n ize  t h s u b s p ac es.  Ho wev er ,   it  f ailed   to   h a n d le  t h p r o b lem   o f   d en s el y   p o p u lated   d ata  p o in ts .   Mo d el - b ased   clu s ter in g   late n tr ait  ( MCL T )   m o d els  w a s   in tr o d u ce d   in   [ 8 ]   w it h   b lo ck   ef f e ct  p r esen s u i tab le  alter n ati v f o r   s a m p led   d ata.   T h MCL T   m o d w a s   n o co n s id er ed   s p ac a n d   ti m co m p lex it y   d u r i n g   th e   clu s ter i n g   p r o ce s s .     P r ed ictiv Su b s p ac C l u s ter i n g   ( P SC )   w as   in tr o d u ce d   in   [ 9 ]   f o r   clu s ter i n g   t h h i g h - d i m en s io n a l   d ata.   Ho w e v er ,   P SC   is   n o s u itab le  f o r   clu s ter i n g   o f   d e n s el y   p o p u lated   h i g h   d i m en s io n al  d ata  p o in ts .   A n   ef f icien h i g h - d i m e n s io n a in d ex in g   lib r ar y   ca lled   HDI d x   was  in tr o d u ce d   in   [ 1 0 ]   f o r   esti m ated   NN  s ea r ch .   I tr an s f o r m ed   t h i n p u h i g h - d i m en s io n a v ec to r s   in to   co m p a ct  b in ar y   co d es  in   e f f icie n a n d   s ca lab le  m a n n er   f o r   NN  s ea r ch   w it h   less er   s p a ce   co m p lex it y .   T h o u g h   s p ac co m p lex it y   w as   r ed u ce d ,   d at r etr iev al   w as   n o t   ca r r ied   o u in   e f f icie n m a n n er .   Ma h alan o b is   d is ta n ce   b as ed   lo ca d is tr ib u tio n   o r ien ted   s p ec tr al  clu s ter i n g   tech n iq u w as  d ev elo p ed   in   [ 1 1 ]   to   g r o u p   th d ata  in   d im en s io n al  s p ac e.   Ho w e v er ,   d ata  r etr iev al  w as  n o ca r r ied   o u t.    I n   o r d e r   to   o v er c o m th ab o v m en tio n ed   is s u es  s u c h   as  le s s   tr u p o s it iv r ate,   h ig h   s p ac an d   ti m co m p le x it y   d u r in g   clu s te r in g ,   lac k   o f   d ata  r etr iev al,   h an d le  d en s el y   p o p u lated   d ata  p o in ts   an d   s o   o n .   I n   o r d er   to   o v er co m s u c h   k in d   o f   is s u es,  Sp ec tr al  C l u s ter i n g   b ased   Van tag P o in T r ee   I n d ex in g   ( SC - VP T I )   T ec h n iq u is   in tr o d u ce d .   T h SC - VP T I   tech n i q u i s   d esi g n ed   f o r   e f f ic ien t   d ata  r etr iev a b ased   o n   t h u s er   q u er y   w it h   m in i m u m   ti m e.   T h co n tr ib u tio n   o f   o u r   r esear ch   w o r k   i n clu d es  as  f o llo w s Sp ec tr al  C lu s ter in g   B ased   VP   T r ee   I n d ex i n g   ( S C - VP T I )   T ec h n iq u clu s ter s   an d   in d e x es  t h d en s el y   p o p u lated   h ig h   d i m e n s i o n al  d ata  p o in ts   f o r   ef f icien d ata  r etr iev al  b ased   o n   th u s er   q u er y .   T h SC - V PT I   tech n iq u co n tai n s   t h r ee   m aj o r   co n tr ib u tio n s .   A f ir s t,  No r m alize d   Sp ec tr a C l u s ter i n g   Alg o r it h m   clu s ter s   th s i m ilar   h ig h   d i m e n s io n al   d ata  p o in ts   b ased   o n   s i m i lar i t y   s co r o f   d ata  p o in ts .   Seco n d ,   Va n ta g P o in t   T r ee   in d ex es  t h cl u s ter ed   h i g h   d i m e n s io n al   d ata   p o in ts   f o r   ef f icie n d ata  r etr iev al.   T h in d ex ed   d ata  p o in ts   ar r ep r esen ted   b y   cir cle.   T h V P   in d ex in g   r ed u ce s   th s p ac co m p le x it y   f o r   s to r in g   th m u lt i p le  h ig h   d i m e n s io n a d ata  p o in ts .   At  last ,   th in d ex ed   s i m ilar   d ata  p o in ts   g ets  r etr ie v ed   f r o m   th i n d ex i n g   tr ee   b ased   o n   th u s er   q u er y   w it h   t h h elp   o f   Van ta g e   P o in t T r ee   b ased   Data   R etr iev al  A lg o r it h m .   As a  r es u lt,   SC - VPT I   tech n iq u ac h iev e s   h i g h er   tr u e   p o s iti v r at e   w it h   m i n i m u m   d ata  r etr iev al  t i m e.   T h r est  o f   th p ap er   o r g an ized   as  f o llo w s .   I n   Sectio n   2 ,   th p r o p o s ed   SC - VPT I   tech n iq u i s   d escr ib ed   w it h   th e   h elp   o f   s tr u ct u r al  d i ag r a m .   I n   Sectio n   3 ,   ex p er i m en tal  e v al u atio n   i s   d is cu s s ed   an d   r esu lt  a n al y s i s   is   ca r r ied   o u w it h   tab les  a n d   g r ap h   i n   Sec tio n   4 .   s u m m ar y   o f   d i f f er en t   clu s ter i n g   tec h n iq u es   f o r   h i g h   d i m en s io n al   d ata  i s   r ev ie w ed   i n   S ec tio n   5 .   T h Secti o n   6   co n cl u d es  th e   p r esen ted   w o r k s .       2.   SPEC T RA L   CL U ST E R I N G   B ASE VP   T R E E   I ND E XI NG   T E CH N I Q UE   T h S p ec tr al  C lu s ter in g   B ase d   VP   T r ee   I n d ex in g   ( S C - VP T I )   T ec h n iq u i s   i n tr o d u ce d   to   clu s ter   a n d   in d ex   t h d en s el y   p o p u lated   h ig h   d i m e n s io n a d ata  p o in ts   f o r   ef f ec ti v d ata  r etr iev al  b ased   o n   th u s er   q u er y .   SC - VP T I   tech n iq u is   u s ed   f o r   clu s ter i n g   t h d en s d at p o in ts   a n d   in cr ea s e s   th d ata  r etr i ev al  r ate.   SC - VP T I   tech n iq u in tr o d u ce s   No r m ali ze d   Sp ec tr al  C lu s ter in g   A l g o r ith m   to   g r o u p   th s i m ilar   h i g h   d i m e n s io n a d ata  o b j ec ts .   T h en ,   SC - VP T I   tech n iq u co n s tr u ct s   Van tag P o in tr ee   f o r   in d ex in g   th cl u s t er ed   d ata  p o in ts   to   f o r m   t h i n d ex i n g   d atab ase  w i th   m i n i m u m   s p ac co m p le x it y .   Fin all y ,   S C - VP T I   tech n iq u u s e s   Van tag P o in t   tr ee   b ased   d ata  r etr iev al  alg o r ith m   to   ex tr ac t h u s er   r eq u e s ted   d ata  f r o m   i n d ex i n g   d atab ase  w it h   less er   d ata   r etr iev al  ti m co n s u m p tio n .   T h e   o v er all  s tr u c tu r al  d esi g n   o f   SC - VP T I   T ec h n iq u f o r   clu s ter in g   th d en s el y   p o p u lated   h ig h   d i m e n s io n al  d ata  p o in ts   is   d escr ib ed   in   Fi g u r 1 .   Fro m   F ig u r 1 ,   S C - VP T I   T ec h n iq u i n it iall y   co llect s   t h d en s el y   p o p u lated   h i g h   d i m en s io n al  d ata   p o in ts   f r o m   E l   Ni n o   w ea t h er   d ataset  as   in p u w h ic h   c o m p r i s es  co llect io n   o f   d en s el y   p o p u lated   h i g h   d i m en s io n al  d ata  p o in ts .   T h en ,   SC - VP T I   T ec h n iq u d esi g n ed   n o r m al ized   s p ec tr al  clu s t er in g   al g o r ith m   f o r   clu s ter i n g   t h d ata   p o in ts   f r o m   h i g h   d i m en s io n al   d atab ase .   T h en ,   S C - VP T I   T e ch n iq u co n s tr u ct s   Van ta g e   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       S p ec tr a l Cl u s teri n g   a n d   V a n ta g P o in t I n d ex in g   fo r   E fficien t D a ta   R etri ev a l ( R .   P u s h p a la t h a )   2263   P o in tr ee   f o r   in d ex in g   t h clu s ter ed   h ig h   d i m e n s io n al  d ata  p o in ts   w it h   m in i m u m   s p ac co m p le x it y .   Fi n all y ,   SC - VP T I   tech n iq u p er f o r m s   Van ta g P o in T r ee   b ased   d ata  r etr iev al  p r o ce s s   to   r etr ie v th u s er   r eq u e s ted   d ata  w it h   le s s er   d ata  r etr iev al  ti m e.   T h b r ief   d escr ip tio n   o f   n o r m alize d   s p ec tr al  cl u s ter i n g   an d   v a n tag p o i n tr ee   in d ex i n g   ar d escr ib ed   in   u p co m i n g   s ec tio n .                                 Fig u r 1 .   Ov er all  s tr u ctu r al  d e s ig n   o f   s p ec t al  cl u s ter in g   b ase d   VP   tr ee   in d ex in g   tec h n iq u e       2 . 1 .   No r m a lize s pect ra l c lu s t er ing   a lg o rit h m   I n   SC - VP T I   tech n iq u e,   n o r m alize d   s p ec tr al  clu s ter in g   tec h n iq u es  u s es  s p ec tr u m   ( ei g en v alu e s )   o f   s i m ilar it y   m atr i x   o f   h i g h   d i m en s io n al  d ata.   T h s im i lar it y   m atr i x   is   g i v e n   as  an   in p u t.  T h s i m ilar it y   m atr i x   co m p r is e s   q u an ti tati v esti m atio n   o f   th r elati v s i m ilar it y   f o r   ea ch   p air   o f   h ig h   d i m en s io n al  d ata  in   d ataset.   Sp ec tr al  C l u s ter in g   i s   to   f o r m   p air w i s s i m ilar it y   m atr ix   S ,   co m p u te   L ap lacia n   m atr i x   L   a n d   eig en v ec to r s   o f   L .   T h eig e n v ec to r   o f   n o r m alize d   g r ap h   L ap lacia n   is   r ela x atio n   o f   b i n ar y   v ec to r   r esu l th a r ed u ce s   n o r m alize d   cu o n   g r ap h .   T h No r m alize d   Sp ec tr al  C lu s ter in g   p r o ce s s   f o r   g r o u p in g   s i m ilar   d ata   p o in ts   is   s h o w n   in   b elo w   Fi g u r 2 .                                                   Fig u r 2 .   P r o ce s s   o f   n o r m a lize d   s p ec tr al  clu s ter in g   f o r   s i m ila r   g r o u p in g   d ata  p o in ts       Fro m   F i g u r 2 ,   n o r m alize d   s p ec tr al  clu s ter i n g   p r o ce s s   is   d escr ib ed   f o r   g r o u p in g   t h s i m ilar   d at a   p o in ts   b ased   o n   t h d ata  t y p e .   I n itiall y ,   t h s i m ilar it y   m atr ix   g ets   co n s tr u cted   a n d   t h en   lap lacia n   m atr i x   i s   S p e c t r a l   C l u st e r i n g         G r o u p t h e   si mi l a r   d a t a   p o i n t s   b a se d   o n   d a t a   t y p e     V a n t a g e   P o i n t   T r e e   I n d e x e s c l u st e r e d   d a t a   p o i n t s   El   N i n o   w e a t h e r   D a t a   S e t   Ef f e c t i v e   D a t a   R e t r i e v a l   b a se d   o n   u se r   q u e r y   u si n g   V a n t a g e   P o i n t   T r e e     C o n st r u c t   s i mi l a r i t y   mat r i x   C o n st r u c t   L a p l a c i a n   ma t r i x   D e t e r mi n e   N o r mal i z e d   L a p l a c i a n   m a t r i x   C o mp u t e   f i r st   K   e i g e n v e c t o r s   Emp l o y   k - me a n s t o   c l u st e r   d a t a   p o i n t   G r o u p i n g   o f   d a t a   p o i n t b a se d   o n   d a t a   t y p e   El   N i n o   w e a t h e r   d a t a se t     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.  8 ,   No .   4 A u g u s t 2 0 1 8   :   2 2 6 1     2 2 7 1   2264   s tr u ct u r ed   b ased   o n   th s i m i lar it y   s co r o b tain ed   f r o m   t h d ata  p o in ts .   I n   ad d itio n ,   n o r m al ized   s p ec tr al  clu s ter i n g   m atr i x   is   co n s tr u cte d   b y   ch a n g in g   r o w   v alu e s   o f   p r ev io u s l y   co n s tr u cted   m atr i x .   T h en ,   n o r m al ized   s p ec tr al  clu s ter i n g   m atr ix   u s ed   k - m ea n s   alg o r it h m   to   clu s ter   th d ata  p o in ts .   Fin all y ,   s i m ila r   h ig h   d i m en s io n al   d ata  p o in ts   ar g r o u p ed   to   f o r m   k - n u m b er   o f   clu s ter s   s u c h   as   s ea   s u r f ac te m p er at u r es,   r elativ h u m id it y ,   r ain f al l,  s u b s u r f ac te m p er at u r es,  air   te m p er atu r d ata  an d   s o   o n .   I n   SC - VP T I   tech n iq u e,   L et  {     b th s et  o f   d ata  p o in ts   w h er     v ar ies  f r o m   th v al u               ‟  in   d en s e l y   p o p u lated   h i g h   d i m en s io n al  d ata  ( i.e . ,   E Nin o   w ea t h er   d ataset) .   Den s el y   p o p u lated   h i g h   d i m en s io n al  d ataset   i s   r ep r esen ted   b y   a n   u n d ir ec ted   g r ap h                 w h er     d en o tes  th s et  o f   v er tices  ( i.e .   d ata  p o in ts )   an d       in d icate s   t h ed g r elatio n s h ip   o f   p air   o f   d ata  p o in ts .   I n itial l y ,   t h s i m ilar it y   m atr ix   i s   d escr ib ed   as  th s y m m etr ic  m atr i x   A .   T h d eg r ee   o f           d ata  p o in t   in   h i g h   d i m en s io n al  d ataset  is   m at h e m a ticall y   f o r m u la ted   as,                                                 ( 1 )     Fro m   E q u atio n   ( 1 ) ,             d en o tes  th s i m ilar it y   m atr i x   b et w ee n   t w o   ( i.e . ,         an d       )   d ata  p o in ts   f r o m   d en s el y   p o p u lated   h ig h   d i m en s io n al  d ata.         d en o te  th d eg r ee   o f           d ata  p o in t.  I n   s p ec tr al  clu s ter in g   p r o ce s s ,   th e   p air - w is s i m ilar it y   is   id en ti f i ed   w it h   h e lp   o f   s i m ilar it y   f u n ctio n .   T h Gau s s ia n   k er n el  f u n ct io n   i s   o n o f   t h e   m o s co m m o n l y   u s ed   s i m ilar it y   f u n ctio n s .   T h s i m ilar it y   b et w ee n   t w o   d ata  p o in ts         an d         is   m ea s u r ed   b ased   o n   t y p e   o f   d ata  w it h   h el p   o f   Ga u s s ian   k er n el   f u n ctio n .   Gau s s ia n   k er n e f u n ctio n   i n   s p ec tr al  clu s ter in g   i s   u s ed   to   ca lcu late  t h s i m i lar it y   s co r b et w ee n   t w o   d ata  p o in an d   it is   f o r m u lated   as,                                                          if            an d                           ( 2 )     Fro m   ( 2 ) ,   s i m ilar it y   m atr ix   i s   co n s tr u cted   f o r   ea ch   d ata  p o in i n   w h ic h                 r ep r esen ts   t h E u clid ea n   d is tan ce   b et w ee n   t w o   d ata  p o in ts         an d       Her e,   p a r am eter       m an a g e s   th w id t h   o f   th n e ig h b o r h o o d .     T h d iag o n al  m atr ix         is   d ef i n ed   as  th m atr ix   w it h   d eg r e es                                          o n   th d iag o n al.   I n   d iag o n al  m atr ix ,   ( i,i) th  ele m e n t   is   th s u m   o f   A‟ s   i n   t h i th  r o w .   Dia g o n al  m a tr i x   is   attai n ed   b y ,         (                                                                                             )                   ( 3 )     Fro m   ( 3 ) ,   th d iag o n al  m a tr i x   is   o b tain ed .   A f ter   o b tain in g   t h d iag o n a m a tr ix ,   t h u n n o r m ali s ed   L ap lacia n   m atr i x   is   co n s tr u cted   w it h   d at p o in ts   an d   g i v e n   b y ,                                 ( 4 )     Fro m   ( 4 ) ,       i s   t h L ap lacia n   m atr i x ,   r ep r esen ts   d ia g o n al   m atr i x   a n d   A   d en o tes   th e   s i m ilar it y   m atr ix .   T h en ,   th f ir s     lar g e s e ig en   v al u es  o f   L ap lacia n   m atr i x   an d   t h eir   co r r esp o n d in g   ei g e n v ec to r s   (                         )   in   co lu m n s   i s   d eter m i n ed   an d   th m atr i x       is   co n s tr u cted   b y ,                                                 ( 5 )             Fro m   ( 5 ) ,       m a tr ix   i s   co n s tr u cted .   T h en ,   n o r m al ized   L ap lacia n   m a tr ix       is   co n s t r u cted   th r o u g h   r en o r m alizi n g   ea c h   r o w   v al u o f       m a tr ix .   T h n o r m alize d   L ap lacia n   m atr i x   is   co n s tr u cted   b y ,                       (             )                   ( 6 )     Fro m   ( 6 ) ,   ea ch   r o w   o f       ac ts   a s   v er tex   an d   cl u s ter   t h e m   in to   m a n y   c lu s ter s   b y   u s i n g   k - m ea n s   cl u s ter i n g   alg o r ith m .   K - m ea n s   clu s ter   al g o r ith m   is   ca r r ied   o u w it h i n   clu s ter   s u m   o f   s q u ar es b y ,                                                               ( 7 )       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       S p ec tr a l Cl u s teri n g   a n d   V a n ta g P o in t I n d ex in g   fo r   E fficien t D a ta   R etri ev a l ( R .   P u s h p a la t h a )   2265   Fro m   ( 7 ) ,   k   n u m b er   o f   clu s te r s   ar f o r m ed ,         r ep r esen ts   t h cl u s te r   m ea n   a n d         s y m b o lizes  th d ata   p o in ts .   T h alg o r ith m ic  p r o ce s s   o f   n o r m a lized   s p ec tr al  clu s te r in g   al g o r ith m   i s   g i v e n   b elo w ,     A l g o r ith m   1 .   No r m alize d   Sp e ctr al  C lu s ter in g   A l g o r ith m   \ \ No r m alize d   Sp ec tr al  C l u s ter i n g   Alg o r it h m   I n p u t: Set  o f   d ata  p o in ts {     }‟ ,   C lu s ter   Nu m b er     .   Ou tp u t: Gr o u p in g   o f   d a ta  p o in ts   in   d i f f er e n t c l u s ter   Step   1 B eg in   Step   2 :           F o r   ea ch   d ata  p o in t in   E l N in o   w ea t h er   d ataset   Step   3 :                C o n s tr u ct   s i m il ar it y   m a tr ix       u s in g   ( 1 )   Step   4 :                       Dete r m in L ap lacia n   m atr ix       u s in g   ( 4 )   Step   5 :                C o m p u t No r m alize d   L ap lacia n   m atr i x       u s in g   ( 6 )   Step   6 :                               I d en ti f y   f ir s     eig e n v ec to r s   o f       an d   d en o te  it   as       u s i n g   ( 7 )   Step   7 :                 Use k - m ea n s   to   g r o u p   th e m   in to       clu s ter s .   Step   8 :                             C lu s ter   t h d ata  p o in ts   to   clu s ter             if   an d   o n l y   if   r o w       o f   th m atr ix       w a s                               ass ig n ed   to   clu s t er           Step   9 :            E n d   fo r       Step   1 0 R etu r n   C lu s ter i n g   r es u lts   o f   d ata  p o in ts   Step   1 1 E n d     A l g o r ith m   1   d escr ib es   th e   n o r m alize d   s p ec tr al  cl u s ter in g   a lg o r ith m ic  p r o ce s s .   B y   co n s tr u cti n g   th e   s i m ilar it y   m atr i x   an d   lap laci an   m a tr ix ,   t h s i m ilar   d ata  p o in ts   ar id en ti f ied .   T h en ,   n o r m al ized   lap lacia n   m atr i x   g et s   co n s tr u cted   a n d   id en ti f ied   k - ei g en   v ec to r s .   Af ter   t h id en ti f icat io n ,   K - m ea n s   al g o r ith m   is   e m p lo y ed   to   g r o u p   t h s i m ilar   d ata  p o in ts   to   f o r m   k - cl u s ter s .   T h u s ,   t h d ata   p o in ts   i n   d e n s el y   p o p u lated   h i g h   d i m en s io n   d ata  s i g n i f ican tl y   g r o u p ed   in   m an y   cl u s ter s   b ased   o n   th d ata  t y p e.       2 . 2 .   Va nta g po int  t re f o ind ex ing   clus t er ed  hig di m en s io n a l da t a     I n   SC - VP T I   tech n iq u e,   v a n ta g p o in tr ee   is   u s ed   f o r   i n d ex in g   th cl u s ter ed   h ig h   d i m e n s io n al  d ata.   I n itiall y ,   S C - VP T I   tech n iq u u s ed   n o r m alize d   s p ec tr al  clu s t er in g   a lg o r it h m   f o r   cl u s ter in g   th d ata  p o in t s   s u c as   s ea   s u r f ac te m p er atu r e s ,   r elativ h u m id it y ,   r ai n f a ll,  s u b s u r f ac e   te m p er at u r es  air   te m p er at u r d ata,   etc.   Af ter   cl u s ter i n g   th d ata  p o i n t s ,   in d ex in g   p r o ce s s   i s   ca r r ied   o u b y   Va n ta g P o in T r ee   f o r   r ed u cin g   t h s p ac co m p le x it y .   T h VP - T r ee   I n d e x in g   H i g h   Di m en s io n al  Da ta  P r o ce s s   is   d escr ib ed   in   F ig u r 3 .                                      Fig u r 3 .   P r o ce s s   o f   VP - T r ee   I n d ex i n g   Hig h   Di m e n s io n al  Da ta       Fig u r 3   s h o w s   t h p r o ce s s   o f   VP - tr ee   i n d ex i n g   h i g h   d im en s io n a d ata.   T h SC - VP T I   tech n iq u e   u s ed   VP - tr ee   f o r   i n d ex in g   t h clu s ter ed   d ata  p o i n ts .   I n   VP - tr ee ,   th s to r in g   o f   cl u s ter ed   d at p o in ts   is   d e n o ted   b y   cir cle.   E ac h   n o d o f   VP   tr ee   co n s i s ts   o f   an   i n p u t   p o in t   an d   a   r ad iu s .   A ll   t h le f t   ch i l d r en   o f   g i v e n   n o d ar p lace d   in s id t h cir cle  a n d   all  th e   r ig h c h ild r en   o f   a   g i v en   n o d ar p lace d   o u t s id t h cir cle.   T h tr ee   its el f   n o n ee d ed   to   k n o w   an y   in f o r m atio n   r eg ar d in g   w h at  i s   s to r ed   an d   its   n ee d   is   t h d is ta n ce   f u n ctio n   w h ich   s atis f ies   t h m etr ic  s p ac p r o p er ties .   A   cir cle  i s   ta k en   in to   co n s id er atio n   w i th   r ad iu s .   T h le f c h ild r en   ar e   all  p lace d   in s id th cir cle  a n d   th r ig h t c h ild r en   ar p lace d   o u ts id t h cir cle.   El   Nin o   w e a th e d a tas e t   S p e c tral  Clu ste rin g   VP - tree   I n d e x in g   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.  8 ,   No .   4 A u g u s t 2 0 1 8   :   2 2 6 1     2 2 7 1   2266   L et  u s   co n s id er   E Nin o   w ea th er   d ataset  i s   cl u s ter ed   in to   k   n u m b er   o f   cl u s ter s   co n s is o f       d ata  p o in ts .   Fo r   ea c h   n o d in   tr e e,   d ata  p o in cl u s ter   is   c h o s en   to   b t h v a n tag e   p o in t   b y   Va n ta g P o in t   Selectio n .   L e u s   co n s id er   clu s ter ed   d ata  p o in is   ch o s en   f o r   t h r o o n o d is          an d   μ   b e   m ed i an   o f   d is tan ce   v alu e s   o f   all  t h o th er   cl u s ter e d   d ata  p o in ts   i n             w i t h   r esp ec to                is   p ar titi o n ed   in to   t w o   s u b s ets  o f   ap p r o x i m atel y   eq u al  s ize s   a s           an d             is   g iv e n   b y ,               {           |                                   ( 8 )               {              |                                   ( 9 )     Fro m   ( 8 )   an d   ( 9 ) ,                     s y m b o lizes  th d is ta n ce   b et w ee n   d ata  p o i n cl u s ter s          an d      .   E ac h   s u b s et  lin k ed   to   o n n o d o f   VP - tr ee .   Fo r   ea ch   n o d e,   v an tag p o in is   c h o s en   to   s to r th cl u s t er ed   d ata  p o in ts   in   re s u lta n s u b s e t.  VP - tr ee   s to r es  m an y   d ata  p o in ts   a o n leaf   n o d e.   Fi n all y ,   t h w h o le  cl u s ter ed   d ata  p o in i s   s o r ted   o u t a s   b alan ce d   tr ee .     T h VP - tr ee   s tr u c tu r i s   s i m p le  w h er ea c h   n o d is   in   f o r m   (                          ) .        s y m b o lize s   v an ta g p o in an d       d en o tes  m ed ian   d is ta n ce   a m o n g   all  d ata   p o in ts   i n d ex ed   b elo w   t h at  n o d w h er ea s           an d           ar p o in ter s   o f   r ig h t a n d   lef t b r an c h es r esp ec ti v el y .   L e f t   b r an ch   o f   n o d in d ex es c lu s te r ed   d ata  p o in ts   w h o s d is tan ce s   f r o m        ar less   t h a n   o r   eq u al  to     .   C o n s e q u en tl y ,   r i g h t   b r an ch   o f   n o d in d ex e s   t h e   clu s ter ed   d ata  p o in t s   w h o s d is tan ce s   f r o m        ar g r ea ter   t h an   o r   eq u al  to     .   I n   leaf   n o d es,  r ath er   t h a n   p o in ter s   to   lef an d   r ig h b r an ch es,  r ef er e n ce s   to   clu s ter ed   d ata  p o in ts   ar k ep t.  T h m ed ia n   d is ta n ce   b et w ee n   v an ta g p o in      an d   th cl u s ter e d   d ata  p o in ts           i s   d eter m i n ed   b y ,                                                                   (1 0)     Fro m   ( 1 0 ) ,   m ed ia n   d is tan ce   is   m ea s u r ed .   Gi v en   d ata  s et  o f       clu s ter ed   d ata   p o in ts           {                                   ,   an d   m ed ia n   d is ta n ce   f u n ctio n                      ,   VP   tr ee   is   co n s tr u cted   b y   u s i n g   th f o llo w i n g   alg o r it h m ic  p r o ce s s ,     A l g o r ith m   2 .   VP   T r ee   b as ed   C lu s ter ed   Data   P o in t I n d ex in g   A l g o r ith m   // VP   tr ee   b ased   C lu s ter ed   Data   P o in t I n d ex in g   A l g o r ith m   I n p u t:      C lu s ter ed   d ata  p o in ts           {                                   Ou tp u t: C r ea te  VP   tr ee   f o r   I n d ex in g   o f   C l u s ter ed   Data   P o in ts   Step   1 : B eg in     Step   2 if   | DP C | =0 ,   t h e n   co n s tr u ct  e m p t y   tr ee   Step   3 :           m ed ian   o f                    )   |                 }   Step   4 :           F o r   ea ch   clu s ter ed   d ata  p o in t „           Step   5 :                     R an d o m l y   s elec t   v an ta g p o in      Step   6                     C alcu late  t h d is tan ce   f r o m   v an tag p o in      to   th d ata  p o in t „                                   u s in g   ( 1 0 )   Step   7 :                     C o m p u te  m ea n   an d   v ar ian ce   o f   d is ta n ce     Step   8 :                       if                          ,   th en   Step   9                                       C lu s t er ed   d ata   p o in           is   s to r ed   in   lef b r an ch   o f   tr ee   Step   1 0 :                 else   Step   1 1                                     C lu s te r ed   d ata  p o in         i s   s to r ed   in   r ig h b r an ch   o f   tr ee   Step   1 2 :                     e n d   if   Step   1 3 :       else fo r   Step   1 4 E n d                               B y   u s i n g   t h ab o v alg o r ith m   2 ,   clu s ter ed   d ata  p o in ts   ar ef f icie n tl y   s to r ed   in   VP   tr e s tr u ctu r e   b ased   o n   d ata  ty p e.   VP   tr ee   i n d ex i n g   m i n i m izes  t h o v er la p   s p ac an d   o p tim izes  t h r etr iev al  p ath   o f   i n d ex .   T h is   i n   tu r n   h e lp s   to   r ed u ce   th s p ac co m p le x it 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       S p ec tr a l Cl u s teri n g   a n d   V a n ta g P o in t I n d ex in g   fo r   E fficien t D a ta   R etri ev a l ( R .   P u s h p a la t h a )   2267   2 . 3 .   VP - t re ba s ed  da t a   re t riev a l   pro ce s s     Af ter   i n d ex i n g   th cl u s ter ed   d ata  p o in ts ,   S C - VP T I   tech n iq u p er f o r m s   VP - tr ee   b ased   d ata  r etr iev al   p r o ce s s   f o r   ef f icie n d ata  r etr iev al  p r o ce s s   b ased   o n   t h u s e r   q u er y .   Da ta   r etr iev al  i s   p r o ce s s   o f   r etr iev in g   th r elev a n d ata  f r o m   th i n d ex ed   d atab ase  b ased   o n   u s er   r eq u ested   d ata.   Fo r   r etr iev in g   th d ata,   u s er   q u er y   is   g i v en   as  a n   in p u t.  T h en ,   th u s er   q u er ied   d ata  ar e   s ea r ch ed   an d   r etr iev ed .   Fin all y ,   th r etr iev ed   d ata  ar tr an s m itted   to   th co r r esp o n d i n g   u s er .   T h d ata  r etr iev al  p r o ce s s   is   s h o w n   in   b elo w   Fi g u r 4 .             F ig u r 4 .   Data   r tr iev al  p r o ce s s es       Fig u r 4   ex p lai n s   th e   b lo ck   d iag r a m   o f   d ata  r etr ie v al  p r o ce s s .   Fo r   t h g iv e n   u s er   q u er y     ,   s et   o f   d ata  p o in ts   th at  ar w it h i n   th d is tan ce       o f       ar r etr iev ed   b y   s ea r ch   alg o r ith m .   T h alg o r ith m ic  p r o ce s s   o f   VP - T r ee   B ased   Data   R etr iev al   A l g o r ith m   is   e x p lai n ed   b elo w .       A l g o r ith m   3 .   VP - T r ee   B ased   Data   R etr iev a A lg o r it h m   // VP - T r ee   B ased   Data   R etr iev al  A l g o r ith m   I n p u t: U s er   q u er y                                 ,   Qu er y   r an g   ‟,   v a n ta g p o in    ,   an d   Me d ian   d is tan ce   M   Ou tp u t: I m p r o v ed   T r u P o s iti v R ate  o f   Da ta  R etr ie v al  an d   R ed u ce d   Data   R etr ie v al  ti m e   Step   1 : B eg in   Step   2 F o r   ea ch   User   q u er y         Step   3 :           if                          ,   th en   v an tag p o i n t a t th r o o t   Step   4 :                       if                                 th en     Step   5 :                               Sear ch   r ig h b r an ch   o f   tr ee   Step   6 :                                               else                              th en     Step   7 :                                                 S ea r ch   lef t b r an c h   o f   tr ee   Step   8 :                         E n d   if           Step   9 :             E n d   if           Step   1 0 :     if  b o th   s ea r ch   co n d it io n s   ar s atis f ied ,   th en   Step   1 1 :                   B o th   b r an ch es  o f   tr ee   is   s ea r ch ed   f o r   r etr iev i n g   u s er   q u er ied   d ata  p o in ts   Step   1 2 :                   Dis p lay   s ea r c h e d   d ata  p o in t to   u s er     Step   1 2 :     E n d   if   Step   1 3 : E n d   f o r       Step   1 4 E n d     B y   u s in g   ab o v al g o r ith m   3 ,   SC - VP T I   tech n iq u e f f icien tl y   r etr iev e s   d ata  p o in ts   f r o m   t h VP   tr ee   in d ex i n g   d atab ase  b ased   o n   th u s er   q u er y .   As  r esu lt,  SC - VPT I   tech n iq u e   i n cr ea s es  t h tr u p o s itiv r ate  o f   d ata  r etr iev al  an d   r ed u ce s   d ata  r etr iev al  ti m e.       3.   E XP E R I M E NT A L   SE T T I N G   T h Sp ec tr al  C lu s ter in g   B ase d   VP  T r ee   I n d ex in g   ( SC - VP T I )   T ec h n iq u is   i m p le m e n te d   in   J av a   L a n g u a g e   w it h   aid   o f   E Ni n o   d ataset  f r o m   U C I   m ac h i n le ar n in g   r ep o s ito r y .   T h E Nin o   d ataset  co m p r is e s   th o ce an o g r ap h ic  an d   s u r f ac m eteo r o lo g ical  r ea d in g s   f r o m   s eq u e n ce   o f   b u o y s   s i ted   all  o v er   th eq u ato r ial  P ac if ic.   T h d ata  is   p r ed ictab le  to   ass is in   a n d   p r ed ictio n   o f   E Nin o /So u t h er n   Oscill at i o n   ( E NSO)   cy c les.  T h d ataset  ch ar ac ter is tics   ar s p atio - te m p o r al  an d   attr ib u te  ch ar ac ter is t ics  is   b o th   r ea an d   in teg er .   I n   ad d itio n ,   n u m b er   o f   i n s ta n ce s   ar 1 7 8 0 8 0   an d   n u m b er   o f   attr ib u tes  ar 1 2 .   E Nin o   d ataset  in c lu d es  t h e   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.  8 ,   No .   4 A u g u s t 2 0 1 8   :   2 2 6 1     2 2 7 1   2268   attr ib u tes  li k d ate,   latitu d e,   l o n g it u d e,   zo n al  w i n d s   ( w e s t< 0 ,   ea s t>0 ) ,   m er id io n al  w i n d s   ( s o u th <0 ,   n o r t h >0 ) ,   r elativ h u m id it y ,   air   te m p er a tu r e,   s ea   s u r f ac te m p er atu r an d   s u b s u r f ac te m p er at u r es  d o w n   to   d ep th   o f   5 0 0   m eter s .       4.   RE SU L T S AN D I S CU SS I O NS   T h r esu lt  an al y s is   o f   S C - VP T I   tech n iq u is   co m p ar ed   ag ai n s w it h   ex i s ti n g   t w o   ap p r o ac h es  n a m el y   L o ca lit y - Sen s iti v Has h i n g   ( L SH)   [ 1 ]   an d   in cr e m en ta s em s u p er v is ed   clu s ter in g   en s e m b le  ( I SS C E )   [ 2 ]   r esp ec tiv el y .   T h p er f o r m a n ce   o f   SC - VP T I   tech n iq u e   i s   ev a lu ated   o n   v ar io u s   f ac t o r s   s u c h   a s   s p ac co m p le x it y ,   d ata  r etr iev al  ti m e   an d   tr u p o s itiv r ate  w it h   h el p   o f   tab les an d   g r ap h s .     4 . 1 .   Sp a ce   co m plex it y   Sp ac co m p le x it y   i s   d ef in ed   as  th a m o u n o f   m e m o r y   s p ac r eq u ir ed   f o r   clu s ter in g   an d   in d ex in g   th d en s el y   p o p u lated   h i g h   d i m e n s io n a d ata.   T h s p ac co m p le x it y   i s   m ea s u r ed   in   ter m s   o f     Me g B y tes ( MB )   an d   f o r m u l ated   as,                                                                                                       ( 1 1 )     Fro m   ( 1 1 ) ,       d en o tes  th n u m b er   o f   d ata   p o in ts   tak en   f o r   cl u s ter i n g   p r o ce s s .   W h en   t h s p ac co m p lex it y   i s   less er ,   th tec h n iq u is   s aid   to   b m o r ef f icie n t.   T ab le  1   d escr ib es  th s p ac co m p le x it y   v a lu e s   o b tain ed   b ased   o n   d if f er en n u m b er   o f   d ata  p o in ts   tak en   in   th r a n g e   o f   5 0 - 5 0 0 .   Fro m   th tab le  v al u e,   p r o p o s ed   SC - VP T I   tech n iq u h a s   les s er   s p ac co m p le x it y   d u r in g   clu s ter in g   an d   i n d ex i n g   th d en s el y   p o p u lated   h ig h   d i m en s io n al  d ata  p o in t s   w h e n   co m p ar ed   to   L SH   T ec h n iq u an d   I SS C E   A p p r o ac h   r esp ec tiv el y .   B esid es,  w h e n   th n u m b er   o f   d ata  p o in ts   d u r in g   clu s ter in g   an d   in d ex i n g   p r o ce s s   in cr ea s e s ,   th s p ac co m p le x it y   also   g et s   i n cr ea s ed   in   all  t h r ee   m et h o d s .       T ab le  1 . T ab u latio n   f o r   Sp ac C o m p le x it y   N u mb e r   o f   D a t a   P o i n t s   S p a c e   C o mp l e x i t y   ( M B )   L S H   Te c h n i q u e   I S S C A p p r o a c h   SC - V P TI   t e c h n i q u e   50   2 6 . 3 6   2 3 . 7 8   1 4 . 3 2   1 0 0   2 8 . 1 2   2 5 . 1 4   1 6 . 3 4   1 5 0   2 9 . 8 9   2 7 . 9 6   1 7 . 9 8   2 0 0   3 1 . 7 8   2 9 . 1 7   1 9 . 2 3   2 5 0   3 3 . 9 8   3 1 . 5 4   2 1 . 5 9   3 0 0   3 5 . 6 3   3 3 . 9 8   2 3 . 8 7   3 5 0   3 7 . 8 9   3 4 . 5 2   2 5 . 9 8   4 0 0   3 9 . 2 7   3 7 . 1 2   2 7 . 4 5   4 5 0   4 1 . 9 6   3 8 . 3 3   2 9 . 7 5   5 0 0   4 2 . 3 4   4 0 . 1 5   3 1 . 4 7         B u t,  th s p a ce   co m p le x it y   u s i n g   p r o p o s ed   SC - VP T I   te ch n iq u is   less er .   T h is   is   b ec au s o f   ap p licatio n   o f   n o r m alize d   s p ec tr al  clu s ter in g   al g o r it h m   an d   VP   b ased   C l u s ter ed   Da ta  P o in t   I n d ex i n g   A l g o r ith m   in   SC - VP T I   tech n iq u w h er it   ef f icie n tl y   g r o u p   an d   in d e x   t h h ig h   d i m en s io n a d ata .   I n   n o r m alize d   s p ec tr al  cl u s ter i n g   alg o r it h m ,   t h s i m i lar it y   m atr i x   an d   lap lacia n   m atr i x   ar co n s tr u cted   to   id en ti f y   s i m ilar   d ata  p o in ts .   F o llo w ed   b y ,   t h K - m ea n s   al g o r ith m   is   ap p lied   to   g r o u p   t h s i m ilar   d ata  p o i n ts   to   co n s tr u ct   k - cl u s ter s .   B y   ap p ly in g   an   in d e x i n g   al g o r ith m ,   s et  o f   d ata   p o in ts   t h at  ar w it h in   t h d is tan ce   ar e   co r r ec tly   i n d ex ed   i n   r i g h an d   lef b r an c h e s   r esp ec tiv e l y .   I n   VP   tr ee ,   lef b r an c h   o f   n o d in d ex e s   cl u s ter ed   d ata  p o in ts   w h o s d is ta n ce s   f r o m   v a n tag p o in ar les s   th a n   o r   eq u al  to   Me d ian   d is tan ce .   A cc o r d in g l y ,   r ig h t   b r an ch   o f   n o d in d ex es  t h cl u s ter ed   d ata  p o in ts   w h o s d is t an ce s   f r o m   v a n tag p o in ar g r ea ter   th an   o r   eq u al  to   Me d ian   d is tan ce .   B ased   o n   in d e x in g   al g o r ith m ,   th d e n s el y   p o p u lated   clu s ter ed   d at ar s to r ed   in   an   ef f icien m a n n er   w i th   le s s   s p ac co m p le x it y .   A s   r esu lt,  p r o p o s ed   SC - VP T I   tech n iq u e   r ed u ce s   th s p ac e   co m p le x it y   o f   d en s el y   p o p u lat ed   h ig h   d i m en s io n al  d ata  b y   3 5 as  co m p ar ed   to   L SH  T ec h n iq u e   [ 1 ]   an d   3 0 %   as c o m p ar ed   to   I SS C E   A p p r o ac h   [ 2 ]   r esp ec tiv el y.     4 . 2 .   T rue  po s it iv ra t e   T r u p o s itiv r ate  ( T P R )   o f   d ata  r etr iev al  is   d escr ib ed   as   th r atio   o f   n u m b er   o f   co r r ec tl y   r etr iev ed   d ata  p o in ts   b ased   o n   u s er   q u e r y   to   t h to tal  n u m b er   o f   d ata   p o in ts .   T h tr u p o s iti v r ate   o f   d ata  r etr ie v al  i 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       S p ec tr a l Cl u s teri n g   a n d   V a n ta g P o in t I n d ex in g   fo r   E fficien t D a ta   R etri ev a l ( R .   P u s h p a la t h a )   2269   m ea s u r ed   in   ter m s   o f   p er ce n ta g es ( %)  an d   f o r m u lated   as,                                                                                                                                                                                 * 1 0 0         ( 1 2 )     w h e n   th tr u p o s itiv r ate  is   h ig h er ,   t h tech n iq u is   s aid   to   b m o r ef f icie n t.   Fig u r 5   p o r tr ay s   t h tr u p o s itiv r ate  m ea s u r o f   d en s el y   p o p u lated   h ig h   d i m en s io n al  d ata  v er s u s   n u m b er   o f   d ata  p o in ts   i n   r an g o f   5 0 - 5 0 0 .   Fro m   f i g u r e,   p r o p o s ed   SC - VP T I   tech n iq u h as   h i g h er   tr u p o s i t iv e   r ate  d u r in g   r etr ie v i n g   th e   d ata   p o in ts   b ased   o n   th e   u s er   q u er y   f r o m   th e   in d e x i n g   d atab ase  w h e n   co m p ar ed   to   L SH   T ec h n iq u a n d   I SS C E   A p p r o ac h   r esp ec ti v el y .   I n   ad d itio n ,   w h en   th e   n u m b er   o f   d ata  p o in ts   d u r in g   clu s ter i n g   an d   i n d ex i n g   p r o ce s s   i n cr ea s es,  t h e   tr u p o s iti v r ate  also   g et s   i n cr ea s ed   in   all  t h r ee   m et h o d s .   Ho w e v er ,   th e   tr u p o s i tiv e   r at u s in g   p r o p o s ed   SC - VP T I   te ch n iq u i s   h ig h er .   T h is   is   b ec au s o f   ap p licatio n   o f   Va n ta g P o in b a s ed   C l u s t er ed   Data   P o in t   I n d ex i n g   A l g o r ith m   an d   Van ta g e   P o in b a s ed   Data   R etr ie v al  A l g o r ith m   i n   SC - VP T I   tech n i q u w h er it  ef f ic ien tl y   s ea r c h es a n d   r etr iev es t h ex ac t u s er   r eq u ested   d ata           Fig u r 5 .   Me asu r e m en t o f   T r u P o s itiv r ate       T h v an ta g p o in tr ee   is   co n s tr u cted   f o r   in d ex in g   t h clu s te r ed   d ata  p o in ts   an d   it   s to r ed   in   leaf   a n d   r ig h b r an c h   o f   tr ee .   Af ter   th at,   Data   r etr iev al  is   p r o ce s s   o f   r etr iev in g   th s i m ilar   d ata  f r o m   th i n d ex ed   d atab ase  b ased   o n   u s er   q u er y   r eq u ested   d ata.   Fo r   r etr iev i n g   t h d ata  p o in t s ,   b o th   b r an c h es  o f   t h v an ta g e   p o in tr ee   ar s ea r c h ed   an d   d is p lay ed   t h d ata  p o in ts   to   u s er s   ac co r d in g   to   th eir   u s er   r eq u ir e m en ts .   T h is   h elp s   to   co r r ec tly   r etr ie v t h s i m i la r   d ata  p o in ts   i n   o r d er   to   ar ch iv h i g h   tr u p o s iti v r ate  i n   a n   ef f icien w a y .   A s   a   r esu lt,  p r o p o s ed   SC - VP T I   tec h n iq u i n cr ea s es  th e   tr u p o s i tiv r ate  o f   d e n s el y   p o p u lated   h i g h   d i m e n s io n al  d ata  b y   2 2 % a s   co m p ar ed   to   L SH T ec h n iq u e   [ 1 ]   an d   1 2 % a s   co m p ar ed   to   I SS C E   A p p r o ac h   [ 2 ]   r esp ec tiv ely .     4 . 3 .   Da t a   re t riev a l t i m e   Data   R etr iev al  T i m is   d ef in ed   as  am o u n o f   ti m ta k e n   f o r   r etr iev in g   th d a ta  p o in ts   f r o m   th e   in d ex i n g   d atab ase.   I t is  m ea s u r ed   in   ter m s   o f   m ill is ec o n d s   ( m s ) .   Data   R e tr iev al  T i m is   f o r m u la ted   as,                                                                                                      ( 1 3 )     Fro m   ( 1 3 ) ,       r ep r esen ts   n u m b er   o f   d ata  p o in ts .   W h en   t h d ata  r etr iev al  ti m is   le s s er ,   th m et h o d   is   s aid   to   b m o r ef f icie n t.    Fig u r 6   d escr ib es  th d ata  r etr iev al  ti m m ea s u r o f   d en s el y   p o p u lated   h ig h   d i m e n s io n al  d ata  v er s u s   n u m b er   o f   d ata  p o in ts   i n   r an g o f   5 0 - 5 0 0 .   Fro m   f i g u r e,   p r o p o s ed   SC - VP T I   tech n iq u co n s u m es  le s s er   ti m d u r i n g   r etr iev i n g   t h d ata  p o in ts   b ased   o n   t h u s er   q u e r y   f r o m   th i n d ex in g   d atab ase   w h e n   co m p ar ed   to   L SH   T ec h n iq u a n d   I SS C E   A p p r o ac h   r esp ec ti v el y .   I n   ad d itio n ,   w h en   th e   n u m b er   o f   d ata  p o in ts   d u r in g   clu s ter i n g   an d   in d e x i n g   p r o ce s s   i n cr ea s es,  t h d ata  r etr iev a ti m al s o   g ets  i n cr ea s ed   in   all  th r ee   m e th o d s .   Ho w e v er ,   th d ata  r etr iev al  ti m u s i n g   p r o p o s ed   SC - VP T I   tech n iq u is   le s s er .   T h is   is   d u to   th Van tag e   P o in b ased   C lu s ter ed   Data   Po in t   I n d ex i n g   A l g o r ith m   a n d   R etr iev al  A l g o r ith m   i n   SC - V PT I   tech n iq u w h er e   it  ef f icie n tl y   s ea r ch e s   d ata  an d   r etr iev es  w it h   m in i m al  ti m e .   An   i n d ex i n g   al g o r it h m   e f f ec ti v el y   s to r es  t h d ata  w ith   t w o   d if f er e n b r an c h es  n a m e l y   le f t   an d   r ig h t   an d   it   is   d en o tes   as   cir cles.  T h is   h e lp s   to   e f f ec ti v el y   s to r t h cl u s ter ed   h i g h   d i m en s io n al   d ata  i n   t h ese   t w o   b r an ch es  o f   n o d e.   Af ter   in d e x in g   t h d ata,   d ata  r etr iev al  f r o m   i n d ex   d atab ase  is   ca r r ied   o u u s i n g   VP - T r ee   B ased   Data   R etr ie v al  Alg o r it h m .   Fo r   ea c h   r eq u e s ted   u s er   q u er y ,   th e   s i m ilar   d ata  p o in ts   ar e   s ea r c h ed   f r o m   th e   in d ex i n g   d atab ase.   T h is   h elp s   to   r ed u ce   th d ata  r etr iev al  tim o f   d en s el y   p o p u lated   h ig h   d im e n s io n al  d ata.   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.  8 ,   No .   4 A u g u s t 2 0 1 8   :   2 2 6 1     2 2 7 1   2270   As  r es u lt,   p r o p o s ed   SC - VP T I   tech n iq u r ed u ce s   d ata  r etr iev al  t i m e   o f   d en s el y   p o p u late d   h i g h   d i m e n s io n al   d ata  b y   1 7 % a s   co m p ar ed   to   L SH T ec h n iq u e   [ 1 ]   an d   3 0 % a s   co m p ar ed   to   I SS C E   A p p r o ac h   [ 2 ]   r esp ec tiv ely .           Fig u r 6 .   Me a s u r e m en t o f   Dat R etr iev al  T i m e       5.   RE L AT E WO RK S   A   s u r p r is i n g   s i m p le  m et h o d   w a s   i n tr o d u ce d   in   [ 1 2 ]   f o r   ad d r ess in g   th ANN  i s s u es   w i th   h i g h   ac cu r ac y   r es u lt s   an d   n ee d s   les s er   n u m b er   o f   r a n d o m   I /O.   B u t,  b in ar y   in d e x   s tr u ct u r r ed u ce s   t h s p ac an d   it  f ailed   to   co n s id er   th p er f o r m a n ce   o f   tr u p o s iti v r at in   th p r o ce s s   o f   d ata  r etr iev al.   A   n e w   s e m i - s u p er v i s ed   h as h in g   m e th o d   was  i n tr o d u ce d   i n   [ 1 3 ]   w ith   p air w i s s u p er v is ed   i n f o r m atio n   c o m p r i s in g   o f   m u s t - lin k   an d   ca n n o t - li n k .   T h d e s ig n ed   m et h o d   in cr ea s ed   th e   in f o r m a tio n   p r o v id ed   b y   ev er y   b it  alo n g   w ith   lab eled   d ata  an d   th e   u n lab ele d   d ata.   A   c lu s ter in g   al g o r it h m   ca lled   SUB SC AL E   w as   in tr o d u ce d   in   [ 1 4 ]   to   id en ti f y   th e   n o n - tr iv ial  s u b s p ac clu s ter s   w i th   les s er   co s a n d   it   n ee d ed   o n l y   k   d at ab ase  s ca n s   f o r   k - d i m en s io n al  d atase ts .   n e w   p en al ized   f o r w ar d   s e lectio n   tec h n iq u e   in   [ 1 5 ]   m i n i m ized   h ig h   d i m e n s io n al  o p ti m izat io n   is s u es  to   m a n y   o n d i m e n s i o n al  o p ti m izatio n   i s s u es  t h r o u g h   s elec t in g   th b est  p r ed icto r .   B u t,  th d ata  r etr iev al  ti m w as  n o r ed u ce d   u s i n g   p en alize d   f o r w ar d   s elec tio n   tech n iq u e.   C o n s tr ai n t - P ar titi o n i n g   K - Me a n s   ( C OP - KM E A N S)  clu s ter in g   alg o r ith m   w a s   i n tr o d u ce d   in   [ 1 6 ]   f o r   clu s ter in g   h ig h   d i m e n s io n al  d ata  an d   to   m i n i m ize  t h co s t h r o u g h   r e m o v i n g   th e   n o is y   d i m en s io n s .   P r ed ictiv S u b s p ac C l u s ter in g   ( P SC )   w as   in tr o d u ce d   i n   [ 1 7 ]   f o r   clu s ter i n g   t h h ig h - d i m e n s io n al  d ata.   B u t,  P SC   is   n o s u itab le  f o r   d en s el y   p o p u lated   h ig h   d i m en s io n al  d ata  p o in t s .     Dis cr i m in at iv e   E m b ed d ed   C l u s ter i n g   ( DE C )   w a s   ca r r ied   o u i n   [ 1 8 ]   th at  co m b i n es   th s u b s p ac e   lear n in g   an d   clu s ter i n g .   Ho wev er ,   DE C   co n s u m ed   lar g a m o u n o f   ti m f o r   d ata  r etr iev al.   H - cl u s ter i n g   alg o r ith m   w a s   d esi g n ed   i n   [ 1 9 ]   to   m i n i m ize  t h s p ac co m p lex i t y   d u r in g   h ig h   d i m en s i o n al  d ata  clu s ter in g .   Hier ar ch ical  A cc u m u lativ e   C l u s ter i n g   A l g o r ith m   w a s   i n tr o d u ce d   in   [ 2 0 ]   to   clu s ter   t h h i g h   d i m en s io n al   d ata   w it h   h ig h er   cl u s ter i n g   ac c u r ac y .   Ho w e v er ,   th d esi g n ed   alg o r ith m   n ee d s   lar g a m o u n o f   m e m o r y   s p ac e.     r o b u s m u lti  o b j ec tiv s u b s p ac clu s ter i n g   ( MO S C L )   alg o r ith m   w as  p r esen ted   in   [ 2 1 ]   f o r   h ig h - d i m e n s io n a l   clu s ter i n g   w it h   h ig h er   ac cu r a c y   o f   s u b s p ac cl u s ter i n g .   B u t,  th s p ac co m p lex it y   r e m ain ed   u n ad d r ess ed   u s i n g   MO SC L   a lg o r it h m . Gr ap h - b ased   cl u s ter in g   w a s   d ev e l o p ed   in   [ 2 2 ]   to   clu s ter   th e   w e b   s ea r ch   r es u lt s   w i th   h ig h   cl u s ter i n g   q u al it y .   Ho w e v er ,   th d en s el y   p o p u late d   clu s ter in g   o n   h i g h   d i m en s io n al  d ata  w as  n o t   p er f o r m ed .   An   in cr e m en tal - c l u s ter i n g   ap p r o ac h   w as  d e v elo p ed   in   [ 2 3 ]   f o r   co n s tr u cti n g   clu s ter   b ased   o n   s elec ti n g   a n   o p ti m al  t h r es h o ld   v alu e.   B u t,  ef f icie n t d ata  r etr iev al  w as  n o t p er f o r m ed   w ith   m in i m u m   ti m e.           6.   CO NCLU SI O N   An   ef f icie n Sp ec tr al  C lu s ter i n g   B as ed   VP   T r ee   I n d ex in g   ( SC - VP T I )   T ec h n iq u is   d e v elo p ed   t o   en h a n ce   th e   d ata  r etr ie v al  p e r f o r m an ce   b ased   o n   u s er   q u e r y   w it h   les s er   s p ac co m p lex it y   a n d   h i g h er   tr u e   p o s itiv r ate.   E x i s ti n g   lo ca lit y   s en s iti v h a s h i n g   ( L SH)   tech n iq u e s   e m p lo y ed   f o r   n ea r - n ei g h b o r   s ea r ch   i s s u e s   b u it  f ailed   to   ad d r ess   r etr i ev al  o f   h i g h   d i m en s io n al   d ata.   An   i n cr e m en ta s e m s u p er v is ed   cl u s ter i n g   en s e m b le  ap p r o ac h   n o co n s i d er ed   th r etr iev al  p r o ce s s .   T h ese  p r o b le m s   ar ad d r ess ed   b y   u s in g   SC - VP T I   T ec h n iq u e.   T h r ee   p r o ce s s in g   s tep s   ar p r esen ted   f o r   i m p r o v in g   th h i g h   d i m e n s io n al  d ata  clu s ter i n g .   A f ir s t,   No r m a lized   Sp ec tr al  C lu s ter i n g   tec h n iq u in   S C - VP T I   tec h n iq u g r o u p s   t h s i m ilar   h i g h   d i m en s io n a d ata  p o in ts   to   f o r m   cl u s ter s   b ased   o n   s i m ilar it y   m a tr ix   w h ic h   co m p r i s es  q u a n ti tati v e   esti m at io n   f o r   ea ch   p air   o f   d ata  in   d ataset.   Af ter   t h at,   v an tag e   p o in tr ee   i n d ex i n g   is   p er f o r m ed   f o r   clu s ter in g   t h e   d ata  p o in ts .   T h ese   p o in ts   ar s to r ed   in   lef an d   r ig h b r an ch e s   o f   tr ee .   T h is   h e lp s   to   r ed u ce   th s p ac co m p lex it y .   Fi n all y ,   t h Evaluation Warning : The document was created with Spire.PDF for Python.