I n t ern a t i o n a l   J o u rn a l   o f   A d v a n ces   i n   A p p l i ed   S ci en ces   ( I J A A S )   V o l .   7 ,   N o .   1 ,   M ar ch   20 1 8 ,   pp .  29 ~ 37   I S S N 225 2 - 88 14 ,   D O I 10. 115 91 /ij a a s . v7 . i 1 . p p 29 - 37             29       Jo u r n al   h om e pa ge h t t p : / / i a e s co r e . c o m/ o n l i n e / i n d e x . p h p / I J A A S   G ra ph B a s e d W or kl oa d   D r i ve n P ar t i t i o ni ng  Sys t e m  by  U s i ng   M o ngo D B       A r v i n S a h u,  Sw a t i   A hi r r a o     D e p a rt m e nt   of   C om put e r   E ngi ne e r i ng ,   S y m bi os i s   I nt e r na t i o na l   U ni ve r s i t y ,   I ndi a       A rt i cl I nf o     A B S T RA C T   Ar t i c l e   h i s t o r y :   R ecei v ed   Ma 2 4 ,   2 01 7   Re v i s e d   J a 18 ,   201 8   A ccep t e d   F eb   11 ,   2 01 8       T he  w e b  a ppl i c a t i ons  a nd w e bs i t e s  of t he  e n t e rpr i s e s  a re  a c c e s s e d b y  a  hug e   num be r of us e r s  w i t h t he  e xpe c t a t i on of  re l i a b i l i t y   a nd h i gh a va i l a bi l i t y .   S oc i a l  n e t w orki n g s i t e s  a r e  ge n e r a t i ng  t he  d a t a  e x pone nt i a l l y   l a rg e  a m ount  of  da t a .  It  i s   a  c ha l l e ngi ng t a s k t s t ore  da t a  e ff i c i e nt l y .  S Q L  a nd  N oS Q L  a re   m os t l y  us e d t o s t ore  da t a .  A s  R D BM S  c a nnot  ha ndl e  t he  uns t ru c t ure d da t a   a nd huge  vol um e  of da t a ,  s o N o S Q L  i s  be t t e r c hoi c e  for w e a ppl i c a t i ons .   G ra ph da t a ba s e   i s  one  of  t he   e ff i c i e nt  w a y s  t o  s t ore  da t a   i n N oS Q L .  G ra ph   da t a b a s e  a l l ow s  us  t o s t ore   da t a  i n t h e  form  of re l a t i on.  In G ra ph  re pre s e nt a t i on  e a c h t up l e   i s  re pre s e nt e d b y   n ode  a nd  t he  r e l a t i ons hi i s   re pre s e nt e d b y   e dge .  Bu t ,   t o h a n dl e  t h e   e xpone nt i a l l y   grow t h of   da t a  i nt o  a   s i ngl e  s e rve r m i ght  de c re a s e   t h e  pe rform a nc e   a nd i nc r e a s e s  t he  re s pons e   t i m e .  D a t a  pa r t i t i oni ng i s  a  good  c hoi c e  t o m a i n t a i n a  m ode r a t e  p e rform a nc e   ev en  t h e w o r k l o ad  i n cr eas es . T h er e ar e m an y   d at a p ar t i t i o n i n g  t ech n i q u e s   l i ke  Ra ng e ,  H a s h a nd Round robi n but  t he y  a re  not  e ffi c i e nt  fo r t he  s m a l l   t ra ns a c t i ons  t ha t  a c c e s s  a  l e s s  num be r of t upl e s .  N oS Q L  da t a  s t ore s  provi de   s c a l a b i l i t y   a nd a va i l a bi l i t y  b y  us i ng va ri ous  pa rt i t i oni ng m e t ho d s .  T o  acc es s   t he  S c a l a b i l i t y ,   G ra ph pa rt i t i on i ng i s  a e ffi c i e nt  w a y  t h a t   c a n  be  e a s i l y   r ep r es en t  an d  p r o ces s  t h at  d at a . T o  b al an ce t h e l o ad  d at a ar e  p ar t i t i o n ed   hori z ont a l l y  a nd  a l l o c a t e  da t a  a c r os s  t he  ge ogra phi c a l  a va i l a bl e  da t a  s t ore s .  If  th e  p a r t itio ns  a r e  not  form e d prope rl y   re s ul t  be c om e s  e xpe ns i ve  di s t ri but e d   t ra ns a c t i ons  i n t e rm s  of re s pons e  t i m e .  S o t he  p a rt i t i on i ng of t he   t upl e  s houl d   be  ba s e d  on r e l a t i on .  In  propos e d s y s t e m ,  S c h i s m  t e c hni que  i s  us e d for   pa rt i t i oni ng t h e  G ra ph.  S c hi s m  i s  a  w orkl o a d a w a re  gr a ph  pa rt i t i oni ng   t e c hn i que .  A ft e r  pa rt i t i on i ng t he  re l a t e d t upl e s   s houl d c om e  i nt o a  s i ngl e   pa rt i t i on.  T h e  i ndi vi dua l  node   from  t he  gra ph i s   m a ppe d t o t he  uni que   pa rt i t i on.  T h e  o ve ra l l  a i m  of G ra ph pa rt i t i oni n g i s  t o m a i nt a i n  node s  ont o   di ffe re n t d is tr ib u te d  p a r ti tio n  s o  t h a t r e la te d  d a t a   c o m e  o n to  th e  s a m e  c lu s te r .   Ke y wo r d s :   G r a p h   P a r t i t i o n i n g ,   N o S Q L   D at a b as e,   O nl i ne   T r a ns a c t i on  P r oc e s s i n g   (O L T P ) ,   S c a l a b i l i t y   TP C - C   be nc h m a r k,   Copy r i ght  ©  201 8   Ins t i t ut e  o f   A d v anc e d  E ngi n e e r i ng and S c i e nc e   A l l  ri g h t s re se rv e d .   C or r e s po n di n A u t h or :   A r v ind   S a hu ,     D e p a rt m e nt   of   C om put e r   E ngi ne e r i ng ,     S y m b i o s i s   I n t e r n a t i o n a l  U n i v e r s i t y ,   P u n e ,   In d i a .       1.   I N T R O D U C T I O N     N o w a d ay s ,  d at a i s  g en e r at ed   b y  t h ei r  s o u r ce s  i s  v er y  h u g i n  v o l u m e t h at   i s  cal l ed  as  B i g - D at a.  T h e   c om pa ni e s  ne e d a  s t r o ng  f o u nda t i o n f or  B i g - D a t a  ha ndl i n g.  S o m a ny  c o m pa ni e s  gi vi n g m or e  im por t a nc e  t o   N o S Q L   d a t a b a s e   a s   c o m p a r e   t o   t r a d i t i o n a l   r e l a t i o n a l   d a t a b as b eca u s e   r el at i o n al   d at ab as es   ar e   u n a b l t o   s cal a n d  l a c k   o f  f l e x i b i l i t y .  Re l a t i o n a l   d a t a b a s e s  a l s o  c a n n o t   h a n d l e   g l o b a l l y   m a s s i v e  a m o u n t s   o f  u n s t r u c t u r e d   da t a .  S o i t  i s  r e qui r e d t o s t o r e  a nd  p r oc e s s   t ha t  h uge  a m ount   of   da t a   by  us i n N o S Q L  da t a ba s e .   N o S Q d at ab as e  i s   p er s i s t en ce s o l u t i o n  i n  t h w o r l d   o f  B i g   D at a.  N o S Q L   d at ab as e i s  m o r e s u i t ab l e as  co m p ar e t o   RD BM S   i n   t e r m s   o f   s c a l a b i l i t y ,   v o l u m e ,   v a r i e t y   a n d   e f f i c i e n c y .   N o S Q L   d a t a b a s e   i s   c a p a b l e   t o   h a n d l e   a l l   t y p e   o f   d a t a   l i k e   s t r u c t u r e d ,   s e m i - s t r u c t u r e d ,   a nd   uns t r uc t ur e d a t a .     Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S SN :   2 252 - 88 14   IJ A A S     V o l .   7 ,   N o .   1 ,   M a r ch   2 018   2   37   30   T o a c hi e ve  s c a l a bi l i t y  i n N oS Q L  t he  da t a   s h oul be   pa r t i t i one d a n d t he di s t r i b ut e  t h os e  pa r t i t i o ns   t o t he   di f f e r e nt  ge og r a phi c a l l y  a va i l a bl e  s e r ve r s .  P a r t i t i oni ng  i s  t he  m os t   e f f e c t i ve  t e c h n i que   w hi c h i s   us e d t acces s  s cal ab i l i t y  i n  a  s y s t e m .  S c a l a b i l i t y   i s  t o  p r o c e s s  t h e  e n t i r e   g e n e r a t e d   w o r k l o a d  a t  t h e   d e f i n e d  t i m e   bo u nda r i e s  f or  a n a p pl i c a t i on t ha t  i s  r u nni ng  on a   num be r  of  s e r ve r   n ode s .  S om e   m os t  c om m onl y us e d   pa r t i t i oni ng t e c hni que s  a r e  r o un d - r obi n pa r t i t i oni n g,  r a n ge  pa r t i t i oni ng a n d ha s h pa r t i t i oni n g.  I n r ou n d - r obi p a r t i t i o n i n g ,  e a c h  t u p l e  i s   u n i f o r m l y  d i s t r i b u t e d  t o  a n  a l t e r n a t e  p a r t i t i o n .   I n  r a n g e  p a r t i t i o n i n g ,  t h e  t u p l e s  a r e   pa r t i t i one d a c c or di n g w i t h a   r a n ge  o f  pa r t i t i on  ke y .  I n ha s h pa r t i t i oni n g,   t he  t upl e s  a r e   pa r t i t i o n e d   b y  u s i n g   ha s ke y .  B ut   t he s e   pa r t i t i oni ng  m e t hods  a r e  n ot  e f f i c i e nt   f o r  t he  s m a l l   wo r kl oa d t r a ns a c t i ons  t ha t  a c c e s s   a   l e s s  num be r  of  t upl e s .  R ou n d - r obi n pa r t i t i o n i ng,  r a n ge  pa r t i t i oni ng a nd  ha s h pa r t i t i oni n g m e t hods  a r e  u na bl e   t o r e pr e s e nt  s e ns i b l e  n - t o - n   r el at i o n s h i p   b et w een  t u p l es .  F o r  e x am p l e s o ci al  n et w o r k i n g  l i k F aceb o o k   d at a   a p p e a r  w i t h  t h e  n - t o - n r e l a t i ons hi ps  t ha t  i s  ha r d t pa r t i t i oni n g by  us i n g r o u nd - r o b i n   p a r t i t i o n i n g ,  r a n g e   pa r t i t i oni ng a n d ha s pa r t i t i o ni n g m e t hods .  S om e t im e s  t h e  r e l a t e d  t u p l e s  c o m e  i n t o  d i f f e r e n t  p a r t i t i o n  a n d   un r e l a t e d t upl e s  c om e  un de r   s a m e  pa r t i t i on w hi c h i s  r o ot  c a us e  o f   di s t r i but e d  t r a ns a c t i on.  I F i ne - G r a i n ed   pa r t i t i oni ng ,  r e l a t e d i ndi vi d ua l  t upl e s  a r e  c o m bi ne d t oge t h e r  i n t he   s a m e  pa r t i t i on t o r e duc e  t he   di s t r i b u t e d   t r an s act i o n  b u t  l o o k u p  t ab l e i s  v er y  ex p en s i v e b eca u s e o f  i t s  s i ze.  I n  cas e o f  M an y - t o - m a n y  r e l a t i o n s h i p  i t  i s   ha r d t pa r t i t i o n by   us i n g F i n e - G r a i ne d pa r t i t i oni ng .   El a sT r a s [ 1 ]  us e d s c he m a  l e ve l  pa r t i t i oni ng t o i m pr o ve   s c a l a b i l i t y .  I n   E l a s T r a s   S c a l a b i l i t y  i s  a c h i e v e d   b y  t h e  e x e c u t i o n  o f  t r a n s a c t i o n s   o n t o  t h e  m u l t i p l e  p a r t i t i o n s .   E l a s T r a s  a l s o   n o t  f o r m e d  e f f e c t i v e  p a r t i t i o n s .  I n  S p e c t r a l  p a r t i t i o n i n g   m e t ho ds  [ 2 - 3 ] ,  p a r t i t i o n s  p r oduc e d  a r e   e f f e c t i ve   but   v e r y   e xpe ns i ve   be c a u s e   t he y   r e qui r e   t he   c om put a t i o o f   e i g e nve c t or   c or r e s po n di n t t h e   f i e dl e r   v e c t o r .  I n  G e o m e t r i c   p a r t i t i o n i n g   a l g o r i t h m s  [ 4] ,  a r e   ve r y  f a s t  t pe r f o r m  pa r t i t i ons   b ut  f or m e d pa r t i t i ons   qua l i t y   a r e   w or s e   t ha pa r t i t i o n s   o f   S p e c t r a l   p a r t i t i o n i n g .     T he   we b a p pl i c a t i ons  a nd  w e bs i t e s  o f  t he  e nt e r pr i s e s  a r e   a c c e s s e by  a  hu ge   num be r   of   us e r s  wi t h   t h e  e x p e c t a t i o n  o f   r e l i a b i l i t y  a n d  h i g h  a v a i l a b i l i t y .  S o c i a l  n e t w o r k i n g  s i t e s  a r e  g e n e r a t i n g  t h e  d a t a  i n  v e r y   hu ge  a m ount  a nd   at   v er y  f a s t  r at e,  s o  t o  h an d l e t h at  d at w e n eed   o f  b o t h  co m p u t er  s o f t w ar e s cal a b i l i t y  an d   ha r d wa r e   s c a l a bi l i t y .  T he  c on c e pt  be hi n pa r t i t i oni n or   s h a di n g i s  t o s pr e a da t a  o f  a  t a bl e  a c r os s  n u m e r o u s   pa r t i t i ons .  P a r t i t i oni ng  t e c h ni que s  s ho ul d  b e  pi c ke d   u p  a p p r o p r i a t e l y  s o  t h a t  a f t e r  p a r t i t i o n i n g  t h e  r e s u l t   b eco m m o r a ccu r at a n d   e f f ect i v e.   W h e n   d a t a  i s  s t o r e d  i n  S Q L  d a t a  b a s e s ,  i t  c a n  b e   p a r t i t i o n e d  t o  p r o v i d e  e f f i c i e n c y  a n d  s c a l a b i l i t y .   D a t a  p a r t i t i o n i n g  i s  p o s s i b l e  i n  S Q L   d a t a  s t o r e  b u t  S Q L  d a t a  s t o r e s  a r e  u n a bl e  t pa r t i t i on t he  da t a   ba s e on   r e l a t i o n s h i p .  I n  S Q L  d a t a  p a r t i t i o n i n g  i n c r e a s e s  t h e  m u l t i s i t e / d i s t r i b u t e d  t r a n s a c t i o n s  b e c a u s e  s o m e t i m e s   r e l a t e d   r o w s   c o m e   i n t o   d i f f e r e n t   p a r t i t i o n .     H e n c e ,  i t  i s  n e c e s s a r y  t o  f i n d  a n  e f f e c t i v e  p a r t i t i o n i n g  t e c hni que ,  w hi c w i l l  c ons i de r  t he  r e l a t i vi t a m ong  t he  t up l e s  or   da t a  a t  t he  t i m e  of  pa r t i t i oni ng.  I pr op os e d s y s t e m ,   S c h i s m  [ 5 ]  a pp r oa c h i s  us e d f o r   pa r t i t i oni ng t h e  No S Q L  da t a   ba s e .   S c hi s m  is  a  w or kl oa d r i ve n a p p r oa c h  f o r  d a t a  pa r t i t ioni ng .  I n S c hi s m  f or   G r a p h  P a r t i t i o n i n g  M E T I S   [ 2 ]  a l g o r i t h m  i s  u s e d .  M E T I S   p r o v i d e s   b a l a n c e d   p a r t i t i o n s   a f t e r   p a r t i t i o n i n g  t h e   da t a .   P r op os e s y s t e m   im pr ov e s   S c a l a bi l i t y   a nd   r e d uc e s   t he   num be r   of   Di s t r i b ut e t r a ns a c t i ons .   W i t h  t h e g o al  t o  acq u i r e i d eal  d at a p l acem en t   m et h o d  i n di f f e r e nt  p a r t i t i ons ,  he r e  num e r ous   w o rk l o a d - a wa r e  pa r t i t i oni ng  a nd l oa ba l a nc i ng t e c hni que s  ha ve  be e n e xa m i ne d.  Gr a ph  pa r t i t i oni n g   t ech n i q u e i s  ea s y  t o  u n d er s t a n d  a n d  t h r el at i o n  b et w een  d at a can   r ep r es e n t  ef f ect i v el y  i n   t h e f o r m  o f   G r ap h .   I n   t h e G r ap h  d at ab as e,  t h n o d es  r e p r e s en t  t h e d at a b as e t u p l es  an d  n o d es  ar e co n n ect e d  b y  an  ed g e i f   t w o   o r   m or e  no de s  a r e  pa r t i c i pa t i ng  i n t he   s a m e  t r a ns a c t i o n.   Gr a p ba s e d w o r kl oa d  a wa r e   pa r t i t i oni ng  t e c h ni que  i s   b a s i c a l l y   a p p l i e d   f o r   s c a l a b i l i t y   b u t   s o m e t i m e s   i f   t h e   d a t a   p a r t i t i o n s   a r e   n o t   f o r m e d   a p p r o p r i a t e l y   t h e n   i t   l e a d s   t o t he  e x pe ns i v e  di s t r i but e  t r a ns a c t i o ns .  He r e  e x pe ns i ve  i t e r m s  of  r e s p o ns e  t i m e  a nd  r e s o ur c e  ut i l i z a t i on  o r   ne t w or us a ge .  S o t o  o ve r c om e  t he  pr o bl e m  of  e x pe n s i ve  di s t r i b ut e d  t r a ns a c t i ons   m i n - cu t  k  b al an ced   p a r t i t i o n s  c o m e  i n t o  t h e  p i c t u r e .  I n  m i n - c u t   ba l a nc e d pa r t i t i ons ,  da t a  p a r t i t i oni n g ha p pe n s  ba s e d on   s om e   r e l a t i o n  t h a t   d a t a  c o n t a i n s ,  w h i c h  m i n i m i z e  t h e  m u l t i s i t e / d i s t r i b u t e d  t r a n s a c t i o n s .  A f t e r  p a r t i t i o n i n g  t h e   d at ab as e ,  t h e  d eci s i o n  t r ee   c l a s s i f i e r  t e c h n i q u e s  a r e  a p p l i e d  t o  e x t r a c t  t h e   s e t  o f  r u l e s   b a s e d   o n  t h a t   r u l e s  d a t a   i s   pa r t i t i one d.   W he s c a l a bi l i t y   im pr ove s   t h e m a i nt e na nc e   of   da t a   be c o m e s   e a s y   a nd  t im e   t a ke t p r oc e s s   a   q u e r y   r e d u c e s .   U l t i m a t e l y ,   a l o n g   w i t h   t h e   s c a l a b i l i t y   p e r f o r m an ce  al s o   i n c r eas es .       T he   r e s t   of  t he  pa pe r  i s  o r ga ni z e d a s  f ol l o w s :   i n  S e c t i o n  2 ,  p a p e r s   r e l a t e d  t o   s c a l a b i l i t y  a n d   g r a p h   da t a ba s e   pa r t i t i oni n g i s   di s c u s s e d.  S e c t i o n 3  gi ve s  B r i e f   o v e r vi e w o f   pr o p os e d s y s t e m .  I n S e c t i o 4,   D e s i gn   of   g r a ph  ba s e d  w or kl oa d   d r i v e n   p a r t i t i o n i n g   s y s t e m   i s   p r e s e n t e d .   I n   S e c t i o n   5 ,   I m p l e m e n t a t i o n   d e t a i l s   e x p l a i n   im pl e m e nt a t i o n a n d t he  pe r f o r m a nc e  e va l ua t i on  of  t he   pa r t i t i oni ng s y s t e m .  I n S e c t i on  6 a nd S e c t i on 7 ,   ex p e r i m en t al   s et u p   a n d   r es u l t s   ar d es c r i b e d   r es p ect i v el y .   F i n al l y   i S e c t i o c onc l us i o of   t he   pa pe r .             Evaluation Warning : The document was created with Spire.PDF for Python.
IJ A A S     I S S N 225 2 - 88 14       G r a p B as e d W or k l o a Dr i v e P ar t i t i oni ng   Sy s t e m   by   Us i ng   M on g oDB   ( A r v in Sah u )   31   2.   R ELA TED   W O R K   S cal ab l d at a b as an d   d i s t r i b u t ed   d at ab a s i s   em er g i n g   a n d   i n t er es t ed   t o p i f o r   t h d at ab as r es ea r ch   gr o up .   A c c or di ngl y ,   m a ny   t e c hni que s   f or   s c a l a bl e   da t a ba s e   t r a ns a c t i o a r e   a l r e a dy   p r e s e nt .   I t hi s   ch a p t er ,   al l   t he   e xi s t i n pa r t i t i oni n a l g o r i t h m s   a nd   g r a p pa r t i t i oni ng   t e c hni que s   a r e   di s c us s e d .     Cu r i n o   [5 ha ve  p r o p os e d S c hi s m   t e c hni q ue  f or  da t a ba s e  r e pl i c a t i on a nd  pa r t i t i oni ng  f or   OL T P   da t a ba s e s .  S c hi s m  i s  a  da t a  dr i ve n g r a ph  pa r t i t i oni ng a l go r i t h m  w h i c h  i m p r o v e s  t h e  s c a l a b i l i t y  o f  t h e  s y s t e m .   S c hi s m  us e s   M E T I S  a l go r i t hm  f or   pa r t i t i oni n g t he  g r a ph .  S c hi s m  f o r m e d t he  ba l a nc e d  pa r t i t i ons  t ha t  r e duc e   t h e  n u m b e r  o f  d i s t r i b u t e d  t r a n s a c t i o n s .   K - w a y  p a r t i t i o n i n g  a l g o r i t h m  i s  u s e d  t o  f i n d  r e f i n e d  p a r t i t i o n   in  M ETI S .  K - w a y  a ppl i e s  f or   f ur t he r   pa r t i t i on i ng t he  da t a  t h a t  r e d uc e s  t he   e f f e c t   of   di s t r i but e d t r a ns a c t i ons   a n d   i nc r e a s e s   t he   t hr o ug h put .     S c hi s m  pr o vi d e s  g oo pa r t i t i oni ng  pe r f or m a nc e  a nd e a s y  t o i nt e g r a t e  i nt o e xi s t i ng  d a t a ba s e s .   I n   S ch i s m   r ep r es e n t at i on  o f   n - t o - n   r e l a t i o n s h i p   e f f e c t i v e l y   a n d   a l l o w   m u l t i p l e   s c h e m a   l a y o u t s .   S c h i s m   i s   a   b e t t e r   a pp r oa c h f o r  r e pl i c a t i on a n pa r t i t i oni ng  of  s oc i a l  ne t w o r ki n g da t a .  I n S c hi s m  w or kl oa d c ha nge s  c a a f f e c t   t h p e r f o r m an ce  an d   a g g r es s i v r ep l i cat i o n   i s   u s e d .   K a ry p i s   [ 6 ]   ha ve  p r op os e d M E T I S   w hi c f o l l ow s  M ul t i l e v e l  Gr a ph  P a r t i t i oni n g.  M E T I S  i s  a n o pe n   s o u r c e  g r a p h  p a r t i t i o n i n g   t e c h n i q u e .  I n   M u l t i l e v e l   g r a p h  p a r t i t i o n i n g   t h e r e  a r e   t h r e e  p h a s e s .   F i r s t l y ,   i n  g r a p h   c oa r s e ni n p ha s e   t he   gr a ph  de ve l o pe by   i nc om i ng  w o r kl o a d   i s   p a r t i t i o n e d .   S e c o n d ,   i n   i n i t i a l   p a r t i t i o n i n g   t h e   gr a p hs  a r e   f u r t he r   pa r t i t i one d  i nt o t he  s m a l l gr a ph s  f or   r e f i ne m e nt .  I ni t i a l  pa r t i t i oni ng  pr od uc e s  t he  ba l a nc e d   pa r t i t i ons .  T hi r d ,  i un - c o a r s e n i n g  i s  f o r   r e b u i l d i n g  t h e  f i n a l   g r a p h  a f t e r  r e f i n e m e n t .   M ETI S  i f a st  a s   c om pa r e  t o  ot he r  pa r t i t i oni n g a l go r i t hm .  M E T I S  p r o vi d e s  q ua l i t y  of   pa r t i t i ons  a nd   r e q ui r e d l e s s   m e m or y   be c a u s e   of   dy n a m i c   m e m or y   a l l oc a t i on.   I M E T I S ,   we   c a nn ot   m a jor   e xa c t   a m ount   o f   r e qui r e d   m e m or y.   T at ar o w i cz  [7 ]   ha ve  p r op os e d F i ne - G r a i n e P a r t i t i oni n g f o r  di s t r i b ut e d da t a ba s e .  I n pr o pos e d   pa r t i t i oni ng a p pr oa c h r e l a t e d  i ndi vi d ua l  t u pl e s  a r e  c om bi ne d t o ge t he r  i n t he  s a m e  pa r t i t i on.  L o o ku p t a bl e   us e d t o m a i nt a i n a  s m oot pa r t i t i oni n g be c a us e  i t  i s  ne e de d t o s t or e  t h e l o cat i o n  o f  eac h  t u p l e.  T h e l o o k u p   t ab l s t o r es   l o c at i o n   o f   each   t u p l t h at   act s   as   m et ad at t ab l e.   M an y - t o - m a n y   r e l a t i o n s h i p   i s   h a r d   t o   p a r t i t i o n   b ecau s e n u m b er  o f   d i s t r i b u t ed  t r a n s act i o n s   i n cr eas e i n  cas e o f  M an y - t o - m a ny  r e l a t i ons hi p.  I n F i ne - G r a i n ed   pa r t i t i oni ng t h e  num be r   of   di s t r i b ut e d t r a ns a c t i o ns  c a be  r e d uc e by  we l l  a s s i g nm e nt  o f  t u pl e s  t o e a c h   pa r t i t i on .  I t   r e duc e s  t he  m a in m e m or y  c on s um pt i on a nd i m pr ove s  t he   p e r f or m a nc e .  S om e tim e s  t m a i nt a i n   F i ne   Gr a i ne d   P a r t i t i oni n g r o ut i ng  ( L oo k up )   t a bl e s   i s   v er y   e x p e n s i v b ecau s o f   i t s   s i ze.     Q u am ar   [8 ]   h av p r o p o s ed  S cal ab l e W o r k l o a d - A w a r e   D a t a  p a r t i t i o n i n g  f o r  T r a n s a c t i o n a l  d a t a   pr oc e s s i ng .  H y pe r gr a ph i s  u s e d t o r e p r e s e nt  t he  w o r kl o a d a n d r e d uc e s  t he  ove r he a ds  o f  pa r t i t i on i ng by   hy pe r e d ge .  O v e r he a ds  ha p p e n  at  t h e t i m e o f  d at p l acem e n t  o r  q u e r y  ex ecu t i o n  at  r u n t i m e t h at  i s  r ed u ces  b y   S W O R D t e c h ni q ue .   W o r kl o a d c ha n ge s  a r e  ha ndl e d by  i n c r e m e nt a l  da t a  r e pa r t i t i oni n g  t e c hni que .  F o r  hi gh  a v a i l a b i l i t y  i t   u s e s  a c t i v e  r e p l i c a t i o n  t e c h n i q u e .  By  A c t i v e  r e p l i c a t i o n num be r  of  di s t r i but e t r a ns a c t i on s   r ed u ces ,  acces s i b i l i t y  i n cr eas es  an d  l o ad   b al an ci n g  ca n   b e   acces s ed .  S W O R D  i s   u s ed  t o  m i n i m i ze t h e co s t   o f   di s t r i b ut e d t r a ns a c t i o ns .  S W O R D r e p r e s e n t s  da t a  i n c om pr e s s e d f o r m a t s o n um be r  of  ge ne r a t e d pa r t i t i ons   w ou ld  b e   m i n i m a l .   L u  W an g   [9 ]  ha v e  pr opo s e d  a  Mu lti - l e ve l  L a be l  P r opa ga t i on  ( M L P )  m e tho d f o r  pa r t i t ioni ng  of  t he   gr a p h.  A l l  t he  w e us e r s  a r e   r e p r e s e nt e d o n  t he  gr a p h.  I f  gr a p h pa r t i t i on e d e f f i c i e nt l y  t he n l oa d ba l a n c i ng   b eco m es  eas y  an d  l es s   co m m u n i cat i o n  o v er h ea d .   T he   q ua l i t y  of  ge ne r a t i ng p a r t i t i ons  by  M L P  a pp r oa c h i s   c om pa r e d t o t h e  s m a ll  s i z e  gr a ph .  T o e va l ua t e  qu a l i t y  of  t h e  f or m e d pa r t i t i ons  i t  i s  c om pa r e d  t o M E T I S .   I n   M L P  f or m e pa r t i t i ons  a r e   go o wi t h r e s pe c t  t o t i m e  a nd  m e m or y .  M L P  a r e  m or e  e f f e c t i ve  a n s cal ab l pa r t i t i oni ng   w h i c c a n   s c a l e   u t o   bi l l i o ns   of   no de s .   M L P   a l go r i t hm   c a nn ot   us e   f or   ge ne r a l - pu r p os e .   Ch r i s   [1 0 ]  ha v e  pr op os e d a  M i n - m a x  Cu t   a l g o r i t h m .  A i m  o f  M i n - M ax  i s  t o  i n cr eas e n u m b er  o f   s im i l a r   no de s  w i t hi n a   c l us t e r   a nd   r e d uc e   t he  num be r  o f  s i m i l a r   n o d e s  b e t w e e n  d i f f e r e n t   c l u s t e r s .  S i m i l a r   no de s   be t w e e n  t wo s u b - gr a p hs  s ho ul be  l e s s .  S i m il a r  no de s   wi t hi n e a c h s ub - g r a ph s h oul d be   hi ghe r .  M i n - m a c ut   i s   us e t o   i m pr ove   t h e   c l us t e r i n a c c ur a c y   a n gi v e s   a n   o pt i m a l   s ol ut i o n.   T ae - You ng   [1 1 ]   ha ve   pr op os e d  k - w a y  G r a p h P a r t i t i oni ng  Al g or i t hm  t o r e duc e  t he  s i z e  of  t he   gr a p h.   T h r ec u r s i v s p ect r al   b i s ect i o n   m et h o d   r e d u ces   t h s i ze  o f   t h g r ap h   b y   t h b r ea k i n g   e d g es   an d   v e r t i ces .   T h e   r e c u r s i ve  s pe c t r a l  bi s e c t i on  m e t hod i s  us e d f or  c l u s t e r i n g s m a ll  gr a p h   i n  a  k - w a y .  Ba l a n c i n g   c o n s t r a i n t s   s ho ul d m a i nt a in t o a l l  pa r t i t ions   o f  g r a p hs .  I n M ul t i - L e v e l  P a r t i t i o n i n g  f o r  r e c u r s i v e  p a r t i t i o n i n g   k - w a a l g o r i t h m  i s  u s e d .   K - w a y  t a k e s  l e s s  t i m e  t o  p a r t i t i o n  t h e   g r a p h .   K - w a y   i s   a   g oo opt i o f or   pa r t i t i oni n s m a ll  g r ap h s   onl y .   D om i ni que   [ 12 ]  i n t r o d u c e   P a r a l l e l  H i l l - Cl i m b i n g  a l g o r i t h m  f o r   g r a p h   p a r t i t i o n i n g .  T h i s  a l g o r i t h m  i s   u s e d  f o r  s h a r e  m e m o r y  f o r   r e f i n e m e n t  a l g o r i t h m  p a r a l l e l .  H i l l - c l im bi ng  t a ke s   i m a gi na r y   m ove  o n di f f e r e nt   v e r t i c e s  s o  t h a t  i t  c a n  f i n d   n e w  l o c a l  m i n i m a .  T he  r e f i ne m e nt  a l gor i t h m  pr o d uc e s  hi gh - q u a l i t y  p a r t i t i o n i n g .   H i l l - S c a n ni n i s  t he  r e f i ne m e nt  a l go r i t hm  f or  r e f i ni n g k - w a y  p a r t i t i o n .  H i l l - S can n i n g  h as  b et t er  p er f o r m an ce   t h a n   o t h e r   p a r a l l e l   r e f i n e m e n t   a l g o r i t h m .   H i l l - S c a nni ng   i t   i s   m uc f a s t e r   a n pr o v i d e s   b e t t e r   q u a l i t y   p a r t i t i o n .     Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S SN :   2 252 - 88 14   IJ A A S     V o l .   7 ,   N o .   1 ,   M a r ch   2 018   2   37   32   M ar i [1 3 in tr odu c e s   a  n e w  s h a r e d  m e m o r y  p a r a l l e l   a l g o r i t h m  t h a t  i s  Co u p l i n g - A wa re  G r a p h   P a r t i t i o n i n g  A l g o r i t h m .   Co u p l i n g - A wa r e  i s   us e d t p r o d uc e  hi g h - q u a l i t y  p a r t i t i o n s  a s  c o m p a r e d  t o  t h e   k - w ay   p a r t i t i o n i n g  a l g o r i t h m .  Co - p a r t i t i o n i n g  a l l o w s  s c a l a b i l i t y  i n  t e r m  o f   p r o c e s s i n g  u n i t .  I n  C o u p l i n g - a w a re   pa r t i t i oni ng t h e r e  i s  n o ne e d  t o pa r t i t i on c ode s  i n de pe n d e nt l y  or  s e pa r a t e l y .  I t  c a n r e us e  a va i l a bl e  c ode s   t hr ou g h a  c ou pl i ng  f r a m e w or wi t h out  c o m bi ni ng t he m  i nt o a  s t a n da l one  a p p l i c a t i o n .  C o u p l i n g   A w ar r e d uc e s   t he   c o upl i n c om m uni c a t i ons   c os t s .   C o upl i n g - A w a r e   pr ovi de s   be t t e r   gl o ba l   gr a p e dge   c ut .   J am es   [1 4 ]  ha ve   pr op os e d S i m ul a t e d B e e  C ol o ny  A l go r i t h m   t o pa r t i t i on   t he  g r a p h.  S i m ul a t e d B e e   Co l o n y  i s  t o t a l l y  i n s p i r e d   b y  t h e  f o r a gi n g be ha vi or   of   ho ne y  be e s .  I n S B C  a l gor i t hm  t he  pa r t i a l  r e s ul t  c a n be   r e us e f u r t he r   i f  c om pa t i bl e  i n a  s c e na r i o.  S B C  pr od uc e s   v e r y  hi g qua l i t y   o f   p a r t i t i o n s .  S BC i s  u s e d   w h e n   t he  qua l i t y  i s   m os t im por t a n t  a nd pe r f or m a nc e  c a n be  m ode r a t e .  S B C  a l go r i t hm   i s  n o t  s u i t a b l e  f o r  r e a l - t i m e   a p p l i c a t i o n s .   S BC  p e r f o r m a n c e   i s   l o w   t h a t   i s   w h y   p a r a l l e l   p r o c e s s i n g   i s   n o t   p o s s i b l e       3.   P RO P O S E S Y S T E O V E R VI E W   I n   o u r   p r o p o s e d  s y s t e m ,  F i r s t l y  s y s t e m  s t o r e s  t h e   d a t a  i n   N o S Q L  d a t a b a s e  t h a t  i s  M o n g o D B a n d   t h en  r ep r es e n t s   t h at   da t a  i n t he  f or m  of   gr a ph  by  u s i n g N e o4 j.   G r a p h r e pr e s e nt a t i on  i s  ne c e s s a r y  f o r  e a s y   un de r s t a n di n whe r e  t upl e s  a r e  r e p r e s e nt s  a s  n ode  a n d t r a ns a c t i o n r e p r e s e nt   by  e d ge .   G r a p h p a r t i t i oni n g   t e c h n i q u e  i s  a p p l i e d  t o  f i n d  t h e  m i n i m u m  c u t  b a l a n c e d   p a r t i t i o n  s o   t h a t   t h e   d i s t r i b u t e  r e l a t i o n  b e t w e e n  n o d e s   s h o u l d  b e  m i n i m a l .  F i n a l l y ,   t h e  D e c i s i o n  t r e e  c l a s s i f i e r  i s  a p p l i e d  t o  d e v e l o p  s o m e  s o r t  o f  r u l e s  t o  t a k e   de c i s i o r e ga r d i ng  pa r t i t i on  s t r a t e gy .   O t he s e   r ul e s   t he   pa r t i t i on  o f   da t a   de pe n ds .     H er e  S c h i s m  a p p r o ach   i s  u s e d f o r   pa r t i t i oni ng  t he   da t a .   S c hi s m  i s  a  w o r kl oa dr i ve n  a pp r oa c h  f or   da t a ba s e   pa r t i t i oni ng .  I n  W or kl oa d dr i ve n   p a r t i t i oni n s y s t e m s ,   t he  pa r t i t i on   o f  da t a  ha p pe n s  ba s e d   o n s om e   r el at i o n  b et w e en  d at a.   T h e r el at i o n   f o u n d  b as e d  o n   acce s s   p at t er n s .   I n   t r a n s a c t i o n ,  t h e   d a t a  t h a t  i s  m o s t l y   acces s ed   t o g et h er   co n t ai n s   h i g h   r el at i o n ,   s o   r el at ed   d at co m es   i n t o   s i n g l p ar t i t i o n  o f   d at ab as e .   T he  a r c hi t e c t u r e  o f  t he  p r o p os e d s y s t e m  “ G r a p h ba s e wo r kl oa d d r i v e pa r t i t i oni ng  s y s t e m  i s   s h own  in  f igur e .  O ur  pr op os e d s y s t e m  i s  de s i gne d t o w or k  a s  a  S c a l a bl e   t r a ns a c t i o na l  s y s t e m  on t he  top  o f   d i s t r i b u t e d  s t o r a g e  s y s t e m .   H e r e  M o n g o D B i s  d i s t r i b u t e d  s t o r a g e   s y s t e m  w h i c h  i m p l e m e n t s   CRU D   ( C r eat e/ I n s er t ,   R ead ,   U p d at a n d   D el et e)   o p e r at i o n s .     A d m i n i s t r a t o r   N o d e  i s  t h e  a c t u a l  s e r v e r   w h i c h  p e r f o r m s  p a r t i t i o n i n g   b y   u s i n g  t h e  a l g o r i t h m  h e r e   S c hi s m  i s  us i ng t o pa r t i t i on t he  da t a .  S ha nn on  I n f o r m a t i on ga i n i s  c a l c ul a t e d t o f i n d t he   r e l a t i on be t we e n t he   d at a.   D eci s i o n  t r ee d eci d es   m i g r at i o n   o f   d at a.  B ac k en d  d at ab a s e i s   M o n g o D B .  M o ngo D B  is  a   N oS Q L   d a t a b a s e   s t o r e ,   w h i c h   a c t u a l l y   c o n t a i n s   t h e   d a t a .           F i g u r e   1 .   S y s t e m   A r c h i t e c t u r e       I ou r  p r o p os e d s y s t e m ,  t he  i np ut  i s  wo r kl oa d t r a c e  a nd  a  num be r  o f  p a r t i t i ons  r e qui r e d a n d t he   out put   i s   t he   b a l a nc e pa r t i t ions .   B e c a us e   o f   ba l a nc e pa r t i t i ons   t he   n um be r   o f   di s t r i b ut e t r a ns a c t i o r e d uc e s   an d   p e r f o r m an ce  i n cr eas es           Evaluation Warning : The document was created with Spire.PDF for Python.
IJ A A S     I S S N 225 2 - 88 14       G r a p B as e d W or k l o a Dr i v e P ar t i t i oni ng   Sy s t e m   by   Us i ng   M on g oDB   ( A r v in Sah u )   33   3. 1.     P a r t i t i o t he   G r a ph   A f t e r   G r a p h  r e p r e s e n t a t i o n ,  t h e  G r a p h   p a r t i t i o n i n g  a l g o r i t h m  i s  a p p l i e d  t o  p a r t i t i o n   t h e  G r a p h .   B al an ced   p ar t i t i o n s  f o r m ed  af t er  G r a p h   p a r t i t i oni n g.  E a c h pa r t i c ul a r   no de / t u pl e  be l on gs  t o a   da t a ba s e   p ar t i t i o n   an d   e ach   d at ab as e   p ar t i t i o n   al l o cat t o   p h y s i cal   s ep ar at e d   n o d e .     3. 2.     Sh a n no I nf o r m a t i o G a i n   S ha nn o n i nf or m a t i on ga i n i s  ne e de d f o r  e f f e c t i ve  c l a s s i f i c a t i on o r  pa r t i t i on of   da t a b a s e .  S h a n non  i nf or m a t i on ga i n i s  us e d t o  c a l c ul a t e  t he  e n t r o py / im pur i t y  of  t he   da t a .  D e c i s i on t r e e  t a ke s   de c i s i o n b a s e o n   S ha nn o n i nf or m a t i on ga i n.  I f  t wo t u pl e s  h a s  ne a r e r  S ha n no n i nf o r m a ti on ga i n i t   m e a ns  t he y  c ont a i n  s om e   r e l a t i on  a n c o m e   i nt a   s i ng l e   p a r t i t i o n .     3. 3 .     D i s t r i b u t e d   Tr a n s a c t i o n s     I n   D i s t r i b u t e d  s y s t e m ,  t h e  t r a n s a c t i o n a l   d a t a  a v a i l a b l e   a t  t h e  d i f f e r e n t  p h y s i c a l  l o c a t i o n s .  T h e   di s t r i b ut i on  o f  da t a  s h o ul b e  ba s e d o n s o m e  a na l y s i s  or  r e l a t i on m i ght  r e d uc e  t he   n um be r  of   di s t r i but e t r an s act i o n .  P r act i cal l y  D i s t r i b u t e d  s y s t em s   ar e g o o d  c h o i ce b ecau s e i t  p r o v i d es  t r a n s p ar en cy ,  s cal ab i l i t y  an d   hi g pe r f o r m a nc e .       4.   G R A P H   B AS E W O R K L O A D RI VE N   P AR T I T I O N I N G   A L G O R I T H M   I p r o p os e d   s y s t e m ,   S c hi s m   A p pr oa c i s   us i ng  f o r   pa r t i t i o ni n t he   g r a p h.   S c h is m   a p p r oa c h   w or ks   i f i v e   s t e p s .   4. 1.     D a ta   P r e - p ro ces s i n g   P ha s e     4. 2.     G r a p h   R ep res en t a t i o n   P h a se   B i g da t a  i s  be i ng  ge ne r a t e b y  w e b  a ppl i c a t i ons .   Gr a ph  r e pr e s e nt a t i on   of  da t a   pr o vi de s   a  p r o pe r  a n d   eas y  u n d er s t a n d i n g ,  m ap p i n g  an d  r el at i o n  b et w een  d at a.   A f t er  t h d at a p r e - p r o ces s i n g  s t ep ,  w h o l e d at a o r   w o r kl oa d t r a c e  i s  r e pr e s e nt e d  i n t he  f o r m  of  G r a ph .  E a c no de  r e pr e s e nt s  a  t upl e  a nd a n e d ge  r e pr e s e nt s  t he   f r e que nc y   of  t upl e s  wi t hi n a   t r a ns a c t i o n.  N ode s ,   w hi c h a r e  a c c e s s e d i n  t he  s a m e  t r a ns a c t i on i s  c o nne c t e d b y   a e dge s .     4. 3.     G r ap h   P ar t i t i on i n P ha s e   I n t hi s   pha s e ,  pa r t i t i oni ng  o f  t he  g r a p pe r f or m e d.  M e t i s  A l g or i t hm  ps ue dc o de - M e t i s  a l g o r i t h m   w or ks   in  thr e e   s te p s :   a.   Co a r s e n i n g -   D ur i ng   t he   C oa r s e ni n p ha s e ,   m e r gi n of   n o de   unt i l   t he   s m a l l   gr a ph   i s   fo rm e d .   b.   I n i t i a l  p a r t i t i o n i n g -   D u r i n g   t h e  I n i t i a l  p a r t i t i o n i n g   p h a s e ,  k - w a y   p a r t i t i o n i n g   o f  t h e  s m a l l e r  g r a p h  i s   c om put e d.     c.   U n - c oa r s e ni n pha s e -   D ur i ng   t he   U n - co a r s e n i n g   p h as e,   r e f i n ed   p a r t i t i o n s   ar f o r m ed   af t er   r e f i n em en t .     4. 4.     Ex p l a n a t i o n  P h a se   I n t hi s   p h as e,   cr eat e t h e r u l e s  an d  s t o r e t h a t  r u l es  i n t o  d at ab as e.  B as e d   o n  t h es r u l es  d eci s i o n  a r e   t a ke n.   F i n a   c om pa c t   m ode l   t ha t   c a pt u r e s   t h e   ( t u pl e ;   pa r t i t i on )   m a ppi n gs   pr o duc e by   t h e   pa r t i t i oni ng   p ha s e .   U s e  de c i s i o n t r e e s  t o p r o d uc e  un de r s t a n da bl e  r ul e - b a s e d  out p ut .  T he s e  r ul e s  a r e  c om bi na t i o n o f  t u pl e  a nd  p a r t i t i o n   ( t u p l e :   p a r t i t i o n ) .   T h a t   d e s c r i b e s   t h e   t u p l e   a n d   s t o r e d   l o c a t i o n .     4. 5.     V a l i d a t i o n   P ha s e       5.   I M P LEM E N TA TI O N   D E TA I LS   C al cu l at S h an n o n   I n f o r m at i o n   G ai n :   H e r e   i n   t h i s   s t e p   d i s t r i b u t i o n   f a c t o r   o f   t h i n p u t   p a r am et er s   ar a na l y z e d by  us i ng S ha n n on i n f o r m a ti on ga i n .  S ha nn o n i nf o r m a ti on ga i n y i e l ds  di s t r i b ut i on e nt i t y  i n be tw e e n   0 a nd   1.   A ny  v a l ue s  t ha t  a r e   ne a r e r  t 1,  i s   a l wa y s  c o ns i de r  a s  t he   hi g hl y   di s t r i b ut e d  f a c t or  a n d i t  i s  c o n s i de r   as  t h e m o s t   i m p o r t a n t   f a c t o r .   S o t hi s  s t e p  a p pl i e s  i nf o  ga i m e t hod  o n c l u s t e r e da t a   f r o m  gr a ph  ba s e d  o n t h e   us e r   a n w a r e h ous e   t c he c f or   t he   p r o ba bi l i t y   of   t he   hi g he s t   or de r   w a r e h ous e   wi t r e s p e c t   t t he   i np ut   da t a .   F or  t hi s   p ur p o s e  s y s t e m  us e s  t he  S ha nn o i nf or m a t i on ga i n t he o r y  w hi c h c a be  s t a t e   wi t h t he  he l of  t he   f o l l o w i n g   e q u a t i o n  1 :     IG E   =     -   (P     /   T   )   l o g   (P   /   T   )   -   (   N   /   T   l o g   (N   /   T     ( 1)       Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S SN :   2 252 - 88 14   IJ A A S     V o l .   7 ,   N o .   1 ,   M a r ch   2 018   2   37   34   w h er e     P     =   F r e q ue nc y   of   t he   w a r e h ous e   e nt i t y s   p r e s e n t   c o u n t   i n   t h e   c l u s t e r s   N     N o n   p r es e n c co u n t   T     =   T ot a l   num be r   of   c l us t e r s   IG   (E )   =   I nf or m a t i on  G a i f or   t he   gi ve n   E nt i t y   O n a p pl y i ng t hi s  e q ua t i o n,  t ha t  y i e l ds  t he  va l ue  i be t w e e n 0 t o 1.  T he  da t a  s i z e ,  t ha t  a r e  ha vi n g   v a l u e   n e a r e r   t o   1   i n d i c a t i n g   t h e   h i g h e s t   p r i o r i t y   i n   t h e   l i s t .   D ev el o p  D eci s i o n   T r e e :  D e c i s i on T r e e  e xt r a c t  s om e  r ul e s  ba s e on  S ha nn o n i nf or m a t ion  ga i n a n d   t a ke  de c i s i o ba s e d o n t ha t  r ul e s .  B a s e on t he  g r a ph  pa r t i t i on c l us t e r s  a n d S ha nn on i nf or m a t i on ga i n   d eci s i o n  t r ee i s  cr eat ed .   A f t e r  d eci s i o n  t r ee  cr eat i o n  a m at r i x  w i l l  cr eat e   f o r   t he  de c i s i on   p r ot oc ol s .  M a t r i c ont a i n s  o pt i m i z e d r out i n pa r t i t i one da t a   w i t h r e s pe c t  t o  t he  w a r e h ou s e s .  T hi s  c a n be   r e p r e s e nt i ng  w i t h t he   f o l l o w i n g   a l g o r i t h m   1 .     A l g o r i t h m   1 :   G e n e r a t e   D e c i s i o n   T r e e   ( d b ,   p ) : d t     / /   F 1,   F 2 ,   F a r e   f i t ne s s   f unc t i ons   S t e p   0 :   S t a r t   S t e p   1 :   W h i l e   s t o p   c r i t e r i o n   i s   n o t   m e t   S t e p   2 :   E v a l u a t e   f i t n e s s   o f   d t   a t t r i b u t e   i t   t o   F 1   S t e 3:   P e r f or m   m ut a t i ons   t S t o r a ge   No d e s   S t e 4:   S t o r e   F i nt F 2   S t e 5:   W hi l e   j < num be r   of   m ut a t i ons   t P r e di c t i on  N ode s   S t ep   6 :   S el ect   an d   m u t at n ode   S t e 7:   E va l ua t e   f i t ne s s   F of   m ut a t e t r e e   S t e 8:   I f   F 3> F 2   S t e p   9 :   A c c e p t   m u t a t e d   t r e e   S t e p   1 0 :   A t t r i b u t e   F 3   t o   F 2   S t e 11:   E n d - i f   S t e 12:   E n d - W h i l e   S t e 13:   I f   F 2> F 1   S t e p   1 4 :   A t t r i b u t e   r e s u l t i n g   t r e e   t o   d t   S t e p   1 5 :   A t t r i b u t e   F 2   t o   F 1   S t e 16:   E nd - If   S t e 17:   E n d - W h i l e   S t e 18:   R e t ur dt   S t e p   1 9 :   S t o p       6.   E X P ER I M EN TA S ETU P   T o i m pl e m e nt  t he  pr op os e s y s t e m  ja va  pr og r a m m i ng l a ng ua ge  a n d ja va - b as e d  N et B ean s  I D E  i s   us e d.  F o r  e xpe r i m e nt a l  pr ove  t hr e e   ha r d w a r e  s e pa r a t e d m a c hi ne s   a r e  c o n s i de r e d t ha t   ha v e c o r e i 3   p r o ces s o r   w i t h   4 G B   o R AM .   H e re   t h re e   Ha rd w a r e   s e p a ra t e d   m a c h i n e s   a re   u s e d   fo t h e   d i s t ri b u t e d   p a ra d i g m .   P r o p o s e d   S y s t e m  us e s  N oS QL  M on g o DB  f or  t he   gr a ph - ba s e d  w or k l oa dr i ve n pa r t i t i oni n g s y s t e m .  T o s t im ul a te  t he   t r a ns a c t i o na l  w o r kl oa d i n t he  f o r m  of  gr a ph t he   N e o 4 j  gr a p h da t a ba s e  i s  us e d.  T he  r e s po ns e  t i m e  of   de ve l ope s y s t e m   i s   va l i da t i n by   us i n T P C - C   be nc hm a r k.       7.   R ES U LT   P r o p os e d s y s t e m  us e s  M on go  DB   N o S Q L  d a t a ba s e  f or  t he  e x pe r i m e nt .  T he   de ve l ope d s y s t e m  put   un de r  ha m m e r  i n m a ny  s c e na r i os  t o   pr o ve  i t s  a ut he nt i c i t y  a s   m e nt ione d i be l o w  t e s t s .  T o e va l ut e   pe r f o r m a nc e  of   t he   s y s t e m   r e s po ns e   t im e ,   t hr ou g hp ut   a nd   n um be r   o f   di s t r i but e t r a ns a c t i ons   a r e   c o ns i d e r i n g.   W he t he   s y s t e m   i s   s ub je c t e t ge t   t he   t hr o u gh p ut   f o r   1 w a r e h o us e s   a e xpe r i m e nt   i s   c o ndu c te d   to  g e t   t h e   s a m e ,   w h o s e   r e s u l t   i s   t a b u l a t e d   i n   T ab l 1               Evaluation Warning : The document was created with Spire.PDF for Python.
IJ A A S     I S S N 225 2 - 88 14       G r a p B as e d W or k l o a Dr i v e P ar t i t i oni ng   Sy s t e m   by   Us i ng   M on g oDB   ( A r v in Sah u )   35   T ab l 1 .   T hr ou g hpu t a nd   T im e   R e s po ns e   f or   10   W a r e h ous e   N o of   T r an s catio n s   Sin g le DB  T i m e in   Seco n d s   M u ltip le DB   T i m e  in   Seco n d s   T hr oughp ut  f or  S i ngl e   DB  ( No  o f  T r an s actio n s   p er  Seco n d s   T hr oughp ut  f or  M ul t i pl e   DB  ( No  o f  T r an s actio n s   p er  Seco n d s   20   8. 547   5. 47   2. 3400 023 4   3. 6563 071 3   40   18. 789   8. 482   2. 1289 052 1   4. 7158 688 99   60   26. 771   15. 774   2. 2412 311 83   3. 8037 276 53   80   37. 44   20. 475   2. 1367 521 37   3. 9072 039 07       W he n a  pl ot  i s  dr a wn  f o r  t h i s   t hr o ug h put  r e s ul t s   we  ge t   s om e   i nt e r es t i n g  f act s  t h at   can  b e s ee n   F i gu r e  3.   W he r e  we  c a n o bs e r ve r  t ha t  t hr o ug h put  i s  i nc r e a s e d s w e e pi n g l y  f or  t he  m ul ti pl e  DB  t r a ns a c t i ons .   T ha t  m e a ns  o n  di s t r i b ut i o of  t he  da t a ba s e s   num be r   of  t r a n s a c t i ons   pe r  s e c on w i l l   i n cr eas e t o  y i el d   b et t er   r e s u l t s               F i gu r e  2.   T i m e   D e l a y   C om pa r i s on   f or   1 W a r eh o u s es   F i gu r e  3.   T hr ou ghp u C om pa r i s o f or   1 W ar eh o u s es         W he t he   s y s t e m   i s   s ub je c t e t ge t   t he   t hr o u gh p ut   f o r   1 w a r e h o us e s   a e xpe r i m e nt   i s   c on d uc t e t o   g e t   t h e   s a m e ,   w h o s e   r e s u l t   i s   t a b u l a t e d   i n   T ab l 2.       T a b l e   2.   T hr ou g hpu a nd   T im e   R e s po ns e   f or   15   W a r eh o u s es   N o of   T r an s catio n s   Sin g le DB  T i m e in   Seco n d s   M u ltip le DB   T i m e  in   Seco n d s   T hr oughp ut  f or  S i ngl e   DB  ( No  o f  T r an s actio n s   p er  Seco n d s   T hr oughp ut  f or  M ul t i pl e   DB  ( No  o f  T r an s actio n s   p er  Seco n d s   20   8. 78   4. 98   2. 2779 043 28   4. 0160 642 57   40   17. 77   7. 87   2. 2509 848 06   5. 0825 921 22   60   21. 58   13. 5   2. 7803 521 78   4. 4444 444 44   80   34. 25   16. 52   2. 3357 664 23   4. 8426 150 12               F i g u re   4 .   T i m e   D e l a y   C om pa r i s on   f or   1 W a r eh o u s es   F ig ur e   5 .   T hr ou ghp u C om pa r i s o f or   1 W a r eh o u s es       Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S SN :   2 252 - 88 14   IJ A A S     V o l .   7 ,   N o .   1 ,   M a r ch   2 018   2   37   36   W he t he   s y s t e m   i s   s ub je c t e t ge t   t he   t hr o u gh p ut   f o r   2 w a r e h o us e s   a e xpe r i m e nt   i s   c on d uc t e t o   g e t   t h e   s a m e ,   w h o s e   r e s u l t   i s   t a b u l a t e d   i n   T ab l 3.       T ab l 3 .   T hr ou g hpu t a nd   T im e   R e s po ns e   f or   20   W a r eh o u s es   N o of   T r an s catio n s   Sin g le DB  T i m e in   Seco n d s   M u ltip le DB   T i m e  in   Seco n d s   T hr oughp ut  f or  S i ngl e   DB  ( No  o f  T r an s actio n s   p er  Seco n d s   T hr oughp ut  f or  M ul t i pl e   DB  ( No  o f  T r an s actio n s   p er  Seco n d s   20   7. 44   4 .4   2. 6881 720 43   4. 5454 545 45   40   15. 66   7. 01   2. 5542 784 16   5. 7061 340 94   60   19. 22   11. 2   3. 1217 481 79   5. 3571 428 57   80   32. 02   15   2. 4984 384 76   5. 3333 333 33               F i g u re   6 .   T i m e   D e l a y   C om pa r i s on   f or   2   W a r eh o u s es   F ig ur e   7 .   T hr ou ghp u C om pa r i s o fo 2 0     W a r e hou s e s       W he t he   s y s t e m   i s   s ub je c t e t ge t   t he   t hr o u gh p ut   f o r   2 w a r e h o us e s   a e xpe r i m e nt   i s   c on d uc t e t o   g e t   t h e   s a m e ,   w h o s e   r e s u l t   i s   t a b u l a t e d   i n   T ab l 4.       T ab l 4 .   T hr ou g hpu a nd   T im e   R e s po ns e   f or   25   W a r eh o u s es   N o of   T r an s catio n s   Sin g le DB  T i m e in   Seco n d s   M u ltip le DB   T i m e  in   Seco n d s   T hr oughp ut  f or  S i ngl e   DB  ( No  o f  T r an s actio n s   p er  Seco n d s   T hr oughp ut  f or  M ul t i pl e   DB  ( No  o f  T r an s actio n s   p er  Seco n d s   20   6. 21   2 .2   3. 2206 119 16   9. 0909 090 91   40   12. 1   6 .4   3. 3057 851 24   6. 25   60   17. 2   10. 24   3. 4883 720 93   5. 8593 75   80   29. 2   13   2. 7397 260 27   6. 1538 461 54               F i g u re   8 .   T i m e   D e l a y   C om pa r i s on   f or   2 wa r e ho us e s   F ig ur e   9 .   T h r o ug h put   c om pa r i s on  f or   2 w a r e ho us e s       8.   C O N CL U S I O N   I pr op os e d a l go r i t hm ,  gr a p h  ba s e w o r kl o a d d r i ve n pa r t i t i oni ng s y s t e m  f or  N oS Q L  da t a ba s e  i s   pr e s e nt e d .   W o r kl oa d i s  r e p r e s e nt e d i n t he  f or m  of  gr a ph t o t a ke  t he  a d v a nt a ge  o f  t he  r e l a t i ons hi p be t we e da t a .  B a s e on  t ha t  r e l a t i ons hi p t u pl e s  a r e   c om bi ne d t o ge t h e r  i n t o  a  s i n g l e  p a r t i t i o n .   P a r t i t i o n i n g   b a s e d  o n   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ A A S     I S S N 225 2 - 88 14       G r a p B as e d W or k l o a Dr i v e P ar t i t i oni ng   Sy s t e m   by   Us i ng   M on g oDB   ( A r v in Sah u )   37   r e l a t i on  r e d uc e s  t he  n um be r   o f  di s t r i but e d t r a ns a c t i o ns  a nd  i nc r e a s e   T h r o ug h put .  T P C - C  be nc hm a r k i s  us e d   f o r   va l i da t i o of  p r op os e d s y s t e m .  P r o p os e d s y s t e m  im p r o ve s  t he   r e s p ons e  t i m e  a nd  t hr o ug h put ,   w hi c h   i s   c on s i de r a bl y  l e s s  t ha n t he   T P C - C  s c he m a .  He nc e ,  p r o pos e d a p pr oa c h s ho w s   be t t e r  r e s ul t s  i n  t e r m s  of   d is tr ibu te d   t r a ns a c tio n s   a nd   thr oug hpu t.       R EF ER E N C ES   [1]   D a s ,  S udi pt o,   D i v y a k a nt  A gra w a l ,   a nd A m r E l  A bba di .   " E l as T r aS :  A n   el a s t i c,  s cal ab l e,  a n d  s el f - m an ag i ng   t ra ns a c t i ona l  d a t a ba s e  fo r t h e   c l o ud. "   A CM  T r ans ac t i ons  on  D at a bas e  Sy s t e m s  ( T O D S )   38. 1:  5 ,  20 13.   [2]   A l ex  P o t h en , H .  D . S i m o n , L i e W an g , an d  S t ep h en  T Be rn a rd T ow a rds  a  fa s t  i m pl e m e nt a t i on of s pe c t ra l  n e s t e d   d is s e c tio n .  In  S upe r c om put i ng ’ 92  P r oc e e di ngs ,  pa ge s   42 51 ,  19 92.   [3]     A l e x P ot he n,  H ors t  D .  S i m on,   a nd K a ng - P u L i o u.   P a rt i t i oni ng   s pa rs e  m a t ri c e s   w i t h e i ge nve c t or s  of gra phs S IA J our nal  of  Mat r i x  A na l y s i s  and  A ppl i c at i ons ,  11(3 ): 430 452,  1990 .   [4]     G ar y  L . M i l l er S h an g - H u a T en g , an d  S t ep h en   A.   V a va s i s .  A  uni fi e d ge om e t ri c  a pproa c h t o gr a ph s e pa ra t ors .  In  P r oc e e d i ngs  of  3 1s t  A nnual  Sy m p os i um  on F ound at i ons  of  Com put e r  Sc i e nc e ,  pa g e s  538 547,  1991 .     [5]   Curi no,  Ca r l o,   e t  a l .   " S c hi s m :   a  w orkl oa d - dri ve n  a pproa c h t o d a t a ba s e  r e pl i c a t i on  a nd pa r t i t i o ni ng . "   P r oc e e di ngs  o f   t he  V L D B   E ndo wm e nt   3. 1 - 2:  4 8 - 57 ,  2010 .   [6]   K a r y pi s ,  G e orge ,  a nd V i pi n K um a r.   " M E T I S   u ns t ruc t ure d gra p h pa rt i t i on i ng a nd s pa rs e  m a t ri x orde ri ng s y s t e m ,   ve rs i on 2. 0 . " 19 95.   [7]     T at ar o w i cz, A u b r e y  L ., e t  al " L ookup t a bl e s :  F i ne - gra i n e pa rt i t i oni ng for di s t ri but e d da t a ba s e s . "   2012 IE E E  28t h   Int e r nat i onal  Co nf e r e nc e  on  D at a E ngi n e e r i ng . I E E E ,   2012 .   [8]   Q ua m a r,  A bdul ,  K .  A s hw i n K u m a r,  a nd  A m ol D e s hpa nde .   " S W O RD :  s c a l a bl e  w orkl oa d - a w ar e  d at a p l ac e m en t  f o r   t ra ns a c t i ona l  w orkl oa ds . "   P r o ceed i n g s  o f   t he  16t h Int e r nat i onal  Conf e r e nc e  on E x t e ndi ng D at aba s e   T e c hnol ogy . A C M ,  2013 .   [9]   W an g , L u , et  a l " H ow  t o pa rt i t i on a  bi l l i on - n ode  gra ph. "   2014 IE E E  30t h Int e r nat i onal  Con f e r e nc e  on D at E ngi ne e r i ng. IE E E ,  2014 .   [10]   D i ng,  Chri s  H Q ,  e t  a l .   " A  m i n - m a x c ut  a l go ri t hm   for gra ph  pa rt i t i oni ng  a n d da t a   c l us t e r i n g. "   D at a Mi ni n g,   2001. ICD M 200 1,  P r oc e e d i ngs  I E E E  Int e r nat i on al  Conf e r e nc e  o n   I E EE ,  2001.   [11]   Choe ,  T a e - Y oun g,  a nd Cha n - Ik  P a rk.   " A k - w a y   gra ph pa rt i t i on i n g a l gori t hm  ba s e d on c l us t e ri ng  b y  e i ge nv e c t or . "   Int e r nat i onal  C o nf e r e nc e  on  Co m put at i onal  Sc i e nc e .   S pri nge r  Be rl i n H e i de l b e rg,   2004. A P A .   [12]   L aS al l e,  D o m i n i q u e,  an d  G eo r g e  K ar y p i s " A  P a r a ll e l H il l - Cl i m bi ng Re _ne m e nt   A l gori t hm  for G ra ph P a rt i t i oni ng . "   2015.   [13]   P re da ri ,  M a r i a ,  a nd A ur_e l i e n E s na rd.   " Coupl i ng - a w a re  gra ph pa r t i t i oni ng a l gori t h m s :  P re l i m i na r y   s t ud y . "   2014 21s t   Int e r nat i onal  Co nf e r e nc e  on  H i g h P e r f or m anc e   Com put i ng ( H i P C) .   IE E E ,  2014 .   [14]     M cC a_ r e y , J a m es  D " G ra ph pa rt i t i oni ng  us i ng a  S i m ul a t e d  Be e  Co l on y  a l gori t hm . "   Inf or m at i on R e us e  a nd  Int e gr at i on  ( IR I),  2011  IE E E   In t e r nat i onal  Conf e r e nc e  on   I E E E ,  2 011.     Evaluation Warning : The document was created with Spire.PDF for Python.