I n t ern a t i o n a l  J o u rn a l  o f  E l ect ri ca l  a n d  C o m p u t er E n g i n eeri n g  ( I J E C E )   V o l.   8 ,  No .   5 O c t obe r   20 1 8,  p p.  32 21~ 3 231   I S S N :  2088 - 8708 D O I :  10. 11 591/ i j ece . v8 i 5 . pp 322 1 - 3231          3221       Jou r n al  h om e p age h ttp : //ia e s c o r e . c o m/ j our nal s / i nde x . php/ I J E C E   A De t er m inis t ic   E v ict io n   M o del f o R e m o v ing  R edun da ncies  in  Video   Co rpus       Jyot i  M al h ot r a Ja gd i s h  B ak al   D ep ar t m en t  o f  C o m p u t er  S ci en ce &  E n g i n eer i n g G .  H.  R a i so n i   C o l l eg e o f  E n g i n eer i n g ,  N ag p u r ,  af f i l i at ed   t R TM   Un i v e r si t y  Na g p u r ,   I ndi a         A rt i cl e I n f o     AB S T RAC T   A r tic le  h is to r y :   R ecei v ed   J un  15,  201 7   R e v i s e d J a n  25,  20 18   A ccep t ed   A u g  2 6 2018       T h e t r ad i t i o n al  s t o r ag e ap p r o ac h es  ar e b ei n g  ch al l en g ed  b y   h u g e d at v o l u m es .  I n  m u l t i m ed i a co n t en t ,   ev er y   f i l e d o es  n o t   n eces s ar i l y  g e t  t ag g ed  as   a n e x a c t  dupl i c a t e ;  r a t he r  t he y  a r e  pr one  t o e di t i ng  a nd r e s ul t i ng  i n s i m i l a r   co p i es  o f  t h e  s am f i l e.  T h i s  p ap er   p r o p o s es  t h e s i m i l ar i t y - b as ed   d ed u p l i cat i o n  ap p r o ach  t o   ev i ct   s i m i l ar  d u p l i cat es  f r o m  t h e ar ch i v e s t o r ag e,   w hi c h c o m pa r e s  t he  s a m pl e s  o f  bi na r y  ha s he s  t o i de nt i f y  t he  dupl i c a t e s .   Th i s   e v ic tio n  is   d o n e  b y  in it ia lly  d iv i di ng  t he  q ue r y  v i de o i nt o  dy na m i c   k e f r a m es   ba s e d on t he  v i de o l e ng t h.  B i na r y  ha s h c ode s  of  t he s e   f r a m e s  a r e   t he c o m p a r e d   w ith  e x is tin g   ke y f r a m e s   to  id e n tif y  th e  d i f f e r e n c e s .   T h e  s i m ila r it y   s co r e i s  d et er m i n ed  b as ed  o n  t h es e d i f f er en ce s ,   w h i ch  d eci d es  t h e er ad i cat i o n   s t r at eg y   of  dupl i c a t e  c opy .  D upl i c a t e  e l i m i na t i on g oe s  t hr oug h t w o l e v e l s ,   na m e l y  r e m o v a l  o f  e x a c t  dupl i c a t e s  a nd s i m i l a r  dupl i c a t e s .  T he  pr op os e a ppr oa c h ha s  s h or t e ne d t he  c o m pa r i s on w i ndow  b y   c om pa r i n g  onl y  t he   can d i d at e h as h  co d es   b as ed  o n  t h e d y n a m i k e y  f r a m es   an d  ai m s  t h e accu r a te   l os s l e s s  dupl i c a t e  r e m ov a l s .   T he   pr e s e nt e d w or k  i s  e xe c ut e d a nd t e s t e d on t he   pr o duc e d s y nt he t i c  v i de da t a s e t .   R e s ul t s  s h ow  t he  r e duc t i on  i n   r e dun da nt   d at a an d  i n cr eas i t h e  s t o r ag e s p ace.  B i n ar y  h as h es  an d  s i m i l ar i t y   s co r es   co n tr i b u te d   to   a c hi e v i ng  g ood  de dup l i c a t i o n r a t i o  a nd  ov e r a l l  pe r f or m a nc e .   Ke y wo rd s :   A r c hi ve   C o m pa r i s on  w i n do w   D e d u p lic a tio n   H as h  co d es   M u lti m e d ia   S i m i l ar i t y  s co r es   C opy r i g ht   ©  201 8   I ns t i t ut e  o f  A d v anc e d E ngi ne e r i ng  an Sc i e nc e   A l l  ri g h t s re se rv e d .   Co rre sp o n d i n g  Au t h o r :   J y o ti M a l h o tr a   D ep ar t m en t  o f  C o m p u t er  S ci e n ce &  E n g i n eer i n g ,   G .  H .  R a i s o ni   C o l l e ge  o f  E n gi ne e r i n g,  N a gp ur ,  a f f i l i a t e d  t o  R T M  U ni ve r s i t y  N a gp ur ,  M S ,  I nd i a .     E m a il:  j y o ti. j . m a lh o tr a @ g m a il . c o m       1.   I NT RO D UCT I O N     T he  m ul t i - o b j e c tiv e  d e d u p lic a tio n  te c h n iq u e   w h ic h  r e m o v e s  t h e  d u p lic a te  f ile s  is   m a k in g  it s   r e le v a n c e   a n d  a p p lic a b ilit y   i n   th e   s to r a g e   w o r ld .   I n   t h e   v ie w   o f   d ig ita d a ta ,   it s   g r o w t h   [ 1 ]   a n d   its   s t o r a ge   c ha l l e nge s ;   t he   p r o g r es s  o f  d ed u p l i cat i o n  can  b e s een   f o r  t ex t u al  d at a [ 2 ] [ 3 ] , [ 4 ] , [ 5 ] ,   [6 ]   an d  r el at i o n al     d at a [ 7 ],  [ 8 ] .  C o m p ar at i v el y   l es s  r es ear ch  i s  o b s er v ed  f o r  m u l t i m ed i a f i l es .  T h er e i s  a h u g m u l t i m ed i a   uni ve r s e   w i t hi t he   d a t a   un i v e r s e   w hi c i s   gr o w i n f a s t   i n   t he   p o p ul a r i t y b e c a us e   o f   s o c i a l   m e d i a ,   o nl i ne   co u r s es ,  d i s t an ce l ear n i n g ,  p r es en t at i o n s ,  s el f - s t ud y  a nd  g r o w t h o f  s m a r t p ho ne  d e vi c e s  i nc l ud i ng  m o b i l e   p ho ne s  a nd  t a b l e t s .  W i t h t he   g r o w t h  o f  i nt e r ne t   us a ge  a l o n w i t h a n i nc r e a s e   i i nt e r ne t  b a nd w i d t h,  t he r e   ha s   b een   s i g n i f i ca n t   i n cr eas i n   o n lin e   v id e o   d a ta  s tr e a m i n g   a l on g   w i t h   v i de da t a   do w n l oa di n g .   V i de os   a r e   b eco m i n g  a p o w er f u l  e - l e a r ni n g t r e n d.  F r o m  e du c a t i o n   vi e w poi nt ;  s t u de n t s ,  r e s e a r c h e r s ,  pr of e s s or s ,  a n d   in d iv id u a ls   a l s o pr e f e r   w a t c h i n g   v i de os  i ns t e a d of  r e a di n g   m a nus c r i pt s  or  book s .   T h e  m a j o r ity  o f  th e m  p r e f e r   d o w nl o a d i ng t he  vi d e o s ,   w hi c h r e s ul t s  i n a  h uge   vi d e o  b a s ke t  r e s ul t i ng  t h e n eed   fo r   d a ta  r e d u c tio n  in   cas e o f   r e du n da n c y .  W i de l y   u s e m e t h ods   f or  r e du c t i on a r e  c o m pr e s s i on a n d de du pl i c a t i on .  M P E G  [ 9 ]  a ddr e ss e s  t h e   c om pr e s s i on   o f  i nd i vi d ua l   vi d e o s  b u t n o t s i m ila r   v id e o s .   I n lin e  d e d u p lic a tio n  [ 10 ]  l i m i t s  t h e s t o r ag e o f  a d u p l i cat e f i l e.   T h e s ear ch  f o r  d u p l i cat es  o ccu r  b ef o r th e  f ile  is   s to r e d ,  b u t th is  i s  v e r y  t i m e - c o ns u m i n g a nd  r e s o ur c e - i nt e ns i ve  p r o c e s s ;  p a r t i c ul a r l y   w i t h t he   v i de f i l es   w h er ei n   C P U  an d   m e m o r y  r es o u r ces  ar k ep t  b u s y   t i l l  t h e p r o ces s  o f  v i d eo  s t r ea m i n g ,  a n d  a d u p l i cat e   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SSN :   20 88 - 8708     In t  J  E l e c  &  C o m p  E n g ,   V o l.   8 , N o 5 O c t obe r  20 18   :   322 1   -   3231   3222   c h e c k   i s  ov e r .  W hi l e  i n  t h i s   w or k ,   w e   f oc us  on  a r c h i v e  s t or a g e  a n d pr opos e  t h e  pos t - pr oc e s s  de du pl i c a t i o n  on  th e  v id e o s   w ith   t he   d y n a m ic  s p litti n g  o f  t h v i d eo s  a n d  r ed u ced  co m p ar i s o n  can d i d at k e y   f r a m es  b as ed  o n   vi d e o  l e ng t h a nd  d up l i c a t e  r e m o va l   w i nd o w .   T h e p r i m e o b j ect i v e o f  d ed u p l i cat i o n  i s  t o  r ed u ce  m u l t i p l r e d und a nt   c o p ie s .  D e d u p lic a tio n   p er f o r m a n ce d ep en d s  o n  t h f act o r s  s u c h  as -   co m p ar i s on   w i n do w ,  s pa c e  s a v i n gs ,   m e t a da t a  l ook u p a n d a bov e   al l  t h e accu r ac y  p er cen t a g o f  d u p l i cat e co n t en t .  T h e p er f o r m an ce r i s e s   w i t h   m o r e d u p l i cat es  an d   m o r s i m ila r it y .  U n li k e  o th e r  te x t  d e d u p lic a tio n   m e t h o d s ,  d u p lic a te  r e m o v a l r a tio  i s  i m p r o v e d  in   m u lt i m e d ia   c o n te n t b y  id e n t if y i n g  s i m ila r  d u p lic a te s .  V id e o  s i m ila r it y   c a n  o c c u r   w it h  r e s p e c t to  r e s o lu tio n ,   f o r m a tti n g ,   f r a m e   r at e a n d  co n t e n t  d i f f er en ce.   T h e e x i s t i n g   w r i t t e n   w o r k   f o cu s e s  o n  t h e p r o g r es s  o f   s i m i l ar   f eat u r es   a m o n g t he  vi d e o s .  I n [ 1 1 ] ,  t he  a ut ho r  p r o p o s e s  t h f r am ew o r k ,  a i m i n g  a n  ef f i ci e n t  an d  f as t  d u p l i c a t e r em o v al   p r o ces s .  K e y  f ac t o r s  ar e -   h as h  t ab l e i n d ex i n g ,  v i d eo  s i m i l ar i t y  an d  t e m p o r al  l o cal i t y  o f  t h f r a m e s .  T h e au t h o r   cr eat es   m u l t i p l e b u c k et s  an d   each  b u c k et  s t o r es  t h e e x t r act ed  f r a m es   s h ar i n g  t h e s a m h as h  co d e.   F r a m e s   ex t r act ed  i n  t h e b u c k et  ar e q u er i ed  f o r  f i n d i n g  t h e s i m i l ar i t y   an d  r e m o v i n g  t h e d u p l i ca t es .     N ear - d u p l i cat e r e m o v al  b as ed  o n  s h o t - s i m i l a r i t y  i s  pr opos e d i n  [ 1 2 ] ,  t o  i d en t i f y  t h e d u p l i cat e s cen e   sh o t s .  I t   f o c u se s  o n   t h e  s a m e   e v en t  cap t u r ed   w i t h  d i f f er e n t   ca m er as ,  a n g l es ,  an d  d i f f er en t  t e m p o r al  o f f s et s .   A   s i m ila r it y  b e t w e e n  a  s e t o f  tr a j e c to r ie s  is  c a lc u la te d  f o r  f i n d in g   th e  d u p lic a te s .  T h e  s i m ila r it y  is   m e a s u r e d  f o r   s t r i ct  n ear  d u p l i cat e s ,  o b j ect   d u p l i cat es ,  an d  s ce n e d u p l i ca t e s .  T he  a ut ho r s  o f  [ 1 3 ],  [1 4 ]  h a v e  pr opos e d a   s e c u r e  v i de o de du pl i c a t i on   f r a m e w or k  ba s e d on  H . 264 c o m pr e s s i o n  a n d a  bl oc k  l e v e l   c ode c  u s e d f or  h i gh  de f i n i t i on   v i de os .   A   s e c u r i t y   pa r a m e t e r  i s   f oc us e d on  e n c r y pt i on ,  pr oof  of   s t or a g e ,  pr oof  of  o w n e r s h i p a n d   re t r i ev al .  H o w e v er ,  s h o t  a n d  s cen e s i m i l ar i t y  an d  s ec u r i t y  as p ect s  ar e n o t   w i t h i n  t h e s co p e o f  t h i s  p ap er .   H as h i n g  b as ed  o n   m u l t i p l e f eat u r es  f o r  d et ect i n g  n ear - d u p lic a te  v id e o s  is  ill u s tr a te d  in  [ 1 5 ] S i m i l ar i t y  a n d  p er f o r m an ce ar e ev al u at ed  b y  cal c u l at i n g   E u cl i d ean  d i s t an ce a n d   m ea n  av e r ag e p r eci s i o n .  T h e   r es ear ch  p r es en t ed  i n  [ 1 6 ]  i n t r o d u ces  an  e f f i ci e n t   y e t  ef f ect i v e n o v el   g l o b al  d es cr i p t o r ;   w h er e n o n - g eo m et r i c   di s t or t i on s  a n d a l l  ot h e r  t r a ns f or m a t i on s   f or  v i de f or m a t  f i l e s  r e s u l t   i n de t e c t i on of  n e a r  d u p l i cat v i d eo  co p y   t a sk s.   F or  pr oc e s s i n g   v i de os ,  t h e y  a r e  c onv e r t e d i n t o i m a ge  f r a m e s ;  a u t h or s  of  [ 1 7 ]  in v e s tig a te d  E u c lid e a n   d i s t an ce a n d  s h ap e b as ed  s i m i l ar  i m a g e r et r i ev a l  b y   m e an s  o f   Z er n i k m o m en t s .  T h e v al i d i t y  o f  d i g i t al   i m a ge s  i s   ve r i f i e d  b y  c o m p a r i ng  hi s t o gr a m  a nd  p r i nc i p a l  c o m p o ne nt  a na l ys i s  o f  t w o  i m a ge s  b y  t he     a ut ho r s  o f  [ 1 8 ].     T h i s  pa pe r  f oc u s es  o n  r e m o v i n g  d u p l i cat e a n d  s i m i l ar  v i d eo s  f r o m  t h e b ack u p  o r  ar ch i v e s t o r ag e.   T h e ar ch i v e  i s  a co l l ect i o n  o f  o l d er  an d  i n act i v e d at w h i c h  i s   h ar d l y  e v er  acce s s ed .  I t  d eal s   w i t h  l o n g - t e r d at a p r es er v at i o n .  W e i n t en d  t o  r ed u ce t h e m u l t i m ed i a d at a s i ze  o f  t h e ar ch i v es  b y  p er f o r m i n g  d ed u p l i cat i o n   o n  t h v i d eo s .  C o m p ar i s o n   w i n d o w  i s  s h o r t en ed  b y  an  e f f ect i v e s a m p l i n g  o f  t h e r eq u i r ed  k e y  f r a m es  b as ed  o n   le n g th   of  t h e   v i de o.   I n  a d d itio n ,  a f te r  f in d i n g  th e  s i m ila r it y ,  th e  c o p y   w h ic h  o c c u p ie s  le s s  s p a c e  is  p r e s er v ed   i n  t h e s t o r ag e.  I t  i s  a t w o   l ev e l  ap p r o ach ,   w h er e t h e v i d eo  i s  ch ec k ed  f o r  t h e e x act  d u p l i c at es ;  t h i s  r es u l t s  i n   t h e r e m o v al  o f  a d u p l i cat e co p y  i f  an  ex act  co n t e n t   m a t ch  i s  f o u n d .  I f  t h e ex act  d u p l i cat e  co p y  i s  n o t  f o u n d ,   t he n t he  s ys t e m  s e a r c he s  f o r  t h e n ear  d u p l i cat e o n es  a n d  t h e y  ar e r e m o v ed  b y  s i m i l ar i t y  r a n k i n g  o f  t h f r a m e s   b as ed  o n  t h ei r  b i n ar y   h as h es .     T h e  o rd e r o f t he  r e m a i ni n g s e c t i o ns   in   t h is  a r tic le   is   s t r uc t ur e d   a s f o l l o w s .   D e s c r i pt i on  of   de s i gn  a n a l g or i t hm   f or  r e m ov i ng  n e a r - d u p lic a te   vi de os  i s  e x pr e s s e d i S e c tio n   I I .  B e s i d e it ,  t he   s ect i o n   a ls o  ill u s tr a te s   m o d el   d es cr i b i n g   t h d at g r o w t h   a n d   d at r em o v al   r at e   i n   an   ar c h i v e.   P er f o r m a n ce  an al y s i s   a n d   r es u l t s   s t a t i ng t he  s t o r a ge   s a vi n gs   ar illu s tr a te d  in  s e c tio n  I I I .  T h e   w o r k   i s c o nc l ud e d   in  S e c tio n  I V .       2.   SY ST E M   P RO CE DURE   2 .1 .     V i de o  R e dunda nc y  E l i m i na t i o n   D e d u p lic a tio n  i s  a  p a r titio n   d ic h o to m y  o f  t h e   v i de os  i n t o  t w o oppos e d c l a s s e s = {d u p l i cat es ,  n o n - d u p l i cat es } b as ed  o n  t h ei r   f i n g er p r i n t  v al u es .  V i d eo s  ar e p r o n e t o  ed i t i n g  t r e n d s ;   w h ic h  r e s u lts  in   its  a l te r a tio n   a n d  f i ltr a tio n .  W it h  r e s p e c t to   g e n e r ic   v id e o  e d itin g  tr e n d ; t h e  d u p lic a te  c la s s  c a n  b e  f u r t h e r  a lie n a te d  i n to  t w o   s u b cl as s es :  { n ear - d u p lic a te s ,   n o - du pl i c a t e s }  ba s e d on s i m i l a r i t y  p er cen t a g e  a m o n g  t h v i d eo s .   C ons i de r i ng  t he   s ce n ar i o  t h at  t h er e ar V   v i de os ,   n   co p i es   o f  t h e v i d eo  an d  ev er y  v i d eo  t ak es  t h e s t o r ag s p ace  V s ,  t he n t he   t o t al  s t o r ag s p ace o v er h ead   T ota l sp a c e   an d  t h e d u p l i cat e  d eg r ee  Du p d eg r ee   can  b e co m p u t ed  as   g i v e n  i n   E q ua t i o ( 1 )   a nd   ( 2 ) :                          =   = 1         ( 1)     Evaluation Warning : The document was created with Spire.PDF for Python.
IJ E C E     I S S N :  2088 - 8708       A   D e te r m in is tic  D e d u p lic a tio n  M o d e l fo r  R e m o v in g   R e dun da nc i e s   ( J y ot i  M al hot r a)   32 23      =                ( 2)   T h e t ar g et  i s  h o w  t o  f i n d  t h es e d u p l i cat e co p i es   n   t o  m i n i m i ze t h e r eq u i r ed  s t o r ag e s p ace an d   d u p l i cat e d eg r ee.  T h e s y s t e m   ar ch i t ect u r e f o r  t h e ap p l i cat i o n   w h i ch  ai m s  t o  co n t r o l  t h m ed i a cr o w d  i n  t h e   ar ch i v e a n d  l es s e n  t h e n u m b e r  o f  co p i es   n   is  a s  e x p o s e d  in  F ig u r e  1 .   T h e  a p p lic a tio n  i m p le m e n ts  d u p lic a te   v i d eo  el i m i n at i o n  p r o ces s  i n   t w o  p h a s es   n a m e l y ,  d u p l i ca t ch eck  b as ed  o n  t h v i d eo  s i g n at u r e s  an d  s i m i l ar   f r a m e s .  D e s c r i pt i o n  of  t h e s e   m odu l e s  i s   g i v e n i A l g or i t hm  1 a n A l g or i t hm  2.  T a bl e  I  br i e f  v a r i ous   n ot a t i ons  a n m e t h ods  us e d i n t h e s e  a l g or i t hm s .       T ab l e 1 .   G l o ss a r y  o f  N o ta t i ons  a n d M e t h ods   N o t a tio n s   Me t h o d s   N o t a tio n   Me a n in g   Me t h o d   Me a n in g   Q v   Q u er y  V i d eo   V i d eo   D e d u p ( )   F i n d  d u p l i c a t e   v i d e o s   H a   H a s h   a l g o r i t h m  f or  v i d e o  s i gn a t u r e   G et   Ha s h   F i n g e rp ri n t s ()   L o a d  f i n g e r p r i n t s  a v a i l a b l e  i n  t h e  m e t a d a t a   Ha s h MD   M e t a d a t a  h a s h   f i n g e r p r i n t s   F i n g er   P ri n t ()   C a l c u l at e h a s h  s i g n a t u r e o f  v i d eo   Du p t y p e   T y p e  o f  d u p l i c a t e     n e a r / n o   U p d a t e   M e t ad at a( )   P a s s  t h e r ef er en c e l i n k  f o r  t h d u p l i c at v i d eo   HC MD   C o l l e c t i o n  o f  h a s h   c o d e s  i n   m e t a d a t a   S im il a r i ty   C h e c k ( )   C h eck   s i m i l a r i t y  s c o r e b et w een  t h e v i d eo s   K F Qv   Q u er y  v i d eo   k ey  f r a m es   G et   Fr a m e   Ha s h   C o d es ( )   L o a d  h a s h   c o d e s  a v a i l a b l e  i n   t h e  m e t a d a t a   H C Q kf   C ol l e c t i o n  of  h a s h   c o d e s  i n   q u e r y  vi d e k ey  f r a m es   E x t r a ct   F ra m e s ()   S p l i q u e r y  v id e o  in t o   k ey  f r a m es   H kf   Ha s h   a l g o ri t h m  fo k e y  fra m e s   C a lc u la t e   H a sh ( )   C a l c u l at h a s h  c o d e   o f   k ey  f r a m es   C a nd H C Q kf   Q u e r y  v i d e o  c a n di d a t e   h as h  co d e s   S el ec t   C an d i d at es ( )   S el ec t  c o m p a r i s o n  ca n d i d at e k ey  f r a m es   C a nd H C MD   M et ad at a  v i d eo  c an d i d at h as h  c o d es       Di s t y x   D i s t an c e b et w e en   h a sh   c o d es   x  a n d  y       τ   P a r a m et er  f o r  s a m p l i n g  c an d i d at e h a s h   c o d es       S i m s c o r e   L is t o f  s i m il a r ity  s c o r e  o f  c a n d i d a te   h a s h  c o d e s       f i n a l S i m s c or e   F in a l  s im il a r ity  r a n k i n g       ω   D ec i s i o n   p a r a m et er  f o r  n ea r - d u p l i ca t es       γ   P a r a m et er  f o r  s el ec t i n g  can d i d a t k ey   fra m e               F i gu r e  1.   S ys t e m   ar ch i t ect u r e       A l g o r i t h m s   s eek i n g  t h e r ed u c t i o n  o f  s t o r ag e s p ace  ar e p r es en t ed  b el o w .   A l g o r i t h m  1  d es cr i b es  t h e   hi g h - l e v e l  ope r a t i on a l  f l o w  o f  t h e  de du pl i c a t i on pr oc e s s .  I n pu t  i s  t h e  qu e r y   v i de o a n h a s h  a l g or i t hm  [ 1 9 wh i c h   us e s  a va l a nc he  e f f e c t .   T he  f i n ge r p r i nt  o r  ha s h  s i gna t ur e  o f  q ue r y vi d e o  i s   m a t c he d  a ga i ns t  t he  e xi s t i n g   f i n g er p r i n t s  i n   t h e   m e t ad at a.   O n  t h e e x act   m a t ch ;  a d u p l i c at e co p y  i s  r e m o v ed ,  an d   m et ad at a i s   u p d at ed  b y   p as s i n g  t h e r ef er e n ce l i n k   f o r  t h e d u p l i cat e c op y .  I f  a   m a t c h i s  n ot   f oun d qu e r y   v i de o i s  gi v e n   t o t h e   m e t h od  de s c r i be d i n  A l g or i t hm  2 f or  f i n di ng  i t s   s i m i l a r  c opy .   A l g or i t hm  2 e xh i bi t s  t h e  pr oc e s s  f or  f i n di n g   s i m i l a r i t y   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SSN :   20 88 - 8708     In t  J  E l e c  &  C o m p  E n g ,   V o l.   8 , N o 5 O c t obe r  20 18   :   322 1   -   3231   3224   s c or e s  of  t h e   v i de os .   A l g or i t hm  l oa ds  t h e   k e y   f r a m e   h a s h c ode s   av ai l ab l e i n  t h m et ad at a  co r p u s .  T h e l en g t h   of   m e t a da t a  c or pu s  i s  a s  g i v e n i n  E qu a t i on   ( 3 ) ,  w h er v   i s  num be r  of   v i de os  a n kf   i s  num be r  of  k e y   f r a m e s .     |   | =     = 1 =               (3 )     Q u e r y   v i de o i s  di v i de d i nt K F Qv   k e y  fr a m e s .  L e n g t h   o K F Qv   i s  d yn a m ic  a n d  it d if f e r s  a s  p e r  th e   v i d eo  l en g t h .  H as h  co d es  [ 20 ]  ar e cal cu l at ed   f o r  al l  t h e s e k e y   f r a m e s .  U n d er s t a n d i n g  t h l en g t h  o f   m et ad at a   c or pu s | H C M D | ,  can d i d at e h as h  co d es   C a nd H C Q kf   a nd   C a nd H C M D   ar e  s el ect ed  f r o m  q u e r y   h as h co d es  an d   m et ad at h as h co d es  b as e d  o n   t h e p ar a m et er   τ   a s  il lu s tr a te d  in   A l g o r ith m   3 .  T he   va l ue  o f   τ   i s   ke p t  d yna m i c  a s   p e r  t he   va l ue  o f   K F Qv . F o r  each  ca n d i d at e h a s h  co d es ,  d i s t a n ce i s  cal c u l at ed  b y  co m p ar i n g  t h e co d es  as  p er   E q ua t i o ( 4 ) .  S i m i l ar i t y   s co r e i s  cal cu l at ed  f r o m  t h es e d i s t a n ces  as  s h o w n  i n  E q u at i o n   ( 5 ) ,   f o r  each  can d i d at h as h  co d es   l .  A f te r  c a lc u la tin g   th e  in d i v id u a l s i m ila r it y  s c o r e ,  th e  f i n a l s i m ila r i t y  r a n k i n g  o f  q u e r y  v id e o  is   c a l c ul a t e d  b y  t a ki n g a n a ve r a ge  o f  t he  i nd i vi d u a s c o r e s .  I f   th is  f i n a s c o r e  is  b ig g e r  t h a n   th e  s ta te d  th r e s h o ld     ω   ,  q u er y   v i d eo  i s   m ea s u r ed  as   a n ear - d u p l i cat e o n e  as  d es cr i b ed  i n  E q u at i o n   ( 6 ) .  T h e f i n al   s co r e l es s  t h a n  t h t hr e s ho l d   ω ,   m ean s  q u er y   v i d eo  i s  n o t  a d u p l i cat e a n d  i s  co n s i d er ed  as  a n e w  v id e o  f ile .  T h is   n e w   v id e o  is   s t o r ed  i n  t h e s t o r ag e a n d  k e y  f r a m e d et ai l s  an d  t h ei r  r es p ect i v e h a s h  co d es  ar e s t o r ed  i n  t h e   m et ad at a.                         C o ns i d e r i ng  x =        a nd y  =     w e   g e t;   =   |     = 1 |               (4 )        = 1             (5 )   Q v = ne a r d up l i c a te ,   m s c o re   ω no d up l i c a te ,           (6 )         A lg o r ith m   1 :   V i d e de du pl i c a t i on   b a s e on   h a s h   s i gna t ur e s   A lg o r ith m   2 :   V i d e de du pl i c a t i on   b a s e on   h a s h   s im ila r iti e s   I np ut :  Q ue r y  vi de ; H a s h  A lg o r ith m     O u tp u t:  D u p li c a t e  ty p e     d u p l i cat e o r   n o - d u p lic a t e   B e gi n  vi de o   De d u p                   [   ]     g e t H a s hF i nge r pr i nt s ( )                      f i nge r P r i nt   ( , );                 S ea r ch       o f  t h e  v i d eo  i n  m e t ad at   [   ]                 i      [   ]   t he n                              V i d e o  i s  d u p l i c at e;  r em o v t h e co p y                              U pda t e   Me t ad a t a( )                 e l se                                 =  s im ila r i t y C he c k( )                              i      = N ea r - d u p l ic a te  th e n                                            V i d e o i s  U ni que ;  s a v e  t h e   c op y                              e l s e  //  v id e o  i s  d u p li c a te                                          upd a t e   M et ad a t a( )                 e nd i f   E nd   I np ut :  Q ue r y  v i de   O u t p u t :  D u p l i cat e t y p e {n ea r - dup l i c a t e ,   no - d u p l i ca t e}   B e g in  s im ila r i ty   C h eck             [   ] [   ]     g e t F r am eH as h C o d es ( )            [   ]     ex t r act F r am es   ( ) ; //D y n a m ic           fo r e a c h   ( k ey  f r am e i n    [   ] )                  [   ]    ←  ca l cu l at e   Ha s h (  , )            E nd   fo r            / / s e l e ct   can d i d at e h as h  c o d es              [   ]   s el ect C an d i d at es (   [   ] , )             [   ]   s el ect C an d i d at es (    [   ] , )           fo r e a c h (  ca n d i d a t e i n    [   ]   a nd                                                                                                                                       [   ] )                     C al c u l at   [   ]            e nd f or                  av e r ag e(   [   ] )             i f (       ≥    )  t he n                          =  “N ea r - d u p l ic a te            e l se                         =  “ No - d upl i c a t e   E nd     A l g o r ith m  3  ill u s tr a te s  th e   s te p s  f o r  s e le c tin g  s a m p le  c a n d id a te  k e y   f r a m e s  f o r  t h e  c o m p a r is o n .     Evaluation Warning : The document was created with Spire.PDF for Python.
IJ E C E     I S S N :  2088 - 8708       A   D e te r m in is tic  D e d u p lic a tio n  M o d e l fo r  R e m o v in g   R e dun da nc i e s   ( J y ot i  M al hot r a)   3225   A l g o r ith m  3 : C a n d id a te  k e y  f r a m e  s e le c t io n   I np ut :    [   ]  C o l l e c t i o o f  ha s hc od e s  i n m e t a d a t a   or   q ue r y  vi de o a n d     de c i di ng t he  c a n d i d a t e s   O ut p ut :    [   ]   B e g i s el ect  C an d i d at es                   f o r  e ach   ( ha s h  c od e     i  [   ] )                              i f   ( = = 1 )   t he n                                         [   ]   ←   [ ]                         e l se                                        [   ]   ←   [ + ]   E nd       2 .1 .   P r o b a b ilit y   M o de l  f o r  S im i la r  V id e o  D e le t io n   T h is   s e c tio n   ill u s tr a te s   t h e   p r o b a b ilis tic   a n d   d e te r m in is t ic   m o d e d e s c r ib in g   th e   f u n d a m e n ta l   r el at i o n s h i p s  b et w ee n  e x act  a n d  n ear - d u p l i cat e  v i d eo s ,   t h ei r  s t o r ag s p ace r eq u i r e m e n t  a n d  t h e r at e o f  t h ei r   gr o w t h a nd   r e m o va l .  T he   p r o b a b ilis tic  e x p e r i m e n t i n v o l ve s  r a nd o m   va r i a b l e s   na m e l y ,   vi d e o  ha s h s i g na t ur e s   an d   s i m i l ar i t y   s co r e.   G i v e n   s a m p l s p ace    o f     v i de os ;   w h e r e  t h e  pr oba bi l i t y  of  du pl i c a t e  v i de o i s  p a n no n - d u p lic a te  is  ( 1 - p ) ,  th e n  th e  p r o b a b ility  o f   g e tti n g  e x a c tl y   k  d u p lic a te  v id e o s  b a s e d  o n  th e   ha s h s i g na t ur e s   i s  a s  s ho w n i n E q ua t i o n ( 7 ) .     P ( k  D u p l i cat es )  =    p k   (1 - p)   V - k               (7 )     A s  v i d eo s  ar e ed i t i n g  p r o n e,  t h e p r o ces s  o f  r ed u n d an t  v i d e o  r em o v al  as   n ear - d u p l i cat es   i s  f u r t h er  p r o ces s ed   b a s e d  o n  its  s i m ila r it y   s c o r e       a nd  a  t hr e s ho l d  va l ue   .   T hr e s ho l d     is  th e  p a r a m e te r   w h ic h  illu s tr a te s   ab o u t  t h e s i m i l ar i t y  s co r e,  an d  t h e v al u e i s  l es s  t h a n  1 .   P r o b a b ility  th a t t h e       t a ke s  va l ue s  i n t he   in te r v a l f r o m     to   1   is  s a m e  a s  th e  p r o b a b ility  o f  a ll p o s s i b le   o u t co m e s   w h er e t h i s  s co r e can   c o me T h P r o b a b ility  d e n s i t y   an d  e x p ect ed  v al u e   o     f o r  its  n u m e r ic a p o s s ib ilitie s       ar e   de s c r i be d i n   E qu a t i on  (8 ) a n d  (9 ).                           P(   ≤        ≤  1 )  =    ( ) 1      (8 )       (   ) =   s   f S im sc o r e ( s ) d s 1 ω      (9 )       A  d is c r e te  ti m e   m o d e l illu s tr a te d  in  F i g u r e  2  d e s c r ib e s  th e  e v o lu tio n  f r o m   vi d e o   a r r iv a l f o r  th e   b ack u p  t o  i t s  s t o r ag e p r o ces s .  T h m o d el  h a s   s ix   p o s s ib le  s ta te s  a n d   s e ve n   p o s s ib le  tr a n s itio n s  b e t w e e n   th e   s ta te s  a n n o ta te d   w it h  t h e ir  r e p r e s e n ta ti v e  tr a n s it io n  p r o b a b ilitie s .   A t a n y   k n o w n  ti m e ; a f te r  th e  a r r iv a l,   vi d e o   can   m o v e t o  ei t h er  o f  t h e s t a t e s  s u c h  as  d u p l i cat e,  s i m i l ar  o r  n o n - d u p l i cat e b as ed  o n  t h vi d e o   ch ar act er i s t i cs   ( f in g e r p r in t,  s i m ila r it y  s c o r e ) .  O n c e  th e   vi d e o   is  id e n ti f ie d   as  a d u p l i cat e o r  m o r e s i m i l ar ,  t h e s y s t e m  g o es  t o   t he   vi d e o   r ef er en ce s t at e an d  s t a y s  i n  t h s a m s t at e.   T he  s ys t e m   s t a ys  i n t he   u ni q ue   vi d e o   s ta te  if  t h e r e  is  n o   m a t c h o n f i n ge r p r i nt s  a nd   v i de os   ar e n o t  s i m i l ar .         F i g ur e   2 P r o b a b ilis tic  d is c r e te  ti m e   m o d e f o r   vi d e o   s t o r a ge       1   1   0 .5   0 .5   0 .4   0 .3   0 .3   V id e o   R ef er e n ce   U ni q ue   V id e o   V id e o  A r r iv a l   D u p lic a te   No n - d u p lic a te   S im il a r   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SSN :   20 88 - 8708     In t  J  E l e c  &  C o m p  E n g ,   V o l.   8 , N o 5 O c t obe r  20 18   :   322 1   -   3231   3226   A f te r  n  tr a n s i tio n s  th e  to ta l p r o b a b ilit y  o f  s y s te m   st   s ta r tin g  a t s ta te     an d  en d i n g  at  s t at ,   s , t     a nd    in te r m e d ia te  s ta te s   i s  g i ve n i n E q ua t i o (1 0 ).                            ( ) =  ( 1 )  = 1                    ( 10 )     T o ta l p r o b a b ility  o f  s y s te m   s t a r tin g  i n  s ta te  1     vi d eo   a r ri v a l   a nd  e nd i n g i t he  s t a t e  5     “R e f er en ce”  i s a s   illu s tr a te d   b e l o i n t he  E q ua t i o ns   ( 11 )   to   ( 13 )     {s t at e 2 -   D u p lic a te   an d  s t at e 3 -   S im ila r }     1 5 ( ) =   1 2 ( 1 ) 2 5 +   1 3 ( 1 ) 3 5   ( 11)         1 5 ( ) =   0 . 3 1 + 0 . 3 0 . 5   ( 12)       1 5 ( ) =   0 . 4 5   ( 13)       T r a n s itio n   m a tr ix   f o r  t h e   m o d e l d e s c r ib e d  in  F i g u r e  2   is  a s  illu s tr a te d   in  T a b le   2 be l ow .   T h e  pr oba bi l i t y  of   g o in g   f r o m   v id e o  a r r iv a l”  to   d u p lic a te  is  3 0 % .  I n itia s ta t e  o f  s y s te m  i s  [ 1 , 0 , 0 , 0 , 0 , 0 ]  i. e .  f ir s s ta te   is   vi d eo   a r ri v a l .  At   o ne - t i me   u ni t  30%  vi de os  a r e  g o n e  i n t dupl i c at e   s t a t e ,  30%   v i de os   ar e g o n e   in to  “ s im i la r ity   s ta te ,  a n d 40%  of  t h e   v i de os  a r e  i n  “ non - dupl i c at e   s ta te .       T ab l 2 P r o b a b ility   T r a n s itio n  M a tr ix   S ta te s *   VA   DUP   S I M   ND   UN I   R EF   VA   0   0 .3   0 .3   0 .4   0   0   DUP   0   0   0   0   0   1   S I M   0   0   0   0 .5   0   0 .5   ND   0   0   0   0   1   0   UN I   0   0   0   0   1   0   R EF   0   0   0   0   0   1   * S ta te s ( V A - V i d e o  ar r i v al , D UP - D u p l i c at e,  S I M - S i m i l ar , N D - n o n - d u p l i c at e,  U N I - U n i q u e  v i d e o ,  R E F - V i d eo  r ef er en c e)       P r o b a b ility  D i s tr ib u t io n   te lls   t h at  af t er  r u n n i n g  t h e p r o ces s  f o r     v id e o s  ( ti m e  u n its ) th e   s y s te m  tr a v e l s  to  a   “u n i q u e v i d eo ” s t at w ith  p r o b a b ilit y     a n d   w it h  p r o b a b ility   sy s t e m   g o e s t o   r ef er en ce   v i de o”   s ta te T h e  s i m u l a t i on   w a s  don e  on  n= 100 v i de os  a n d t ot a l  pr oba bi l i t y   m e nt i o ne d  i n t he   E q ua t i o ( 10)   is  illu s tr a te d   b e l o a l ong   wi t h   t h e  p r o b a b i lit y  d i s tr ib u tio n   w it h  a n  a s s u m p tio n   th a t  th e  s y s te m  a lr e a d y   h a d  3 0  d u p lic a te   v i de os .       i s  gi ve n b y:   [ 0. 00  0. 0 0 0. 00  0. 00  0. 5 5 0. 45 ]   [ 0. 00  0. 0 0 0. 00  0. 00  0. 0 1 .0 0 ]   [ 0. 00  0. 0 0. 00  0. 00  0. 5 0 0. 50 ]   [ 0. 00  0. 0 0 0. 00  0. 00  1. 0 0   0. 00 ]   [ 0. 00  0. 0 0 0. 00  0. 00  1. 0 0   0. 00 ]   [ 0. 00  0. 0 0 0. 00  0. 00  0. 0 0 1. 0 0 ]   P r o b a b ility  d is tr ib u tio n  a f te r  r u n n i n g  th e   pr oc e s s   f or  100  vi de o s   i -   [ 0. 0,  0. 0,  0. 0 ,  0. 0,  0. 55 ,  0. 75 ]     i .e = 0 . 5 5      = 0 . 7 5   . . ( 0 . 4 5 + 3 0 )   T he  d e te r m in is tic   m o d e l   d e f i ne s   t he   f o r m ul a t i o n o f   i np ut s  a nd   o ut p ut s  o ve r   t he   t i m e   w he r e   i np ut s   a r e   t he   n u m b er  o f  d u p l i cat e ar r i v al s  an d  o u t p u t s  ar e t h e n u m b er  o f   d u p l i cat e r e m o v al s .   T h e r at o f  ch an g e o f  s t o r ag e   s p ace d ep en d s  o n  t h e  r a t e  of  vi de o a r r i v a l s  a n d r a t e  of  v i de o r e m ov a l s  a s  s t a t e d i n  E qu a t i on ( 14) .                            = (    ) (    )                      ( 14 )       Evaluation Warning : The document was created with Spire.PDF for Python.
IJ E C E     I S S N :  2088 - 8708       A   D e te r m in is tic  D e d u p lic a tio n  M o d e l fo r  R e m o v in g   R e dun da nc i e s   ( J y ot i  M al hot r a)   3227   C o ns i d e r i ng  0   as  t h e i n i t i al  v al u e o f  s t o r ag e s p ace,   w i t h  d u p l i cat e v i d eo  ar r i v al  an d  d u p l i ca t e v i d eo   r e m o v al  r at e p er  f i l as        ,  t h e s t o r ag e s i ze  ( )   at  an y  t i m   c a n  be  o bt a i n e d by  r e w r i t i ng  E qua t i on   ( 1 4 )  a s  gi ve n i n E q ua t i o n ( 1 5 ) .                              = ( ) =   ( )     ( )            ( 15)       =                  ( 16)       L e t   =     i n  E qu a t i on  16,   w e  obt a i n   =                   ( 17)       A f te r  s o l v in g  t h is  d i f f e r e n tia e q u a tio n ,   w e  g e -       ( ) =   0             ( 18)     A c c or di ng   to  E q u a tio n   ( 18 ) ,  t h e  r at e o f  c h an g e o f   s t o r ag s p ace o n   t h e  r e m o v al  o f  d u p l i cat es   d e p e nd s  o n t he   va l ue  o f  r ,  a nd  i t  s ho ul d  b e  gr e a t e r  t ha n   zer o .  T h i s  p ap er  ai m   t o  k eep  t h v al u e   o f  r  ( d u p lic a te   v i de a r r iv a ls - d u p lic a te   v id e o  r e m o v a ls )     0 by  r e m ovi ng   m or e  du pl i c a t e  c opi e s .       3.   RE S U L T S  AND D I S CU S S I O N   I n  t h i s  s ect i o n ,   w f i r s t l y  co m p ar e t h e co m p r es s i o n  r at i o  b et w ee n  t h v i d eo s  b y  co m p ar i n g  t h h as h es  g e n er at ed  b y  a v al an c h e ef f ect  an d  t h e b i n ar y   h as h e s .   S eco n d l y ,   th e  p e r f o r m a n c e  o f  s i m ila r it y   s co r an d  p r eci s i o n - r ecal l   i s  o b s er v e d .  E x p er i m e n t at i o n   w as  i m p l e m en t ed  o n   t h e  co m b i n ed  d at as et  b y  t ak i n g  a  f e w   v i d eo s  f r o m  t h e d at as et  [ 21 ] A  s y n t h et i c d at as et  i s   g en er at e d  acco r d i n g  t o  t h e p r i n ci p l es  d i s cu s s ed  i n  [ 2 2 ]  on  t he  vi d e o s  f r o m   [ 2 3 ] ,  Y o uT ub e   v i d eo s  an d  a p er s o n al  v i d eo  co l l ect i o n .  D at as et  v i d eo s  ar e ei t h er  ex act   d u p lic a te s  o r  a p p r o x i m a te  s i m ila r ,  b u t d if f e r e n t i n  r e s o lu tio n ,  e n c o d in g  f o r m a ts ,  c o n te n t a d d itio n ,  le n g t h ,  e tc .   V i d eo s  u s ed  i n  t h e s t a n d ar d  d at as et s  ar e t o o  s m al l .  U n l i k e [ 2 1 ] ,  t he   da t as et   us e d   f or  ou r  a ppl i c a t i on   c o n ta in s   v i de os  of  a l l  t i m e  du r a t i o n s   f r om  1  m i nu t e  t m or e  t h a n  10 m i n u t e s .     W e  f ir s t a d o p t th e   m e th o d  o f  a v a la n c h e  a n d  it  is   co m p ar ed  a g ai n s t  t h e b i n ar y   h as h e s .  F i g u r 3   s ho w s   t he   r e s ul t s   o f   t hr e e   va r i o us   r e d uc t i o m e t ho d s   ( HE -   H a s h   b as ed   ex act  d u p l i cat r e m o v a l ,   HS -   H as h   b as ed   s i m ila r  d u p lic a te  r e m o v a l ,  SS -   S i m ila r it y - b as ed   s i m i l ar  d u p l i cat e r e m o v al )  o n  t w o  d i f f er en t  d at as et s ;  d at a s et 1   i s  a v i d eo  co l l ect i o n   w i t h  ex ac t  d u p l i cat es ;  d at a s et 2  co n t ai n s   ex act  an d   s i m i l ar  d u p l i cat e s .   R e d uc t i o n m e t ho d s   ar e H E -   H a s h ba s e ex act   d u p lic a te  r e m o v a l,  H S   -   H as h  b as ed   s im il a r   d u p l i cat e r e m o v al  a n d  S S   -   S i m ila r it y - b as ed   s i m ila r   du pl i c a t e  r e m ova l .   H E  i s  ad o p t ed  o n  d at as et 1  an d  i t  i s  o b s er v ed  t h at  d at a s i ze g o t  r ed u ced  t o   12% ,   28% ,   a n d 34%  r e s p e c t i v e l y   w i t h  c o m pr e s s i on ( C ) ,  de du pl i c a t i on  ( D D )  a nd c om pr e s s i on  pl u s   d e d u p lic a tio n  ( C D D ) .  H S  a n d  S S  te c h n iq u e s  a r e   i m p le m e n te d  o n  th e  c o m m o n  d a ta s e t2   w it h  e x a c t a n d   s i m ila r   d u p l i cat es .  W i t h  H S  t h e r ed u c t i o n  p er cen t a g of   C,   DD ,   a n d C D D  i s  obs e r v e d a s  5% 19% ,   a n d 22%  be c a us e   h as h  b as ed  al g o r i t h m  d o es n t  d et ect  s i m i l ar i t y  f eat u r es .  S i g n i f i can t  i m p r o v e m en t  i n  t h e r ed u ct i o n  p er cen t ag e   i s  s e e n   w i t h  S S  a ppr oa c h  a s   5% ,  46% ,   an d  5 0 %  f u l f i l l i n g   t h e ai m  o f  d at a r ed u ct i o n  an d   an   i n cr ea s e   i n t he   s t o r ag e s p ace.           F i g ur e   3 Co m p r e ss i o n  v s d ed u p l i cat i o n  p er f o r m an ce   HE HS S S D at a S i z e( G B ) 0 1 2 3 4 O r i gi n al C om pr es s i on D edu pl i c at i on C om pr es s i on  an d D edu pl i c at i on Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SSN :   20 88 - 8708     In t  J  E l e c  &  C o m p  E n g ,   V o l.   8 , N o 5 O c t obe r  20 18   :   322 1   -   3231   3228   F i g u r e 4  p l o t s  t h e g r ap h i cal   r ep r es en t at i o n  o f  t h s p r ead   o f  a ll d i f f e r e n v id e o  s i m ila r it y   s c o r e s   a m o n g  t h e d at as et .  W h i s k er s   s ho w   t h e r an g e o f   s i m i l ar i t y  s co r es  f o r  t h e en t i r e d at as et .   L o w es t   s co r e i n  t h i s   s a m p l e i s  0  an d   m a x i m u m  i t   g o es  t o  1 .  M ed i an  s i m i l ar i t y   s co r e i n  t h e d at as et  i s  ap p r o x i m at el y  at  0 . 7 .   T he   f ir s t p lo t s h o w s  t h e  r e p r e s e n ta tio n  o f  s i m ila r it y   s c o r e   o f  a ll th e  te s t d a ta T he  s e c o nd  p l o t   s ho w s  t he  r e s ul t  o f   t he  ne a r  d up l i c a t e  o ne s   w he n t he  t hr e s ho l d   ω   w as  k ep t  0 . 7 T he  r e c t a ngul a r  b o x r a nge s  f r o m  t he  0 . 7   t o 0 . w i t w h i s ke r s  e xt e nd i n up  t o  m a xi m u m   1 . 0 .   T h e  la s pl ot   is  th e  r e s u l t o f  n o  d u p lic a te  o n e w i t h   s c o r e s   b e lo w   0 . 7  an d  an  o u t l i er  at  s co r e 0 . 0 .               F ig u r e  4 .  D is tr ib u tio n  o f  s i m il a r it y  s c o r e s  ( B o x  p lo ts   d e p ic tin g   m e d ia n  a n d  q u a r tile   v a lu e s  o f  s i m ila r it y   s co r es  f o r  en t i r e d at as et ,  n ear   d u p l i cat es  an d   n o   d u p lic a te s )   F i gu r e  5.  C o m pa r i s on  of   s i m i l a r i t y  s c or e s   wi t h   d i f f er e n t  k e y   f r a m e s i zes   ( B ox a n w h i s k e r  pl ot s   d ep i ct i n g  t h e co m p ar i s o n  o f  s i m i l ar i t y  s co r es   f o r   d i f f er e n t  k e y   f r a m e s i zes )       F i g u r e 5  d es cr i b es  t h e co m p ar i s o n  o f  s i m i l ar i t y   s co r es   w i t h  d i f f er e n t   k e y   f r a m e s i z es .  A s  p er   a lg o r ith m  2   f r a m e  e x tr a c tio n  i ke p t   d yna m i c  a s  p e r  t he   vi d e o  l e n gt h.  F r o m  t he   f i g ur e ,   w e   c o nc l ud e  t ha t   w he n   ou r  pr o pos e d s y s t e m  s e t s  t h e  f ps  ( f r a m e s  pe r  s e c on d)  r a n g i ng   1 - 5,   we   g et   t h e m ax i m u m  s i m i l ar i t y  s co r f r o m   0. 45 t o 0. 95 w i t h   w h i s k e r s  e xt e n di ng  u p t o 1. 0 a l on g   w i t h  a n  ou t l i e r  t o w a r ds  0,  a n d m e di a n  0. 75 i s  c l os e r  t o   t h e   u ppe r  qu a r t i l e .  W h e r e a s   f or  f ps  10,  t h e  s i m i l a r i t y  s c or e  v a r i e d f r o m  0. 55 t o 0. 9 w i t h   w hi s k e r s  e x t e n di n g   u p t o l o w e r  qu a r t i l e  0. 0 a n d uppe r  qu a r t i l e  1. 0.  I n  t h e  l a s t  c a s e ,  f or  f ps  15  w e   g ot  t h e  r e c t a n gu l a r  box   w i t h  a   r a nge   of  0. 5 t o 0. 9.   T h e  r e s pe c t i v e   m e di a ns  i n di c a t e d f r o m   t he  g r a ph  a r e  0. 75,  0. 7,  a n d 0. 6 5 .             F i g u r e 6 .  P er f o r m a n ce o f  s i m i l ar  v i d eo  r em o v al  p r o ces s     ( A  p r e c is io n - r ecal l   c u r v e d ep i ct i n g  t h e acc u r ac y  o f   s i m i l ar  v i d eo  d et ect i o n   w i t h     =0 . 7 .  R ecei v er  o p er at i n g   ch ar act er i s t i c c u r v e ( R O C )  v i e w i n g  t h e p er f o r m an ce o f  t h n ear  d u p l i cat es  an d  n o  d u p l i cat es   cl as s i f i cat i o n )     T ot al . S c or es N ear . D upl i c at es N o. D upl i c at es 0. 0 0. 2 0. 4 0. 6 0. 8 1. 0 S im ila r it y  S c o r e s f ps 1_5 f ps 10 f ps 15 0. 0 0. 2 0. 4 0. 6 0. 8 1. 0 S im ila r it y  S c o r e s 0. 00 0. 25 0. 50 0. 75 1. 00 0. 00 0. 25 0. 50 0. 75 1. 00 1 -  S pec i f i c i t y S e n s it iv it y RO C 0. 00 0. 25 0. 50 0. 75 1. 00 0. 00 0. 25 0. 50 0. 75 1. 00 R ec al l P r ec i s i on P r ec i s i on- R ec al l Evaluation Warning : The document was created with Spire.PDF for Python.
IJ E C E     I S S N :  2088 - 8708       A   D e te r m in is tic  D e d u p lic a tio n  M o d e l fo r  R e m o v in g   R e dun da nc i e s   ( J y ot i  M al hot r a)   3229   F i g ur e   6  s h o w s  t h e acc u r acy  an d  p er f o r m an ce  o f  t h n ear  s i m i l ar  an d   n o  d u p l i cat e s   w i t h   t he   t hr e s ho l d     a s 0 . 7 P r e c is io n   is   th e  p o r tio n  o f  id e n t if ie d  s c o r e s  th a t a r e  s i m ila r ,   w h ile  r e c a ll  is   t he   s e g m e nt  o f   s i m i l ar  s co r es  t h at  ar i d en t i f i ed .  P r eci s i o n - r ecal l  c u r v es  ar e  u s ed  t o  i d e n t i f y  t h e co n f i d e n t  zo n e o f  t h e  o v er al l   p er f o r m a n ce,   w h er e a l ar g er  ar ea i n d i cat es  t h e b et t er  p er f o r m a n ce.   A cc u r ac y  o f  t h e e x p er i m e n t  r e s u l t s  i s   m e a s ur e d  b y  t he  r e gi o n b e l o w  t he  R O C  c ur ve .  T he  r e gi o n t o w a r d s  1 . 0 0   r ep r es en t s  a p er f ect  cl as s i f i cat i o n .   A s   s ho w n  i n t he   F i g ur e   6 ,  ar ea o f   R O C  cu r v e i s  ap p r o x i m at el y  0 . 8 - 0. 9 i . e .  t o w a r ds  1.  T a k i ng   f a l s e  pos i t i v e  a n d   f al s n eg a t i v e i n t o  acco u n t ,  t h w ei g h t ed   m ea n  i . e.  t h e F 1  s c o r e i s  ev al u at ed  an d  t h e v al u i s  0 . 8 9 .   F i g ur e   7  s ho w s  t hr e e  R O C  c u r ve s   f o r  t hr e s ho l d     v al u e s  0 . 7 ,  0 . 7 5 ,  0 . 8  r es p ect i v el y .  T h e ex cel l e n t   accu r ac y   r es u l t   i s  b ei n g   d ep i ct ed   b y   r ed   c u r v ( =0 . 7 )   b y   cal cu l at i n g   t h ar ea  o f   R O C   an d   i t   i s   o b s er v ed   t o w a r ds  1.  P R  c u r v e  i s  t h o ug h t   t o be   m or e  i nf or m a t i v e  i n   f i na l i z i n g t he  t hr e s ho l d  va l ue   w h i c gi ve s  t he   s i m i l ar i t i es  a s  p r ed i ct ed .   T h e l ar g er  cu r v e ar ea i s  b een  o b s er v ed  b y  r ed  cu r v w i t h   =0 . 7 .  H en ce,  t h s i m i l ar i t y   s co r e t h r es h o l d   f o r  d et ect i n g   m o r e s i m i l ar  v i d eo s  i s   m eas u r ed  as  0 . 7 .   V id e o s  w it h       > =   0 . 7   ar e co n s i d er ed  as  d u p l i cat es  an d  ar e d el et ed  f r o m  t h e co r p u s .           F i g u r e 7 .  P er f o r m a n ce u s i n g  d i f f er en t  s i m i l ar i t y   s co r e t h r es h o l d           F i g u r e 8 .  R at e o f  ch a n g e o f  s t o r ag e s p ace       A s  p e r  th e  d e te r m in is tic   m o d e l,  d is c u s s e d  in   S e c tio n   I I ,  t h r at e o f  ch a n g e o f   s t o r ag e s p ac e d ep en d s   o n  t h e r at of   d u p lic a te  v id e o  a r r iv a ls  a n d  r a te  o f  d u p lic a te  o r  s i m ila r  v id e o  r e m o v a ls .  R e m o v in g  d u p lic a te s  i s   i n v er s el y  p r o p o r t i o n al  t o  s t o r ag e s p ace.  F i g u r e 8  s h o w s  t h i s   r at e o f   c ha n ge   an d  d es cr i b es  t h at  a s  t h e  v id e o  f ile   r ed u n d an c y  co u n t  d ecr eas es  i . e.  as  d u p l i cat e o r  s i m i l ar  v i d eo  f i l es  ar e r e m o v ed ;  t h er e i s  an  i n cr eas e i n  t h e   s t o r ag e s p ace.     0. 00 0. 25 0. 50 0. 75 1. 00 0. 00 0. 25 0. 50 0. 75 1. 00 1 -  S pec i f i c i t y S e n s it iv it y RO C 0. 00 0. 25 0. 50 0. 75 1. 00 0. 00 0. 25 0. 50 0. 75 1. 00 R ec al l P r ec i s i on P r ec i s i on- R ec al l 0. 70 0. 75 0. 80 0 100 200 300 400 500 600 700 0 10 20 30 40 S t or age s pac e V i deo R edundan Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SSN :   20 88 - 8708     In t  J  E l e c  &  C o m p  E n g ,   V o l.   8 , N o 5 O c t obe r  20 18   :   322 1   -   3231   3230   4.   CO NCL U S I O N   T h i s  p ap er   p r es en t s   t h ef f i c i en t   d u p l i cat v i d eo  r e m o v al   p r o ces s  b as ed  o n   t h v i d eo  s i m i l ar i t i e s .   T he   r e p o r te d  w o r k  s h o w s  t h a t  d e d u p lic a tio n   w ith   s i m ila r it y   s c o r e s  p e r f o r m   w e ll a s  c o m p a r e  to  d e d u p lic a tio n   w i t h  h a s h  s i g n at u r es  o n  t h e d a t as et   w h er e t h er e ar e   m o r s i m i l ar  co n t en t s .   O r i g i n al  d at a s i ze h a s   s i g n i f i ca n t l y   r e du c e w i t h  50%  de du pl i c a t i on  r a t i o.  T h e   accu r acy  o f   s i m i l ar  v i d eo  d et ect i o n  i s  o b s er v ed  w i t h  t h e p r eci s i o n - r ecal l  cu r v w i t h  l ar g er  c u r v e  ar ea an d  R O C  cu r v e ar ea t o w ar d s  1 .  T h e accu r ac y  o f   v i d eo  cl as s i f i cat i o n  as   s i m i l ar  d u p l i cat es  a n d  n o  d u p l i cat es  i s   m eas u r ed   w i t h  t h e F 1  s co r e ( m ea n  o f  p r eci s i on  a n d r e c a l l )  of  89% .       ACK NO W L E D G E M E NT S   W e  w is h  to   ex p r es s  o u r  s i n ce r t ha nks   to   e ve r y  a no nym o us  p e r s o n f or  t he i r   p r e c i o us  r e vi e w ,   s ugge s t i o ns ,   a nd   r em ar k s   t o  m a ke  t hi s  w o r k t he   pr og r e s s .       R EF ER EN C ES     [ 1]   h ttp s :/ /w w w . e m c . c o m / c o lla te r a l/a n a ly s t - r e p o r ts /id c - th e - d ig ita l - u n i ve r s e - in - 202 0. pdf   [ 2]   A   A g r a w al ,  J  M al h o t r a,  “C l u s t er ed  O u t b an d  D ed u p l i cat i o n  o n  P r i m ar y  D at a ”.   I n C om pu t i n g  C om m uni c a t i o C ont r o l  a nd  A ut om at i o n ( I C C U B E A ) ,   2 01 5 I nt e r na t i ona l  C onf e r e nc e  on 2 01 5 F e b 2 6 ( pp.  4 46 - 4 5 0 ) . I E E E .   [ 3]   J i n S a n K o ng ,   et . a l ., “ T w o - L e v el   M et ad at a M an ag e m en t   f o r  D at D ed u p l i cat i o n  S y s t e m ”.  I S T  2 0 1 3 ,  A S T L  V o l .  2 3 ,   pp. 29 9 - 3 03.   [ 4]   D Ki m ,   e t. a l. ,  “ S A F E: S tr u c tu r e - a w ar f i l an d  em ai l  d ed u p l i cat i o n  f o r  cl o u d - b as ed  s t o r ag e s y s t e m s ”.  I n  D at a   D e dupl i c a t i on f or  D a t a  O pt i m i z a t i on f or  S t or a g e  a nd N e t w or k  S ys t e m s  2017 ( p p.  9 7 - 1 15) .   Spr i ng e r  I nt e r nat i o na l   P ubl i s hi n g.   [ 5]   V .   A .   N ar ay an a,  P .  P r em ch an d ,  an d   A .  G o v ar d h an .  " P er f o r m an c e an d  co m p ar at i v e an al y s i s  o f  t h e t w o  co n t r ar y   a ppr oa c he s  f or  de t e c t i ng  ne a r  dupl i c a t e  w e b doc um e nt s  i n w e b c r a w l i ng . "   I nt e r nat i o nal  J o ur n al  of  E l e c t r i c al  an d   C om put e r   E ng i ne e r i ng  ( IJ E CE ),   2. 6,  2 01 2,   pp.  8 19 - 83 0.   [ 6]   F  Y in jin ,   e t . a l. ,   A p p lic a tio n - A w ar e S o u r ce D ed u p l i cat i o n  f o r  C l o u d  B ack u p  S er v i ces  o f  P er s o n al  S t o r ag e”.   I E E E   T r ans ac t i ons   on  P ar al l e l   an d D i s t r i but e d  Sy s t e m s .  20 13 .   [ 7]   D e C ar v al h o ,  M o i s es  G . ,   et  a l . ,  " A  g e ne t i c  pr og r a m m i ng   a ppr oa c h t o r e c or d de d upl i c a t i on, "   I E E E  T r ans ac t i on s  on  K now l e d ge  a nd D at a  E n gi ne e r i ng,   2 4( 3) :  3 99 - 41 2,  M a r   2 01 2.   [ 8]   A  C u lo tta  a n d  A  M c C a llu m .  " J o i n t d e d u p lic a tio n  o f  m u ltip le  r e c o r d  ty p e s  in  r e la tio n a d a ta . "   I P r oc e e di ng s  of  t he   14t A C M  i n t e r nat i on al  c onf e r e n c e  on I n f or m at i o n a nd  k now l e dge  m an age m e nt   20 05   O c t  3 ( pp .  2 57 - 2 5 8 ).  A CM .   [ 9]   L e   G a l l ,  D i di e r .  " M P E G :  A   v i de o c om pr e s s i on s t a nda r d f or   m ul t i m e di a  a ppl i c a t i o ns . "  C om m uni c a t i ons  of  t he  A C M   34. ( 19 91) :  46 - 5 8.   [ 1 0]   N .  M an d ag er e,   et . a l . ,   “D em y s t i f y i n g  d at a d ed u p l i cat i o n ”.  I n   P r o ceed i n g s  o f  t h A CM / IF IP / U S E NI X   M i ddl e w ar e ' 08   C onf e r e nc e  C om p ani on   2 00 8 D e c  1 ( pp.  1 2 - 1 7 ).  A CM .   [ 1 1]   L i Y ,  X ia  K .  “ F a s t V id e o  D e d u p l ic a tio n  v ia  L o c a lit y  S e n s itiv e   H a s h in g  w ith  S im ila r it y  R a n k in g .   I n P r oc e e di ngs  of   t he  I nt e r n at i on al  C onf e r e nc e  o n I nt e r ne t  M ul t i m e di a C om p ut i n an d Se r v i c e  20 16   A ug  19 ( p p.   94 - 9 8 ).  A CM .   [ 1 2]   Sa t o h  SI ,   e t. a l. ,   “S cen e d u p l i cat e d et ect i o n  f r o m  v i d eo s  b as ed  o n   t r aj ect o r i es  o f   f eat u r e p o i n t s ”.  I n  P r o ceed i n g s  o f   th e   I nt e r n at i on al  w or k s hop  o n W or k s hop  o n m ul t i m e di a  i nf or m at i on r e t r i e v al   20 07   S e 24 ( pp .  2 37 - 2 4 4 ).  A CM .   [ 1 3]   F  R as h id ,   e t .a l .,   P r o of  of  s t or a g e   f or  v i de o de d upl i c a t i on i n t h e  c l oud” .   I n B i g D at a ( B i gD at C ongr e s s ) ,  2 01 I E E E  I n t e r nat i on al  C on gr e s s  on  201 5   J un 27   ( p p.  49 9 - 5 0 5 ) .  I E E E . "   [ 1 4]   R as h i d et . a l . ,   " A  S e c ur e   V i de o D e du pl i c a t i o n S c he m e  i n C l o ud  S t or a g e  E nv i r o nm e nt s  U s i ng  H .  26 4   C om pr e s s i on"   I n B i g D at a C om put i ng  Se r v i c e  and  A p pl i c at i o ns   ( B i gD at aSe r v i c e ) ,   2 01 5 I E E E   F i r s t  I nt e r na t i ona l   C onf e r e nc e  on 2 01 5 M a r   30  ( p p.   138 - 1 4 6 ).  IE E E .   [ 1 5]   J  S ong ,   e t. a l. , .  “ M ul t i p l e f eat u r h as h i n g  f o r  r eal - t i m e l ar g e s cal e n ear - d u p l i cat e v i d eo  r et r i ev al ”.  I n   P r o ceed i n g s  o f   t h 1 9t h  A C M  i nt e r n at i on al  c o nf e r e nc e  on M ul t i m e d i 20 11   N o v 28  ( pp .   4 23 - 4 32) .  A C M .   [ 1 6]   R ouhi  a nd J a m e s   A .  T hom .  " A  c om pr e s s e d - dom a i n r obus t  de s c r i pt or  f or  ne a r   du pl i c a t e  v i de o c op y  de t e c t i on. "   I P r oc e e di ngs  of  t he  29t h I nt e r n at i ona l  C onf e r e nc e  on I m a ge  an d V i s i on C om put i ng N e w  Z e al an d,   2 014 N ov  1 9 ( pp .   130 - 1 3 5 ).  A CM  .   [ 1 7]   G .  S u ch ar i t h a,  an d  R an j an  K .  S en ap at i .  “S h ap e B as ed  I m a g e R et r i ev al  u s i n g   L o w er  O r d er  Z er n i k e   M o m en t s ”,   I nt e r nat i o nal  J our n al   of  E l e c t r i c al  an d C om pu t e r  E n gi ne e r i n g ( I J E C E ) ,   7( 3) ,  20 17,   p p.  11 44 - 11 53.   [ 1 8]   P .  A m u d h a v a lli,  ,  N .  R a ja la k s h m i,  a n d  K .  S .  S in d h u .  " D e d u p lic a tio n  A n a ly s is  o f  P r o d u c ts  I n  D i g ita l M a r k e tin g . "   I nd one s i a n J o ur na l  o f  E l e c t r i c al   E ngi ne e r i ng  an d C om p ut e r  Sc i e n c e ( I J E E C S) ,   1 0( 1) ,  2 01 8,   pp.  3 92 - 39 9.   [ 1 9]   R F C  3 17 -   U S   S e c ur e  H a s h A l gor i t hm  1 ,  S e pt e m be r   200 1.   h tt p s :/ /to o ls . ie tf . o r g /h tm l/r f c 3 1 7 4   [ 2 0]   ht t p: / / w w w . pha s h. or g /   [ 2 1]   ht t p: / / v i r e o. c s . c i t y u. e du. hk / w e bv i de o/   [ 2 2]   V  T ar as o v ,   e t. a l. , “ G en er at i n g  R e a lis tic   D a ta s e ts  f o r  D e d u p lic a tio n   A n a l y s is .   I U SE N I X  A nnu al  T e c hn i c al   C o n f er en ce 2 0 1 2   J u n 1 3 ( pp.  2 61 - 27 2) .   [ 2 3]   h ttp : //g e o v id . o r g / d a ta s e t/v id e o s /       Evaluation Warning : The document was created with Spire.PDF for Python.