I n t e r n a t i o n a l   J o u r n a l   o f   E l e c t r i c a l   a n d   C o m p u t e r   E n g i n e e r i n g   ( I J E C E )   V o l . 1 ,   N o . 2 ,   D e c e m b e r   2 0 1 1 ,   p p .   1 8 7 ~ 1 9 4   I S S N :   2 0 8 8 - 8 7 0 8             1 8 7       R e c e i v e d   S e p   1 0 th ,   2 0 1 1 ;   R e v i s e d   N o v   1 3 th ,   2 0 1 1 ;   A c c e p t e d   N o v   1 8 th ,   2 0 1 1   A n   E f f i c i e n t   A p p r o a c h   f o r   F i n d i n g   N e a r   D u p l i c a t e   W e b   p a g e s   u s i n g   M i n i m u m   W e i g h t   O v e r l a p p i n g   M e t h o d       S h i n e   N .   D a s 1 ,   M i d h u n   M a t h e w 2 ,   P r a m o d   K . V i j a y a r a g h a v a n 3   1 D e p t .   o f   C o m p u t e r   A p p l i c a t i o n s ,   C U S A T ,   I N D I A   2 D e p t .   o f   C o m p . S c i e n c e   &   E n g g . ,   M B I T S ,   Ko t h a m a n g a l a m ,   I N D I A   3 D e p t .   o f   C o m p u t e r   A p p l i c a t i o n s ,   C U S A T ,   I N D I A       A b s t r a c t   T h e   e x i s t e n c e   o f   b i l l i o n s   o f   we b   d a t a   h a s   s e v e r e l y   a f f e c t e d   t h e   p e r f o r m a n c e   a n d   r e l i a b i l i t y   o f   we b   s e a r c h .   T h e   p r e s e n c e   o f   n e a r   d u p l i c a t e   we b   p a g e s   p l a y s   a n   i m p o r t a n t   r o l e   i n   t h i s   p e r f o r m a n c e   d e g r a d a t i o n   w h i l e   i n t e g r a t i n g   d a t a   f r o m   h e t e r o g e n e o u s   s o u r c e s .   W e b   m i n i n g   f a c e s   h u g e   p r o b l e m s   d u e   t o   t h e   e x i s t e n c e   o f   s u c h   d o c u m e n t s .   T h e s e   p a g e s   i n c r e a s e   t h e   i n d e x   s t o r a g e   s p a c e   a n d   t h e r e b y   i n c r e a s e   t h e   s e r v i n g   c o s t .   B y   i n t r o d u c i n g   e f f i c i e n t   m e t h o d s   t o   d e t e c t   a n d   r e m o v e   s u c h   d o c u m e n t s   f r o m   t h e   W e b   n o t   o n l y   d e c r e a s e s   t h e   c o m p u t a t i o n   t i m e   b u t   a l s o   i n c r e a s e s   t h e   r e l e v a n c y   o f   s e a r c h   r e s u l t s .   W e   a i m   a   n o v e l   i d e a   f o r   f i n d i n g   n e a r   d u p l i c a t e   we b   p a g e s   wh i c h   c a n   b e   i n c o r p o r a t e d   i n   t h e   f i e l d   o f   p l a g i a r i s m   d e t e c t i o n ,   s p a m   d e t e c t i o n   a n d   f o c u s e d   we b   c r a w l i n g   s c e n a r i o s .   H e r e   we   p r o p o s e   a n   e f f i c i e n t   m e t h o d   f o r   f i n d i n g   n e a r   d u p l i c a t e s   o f   a n   i n p u t   we b   p a g e ,   f r o m   a   h u g e   r e p o s i t o r y .   A   T D W   m a t r i x   b a s e d   a l g o r i t h m   i s   p r o p o s e d   wi t h   t h r e e   p h a s e s ,   r e n d e r i n g ,   f i l t e r i n g   a n d   v e r i f i c a t i o n ,   wh i c h   r e c e i v e s   a n   i n p u t   we b   p a g e   a n d   a   t h r e s h o l d   i n   i t s   f i r s t   p h a s e ,   p r e f i x   f i l t e r i n g   a n d   p o s i t i o n a l   f i l t e r i n g   t o   r e d u c e   t h e   s i z e   o f   r e c o r d   s e t   i n   t h e   s e c o n d   p h a s e   a n d   r e t u r n s   a n   o p t i m a l   s e t   o f   n e a r   d u p l i c a t e   we b   p a g e s   i n   t h e   v e r i f i c a t i o n   p h a s e   b y   u s i n g   M i n i m u m   W e i g h t   O v e r l a p p i n g   ( M W O )   m e t h o d .   T h e   e x p e r i m e n t a l   r e s u l t s   s h o t h a t   o u r   a l g o r i t h m   o u t p e r f o r m s   i n   t e r m s   o f   t wo   b e n c h m a r k   m e a s u r e s ,   p r e c i s i o n   a n d   r e c a l l ,   a n d   a   r e d u c t i o n   i n   t h e   s i z e   o f   c o m p e t i n g   r e c o r d   s e t .       Ke y wo r d s :   n e a r   d u p l i c a t e   d e t e c t i o n ,   t e r m   d o c u m e n t   we i g h t   m a t r i x ,   p r e f i x   f i l t e r i n g ,   p o s i t i o n a l   f i l t e r i n g ,   m i n i m u m   we i g h t   o v e r l a p p i n g ,   we b   p a g e   c l a s s i f i c a t i o n       1 .   I n t r o d u c t i o n   H o l o c e n e   e p o c h   h a s   d e t e c t e d   t h e   e n o r m o u s   e m e r g e n c e   o f   I n t e r n e t   d o c u m e n t   i n   t h e   W o r l d   W i d e   W e b .   I n t e r n e t   i s   n o w   a   v i t a l   f a c t o r   f o r   d a y   t o d a y   l i f e   i n   g a t h e r i n g   i n f o r m a t i o n   a n d   e x t r a c t i n g   u s e f u l   i n f o r m a t i o n   f r o m   w e b   p a g e s   t h u s   b e c o m e s   a n   i m p o r t a n t   t a s k .   T h e   p e r f o r m a n c e   a n d   r e l i a b i l i t y   o f   w e b   s e a r c h   e n g i n e s   f a c e   h u g e   p r o b l e m s   d u e   t o   t h e   p r e s e n c e   o f   e x t r a o r d i n a r i l y   l a r g e   a m o u n t   o f   w e b   d a t a .   T h e   v o l u m i n o u s   a m o u n t   o f   w e b   d o c u m e n t s   h a s   r e s u l t e d   i n   p r o b l e m s   f o r   s e a r c h   e n g i n e s   l e a d i n g   t o   t h e   f a c t   t h a t   t h e   s e a r c h   r e s u l t s   a r e   o f   l e s s   r e l e v a n c e   t o   t h e   u s e r .   I n   a d d i t i o n   t o   t h i s ,   t h e   p r e s e n c e   o f   d u p l i c a t e   a n d   n e a r   d u p l i c a t e   w e b   d o c u m e n t s   h a s   c r e a t e d   a n   a d d i t i o n a l   o v e r h e a d   f o r   t h e   s e a r c h   e n g i n e s   c r i t i c a l l y   a f f e c t i n g   t h e i r   p e r f o r m a n c e   [ 1 ] .   T h e   d e m a n d   f o r   i n t e g r a t i n g   d a t a   f r o m   h e t e r o g e n e o u s   s o u r c e s   l e a d s   t o   t h e   p r o b l e m   o f   n e a r   d u p l i c a t e   w e b   p a g e s .   N e a r   d u p l i c a t e   d a t a   b e a r   h i g h   s i m i l a r i t y   t o   e a c h   o t h e r ,   y e t   t h e y   a r e   n o t   b i t w i s e   i d e n t i c a l   [ 2 ] [ 3 ] .   N e a r   d u p l i c a t e s   a r e   d o c u m e n t s   ( w e b   p a g e s )   t h a t   d i f f e r   o n l y   s l i g h t l y   i n   c o n t e n t .   T h e   d i f f e r e n c e   b e t w e e n   t h e s e   d o c u m e n t s   c a n   b e   d u e   t o   e l e m e n t s   o f   t h e   d o c u m e n t   t h a t   a r e   i n c l u d e d   b u t   n o t   i n h e r e n t   t o   t h e   m a i n   c o n t e n t   o f   t h e   p a g e .   F o r   e x a m p l e ,   a d v e r t i s e m e n t s   o n   w e b   p a g e s ,   o r   t i m e s t a m p s   o f   w h e n   a   p a g e   w a s   u p d a t e d ,   a r e   b o t h   i n f o r m a t i o n   t h a t   i s   n o t   i m p o r t a n t   t o   a   u s e r   w h e n   s e a r c h i n g   f o r   t h e   p a g e ,   a n d   t h u s   n o t   i n f o r m a t i v e   f o r   t h e   s e a r c h   e n g i n e   w h e n   c r a w l i n g   a n d   i n d e x i n g   t h e   p a g e .     T h e   e x i s t e n c e s   o f   n e a r   d u p l i c a t e   w e b   p a g e   a r e   d u e   t o   e x a c t   r e p l i c a   o f   t h e   o r i g i n a l   s i t e ,   m i r r o r e d   s i t e ,   v e r s i o n e d   s i t e ,   a n d   m u l t i p l e   r e p r e s e n t a t i o n s   o f   t h e   s a m e   p h y s i c a l   o b j e c t   a n d   p l a g i a r i z e d   d o c u m e n t s .   I n   m a n y   s i t u a t i o n s ,   t w o   d o c u m e n t s   t h a t   a r e   n o t   e x a c t l y   i n d i s t i n g u i s h a b l e   m a y   s t i l l   c o n t a i n   t h e   s a m e   c o n t e n t   a n d   s h o u l d   b e   t r e a t e d   a s   n e a r   d u p l i c a t e s .   F o r   e x a m p l e ,   w e b   p a g e s   f r o m   d i f f e r e n t   m i r r o r e d   s i t e s   m a y   o n l y   d i f f e r   i n   t h e   h e a d e r   o r   f o o t n o t e   z o n e s   t h a t   d e n o t e   t h e   s i t e   U R L   a n d   u p d a t e   t i m e .   T w o   s u c h   d o c u m e n t s   a r e   i d e n t i c a l   i n   t e r m s   o f   c o n t e n t   b u t   d i f f e r   i n   a   s m a l l   p o r t i o n   o f   t h e   d o c u m e n t   s u c h   a s   a d v e r t i s e m e n t s ,   c o u n t e r s   a n d   t i m e s t a m p s .   T h e s e   d i f f e r e n c e s   a r e   i r r e l e v a n t   f o r   w e b   s e a r c h   [ 4 ] .   N e a r   d u p l i c a t e   d e t e c t i o n   h a s   b e e n   r e c o g n i z e d   a s   a n   i m p o r t a n t   r e s e a r c h   p r o b l e m   i n   r e c e n t   y e a r s .   S e v e r a l   a p p l i c a t i o n s   a r e   b e n e f i t e d   b y   t h e   i d e n t i f i c a t i o n   o f   t h e   n e a r   d u p l i c a t e s   i n   t h e   f i e l d   o f   p l a g i a r i s m   d e t e c t i o n ,   s p a m   d e t e c t i o n   a n d   i n   f o c u s e d   w e b   c r a w l i n g   s c e n a r i o s .     I n   p l a g i a r i s m   d e t e c t i o n ,   a   p o r t i o n   o f   o n e   d o c u m e n t ,   s u c h   a s   a   s e n t e n c e   o r   a   p a r a g r a p h ,   i s   c o n t a i n e d   i n   a n o t h e r   d o c u m e n t ,   a n d   t h e n   t h e s e   t w o   d o c u m e n t s   c o u l d   b e   s e e n   a s   n e a r   d u p l i c a t e s .   S p a m   m e s s a g e s   t h a t   b e l o n g   t o   t h e   s a m e   c a m p a i g n   m a y   l o o k   v e r y   d i f f e r e n t   b e c a u s e   s p a m m e r s   o f t e n   n e e d   t o   r a n d o m i z e   t h e   m e s s a g e s   b y   m o d i f y i n g   i t   w i t h   o b s c u r e   t e r m s   o r   a d d i n g   u n r e l a t e d   p a r a g r a p h s   t o   p a s s   t h e   f i l t e r s   [ 5 ] [ 3 ] .   H o w e v e r ,   t h e s e   s p a m s   c o u l d   b e   e a s i l y   d i s c o v e r e d   b y   n e a r   d u p l i c a t e   d e t e c t i o n   m e t h o d s .   T h e   d e t e r m i n a t i o n   o f   n e a r   d u p l i c a t e   w e b   p a g e s   a i d s   i n   f o c u s e d   c r a w l i n g ,   a n d   e n s u r e s   e n h a n c e d   q u a l i t y   a n d   d i v e r s i t y   o f   q u e r y   r e s u l t s .   I n   t h i s   p a p e r ,   w e   p r o p o s e   a   n o v e l   i d e a   f o r   f i n d i n g   n e a r   d u p l i c a t e s   o f   a n   i n p u t   w e b   p a g e ,   f r o m   a   h u g e   r e p o s i t o r y .   T h i s   a p p r o a c h   e x p l o r e s   t h e   s e m a n t i c   s t r u c t u r e ,   c o n t e n t   a n d   c o n t e x t ,   o f   a   w e b   p a g e   r a t h e r   t h a n   t h e   c o n t e n t   o n l y   a p p r o a c h .   T h e   w e i g h t i n g   s c h e m e   s u g g e s t e d   i n   [ 6 ]   i s   c o n s i d e r e d   f o r   c r e a t i n g   a   t e r m   d o c u m e n t   w e i g h t   m a t r i x   ( T D W )   w h i c h   p l a y s   a n   i m p o r t a n t   r o l e   i n   t h e   p r o p o s e d   a l g o r i t h m .   W e   p r e s e n t   a   t h r e e - s t a g e   a l g o r i t h m   w h i c h   r e c e i v e s   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 8 - 8 7 0 8   I J E C E     V o l .   1 ,   N o . 2 ,   D e c e m b e r   2 0 1 1   :     1 8 7     1 9 4   1 8 8 a n   i n p u t   r e c o r d   a n d   a   t h r e s h o l d   v a l u e   a n d   r e t u r n s   a n   o p t i m a l   s e t   o f   n e a r   d u p l i c a t e s .   I n   f i r s t   p h a s e ,   r e n d e r i n g   p h a s e ,   a l l   p r e - p r o c e s s i n g   a r e   d o n e   a n d   a   w e i g h t i n g   s c h e m e   i s   a p p l i e d .   T h e n   a   g l o b a l   o r d e r i n g   i s   p e r f o r m e d   a l o n g   w i t h   s o m e   s t a n d a r d   n o r m a l i z a t i o n   t e c h n i q u e s   t o   f o r m   a   t e r m   d o c u m e n t   w e i g h t   m a t r i x .   I n   s e c o n d   p h a s e ,   f i l t e r i n g   p h a s e ,   t w o   w e l l - k n o w n   f i l t e r i n g   m e c h a n i s m s ,   p r e f i x   f i l t e r i n g   a n d   p o s i t i o n a l   f i l t e r i n g   [ 2 ] ,   a r e   a p p l i e d   t o   r e d u c e   t h e   s i z e   o f   c o m p e t i n g   r e c o r d   s e t   a n d   h e n c e   t o   r e d u c e   t h e   n u m b e r   o f   c o m p a r i s o n s .   I n   t h i r d   p h a s e ,   v e r i f i c a t i o n   p h a s e ,   a   s i m i l a r i t y   c h e c k i n g   i s   d o n e   b y   i n t r o d u c i n g   a   n e w   t e c h n i q u e   k n o w n   a s   M i n i m u m   W e i g h t   O v e r l a p p i n g   ( M W O )   b a s e d   o n   t h e   t h r e s h o l d   v a l u e   a n d   f i n a l l y   w e   g e t   a n   o p t i m a l   n u m b e r   o f   n e a r   d u p l i c a t e   r e c o r d s .   T h e   r e s t   o f   t h i s   p a p e r   i s   o r g a n i z e d   a s   f o l l o w s .   S e c t i o n   2   d e s c r i b e s   r e l a t e d   w o r k s .   S e c t i o n   3   g i v e s   t h e   d e t a i l s   o f   p r o p o s e d   w o r k .   S e c t i o n   4   a n a l y s e s   t h e   e x p e r i m e n t a l   r e s u l t s   i n   t e r m s   o f   p r e c i s i o n   a n d   r e c a l l .   I n   t h e   l a s t   s e c t i o n ,   w e   g i v e   t h e   c o n c l u s i o n   a n d   f u t u r e   w o r k s .       2 .   R e l a t e d   w o r k s   V e r y   f e w   r e s e a r c h   p a p e r s   h a v e   s u g g e s t e d   m e t h o d o l o g i e s   f o r   n e a r   d u p l i c a t e   d e t e c t i o n   b o t h   i n   g e n e r a l   d o c u m e n t s   a n d   t h e   w e b   d o c u m e n t s   o b t a i n e d   b y   w e b   c r a w l i n g .   T e c h n i q u e   f o r   t h e   e s t i m a t i o n   o f   t h e   d e g r e e   o f   s i m i l a r i t y   a m o n g   p a i r s   o f   d o c u m e n t s   i s   k n o w n   a s   s h i n g l i n g .     B r o d e r   e t   a l .   [ 7 ]   h a v e   s u g g e s t e d   a   t e c h n i q u e   o n   t h i s ,   i n   w h i c h   a l l   s e q u e n c e s   o f   a d j a c e n t   w o r d s   a r e   e x t r a c t e d .     I f   t w o   d o c u m e n t s   c o n t a i n   t h e   s a m e   s h i n g l e s   s e t   t h e y   a r e   t r e a t e d   a s   e q u i v a l e n t   a n d   i f   t h e   s h i n g l e s   s e t   o v e r l a p s ,   t h e y   a r e   c o n s i d e r e d   a s   e x a c t   s i m i l a r .   I n   t h i s   m e t h o d   t h e   a u t h o r s   n o t e d   t h a t   i t   d o e s   n o t   w o r k   w e l l   o n   s m a l l   d o c u m e n t s .   F e t t e r l y   e t   a l .   [ 8 ]   u s e   f i v e - g r a m   a s   a   s h i n g l e   a n d   s a m p l e   8 4   s h i n g l e s   f o r   e a c h   d o c u m e n t .   T h e n   t h e   8 4   s h i n g l e s   a r e   b u i l t   i n t o   s i x   s u p e r   s h i n g l e s .   T h e   d o c u m e n t s   h a v i n g   t w o   s u p e r   s h i n g l e s   i n   c o m m o n   a r e   c o n s i d e r e d   a s   n e a r l y   d u p l i c a t e   d o c u m e n t s .   A n d r e i   Z .   B r o d e r   e t   a l .   [ 7 ]   h a v e   d e v e l o p e d   a n   e f f i c i e n t   w a y   t o   d e t e r m i n e   t h e   s y n t a c t i c   s i m i l a r i t y   o f   f i l e s   a n d   h a v e   a p p l i e d   i t   t o   e v e r y   d o c u m e n t   o n   W o r l d   W i d e   W e b .   U s i n g   t h e i r   m e c h a n i s m ,   t h e y   h a v e   b u i l t   a   c l u s t e r i n g   o f   a l l   t h e   d o c u m e n t s   t h a t   a r e   s y n t a c t i c a l l y   s i m i l a r .     A n o t h e r   m e t h o d   t o   d e t e c t   a n d   d e l e t e   n e a r   d u p l i c a t e d   w e b   p a g e s ;   p r i o r i t y - b a s e d   o n   t e x t   i n f o r m a t i o n ,   i s   p r o p o s e d   i n   [ 9 ] .   B y   t h i s   m e t h o d ,   a n   a l g o r i t h m   t o   e x t r a c t   t e x t   i n f o r m a t i o n   o f   w e b   p a g e s   b y   D O M   t r e e   a n d   a   p r i o r i t y - b a s e d   a l g o r i t h m   f o r   d e t e c t i n g   n e a r   d u p l i c a t e d   t e x t   i n f o r m a t i o n   a r e   i m p l e m e n t e d ,   s o   a s   t o   r e d u c e   t h e   n o i s e   o f   w e b   p a g e s   a n d   h e n c e   t o   i m p r o v e   t h e   e f f i c i e n c y   o f   d e t e c t i n g   n e a r   d u p l i c a t e d   t e x t   i n f o r m a t i o n .     N a r a y a n a   e t   a l .   [ 1 0 ]   p r e s e n t e d   a n   a p p r o a c h   f o r   t h e   d e t e c t i o n   o f   n e a r   d u p l i c a t e   w e b   p a g e s   i n   w e b   c r a w l i n g .     N e a r   d u p l i c a t e   w e b   p a g e s   a r e   d e t e c t e d   f o l l o w e d   b y   t h e   s t o r a g e   o f   c r a w l e d   w e b   p a g e s   i n   t o   r e p o s i t o r i e s .   T h e   k e y w o r d s   a r e   e x t r a c t e d   f r o m   c r a w l e d   p a g e s   a n d   o n   t h e   b a s i s   o f   t h e s e   k e y w o r d s ;   t h e   s i m i l a r i t y   s c o r e   b e t w e e n   t w o   p a g e s   i s   c a l c u l a t e d .   T h e   d o c u m e n t s   a r e   c o n s i d e r e d   a s   n e a r   d u p l i c a t e s   i f   i t s   s i m i l a r i t y   s c o r e   s a t i s f i e s   a   t h r e s h o l d   v a l u e .   B u t   t h e y   h a v e n t   e x p l o i t e d   t h e   s t r u c t u r a l   i n f o r m a t i o n   o f   w e b   p a g e   w h i c h   i s   m o r e   i m p o r t a n t   f o r   g e t t i n g   t h e   s e m a n t i c   i n f o r m a t i o n   a b o u t   t h e   p a g e .   T h i s   w o r k   i s   a n   e x t e n s i o n   o f   w o r k   [ 1 1 ]   w h i c h   o f f e r e d   a   n o v e l   i d e a   f o r   t h e   d e t e c t i o n   o f   n e a r   d u p l i c a t e   w e b   p a g e s .   I t   a l s o   u s e s   a   t h r e e   s t a g e   a l g o r i t h m   i n   w h i c h   t h e   s i m i l a r i t y   v e r i f i c a t i o n   i s   b a s e d   o n   S i n g u l a r   V a l u e   D e c o m p o s i t i o n   ( S V D )   [ 1 2 ]   u s i n g   a n g l e   t h r e s h o l d   θ .   B u t   S V D   r e q u i r e s   m o r e   c o m p l i c a t e d   M a t h e m a t i c a l   o p e r a t i o n s   o n   T D W   m a t r i x   a l o n g   w i t h   t h e   c o n v e r s i o n   o f   J a c c a r d   t h r e s h o l d   t   i n t o   a n g l e   t h r e s h o l d   θ .   I t   i n c r e a s e s   t h e   a l g o r i t h m   c o m p l e x i t y   a s   w e l l   a s   t h e   p r a c t i c a l   d i f f i c u l t i e s   i n   m e a s u r i n g   t h e   a n g l e .   H e r e   w e   i n t r o d u c e   a   n e w   t e c h n i q u e   c a l l e d   M W O   f o r   s i m i l a r i t y   v e r i f i c a t i o n   w h i c h   d i r e c t l y   w o r k s   o n   J a c c a r d   t h r e s h o l d   t   a n d   i t   r e d u c e s   t h e   c o m p l e x i t y   o f   t h e   a l g o r i t h m .             3 .   P r o p o s e d   W o r k   H e r e   w e   p r o p o s e   a n   i n n o v a t i v e   i d e a   f o r   f i n d i n g   n e a r   d u p l i c a t e   w e b   p a g e s   o f   a n   i n p u t   r e c o r d   r .   S i m i l a r i t y   v e r i f i c a t i o n   i s   d o n e   o n   a   h u g e   r e c o r d   s e t   h a v i n g   n   n u m b e r   o f   r e c o r d s   { r 1 , r 2 , . , r n }   a n d   a n   o p t i m a l   s e t   o f   n e a r   d u p l i c a t e   r e c o r d s   a r e   r e t u r n e d .   T h e   s i m i l a r i t y   v e r i f i c a t i o n   i s   b a s e d   o n   a   J a c c a r d   t h r e s h o l d   v a l u e   t ,   0     t   1 ,   s u c h   t h a t   o u r   a l g o r i t h m   r e t u r n s   a   s e t   o f   r e c o r d s   h a v i n g   a   m i n i m u m   s i m i l a r i t y   t .   t = 0   r e t u r n s   f u l l   r e c o r d   s e t   w h i c h   s h a r e s   a t   l e a s t   a   s i n g l e   w o r d   w i t h   i n p u t   r e c o r d   r ,   w h i l e   t = 1   r e t u r n   o n l y   e x a c t l y   s i m i l a r   r e c o r d s   o f   r .   O u r   o b j e c t i v e   i s   t o   f i n d   h o w   t o   s e l e c t   s i m i l a r   r e c o r d s   f r o m   t h e   e n t i r e   r e c o r d   s e t   w i t h   a   r e d u c e d   n u m b e r   o f   c o m p a r i s o n s .   A   t h r e e - s t a g e   s e l e c t i o n   a l g o r i t h m   i s   p r o p o s e d   b y   c o m b i n i n g   a   d i f f e r e n t   t e r m   w e i g h t i n g   a p p r o a c h   [ 6 ] ,   t e r m   f i l t e r i n g   a p p r o a c h   a n d   a   n e w   s i m i l a r i t y   v e r i f i c a t i o n   t e c h n i q u e ,   M W O ,   f o r   t h i s   p u r p o s e .   I n   t h e   f i r s t   p h a s e ,   r e n d e r i n g   p h a s e ,   s t a n d a r d   w e b   p a g e   p r e - p r o c e s s i n g   m e t h o d s   l i k e   h t m l   t a g   r e m o v a l ,   t o k e n i z a t i o n ,   r e m o v a l   o f   s t o p   w o r d s   a n d   s t e m m i n g   a r e   a p p l i e d   o n   t h e   i n p u t   r e c o r d   r   a n d   a   f e a t u r e   s e t   F   o f   m   t o k e n s   { x 1 , x 2 , . , x m }   a r e   r e t r i e v e d .   T h e n   a   s t a n d a r d   w e i g h t i n g   s c h e m e   W   i s   p r o p o s e d ,   b a s e d   o n   t h e   t e r m   f i e l d   w h e r e   t h e   t e r m   x   i s   p r e s e n t   i n   a   r e c o r d .   E v e n   t h o u g h   a   c o m m o n   t e r m   i s   p r e s e n t   i n   t w o   w e b   p a g e s ,   i t   n o t   o n l y   d e p e n d s   o n   t h e   n u m b e r   o f   o c c u r r e n c e s   i n   e a c h   p a g e ,   b u t   a l s o   d e p e n d s   o n   t h e   f i e l d   i n   w h i c h   i t   i s   p r e s e n t ,   s i n c e   a   w e b   p a g e   i s   e n t i r e l y   d i f f e r e n t   f r o m   a   n o r m a l   t e x t   f i l e .   F o r   e x a m p l e ,   i f   a   w o r d   i s   p r e s e n t   i n   t h e   t i t l e   o f   o n e   w e b   p a g e   a n d   i n   t h e   c o n t e n t   b l o c k   o f   a n o t h e r   w e b   p a g e ,   t h e y   d i f f e r   b y   s i g n i f i c a n c e .   I n   t h e   f i r s t   d o c u m e n t ,   i t   m a y   b e   a   m a i n   f e a t u r e   w h i l e   i n   t h e   s e c o n d   o n e   i t   h a s   g o t   a   l e s s   i m p o r t a n c e .   N u m b e r   o f   o c c u r r e n c e s   o f   e a c h   t o k e n   x   i s   m u l t i p l i e d   w i t h   t h e   w e i g h t   o f   r e s p e c t i v e   t e r m   f i e l d s   w i   w h e r e v e r   t h e   t e r m   i s   p r e s e n t   a n d   a d d e d   t o g e t h e r   f o r   t o t a l   w e i g h t   o f   a   t e r m   W x .         Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I S S N :   2 0 8 8 - 8 7 0 8       A n   E f f i c i e n t   A p p r o a c h   f o r   F i n d i n g   N e a r   D u p l i c a t e   W e b   p a g e s   u s i n g   M i n i m u m   W e i g h t   .   ( S h i n e   N .   D a s )   1 8 9 T a b l e   1 .   P r o p o s e d   W e i g h t i n g   S c h e m e   T e r m   F i e l d   W e i g h t   U R L   2   H e a d i n g   2   T i t l e   2   A n c h o r   T e x t     T o   t h e   s a m e   w e b   s i t e   1   A n c h o r   T e x t     T o   a   d i f f e r e n t   w e b   s i t e   0 . 5   K e y w o r d s   3   D e s c r i p t i o n   3   M a i n   c o n t e n t   b l o c k   1       F u r t h e r   t h i s   w e i g h t   i s   n o r m a l i z e d   b a s e d   o n   t h e   t o t a l   w e i g h t   o f   t h e   r e c o r d ,   W r   a n d   c o l u m n   s u m   o f   T D W   m a t r i x   u s i n g   s o m e   s t a n d a r d   a p p r o a c h e s .   T h i s   i s   d o n e   i n   p e r s p e c t i v e   o f   t h e   g l o b a l   o r d e r i n g   t o   b e   u s e d   i n   t h e   u p c o m i n g   s t a g e s .   O b t a i n e d   f e a t u r e   s e t   a l o n g   w i t h   i t s   w e i g h t s   i s   c o m p a r e d   w i t h   t h e   f e a t u r e s   o f   o t h e r   r e c o r d s   p r e s e n t   i n   t h e   r e p o s i t o r y   f o r   m e a s u r i n g   t h e   s i m i l a r i t y .         F i g u r e   1 .   G e n e r a l   A r c h i t e c t u r e       I f   a   t e r m   x   i s   p r e s e n t   i n   a   r e c o r d   r ,   i t s   t o t a l   w e i g h t   i s   r e p r e s e n t e d   a s   W x r .   H e r e   w e   a p p l y   s o m e   f i l t e r i n g   m e c h a n i s m s   w h i c h   f u r t h e r   r e d u c e   t h e   s i z e   o f   c a n d i d a t e   s e t   a n d   i m p r o v e   t h e   e f f i c i e n c y .   P r i o r   t o   t h i s ,   w e   h a v e   t o   p e r f o r m   a   g l o b a l   o r d e r i n g   b a s e d   o n   a n   i n v e r t e d   i n d e x .   T h e   d o c u m e n t   f r e q u e n c y   o f   a   t o k e n   i s   t h e   n u m b e r   o f   r e c o r d s   t h a t   c o n t a i n   t h e   t o k e n .   W e   c a n   c a n o n i c a l i z e   a   r e c o r d   b y   s o r t i n g   i t s   t o k e n s   b a s e d   o n   a   g l o b a l   o r d e r i n g .   A   d o c u m e n t   f r e q u e n c y   o r d e r i n g   a r r a n g e s   t h e   e n t i r e   t o k e n s   a c c o r d i n g   t o   t h e   i n c r e a s i n g   o r d e r   o f   i t s   d o c u m e n t   f r e q u e n c y .   I n s t e a d   o f   s i m p l y   c o n s i d e r i n g   t h e   d o c u m e n t   f r e q u e n c y ,   w e   m a y   u s e   t h e   f e a t u r e   w e i g h t s   f o r   t h i s   o r d e r i n g .   T h e   n e x t   s t e p   i s   t o   c r e a t e   a   t e r m   d o c u m e n t   w e i g h t   m a t r i x   ( T D W )   t h a t   m a p s   a   t o k e n   x   t o   a   l i s t   o f   r e c o r d s   t h a t   c o n t a i n   x   a n d   t h e   t o t a l   w e i g h t   p e r c e n t a g e   o f   t h e   t o k e n   i n   e a c h   r e c o r d .   I f   a   p a r t i c u l a r   t o k e n   i s   n o t   p r e s e n t   i n   a   r e c o r d ,   i t s   w e i g h t   i s   c o n s i d e r e d   a s   z e r o .   E a c h   r e c o r d   i s   r e p r e s e n t e d   a s   p e r   t h e   g l o b a l   o r d e r i n g .   L e t   r 1 ,   r 2 ,   r 3   b e   t h r e e   c a n o n i c a l i z e d   r e c o r d s .     r 1 = { x 2 ,   x 1 ,   x 3 }   r 2 = { x 4 ,   x 1 ,   x 3 }   r 3 = { x 2 ,   x 4 ,   x 1 ,   x 3 }   T h e   T D W   m a t r i x   i s   g i v e n   i n   T a b l e   2   w h e r e   1       i     4 .   I n   f i l t e r i n g   p h a s e ,   t w o   f i l t e r i n g   m e c h a n i s m s ,   p r e f i x   f i l t e r i n g   a n d   p o s i t i o n a l   f i l t e r i n g ,   a r e   p e r f o r m e d   t o   r e d u c e   t h e   n u m b e r   o f   c a n d i d a t e   r e c o r d s .   P r e f i x   l e n g t h   o f   r   i s   c a l c u l a t e d   a s :       P r e f i x   l e n g t h   =   | r | -   t . | r | + 1                       ( 1 )     b y   a s s u m i n g   t h e   t h r e s h o l d   v a l u e   t   a s   J a c c a r d   s i m i l a r i t y   t h r e s h o l d .   E a c h   t o k e n   i n   p r e f i x   s e t   o f   r   i s   c o m p a r e d   w i t h   p r e f i x   s e t   o f   a l l   r e c o r d s   i n   t h e   r e p o s i t o r y   a n d   i f   a n y   r e c o r d   r i   i s   s h a r i n g   a   t o k e n   w i t h   r   i n   i t s   p r e f i x   s e t ,   i t   i s   a d d e d   t o   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 8 - 8 7 0 8   I J E C E     V o l .   1 ,   N o . 2 ,   D e c e m b e r   2 0 1 1   :     1 8 7     1 9 4   1 9 0 c a n d i d a t e   s e t   C .   T h e   b a s i c   i d e a   b e h i n d   p r e f i x   f i l t e r i n g   p r i n c i p l e   i s   t h a t   i f   t w o   w e b   p a g e s   s h a r e   r a r e   t o k e n s ,   t h e r e   i s   a   c h a n c e   t h a t   i t   m i g h t   b e   s i m i l a r .   S i n c e   w e   a r e   d o i n g   a   g l o b a l   o r d e r i n g   b a s e d   o n   d o c u m e n t   f r e q u e n c i e s   o r   f e a t u r e   w e i g h t s ,   p r e f i x   s e t   o f   a   r e c o r d   c o n t a i n   r a r e   t o k e n s   o r   i r r e l e v a n t   t o k e n s .   I f   n o   t o k e n s   a r e   s h a r e d   i n   p r e f i x   s e t ,   t h a t   r e c o r d   c a n   b e   a v o i d e d   f r o m   f u r t h e r   p r o c e s s i n g .   O n c e   p r e f i x   f i l t e r i n g   i s   o v e r ,   p o s i t i o n a l   f i l t e r i n g   p r i n c i p l e   i s   a p p l i e d   i n   o r d e r   t o   p r u n e   u n w a n t e d   r e c o r d s   f r o m   c a n d i d a t e   s e t   C .       T a b l e   2 .   S a m p l e   T D W   M a t r i x   r e c o r d s   t e r m s   r 1   r 2   r 3   x 2   2 1 1   0   2 3 3   x 4   0   4 2 2   4 3 3   x 1   1 1 1   1 2 2   1 3 3   x 3   3 1 1   3 2 2   3 3 3       C h u a n   X i a o   e t .   a l . [ 2 ]   o b s e r v e d   t h a t   p o s i t i o n a l   i n f o r m a t i o n   c a n   b e   e x p l o i t e d   i n   s e v e r a l   w a y s   t o   f u r t h e r   r e d u c e   t h e   c a n d i d a t e   s i z e .   P o s i t i o n   o f   e a c h   t o k e n   i n   a   r e c o r d   c a n   b e   c o u n t e d ,   s t a r t i n g   f r o m   o n e ,   w h i c h   g i v e s   i n f o r m a t i o n   a b o u t   t h e   u p p e r   b o u n d s   o f   o v e r l a p p i n g   i n   w h i c h   J a c c a r d   t h r e s h o l d   t   c a n   b e   s t a t e d   i n   t e r m s   o f   o v e r l a p   t h r e s h o l d   O   a s       J ( r , r i )     t     O ( r , r i )    ( | | + | r i | )     ( 2 )     a n d   u p p e r   b o u n d s   o f   O   c a n   b e   c a l c u l a t e d   a s       u b o u n d = 1 +   m i n ( | r | - p ,   | r i | - q )     ( 3 )     w h e r e   r e c o r d   r   s h a r e s   a   t e r m   a t   p th   p o s i t i o n   w i t h   a n o t h e r   r e c o r d   r i   a t   p o s i t i o n   q .   I f   u b o u n d   s a t i s f i e s   o v e r l a p   t h r e s h o l d   O ,   r e c o r d   r i   c a n   b e   a d d e d   i n t o   t h e   m e z z a n i n e   s e t   M   f r o m   w h e r e   a n   o p t i m a l   s e t   i s   e x t r a c t e d .       T a b l e   3 .   C a l c u l a t i n g   M W O   r e c o r d s   t e r m s   r 1   r 2   M i n   ( W )   x 2   2 1 1   0   0   x 4   0   4 2 2   0   x 1   1 1 1   1 2 2   m i n (     ,     )   x 3   3 1 1   3 2 2   m i n (     ,     )   T o t a l   1   1   M W O   =   M i n ( W )       B a s e d   o n   t h e   r e c o r d s   f r o m   m e z z a n i n e   s e t   M ,   w e   c r e a t e   a   w e i g h t   m a t r i x   A   s u c h   t h a t   c o l u m n s   r e p r e s e n t   d o c u m e n t s   a n d   r o w s   r e p r e s e n t   t e r m s .   A n   e l e m e n t   a ij   r e p r e s e n t s   t h e   w e i g h t   p e r c e n t a g e   o f   t h e   g l o b a l   f e a t u r e   x i   i n   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I S S N :   2 0 8 8 - 8 7 0 8       A n   E f f i c i e n t   A p p r o a c h   f o r   F i n d i n g   N e a r   D u p l i c a t e   W e b   p a g e s   u s i n g   M i n i m u m   W e i g h t   .   ( S h i n e   N .   D a s )   1 9 1 r e c o r d   r j- 1   s i n c e   t h e   f i r s t   c o l u m n   r e p r e s e n t s   t h e   i n p u t   r e c o r d   r .   I n   v e r i f i c a t i o n   p h a s e ,   e a c h   r e c o r d   i n   M   i s   c o n s i d e r e d   f o r   s i m i l a r i t y   v e r i f i c a t i o n   w i t h   r .   L e t   r   a n d   r j   b e   t h e   r e c o r d s   u n d e r   c o n s i d e r a t i o n .   T h e n   i t s   M W O   i s   c a l c u l a t e d   a s   t h e   s u m   o f   m i n i m u m   w e i g h t s   o f   e a c h   t o k e n   i n   t h o s e   r e c o r d s .   A n   e x a m p l e   c a l c u l a t i o n   o f   M W O   b e t w e e n   r 1   a n d   r 2   a r e   s h o w n   i n   T a b l e   3   w h e r e   1       i     4 .   I f   M W O   s a t i s f i e s   t h e   t h r e s h o l d   t ,   i t   c a n   b e   m a r k e d   a s   a   n e a r   d u p l i c a t e   o f   r   a n d   r a n k e d   o n   t h e   b a s i s   o f   M W O .       3 . 1   P r o p o s e d   A l g o r i t h m     3 . 1 . 1     A l g o r i t h m :   N e a r _ D u p l i c a t e _ D e t e c t i o n     I n p u t :         A   W e b   p a g e   ( W e b _ D o c u m e n t ) ,   r e c o r d s   i n   r e p o s i t o r y                                             ( R e c o r d _ S e t )   a n d   J a c c a r d   t h r e s h o l d   ( t )   O u t p u t :         O p t i m a l   n e a r   d u p l i c a t e   r e c o r d   s e t ,   O *   R e m a r k s :   M     M e z z a n i n e   r e c o r d   s e t                                       T D W _ M a t r i x     t e r m   d o c u m e n t   w e i g h t   m a t r i x     N e a r _ D u p l i c a t e _ D e t e c t i o n   ( W e b _ D o c u m e n t ,   R e c o r d _ S e t ,   t )                 T D W _ M a t r i x     R e n d e r i n g   ( W e b _ D o c u m e n t ,   R e c o r d _ S e t ) ;                 M     F i l t e r i n g ( T D W _ M a t r i x ,   R e c o r d _ S e t ,   t ) ;                                                         O *   V e r i f i c a t i o n ( M ,   R e c o r d _ S e t ,   t ) ;               r e t u r n   O * ;       3 . 1 . 2       A l g o r i t h m :     R e n d e r i n g     I n p u t :       W e b _ D o c u m e n t ,   R e c o r d _ S e t     O u t p u t :       T D W _ M a t r i x   R e m a r k s :   W x   t o t a l   w e i g h t   o f   t h e   t e r m   x     R e n d e r i n g   ( W e b _ D o c u m e n t ,   R e c o r d _ S e t )   I n p u t _ R e c o r d   P r e _ P r o c e s s i n g ( W e b _ D o c u m e n t ) ;   F F u l l   f e a t u r e   s e t ( I n p u t _ R e c o r d ) ;   f o r   a l l   x i     F   W x W e i g h t _ S c h e m e ( x i ) ;   W r W x ;   f o r   a l l   i ,   1     i     | F |   W x N o r m a l i z e ( W x ,   W r ) ;   T D y n a m i c _ T h r e s h o l d i n g ( W r ) ;   r   φ ;   f o r   a l l   x i     F     i f   ( W x     T )         r       r     x i ;   T D W _ M a t r i x   C a n o n i c a l i z e ( r ,   R e c o r d _ S e t ) ;   T D W _ M a t r i x   C o l u m n _ N o r m a l i z e ( T D W _ M a t r i x ) ;   r e t u r n   T D W _ M a t r i x ;     3 . 1 . 3     A l g o r i t h m :     F i l t e r i n g     I n p u t :         T D W _ M a t r i x , R e c o r d _ S e t , t   O u t p u t :         M   R e m a r k s :   A s s u m e   t h a t   I n p u t _ R e c o r d   i s   r e p r e s e n t e d   a s   t h e   f i r s t         c o l u m n   i n   T D W _ M a t r i x     F i l t e r i n g   ( T D W _ M a t r i x ,   R e c o r d _ S e t ,   t )             r T D W _ M a t r i x [ 1 ] ;             / / p r e f i x   f i l t e r i n g             C   φ ;             P r e f i x _ L e n g t h     | r | -   t . | r |   + 1 ;             f o r   a l l   r i     R e c o r d _ S e t   P r e f i x i | r i | -   t . | r i |   + 1 ;     f o r   a l l   j , k ;   1   j     P r e f i x _ L e n g t h ,   1   k     P r e f i x i   i f   ( r [ j ]   = =   r i [ k ] )   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 8 - 8 7 0 8   I J E C E     V o l .   1 ,   N o . 2 ,   D e c e m b e r   2 0 1 1   :     1 8 7     1 9 4   1 9 2       C     C     r i ;             / / p o s i t i o n a l   f i l t e r i n g             M   φ ;             f o r   a l l   r i     C         O   ( | | + | r i | ) ;     f o r   a l l   p , q ;   1   p     P r e f i x _ L e n g t h ,   1   q     P r e f i x i       i f   ( r [ p ] = = r i [ q ] )         u b o u n d 1 +   m i n ( | r | - p ,   | r i | - q ) ;         i f   ( u b o u n d     O )           M     M     r i ;             r e t u r n   M ;     3 . 1 . 4     A l g o r i t h m :     V e r i f i c a t i o n     I n p u t :       M ,   R e c o r d _ S e t ,   t   O u t p u t :       O *     V e r i f i c a t i o n ( M ,   R e c o r d _ S e t ,   t )   O *   φ ;                             f o r   e a c h   r i     M                     f o r   e a c h   f e a t u r e   x       R e c o r d _ S e t ;   1   j   | r | ,   1   k | r i |                               m i n _ W x     m i n   (        ,       ) ;                                                 M W O       m i n _ W x ;                   i f   ( M W O     t )                               O *     O *     r i ;   r e t u r n   O * ;       4 .   E x p e r i m e n t a l   R e s u l t s   4 . 1   D a t a   C o l l e c t i o n   W e   h a v e   g e n e r a t e d   a   h u g e   r e p o s i t o r y   o f   w e b   p a g e   r e c o r d s   f r o m   G o o g l e   s e a r c h   e n g i n e .   I t   w a s   d o n e   f o r   s o m e   s p e c i f i c   q u e r y   w o r d s   g i v e n   t o   G o o g l e   a n d   c o l l e c t e d   a l l   s i m i l a r   p a g e s   w i t h   r e s p e c t   t o   t h e   f i r s t   r a n k e d   r e s u l t   o f   G o o g l e .   S o m e   o f   t h e s e   p a g e s   w e r e   r e m o v e d   d u e   t o   t h e   l a c k   o f   r e q u i r e d   c o n t e n t s   r e t r i e v e d   a n d   n o n - s u i t a b l e   f i l e   f o r m a t s   l i k e   P D F .   E a c h   p a g e   t h u s   o b t a i n e d   i s   p r e - p r o c e s s e d ,   f e a t u r e d   a n d   w e i g h t e d   a c c o r d i n g   t o   t h e   w e i g h t i n g   s c h e m e   a n d   p r o p e r l y   i n d e x e d   t o   c r e a t e   a   T D W   m a t r i x .   T h i s   p r o c e d u r e   w a s   r e p e a t e d   f o r   1 0   d i f f e r e n t   q u e r i e s   a n d   e x p e r i m e n t s   w e r e   c o n d u c t e d   o n   1 0   d i f f e r e n t   r e p o s i t o r i e s   t h u s   c r e a t e d .   E a c h   e x p e r i m e n t   i s   r e s u l t e d   a n   o p t i m a l   s e t   o f   n e a r   d u p l i c a t e   w e b   p a g e s   w i t h   r e s p e c t   t o   t h e   f i r s t   r a n k e d   w e b   p a g e   i n   t h e   q u e r y   r e s u l t .           4 . 2                   E x p e r i m e n t a l   S e t   u p   T o   c o n d u c t   r e q u i r e d   e x p e r i m e n t s ,   w e   c r e a t e d   a n   o n l i n e   t o o l   w h i c h   r e t r i e v e s   t h e   c o n t e n t s   o f   a n   i n p u t   w e b   p a g e ;   p e r f o r m   a l l   p r e - p r o c e s s i n g   s t e p s   a n d   e x t r a c t   w e i g h t e d   f e a t u r e   s e t .   W i t h   r e s p e c t   t o   t h e   h u g e   r e p o s i t o r y   c r e a t e d   e a r l i e r ,   a   T D W   m a t r i x   i s   f o r m e d   i n   a   g l o b a l   o r d e r i n g   a n d   f i l t e r i n g   p r i n c i p l e s   a r e   a p p l i e d .   T h e   r e s u l t a n t   m a t r i x   t h u s   o b t a i n e d   i s   s u p p l i e d   f o r   s i m i l a r i t y   v e r i f i c a t i o n   b y   a n a l y z i n g   M W O   o f   e a c h   r e c o r d   w i t h   t h e   i n p u t   r e c o r d .   I f   i t   s a t i s f i e s   t h e   t h r e s h o l d   v a l u e   t ,   t h a t   r e c o r d   i s   m a r k e d   a s   a   n e a r   d u p l i c a t e   o n e .   A l l   t h e s e   s t e p s   w e r e   i m p l e m e n t e d   u s i n g   P H P .     4 . 3                   R e s u l t   A n a l y s i s   T o   e v a l u a t e   t h e   d e g r e e   o f   a c c u r a c y ,   e f f i c i e n c y   a n d   s c a l a b i l i t y   o f   o u r   a l g o r i t h m ,   w e   h a v e   u s e d   t w o   s t a n d a r d   b e n c h m a r k   m e a s u r e s ,   p r e c i s i o n   a n d   r e c a l l .     = N u m be r   o f   w e b   p a g e s   d e t e c t e d   c o r r e c t l y T o t a l   n u m be r   o f   n e a r _ d u p l i c a t e   w e b   p a g e s   d e t e c t e d      = N u m be r   o f   w e b   p a g e s   d e t e c t e d   c o r r e c l t y T o t a l   n u m b e r   o f   n e a r _ d u p l i c a t e   w e b   p a g e s     T h e   m e a s u r e s   o b t a i n e d   f o r   1 0   d i f f e r e n t   r e p o s i t o r i e s   a r e   g i v e n   b y   T a b l e   4 .   W h i l e   c r e a t i n g   a   r e p o s i t o r y   o f   5 0   p a g e s ,   a   T D W   m a t r i x   o f   a l m o s t   s i z e   3 0 0 0   x   5 0   i s   c r e a t e d   i n   r e n d e r i n g   p h a s e .   A f t e r   f i l t e r i n g   p h a s e ,   i t s   s i z e   w a s   r e d u c e d   t o   2 5 0 0   x   6   w h e n   a   t h r e s h o l d   t = 0 . 5   i s   a p p l i e d .   A n d   f i n a l l y ,   a   s e t   o f   t h r e e   n e a r   d u p l i c a t e s   { d 1 ,   d 2 ,   d 3 }   a r e   r e t u r n e d .   W e   c o u l d   i m p r o v e   r e c a l l   v a l u e   w i t h o u t   c o m p r o m i s i n g   p r e c i s i o n   v a l u e .         Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I S S N :   2 0 8 8 - 8 7 0 8       A n   E f f i c i e n t   A p p r o a c h   f o r   F i n d i n g   N e a r   D u p l i c a t e   W e b   p a g e s   u s i n g   M i n i m u m   W e i g h t   .   ( S h i n e   N .   D a s )   1 9 3 T a b l e   4 :   P e r f o r m a n c e   M e a s u r e s   Q u e r y   w o r d   N o   o f   n e a r   d u p l i c a t e s   P r e c i s i o n   %   R e c a l l   %   Q 1   1 6 7   9 4 . 4   9 4 . 2   Q 2   9 8   9 4 . 9   9 4 . 9   Q 3   1 5 6   9 4 . 8   9 3 . 6   Q 4   1 2 3   9 3 . 0   9 3 . 7   Q 5   7 9   9 5 . 2   9 5 . 8   Q 6   1 2 9   9 4 . 6   9 4 . 5   Q 7   6 3   9 3 . 1   9 4 . 1   Q 8   1 1 2   9 4 . 3   9 5 . 6   Q 9   1 0 9   9 3 . 6   9 4 . 9   Q 1 0   5 9   9 4 . 7   9 5 . 8   A v e r a g e   9 4 . 3   9 4 . 7       A l l   t h e   r e s u l t s   o b t a i n e d   d u r i n g   t h e   e x p e r i m e n t s   w e r e   h a v i n g   a   g o o d   l e v e l   o f   s i m i l a r i t y   b o t h   i n   t e r m s   o f   s y n t a x   a n d   s e m a n t i c s .   W e i g h t i n g   s c h e m e   p l a y s   a n   i m p o r t a n t   r o l e   i n   s e m a n t i c   a n a l y s i s   w h i l e   m a j o r i t y   o f   e x i s t i n g   w o r k s   d e p e n d   o n l y   o n   s i m p l e   t e r m   f r e q u e n c y   b a s e d   a p p r o a c h e s   o r   b o o l e a n   a p p r o a c h e s .   S h i n g l e   b a s e d   a p p r o a c h e s   c h e c k   o n l y   t h e   n u m b e r   o f   o v e r l a p p e d   s h i n g l e s   i n   t h e   p a i r   w h i c h   i s   p u r e l y   a   s y n t a x   b a s e d   o n e .   I n   o u r   m e t h o d ,   b y   m e a s u r i n g   t h e   M W O   v a l u e s ,   w e   c o u l d   p r e d i c t   t h e   o p t i m a l   s e t   o f   n e a r   d u p l i c a t e s   i n s t a n t l y   a n d   p r e c i s e l y .         5 .   C o n c l u s i o n   a n d   F u t u r e   W o r k   T h i s   p a p e r   p r o p o s e d   a   n o v e l   t a s k   f o r   f i n d i n g   n e a r   d u p l i c a t e   w e b   p a g e s .   T h e   p r o p o s e d   t e c h n i q u e   a i m s   a t   h e l p i n g   d o c u m e n t   c l a s s i f i c a t i o n   i n   w e b   c o n t e n t   m i n i n g   b a s e d   o n   T D W   m a t r i x   a n d   M W O   m e t h o d .   I n s t e a d   o f   s i m p l y   u s i n g   t h e   t r a d i t i o n a l   c o s i n e   s i m i l a r i t y   o r   d o c u m e n t   f r e q u e n c y   f o r   f i n d i n g   s i m i l a r   p a g e s ,   w e   p r o p o s e d   a   t h r e e   s t a g e   a l g o r i t h m   w h i c h   r e d u c e s   t h e   s i z e   a n d   e n h a n c e s   t h e   r e l e v a n c y   f u r t h e r .     I n   t h i s   p a p e r ,   w e   f o c u s   a   T D W   m a t r i x   b a s e d   M W O   m e t h o d   t h a t   c a n   b e   a p p l i e d   f o r   g e n e r a t i n g   a n   o p t i m a l   n e a r   d u p l i c a t e   s e t .   W e   e v a l u a t e   t h e   a c c u r a c y   a n d   s c a l a b i l i t y   o f   o u r   a l g o r i t h m   i n   t e r m s   o f   p r e c i s i o n   a n d   r e c a l l   a n d   w e   c o u l d   a c h i e v e   a   m u c h   b e t t e r   r e c a l l   v a l u e   w i t h o u t   c o m p r o m i s i n g   t h e   p r e c i s i o n   v a l u e .   T h e   e x p e r i m e n t s   p r o v e d   t h a t   o u r   w o r k   h a s   a   b e t t e r   p e r f o r m a n c e   t h a n   o t h e r   m e t h o d s .     F u r t h e r   r e s e a r c h   w o r k s   c a n   e x t e n d   t h i s   t o   a   m o r e   e f f i c i e n t   m e t h o d   f o r   f i n d i n g   s i m i l a r i t y   j o i n s   w h i c h   c a n   b e   i n c o r p o r a t e d   i n   f o c u s e d   w e b   c r a w l e r s .   A c c u r a c y   c a n   b e   i m p r o v e d   f u r t h e r   b y   a p p l y i n g   t h i s   m e t h o d   a f t e r   i d e n t i f y i n g   t h e   m a i n   c o n t e n t   b l o c k s   r a t h e r   t h a n   t h e   e n t i r e   w e b   p a g e .       R e f e r e n c e s   [ 1 ]   F e t t e r l y   D ,   M a n a s s e   M ,   N a j o r k   M ,   O n   t h e   e v o l u t i o n   o f   c l u s t e r s   o f   n e a r   d u p l i c a t e   W e b   p a g e s ,   I n   P r o c e e d i n g s   o f   t h e   F i r s t   L a t i n   A m e r i c a n   W e b   Co n g r e s s ,   p p . 3 7 -   4 5   N o v .   2 0 0 3 .   [ 2 ]   Ch u a n   X i a o ,   W e i   W a n g ,   X u e m i n   L i n ,   E f f i c i e n t   S i m i l a r i t y   J o i n s   f o r   N e a r   D u p l i c a t e   D e t e c t i o n ,   P r o c e e d i n g   o f   t h e   1 7 t h   i n t e r n a t i o n a l   c o n f e r e n c e   o n   W o r l d   W i d e   W e b ,   p p   1 3 1     1 4 0 .   A p r i l   2 0 0 8 .   [ 3 ]   G u r m e e t   S i n g h   M a n k u ,   A r v i n d   J a i n   a n d   A n i s h   D a s   S a r m a ,   D e t e c t i n g   n e a r   d u p l i c a t e s   f o r   w e b   c r a w l i n g ,   I n   P r o c e e d i n g s   o f   t h e   1 6 t h   i n t e r n a t i o n a l   c o n f e r e n c e   o n   W o r l d   W i d e   W e b ,   p p .   1 4 1   -   1 5 0 ,   Ba n f f ,   A l b e r t a ,   Ca n a d a ,   2 0 0 7 .   [ 4 ]   D e n n i s   F e t t e r l y ,   M a r k   M a n a s s e   a n d   M a r c   N a j o r k ,   D e t e c t i n g   p h r a s e - l e v e l   d u p l i c a t i o n   o n   t h e   W o r l d   W i d e   W e b ,   I n   P r o c e e d i n g s   o f   t h e   2 8 t h   a n n u a l   i n t e r n a t i o n a l   A CM   S I G I R   c o n f e r e n c e   o n   Re s e a r c h   a n d   d e v e l o p m e n t   i n   i n f o r m a t i o n   r e t r i e v a l ,   p p . 1 7 0   -   1 7 7 ,   S a l v a d o r ,   Br a z i l ,   2 0 0 5 .   [ 5 ]   D .   L o w d   a n d   C.   M e e k ,   G o o d   w o r d   a t t a c k s   o n   s t a t i s t i c a l   s p a m   f i l t e r s ,   S e c o n d   C o n f e r e n c e   o n   E m a i l   a n d   A n t i - S p a m ,   J u l y   2 0 0 5 .   [ 6 ]   S h i n e   N   D a s ,   M i d h u n   M a t h e w ,   P r a m o d   K . V i j a y a r a g h a v a n ,   A n   A p p r o a c h   f o r   O p t i m a l   F e a t u r e   S u b s e t   S e l e c t i o n   u s i n g   a   N e w   T e r m   W e i g h t i n g   S c h e m e   a n d   M u t u a l   I n f o r m a t i o n ,   P r o c e e d i n g   o f   t h e   I n t e r n a t i o n a l   Co n f e r e n c e   o n   A d v a n c e d   S c i e n c e ,   E n g i n e e r i n g   a n d   I n f o r m a t i o n   T e c h n o l o g y ,   M a l a y s i a ,   2 0 1 1 ,   p p   2 7 3 - 2 7 8 ,   J a n u a r y   2 0 1 1 .   [ 7 ]   Br o d e r ,   A . ,   G l a s s m a n ,   S . ,   M a n a s s e ,   M . ,   a n d   Z w e i g   G .   S y n t a c t i c   Cl u s t e r i n g   o f   t h e   W e b ,   I n   6 t h   I n t e r n a t i o n a l   W o r l d   W i d e   W e b   Co n f e r e n c e ,   p p :   3 9 3 - 4 0 4 ,   1 9 9 7 .   [ 8 ]   F e t t e r l y ,   D . ,   M a n a s s e ,   M .   a n d   N a j o r k ,   M .   O n   t h e   e v o l u t i o n   o f   c l u s t e r s   o f   n e a r   d u p l i c a t e   w e b   p a g e s ,   I n   P r o c e e d i n g s   o f   t h e   f i r s t   L a t i n   A m e r i c a n   W e b   Co n g r e s s   ( L A W e b ) ,   3 7 4 5 ,   2 0 0 3 .   [ 9 ]   Y u n   L i n g ,   X i a o b o   T a o   H e x i n   L v ,   A   P r i o r i t y - Ba s e d   M e t h o d   O f   N e a r   d u p l i c a t e d   T e x t   I n f o r m a t i o n   O f   W e b   P a g e s   D e l e t i o n ,   I E E E   I n t e r n a t i o n a l   Co n f e r e n c e   o n   S o f t w a r e   E n g i n e e r i n g   a n d   S e r v i c e   S c i e n c e s   ( I CS E S S ) ,   A u g u s t   2 0 1 0 .   [ 1 0 ]   V . A .   N a r a y a n a ,   P .   P r e m c h a n d   a n d   A .   G o v a r d h a n ,   E f f e c t i v e   D e t e c t i o n   o f   N e a r   D u p l i c a t e   W e b   D o c u m e n t s   i n   W e b   Cr a w l i n g ,   I n t e r n a t i o n a l   J o u r n a l   o f   Co m p u t a t i o n a l   I n t e l l i g e n c e   Re s e a r c h ,   V o l u m e   5 ,   N u m b e r   1 ,   p p .   8 3 9 6 ,   2 0 0 9 .   [ 1 1 ]   M i d h u n   M a t h e w ,   S h i n e   N   D a s ,   P r a m o d   K . V i j a y a r a g h a v a n   " A   N o v e l   A p p r o a c h   f o r   N e a r - D u p l i c a t e   D e t e c t i o n   o f   W e b   P a g e s   u s i n g   T D W   M a t r i x . "   I n t e r n a t i o n a l   J o u r n a l   o f   Co m p u t e r   A p p l i c a t i o n s   1 9 ( 7 ) : 1 6 - 2 1 ,   A p r i l   2 0 1 1 . P u b l i s h e d   b y   F o u n d a t i o n   o f   C o m p u t e r   S c i e n c e   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 8 - 8 7 0 8   I J E C E     V o l .   1 ,   N o . 2 ,   D e c e m b e r   2 0 1 1   :     1 8 7     1 9 4   1 9 4 [ 1 2 ]   S h i n e   N   D a s ,   K .   V .   P r a m o d ,   R e l e v a n c y   b a s e d   Re - r a n k i n g   o f   S e a r c h   E n g i n e   Re s u l t ,   P r o c e e d i n g s   o f   I n t e r n a t i o n a l   C o n f e r e n c e   o n   M a t h e m a t i c a l   C o m p u t i n g   a n d   M a n a g e m e n t ,   K e r a l a ,   I n d i a ,   J u n e   2 0 1 0 .       B i b l i o g r a p h y   o f   a u t h o r s     S h i n e   N   D a s   r e c e i v e d   h i s   M . T e c h   d e g r e e   f r o m   Co c h i n   U n i v e r s i t y   o f   S c i e n c e   a n d   T e c h n o l o g y .     H e   i s   w o r k i n g   a s   a n   A s s o c i a t e   p r o f e s s o r   i n   D e p a r t m e n t   o f   Co m p u t e r   S c i e n c e   &   E n g i n e e r i n g ,   Co l l e g e   o f   E n g i n e e r i n g   M u n n a r ,   I n d i a .     H e   h a s   m o r e   t h a n   9   y e a r s   o f   i n d u s t r i a l   e x p e r i e n c e   a n d   1 2   y e a r s   o f   t e a c h i n g   e x p e r i e n c e .   H e   i s   d o i n g   h i s   r e s e a r c h   i n   t h e   D e p a r t m e n t   o f   Co m p u t e r   A p p l i c a t i o n s ,   Co c h i n   U n i v e r s i t y   o f   S c i e n c e   a n d   T e c h n o l o g y   u n d e r   t h e   g u i d a n c e   o f   D r .   P r a m o d   K   V i j a y a r a g h a v a n .   H i s   r e s e a r c h   i n t e r e s t s   i n c l u d e   w e b   c o n t e n t   m i n i n g ,   b i o l o g i c a l l y   i n s p i r e d   c o m p u t i n g ,   a r t i f i c i a l   n e u r a l   n e t w o r k   a n d   m a c h i n e   l e a r n i n g ,   a n d   e - l e a r n i n g .   H e   h a s   p u b l i s h e d   a r o u n d   9   p e e r   r e v i e w e d   r e s e a r c h   p a p e r s   i n   I n t e r n a t i o n a l   J o u r n a l s .         M i d h u n   M a t h e w   r e c e i v e d                             M i d h u n   M a t h e w   B. T e c h .   d e g r e e   i n   Co m p u t e r   S c i e n c e   &   E n g i n e e r i n g   f r o m   Co c h i n   U n i v e r s i t y   o f   S c i e n c e   &   T e c h n o l o g y ,   I n d i a ,   i n   2 0 0 8   a n d   M . T e c h .   D e g r e e   i n   A d v a n c e d   Co m p u t i n g   f r o m   S A S T R A   U n i v e r s i t y ,   I n d i a ,   i n   2 0 1 1 .   H e   s t a r t e d   h i s   t e a c h i n g   c a r e e r   a s   a   l e c t u r e r   i n   Co l l e g e   o f   E n g i n e e r i n g   M u n n a r ,   I n d i a ,   i n   2 0 0 8 .   C u r r e n t l y   h e   i s   a n   a s s i s t a n t   p r o f e s s o r   a n d   a   r e s e a r c h e r   w i t h   M a r   Ba s e l i o s   I n s t i t u t e   o f   T e c h n o l o g y   &   S c i e n c e   [ M BI T S ] ,   K e r a l a ,   I n d i a .   H i s   r e s e a r c h   i n t e r e s t s   i n c l u d e   W e b   m i n i n g ,   A l g o r i t h m   d e s i g n ,   D a t a   s t r u c t u r e   d e s i g n ,   I n f o r m a t i o n   P r o c e s s i n g ,   M a c h i n e   l e a r n i n g   a n d   T h e o r e t i c a l   c o m p u t i n g .   H e   h a s   p u b l i s h e d   a b o u t   1 0   r e s e a r c h   p a p e r s   i n   r e p u t e d   j o u r n a l s   a n d   w o n   s e v e r a l   a w a r d s .       D r .   P r a m o d   K   V i j a y a r a g h a v a n ,   p r e s e n t l y   w o r k i n g   a s   A s s o c i a t e   P r o f e s s o r   a n d   H e a d   o f   t h e   D e p a r t m e n t   o f   Co m p u t e r   A p p l i c a t i o n s ,   Co c s h i n   U n i v e r s i t y   o f   S c i e n c e   a n d   T e c h n o l o g y .   H e   h a s   m o r e   t h a n   2 0   y e a r s   o f   r e s e a r c h   a n d   t e a c h i n g   e x p e r i e n c e .   H i s   a r e a s   o f   I n t e r e s t   a r e   Cr y p t o g r a p h y   a n d   Co d i n g   T h e o r y ,   S i m u l a t i o n s   a n d   M o d e l l i n g ,   M a t h e m a t i c a l   M o r p h o l o g y   a n d   D a t a   m i n i n g .   H e   h a s   g o t   m o r e   t h a n   t w e n t y   f i v e   r e s e a r c h   p u b l i c a t i o n s   i n   N a t i o n a l   a n d   I n t e r n a t i o n a l   J o u r n a l       Evaluation Warning : The document was created with Spire.PDF for Python.