T E L K O M N I K A ,   V o l . 9 ,   N o . 3 ,   D e c e m b e r   2 0 1 1 ,   p p .   4 0 3 ~ 4 1 0   I S S N :   1 6 9 3 - 6 9 3 0   a c c r e d i t e d   b y   D G H E   ( D I K T I ) ,   D e c r e e   N o :   5 1 / D i k t i / K e p / 2 0 1 0           4 0 3       R e c e i v e d   A p r i l   1 8 th ,   2 0 1 1 ;   R e v i s e d   J u n e   1 1 th ,   2 0 1 1 ;   A c c e p t e d   J u n e   2 7 th ,   2 0 1 1   F o c u s e d   C r a w l e r   O p t i m i z a t i o n   U s i n g   G e n e t i c   A l g o r i t h m       B a n u   W i r a w a n   Y o h a n e s 1 ,   H a n d o k o 2 ,   H a r t a n t o   K u s u m a   W a r d a n a 3   F a c u l t y   o f   E l e c t r o n i c   a n d   C o m p u t e r   E n g i n e e r i n g ,   U n i v e r s i t a s   K r i s t e n   S a t y a   W a c a n a ,   S a l a t i g a   J l .   D i p o n e g o r o   5 2 - 6 0   S a l a t i g a   5 0 7 1 1   C e n t r a l   J a v a ,   P h o n e / F a x . :   + 6 2   2 9 8   3 1 1 8 8 4   E - m a i l :   b o n a _ y o @ y a h o o . c o . i d 1 ,   h a n d o k o @ s t a f f . u k s w . e d u 2 ,   h k w a r d a n a @ y a h o o . c o m 3       A b s t r a k   Se l a m a   u k u r a n   d a r i   W e b   t e r u s   b e r k e m b a n g ,   p e n c a r i a n   i n f o r m a s i   y a n g   b e r g u n a   p a d a   W e b   t e l a h   m e n j a d i   s e m a k i n   s u l i t .   F o c u s e d   c r a w l e r   b e r t u j u a n   u n t u k   m e n e l u s u r i   W e b   d e n g a n   m e n y e s u a i k a n   k e p a d a   s e b u a h   t o p i k   t e r t e n t u .   M a k a l a h   i n i   m e n d i s k u s i k a n   p e r m a s a l a h a n   y a n g   d i s e b a b k a n   o l e h   a l g o r i t m a   p e n c a r i a n   l o k a l .   C r a w l e r   d a p a t   t e r j e b a k   d i   d a l a m   s e j u m l a h   k o m u n i t a s   W e b   y a n g   t e r b a t a s   d a n   m e n g a b a i k a n   h a l a m a n   W e b   y a n g   r e l e v a n   d i   l u a r   j a l u r   p e n e l u s u r a n n y a .   Se b u a h   a l g o r i t m a   g e n e t i k   s e b a g a i   a l g o r i t m a   p e n c a r i a n   g l o b a l   d i m o d i f i k a s i   u n t u k   m e n g a t a s i   p e r m a s a l a h a n   t e r s e b u t .   Al g o r i t m a   g e n e t i k   d i g u n a k a n   u n t u k   m e n g o p t i m a l k a n   p e n e l u s u r a n   p a d a   W e b   d a n   m e m i l i h   h a l a m a n   W e b   y a n g   l e b i h   s e s u a i   u n t u k   d i u n d u h   o l e h   c r a w l e r .   Be b e r a p a   p e r c o b a a n   e v a l u a s i   d i s e l e n g g a r a k a n   u n t u k   m e m e r i k s a   e f e k t i f i t a s   d a r i   p e n d e k a t a n   y a n g   d i a j u k a n   p a d a   m a k a l a h .   P e n e l u r a n   c r a w l e r   m e n g h a s i l k a n   k o l e k s i   b e r i s i   3 3 9 6   h a l a m a n   W e b   d a r i   5 3 9 0   l i n k   y a n g   d i t e l u s u r i ,   a t a u   t i n g k a t   p e n y a r i n g a n   s e l e k s i   R o d a - R o u l e t t e   s e b e s a r   6 3 %   d a n   t i n g k a t   k e a k u r a t a n   9 3 %   p a d a   5   k a t e g o r i   y a n g   b e r b e d a .   H a s i l   t e r s e b u t   m e n u n j u k k a n   b a h w a   p e n g g u n a a n   a l g o r i t m a   g e n e t i k   t e l a h   m e m a m p u k a n   f o c u s e d   c r a w l e r   u n t u k   m e n e l u s u r i   W e b   s e c a r a   k o m p r e h e n s i f ,   m e s k i p u n   k o l e k s i n y a   r e l a t i f   k e c i l .   Se l a n j u t n y a ,   p e n e l i t i a n   i n i   m e m b a w a   p o t e n s i   y a n g   b e s a r   u n t u k   m e m b a n g u n   k o l e k s i   y a n g   l e b i h   b a i k   d i b a n d i n g k a n   d e n g a n   m e t o d e   f o c u s e d   c r a w l i n g   t r a d i s i o n a l .     K e y w o r d s :   f o c u s e d   c r a w l e r ,   a l g o r i t m a   g e n e t i k ,   p e n c a r i a n   p a d a   W e b .       A b s t r a c t   As   t h e   s i z e   o f   t h e   W e b   c o n t i n u e s   t o   g r o w ,   s e a r c h i n g   i t   f o r   u s e f u l   i n f o r m a t i o n   h a s   b e c o m e   m o r e   d i f f i c u l t .   F o c u s e d   c r a w l e r   i n t e n d s   t o   e x p l o r e   t h e   W e b   c o n f o r m   t o   a   s p e c i f i c   t o p i c .   T h i s   p a p e r   d i s c u s s e s   t h e   p r o b l e m s   c a u s e d   b y   l o c a l   s e a r c h i n g   a l g o r i t h m s .   C r a w l e r   c a n   b e   t r a p p e d   w i t h i n   a   l i m i t e d   W e b   c o m m u n i t y   a n d   o v e r l o o k   s u i t a b l e   W e b   p a g e s   o u t s i d e   i t s   t r a c k .   g e n e t i c   a l g o r i t h m   a s   a   g l o b a l   s e a r c h i n g   a l g o r i t h m   i s   m o d i f i e d   t o   a d d r e s s   t h e   p r o b l e m s .   T h e   g e n e t i c   a l g o r i t h m   i s   u s e d   t o   o p t i m i z e   W e b   c r a w l i n g   a n d   t o   s e l e c t   m o r e   s u i t a b l e   W e b   p a g e s   t o   b e   f e t c h e d   b y   t h e   c r a w l e r .   Se v e r a l   e v a l u a t i o n   e x p e r i m e n t s   a r e   c o n d u c t e d   t o   e x a m i n e   t h e   e f f e c t i v e n e s s   o f   t h e   a p p r o a c h .   T h e   c r a w l e r   d e l i v e r s   c o l l e c t i o n s   c o n s i s t   o f   3 3 9 6   W e b   p a g e s   f r o m   5 3 9 0   l i n k s   w h i c h   h a d   b e e n   v i s i t e d ,   o r   f i l t e r i n g   r a t e   o f   R o u l e t t e - W h e e l   s e l e c t i o n   a t   6 3 %   a n d   p r e c i s i o n   l e v e l   a t   9 3 %   i n   5   d i f f e r e n t   c a t e g o r i e s .   T h e   r e s u l t   s h o w e d   t h a t   t h e   u t i l i z a t i o n   o f   g e n e t i c   a l g o r i t h m   h a d   e m p o w e r e d   f o c u s e d   c r a w l e r   t o   t r a v e r s e   t h e   W e b   c o m p r e h e n s i v e l y ,   d e s p i t e   i t   r e l a t i v e l y   s m a l l   c o l l e c t i o n s .   F u r t h e r m o r e ,   i t   b r o u g h t   u p   a   g r e a t   p o t e n t i a l   f o r   b u i l d i n g   a n   e x e m p l a r y   c o l l e c t i o n s   c o m p a r e d   t o   t r a d i t i o n a l   f o c u s e d   c r a w l i n g   m e t h o d s .     K e y w o r d s :   f o c u s e d   c r a w l e r ,   g e n e t i c   a l g o r i t h m ,   W e b   s e a r c h i n g .         1 .     I n t r o d u c t i o n   N o w a d a y s   t h e   W e b   b e c o m e s   a   h u g e   i n f o r m a t i o n   s o u r c e ,   w h i c h   h a s   a t t r a c t e d   m a n y   p e o p l e   f r o m   a l l   o v e r   t h e   w o r l d .   F o r   a   W e b   c r a w l e r ,   o n e   o f   t h e   m o s t   i m p o r t a n t   p a r t s   o f   s e a r c h   e n g i n e s ,   s e a r c h i n g   t h r o u g h   s o   m a n y   d o c u m e n t s   t o   s e l e c t   t h e   c o m p a t i b l e   o n e s   i s   a   t e d i o u s   t a s k .   M o r e o v e r ,   t h e   W e b ,   w h i c h   c o n t a i n s   m o r e   t h a n   1 1   m i l l i o n   p a g e s   s t i l l   k e e p s   g r o w i n g   a n d   c h a n g i n g   r a p i d l y .   F o c u s e d   c r a w l e r   [ 1 ]   i s   u s e d   t o   s e l e c t i v e l y   c o l l e c t   s m a l l e r   W e b   p a g e s   c o l l e c t i o n s   a c c o r d i n g   t o   a   p a r t i c u l a r   t o p i c   w i t h   h i g h   p r e c i s i o n .   A   f o c u s e d   c r a w l e r   w i l l   t r y   t o   p r e d i c t   w h e t h e r   a   t a r g e t   U R L   i s   p o i n t i n g   t o   a   r e l e v a n t   W e b   p a g e   b e f o r e   a c t u a l l y   f e t c h i n g   i t .   F o c u s e d   c r a w l e r s   r e l y   o n   t w o   k i n d s   o f   a l g o r i t h m   t o   k e e p   t h e   c r a w l i n g   p r o c e s s   o n   t h e   t r a c k .   F i r s t ,   W e b   a n a l y s i s   a l g o r i t h m   w i l l   e v a l u a t e   t h e   q u a l i t y   a n d   r e l e v a n c e   o f   W e b   p a g e s   p o i n t e d   b y   t a r g e t   U R L s .   S e c o n d ,   W e b   s e a r c h i n g   a l g o r i t h m   w i l l   d e t e r m i n e   t h e   o p t i m a l   o r d e r   i n   w h i c h   t h e   t a r g e t s   U R L s   a r e   v i s i t e d .   L a t e r   W e b   a n a l y s i s   a l g o r i t h m s   c a n   b e   c a t e g o r i z e d   i n t o   t w o   t y p e s :   t h e   c o n t e n t - b a s e d   a l g o r i t h m s   w h i c h   a n a l y z e   t h e   a c t u a l   H T M L   c o n t e n t   o f   a   W e b   p a g e   t o   o b t a i n   i n f o r m a t i o n   a b o u t   Evaluation Warning : The document was created with Spire.PDF for Python.
                                        I S S N :   1 6 9 3 - 6 9 3 0   T E L K O M N I K A     V o l .   9 ,   N o .   3 ,     D e c e m b e r   2 0 1 1   :     4 0 3     4 1 0   4 0 4 t h e   p a g e   i t s e l f   a n d   t h e   l i n k - b a s e d   a l g o r i t h m s   t h a t   r e p r e s e n t   a   c o n s i d e r a b l e   a m o u n t   o f   l a t e n t   h u m a n   a n n o t a t i o n   a n d   o f f e r s   s o m e   i m p o r t a n t   i n f o r m a t i o n   f o r   a n a l y z i n g   t h e   r e l e v a n c e   a n d   q u a l i t y   o f   W e b   p a g e s   [ 2 ] .   F o r   e x a m p l e ,   t h e   c o n t e n t - b a s e d   a l g o r i t h m s   e x t r a c t   k e y w o r d s   o r   p h r a s e s   f r o m   t h e   b o d y   t e x t   u s i n g   d o c u m e n t - i n d e x i n g   t e c h n i q u e s   t o   d e t e r m i n e   a   p a g e s   r e l e v a n c e .   W e b   p a g e   c a n   b e   c o n s i d e r e d   a s   s t a n d a r d   d o c u m e n t   w h i c h   i s   a l r e a d y   k n o w n   a s   t h e   s p e c i f i c   d o m a i n   u s i n g   t h e   v e c t o r   s p a c e   m o d e l   [ 3 ] .   T h e   v e c t o r   s p a c e   m o d e l   h a s   b e e n   e m p l o y e d   i n   m a n y   e x i s t i n g   f o c u s e d   c r a w l e r s   [ 4 ] ,   [ 5 ] .   W h e r e a s   i n   t h e   l i n k - b a s e d   a l g o r i t h m s ,   W e b   p a g e s   c o n s i s t i n g   o f   m o r e   i n c o m i n g   l i n k s .   T h e y   a r e   c o n s i d e r e d   t o   b e   m o r e   i m p o r t a n t   t h a n   t h e   o t h e r .   T h i s   i s   s i m i l a r   t o   t h e   c i t a t i o n   a n a l y s i s   i n   w h i c h   f r e q u e n t l y   c i t e d   a r t i c l e s   a r e   r e p u t e d l y   t o   b e   m o r e   s i g n i f i c a n t .   T h e   m o s t   n o t o r i o u s l y   l i n k - b a s e d   W e b   a n a l y s i s   a l g o r i t h m s   i n c l u d e   P a g e   R a n k   [ 6 ]   a n d   H I T S   [ 7 ] .   M a n y   d i f f e r e n t   W e b   s e a r c h i n g   a l g o r i t h m s   h a d   b e e n   e x a m i n e d   i n   f o c u s e d   c r a w l i n g .   A m o n g   t h e m   a r e   t h e   b r e a d t h - f i r s t   s e a r c h   [ 8 ]   a n d   t h e   b e s t - f i r s t   s e a r c h   [ 1 ] ,   [ 4 - 5 ] ,   [ 9 ] ,   t h e   t w o   m o s t   p o p u l a r   s e a r c h e s .   T h e   o t h e r   m o r e   a d v a n c e d   s e a r c h i n g   a l g o r i t h m s   s u c h   a s   s p r e a d i n g   a c t i v a t i o n   [ 2 ]   a n d   g e n e t i c   a l g o r i t h m   ( G A )   [ 1 0 ]   h a d   b e e n   p r o p o s e d   a s   w e l l .   S e v e r a l   p r o b l e m s   e m e r g e d   f r o m   t r a d i t i o n a l   f o c u s e d   c r a w l e r   d e s i g n ,   n o t a b l y   t h e   o n e s   c a u s e d   b y   u s i n g   l o c a l   W e b   s e a r c h i n g   a l g o r i t h m s .   T h e   l o c a l   s e a r c h i n g   a l g o r i t h m s   t r a v e r s e d   t h e   s e a r c h   s p a c e   b y   v i s i t i n g   n e i g h b o r s   o f   p r e v i o u s l y   v i s i t e d   n o d e s .   H e n c e ,   t h e y   c o u l d   f i n d   o n l y   s u i t a b l e   p a g e s   w i t h i n   a   l i m i t e d   s u b - g r a p h   o f   t h e   W e b   n e a r b y   t h e   s t a r t i n g   U R L s .   T h i s   p r o b l e m   i s   u s u a l l y   a s s u m e d   a s   b e i n g   t r a p p e d   i n   l o c a l   o p t i m a l .   I t   b e c a m e   m o r e   o b v i o u s   a f t e r   t h e   p r e v i o u s   W e b   s t r u c t u r a l   s t u d i e s   r e v e a l e d   t h e   e x i s t e n c e   o f   W e b   c o m m u n i t i e s   [ 7 ] ,   [ 1 1 ] ,   [ 1 2 ] .   R e s e a r c h e r s   f o u n d   t h r e e   s t r u c t u r a l   p r o p e r t i e s   o f   W e b   c o m m u n i t i e s   t h a t   m a d e   l o c a l   s e a r c h i n g   a l g o r i t h m s   w e r e   n o t   s u i t a b l e   f o r   f o c u s e d   c r a w l i n g .   F i r s t ,   i n s t e a d   o f   d i r e c t l y   l i n k e d   t o   e a c h   o t h e r ,   m a n y   p a g e s   c o n n e c t e d   t o   e a c h   o t h e r   t h r o u g h   c o - c i t a t i o n   r e l a t i o n s h i p s   [ 1 1 ] ,   [ 1 3 ] .   T h o s e   W e b   p a g e s   c o u l d   b e   m i s s e d   b y   f o c u s e d   c r a w l e r s ,   a s   i l l u s t r a t e d   i n   F i g u r e   1 a .   S e c o n d ,   r e l e v a n t   p a g e s   w i t h i n   t h e   s a m e   d o m a i n   c o u l d   b e   s e p a r a t e d   i n t o   d i f f e r e n t   W e b   c o m m u n i t i e s   b y   u s i n g   i r r e l e v a n t   p a g e s   [ 1 4 ] ,   a s   d e s c r i b e d   i n   F i g u r e   1 b .   T h i r d ,   s o m e t i m e s   l i n k s   c o u l d   b e   l a i d   b e t w e e n   t w o   p a g e s   o f   d i f f e r e n t   c o m p a t i b l e   W e b   c o m m u n i t i e s ,   b u t   t h e s e   l i n k s   u s u a l l y   o n l y   p o i n t e d   f r o m   o n e   c o m m u n i t y   t o   t h e   o t h e r   w i t h   n o n e   o f   t h e m   p o i n t i n g   b a c k   i n   r e v e r s e   d i r e c t i o n   [ 1 3 ] .   T h i s   i s   s h o w n   i n   F i g u r e   1 b .           =   S t a r t i n g   U R L       =   H y p e r l i n k s     =   R e l e v a n t   p a g e s       =   H y p e r l i n k s   t h a t   c r a w l e r s   c a n   f o l l o w     =   I r r e l e v a n t   p a g e s       =   H y p e r l i n k s   t h a t   c r a w l e r s   c a n n o t   f o l l o w     F i g u r e   1 .   P r o b l e m s   c a u s e d   b y   l o c a l   s e a r c h i n g   a l g o r i t h m s :   ( a )   C r a w l e r   c o u l d   m i s s   p a g e s   w h i c h   c o n n e c t e d   t o   e a c h   o t h e r   t h r o u g h   c o - c i t a t i o n   r e l a t i o n s h i p .   ( b )   C r a w l e r   w a s   t r a p p e d   w i t h i n   t h e   i n i t i a l   c o m m u n i t y .       T o   a l l e v i a t e   t h e   p r o b l e m s   o f   l o c a l   s e a r c h i n g   a l g o r i t h m s ,   r e s e a r c h e r s   h a v e   s u g g e s t e d   s e v e r a l   s t r a t e g i e s .   O n e   o f   t h e m   i s   b y   u s i n g   m o r e   s t a r t i n g   U R L s .   H o w e v e r ,   c o m p o s i n g   a   l i s t   o f   h i g h - q u a l i t y   s t a r t i n g   U R L s   i s   a n   e x p e n s i v e   a n d   t i m e - c o n s u m i n g   t a s k .   B e r g m a r k   [ 1 4 ]   p r o p o s e d   t o   u s e   t u n n e l i n g   m e t h o d   t o   a d d r e s s   t h e   p r o b l e m s .   E v e n   t h o u g h   i t   c a n   f i n d   m o r e   s u i t a b l e   p a g e s   t h a n   t h o s e   w i t h o u t   t u n n e l i n g ,   i t   d o e s   n o t   c h a n g e   t h e   l o c a l   s e a r c h i n g   n a t u r e   o f   f o c u s e d   c r a w l i n g .   O v e r l a p p i n g   b e t w e e n   s e a r c h i n g   i n d i c e s   o f   m a j o r   s e a r c h   e n g i n e   i s   n o t   s i g n i f i c a n t .   F u r t h e r m o r e ,   a c c o r d i n g   t o   L a w r e n c e   a n d   G i l e s   [ 1 5 ] ,   t h e   c o m b i n e d   t o p   r e s u l t s   f r o m   m u l t i p l e   s e a r c h   e n g i n e s   h a d   h i g h   c o v e r a g e   o v e r   t h e   W e b .   A s   a   p o t e n t i a l   s o l u t i o n ,   t h e   m e t a - s e a r c h i n g   t h r o u g h   m u l t i p l e   s e a r c h   e n g i n e s   i s   i n t e g r a t e d   i n t o   c r a w l i n g   p r o c e s s .   Evaluation Warning : The document was created with Spire.PDF for Python.
T E L K O M N I K A     I S S N :   1 6 9 3 - 6 9 3 0               F o c u s e d   C r a w l e r   O p t i m i z a t i o n   U s i n g   G e n e t i c   A l g o r i t h m   ( B a n u   W i r a w a n   Y o h a n e s )   4 0 5   G A   i s   g o i n g   t o   a c r o s s   s o m e   v a s t   s e a r c h   s p a c e s   e f f i c i e n t l y   a n d   i t   c a n   d i s c o v e r   t h e   a p p r o x i m a t e   g l o b a l   o p t i m a l   s o l u t i o n s   i n s t e a d   o f   t h e   l o c a l   o n e s .   C h e n   e t   a l .   [ 1 0 ]   d i d   a n   e x p e r i m e n t   u s i n g   G A   t o   b u i l d   a   p e r s o n a l   s e a r c h   a g e n t .   T h e i r   r e s u l t s   s h o w e d   t h a t   G A   c o u l d   e f f e c t i v e l y   p r e v e n t   t h e   s e a r c h   a g e n t   f r o m   b e i n g   t r a p p e d   i n   l o c a l   o p t i m a l ,   a n d   t h e n   i t   w o u l d   s i g n i f i c a n t l y   i m p r o v e   t h e   q u a l i t y   o f   s e a r c h   r e s u l t s .   B e c a u s e   o f   c l o s e   r e s e m b l a n c e   f e a t u r e s   b e t w e e n   a   p e r s o n a l   s e a r c h   a g e n t   a n d   a   f o c u s e d   c r a w l e r ,   G A   i s   p r o p o s e d   t o   o p t i m i z e   W e b   s e a r c h i n g   i n   f o c u s e d   c r a w l e r .       2 .     P r o p o s e d   G e n e t i c   A l g o r i t h m   I n   t h i s   p a p e r ,   G A   i s   u s e d   t o   i m p r o v e   t h e   q u a l i t y   o f   s e a r c h i n g   r e s u l t s   i n   f o c u s e d   c r a w l i n g .   G A   i s   a n   a d a p t i v e   a n d   h e u r i s t i c   m e t h o d   f o r   s o l v i n g   o p t i m i z a t i o n   a n d   s e a r c h i n g   f o r   p r o b l e m s .   G A   e x p l o i t s   s e v e r a l   t e c h n i q u e s   i n s p i r e d   b y   b i o l o g i c a l   e v o l u t i o n   s u c h   a s   i n h e r i t a n c e ,   s e l e c t i o n ,   c r o s s - o v e r ,   a n d   m u t a t i o n .   G A   i s   a   m e m b e r   o f   e v o l u t i o n a r y   a l g o r i t h m s   w h i c h   i s   i n c l u d e d   t o   t h e   r a p i d l y   g r o w i n g   a r e a   o f   A r t i f i c i a l   I n t e l l i g e n c e .   B e c a u s e   i t   i s   h a r d   t o   r e p r e s e n t   W e b   p a g e s   i n   b i t   s t r i n g s   a n d   o t h e r   c o n v e n t i o n a l   g e n e t i c   o p e r a t o r s   c a n n o t   d i r e c t l y   b e   a p p l i e d   i n   t h e   W e b   c o n t e x t ,   a   f o c u s e d   c r a w l e r   i s   d e s i g n e d   b a s e d   o n   t h e   p r e v i o u s   s t u d y   b y   C h e n   e t   a l .   [ 1 0 ] .   T h e   f l o w c h a r t   o f   t h e   G A - c r a w l e r   i s   s h o w n   i n   F i g u r e   2 .   A l t h o u g h   G A - c r a w l e r   d o e s   n o t   a d d   n e w   t e r m s   l i k e   t h e   G c r a w l e r   [ 1 6 ]   a n d   t h e   M u l t i C r a w l e r   A g e n t   ( M C A )   [ 1 7 ]   d o ,   i t   i s   e x p e c t e d   t o   m a i n t a i n   a   g o o d   t r a c k i n g   t h r o u g h o u t   W e b   l i n k s .   I n   d i f f e r e n t   f i e l d ,   a   m u l t i - o b j e c t i v e   G A   f o r   g e n e r a t o r   c o n t r i b u t i o n   b a s e d   c o n g e s t i o n   m a n a g e m e n t   w a s   p r o p o s e d   b y   S e n   e t   a l .   [ 1 8 ] .   T h e   a l g o r i t h m   o p t i m i z e s   b o t h   r e a l   a n d   r e a c t i v e   l o s s e s   u s i n g   o p t i m a l   p o w e r   f l o w   m o d e l .   I n   t h e   m a n y   a p p l i c a t i o n s   G A   h a v e   s u c c e s s f u l l y   i m p l e m e n t e d   [ 1 9 - 2 0 ] .   T h e   G A s   a r e   o f t e n   m o d i f i e d   t o   s o l v e   s o m e   s p e c i f i c   p r o b l e m s .     S t e p   1 .   I n i t i a l i z a t i o n   T h e   f i r s t   p h a s e   i s   t o   s e t   u p   s e v e r a l   p a r a m e t e r s   o f   G A   s u c h   a s   p o p u l a t i o n   s i z e ,   g e n e r a t i o n   s i z e ,   c r o s s - o v e r   r a t e   o r   p r o b a b i l i t y   o f   c r o s s - o v e r ,   a n d   m u t a t i o n   r a t e   o r   p r o b a b i l i t y   o f   m u t a t i o n .   S t a r t i n g   U R L s   a n d   W e b   p a g e s   a s   t h e   l e x i c o n   a l s o   b e c o m e s   a n   i n p u t   f o r   t h e   c r a w l e r .   A f t e r   a l l   i n i t i a l   p a r a m e t e r s   a r e   d e t e r m i n e d   W e b   p a g e s   w h i c h   a r e   p o i n t e d   b y   t h e   s t a r t i n g   U R L s   a r e   f e t c h e d   b a c k   b y   t h e   c r a w l e r   a n d   s a v e d   i n   a   s e t   c a l l e d   g e n e r a t i o n .     S t e p   2 .   S e l e c t i o n   b a s e d   o n   c o n t e n t - b a s e d   W e b   a n a l y s i s   J a c c a r d s   s i m i l a r i t y   f u n c t i o n   u s e d   a s   t h e   f i t n e s s   f u n c t i o n   o f   t h e   G A - c r a w l e r   i s   u t i l i z e d   t o   c a l c u l a t e   f i t n e s s   v a l u e   o f   a   W e b   p a g e ,   w h i c h   r e p r e s e n t s   s i m i l a r i t y   b e t w e e n   a   p a g e   a n d   t h e   l e x i c o n   o n   s p e c i f i c   d o m a i n .   T h e   h i g h e r   t h e   f i t n e s s   v a l u e   t h e   m o r e   s i m i l a r   a   p a g e   t o   d o m a i n   l e x i c o n .   C o n s e c u t i v e l y ,   i t   b e c o m e s   m o r e   c o m p a t i b l e   t o   t h e   t a r g e t   d o m a i n .   T h e   J a c c a r d s   s c o r e   b a s e d   o n   b o t h   l i n k s   a n d   k e y w o r d s   a n a l y s i s   i s   c o m b i n e d .   J a c c a r d s   f u n c t i o n   b a s e d   o n   l i n k s   i s   a   r a t i o   o f   t h e   n u m b e r   o f   i n t e r s e c t i o n   l i n k s   a n d   u n i o n   l i n k s   b e t w e e n   t w o   W e b   p a g e s .   T h e   m o r e   n u m b e r   o f   c o m m o n   l i n k s   t h a t   b o t h   W e b   p a g e s   h a v e ,   t h e   h i g h e r   J a c c a r d s   s c o r e   o f   a   W e b   p a g e   c o m p a r e d   t o   t h e   d o m a i n   l e x i c o n   w i l l   b e .     , =   # ( ) # ( )                                                                                                                                                                                                                                             ( 1 )       r e p r e s e n t s   a   d o m a i n   l e x i c o n   a n d     r e p r e s e n t s   e v e r y   W e b   p a g e   t h a t   h a s   b e e n   v i s i t e d   b y   c r a w l e r .     i s   a   s e t   o f   l i n k s   w i t h i n   p a g e     a n d     i s   a   s e t   o f   l i n k s   w i t h i n   p a g e   .   # ( )   d e n o t e s   c a r d i n a l i t y   o f   s e t     a n d   ,   r e p r e s e n t s   J a c c a r d s   s c o r e   b a s e d   o n   l i n k s   o f   a   W e b   p a g e   c o m p a r e d   t o   t h e   d o m a i n   l e x i c o n .   J a c c a r d s   f u n c t i o n   b a s e d   o n   k e y w o r d s   i s   c a l c u l a t e d   u s i n g   T e r m   f r e q u e n c y - I n v e r s e   d o c u m e n t   f r e q u e n c y   m e t h o d   ( T f - I d f ) .   T h e   w e i g h t e d   t e r m   o f   k e y w o r d s     i n   a   W e b   p a g e   ,   c a l l e d       i s   e v a l u a t e d   a s   f o l l o w s :     =   ×  ×                                                                                                                                                                                                                           ( 2 )       Evaluation Warning : The document was created with Spire.PDF for Python.
                                        I S S N :   1 6 9 3 - 6 9 3 0   T E L K O M N I K A     V o l .   9 ,   N o .   3 ,     D e c e m b e r   2 0 1 1   :     4 0 3     4 1 0   4 0 6       F i g u r e   2 .   F l o w c h a r t   o f   t h e   g e n e t i c   a l g o r i t h m   c r a w l e r       W h e r e     i s   t h e   n u m b e r   o f   k e y w o r d s   a p p e a r a n c e ,   ,   i n   a   W e b   p a g e   .     i s   t h e   n u m b e r   o f   W e b   p a g e s   i n   a   c o l l e c t i o n   ,   w h e r e   k e y w o r d s     i s   f o u n d .     i s   a   n u m b e r   o f   w o r d s   f r o m   k e y w o r d s     .     i s   a   n u m b e r   o f   W e b   p a g e s   t h a t   h a v e   b e e n   v i s i t e d   b y   t h e   c r a w l e r .   A   s i m i l a r   T f - I d f   m e t h o d   h a d   b e e n   u s e d   b y   G h o z i a   e t   a l .   [ 2 1 ]   t o   e s t i m a t e   t h e   t e x t u a l   s i m i l a r i t y   o f   W e b   p a g e s .   Evaluation Warning : The document was created with Spire.PDF for Python.
T E L K O M N I K A     I S S N :   1 6 9 3 - 6 9 3 0               F o c u s e d   C r a w l e r   O p t i m i z a t i o n   U s i n g   G e n e t i c   A l g o r i t h m   ( B a n u   W i r a w a n   Y o h a n e s )   4 0 7   T h e   J a c c a r d s   s c o r e   b a s e d   o n   k e y w o r d s   f o r   e a c h   W e b   p a g e   c o m p a r e d   t o   t h e   d o m a i n   l e x i c o n   i s   c a l c u l a t e d   a s   f o l l o w s :     , =   ( ×  ) +    ( ×  )                                                                                                                                                           ( 3 )     T h e   m o r e   o f t e n   k e y w o r d s   a p p e a r   i n   a   d o c u m e n t   a n d   t h e   r a r e r   d o c u m e n t s   c o n t a i n   t h e   k e y w o r d s .   T h e r e f o r e ,   t h e   J a c c a r d s   s c o r e   o f   a   W e b   p a g e   b a s e d   o n   k e y w o r d s   w i l l   b e   b e t t e r .   F i n a l l y ,   J a c c a r d s   s c o r e ,   , ,   f o r   e a c h   p a g e   t h a t   h a s   b e e n   v i s i t e d   b y   t h e   c r a w l e r   i s   a n   a v e r a g e   b e t w e e n   ,   a n d   , .   I t   i s   p r e s e n t e d   a s   f o l l o w s :     , = 0 . 5   × , + 0 . 5   × ,                                                                                                                     ( 4 )     A f t e r   t h e   f i t n e s s   v a l u e s   d e n o t e d   b y   J a c c a r d s   s c o r e s   i n   t h e   c u r r e n t   g e n e r a t i o n   a r e   c a l c u l a t e d ,   p a g e s   w i t h   b e t t e r   f i t n e s s   v a l u e s   a r e   s t o c h a s t i c a l l y   s e l e c t e d   b y   a   r a n d o m   n u m b e r   g e n e r a t o r .   A   h i g h e r   f i t n e s s   v a l u e   w i l l   g i v e   a   p a g e   m o r e   l i k e l i h o o d   t o   s u r v i v e   i n   t h i s   s e l e c t i o n   p h a s e .   T h e   s u r v i v e d   p a g e s   a r e   s t o r e d   l o c a l l y   a n d   t h e   r e s t   o f   p a g e s   a r e   d i s c a r d e d   a s   t h e y   a r e   i r r e l e v a n t .   T h e   s u r v i v e d   p a g e s   a r e   e l i g i b l e   t o   f o r m   a   n e w   p o p u l a t i o n   f o r   t h e   n e x t   g e n e r a t i o n .   A f t e r w a r d s ,   t h e   c r a w l e r   c h e c k s   w h e t h e r   t h e   s e a r c h   h a s   r e a c h e d   a   c o n v e r g i n g   p o i n t   o r   n o t .   I f   i t   h a s ,   t h e n   t h e   c r a w l e r   w i l l   s t o p   s e a r c h i n g .   O n   t h e   o t h e r   h a n d ,   t h e   c r a w l e r   w i l l   c o n t i n u e   t o   e x a m i n e   t h e   W e b   u n t i l   i t   r e a c h e s   a n y   c o n v e r g e n t   p o i n t ,   w h i c h   h a s   b e e n   s p e c i f i e d   a t   t h e   b e g i n n i n g   o f   t h e   c r a w l i n g   p r o c e s s .   T h e   c r i t e r i a   o f   a   c o n v e r g e d   p o i n t   a r e   t h e   n u m b e r   o f   p a g e s   i n   l o c a l   r e p o s i t o r y ,   w h i c h   h a s   r e a c h e d   a   p r e - s e t   l i m i t   o r   t h e   i m p r o v e m e n t   o f   f i t n e s s   v a l u e s   o f   a l l   p a g e s   i n   a   g e n e r a t i o n   b e l o w   a   t h r e s h o l d   v a l u e   o r   t h e   i t e r a t i o n   t h r o u g h   g e n e r a t i o n   h a s   r e a c h e d   a   p r e - s e t   c o u n t e r .     S t e p   3 .   C r o s s - o v e r   b a s e d   o n   l i n k - b a s e d   W e b   a n a l y s i s   A l l   o u t b o u n d - l i n k s   ( o u t - g o i n g   U R L s )   i n   t h e   s u r v i v e d   p a g e s   a r e   e x t r a c t e d ,   a n d   t h e n   a   c r o s s - o v e r   o p e r a t i o n   i s   p e r f o r m e d   t o   s e l e c t   t h e   m o s t   p r o m i s i n g   U R L s .   F o r   e a c h   o u t b o u n d - l i n k ,   ,   t h e   c r o s s - o v e r   s c o r e   i s   c a l c u l a t e d   a s   f o l l o w s ;       =      ( ! )                                                                                                                                                                                             ( 5 )     "   i s   e v e r y   p a g e   !   w h i c h   c o n t a i n s   U R L   .     T h e   U R L s   a r e   s o r t e d   a c c o r d i n g   t o   t h e i r   c r o s s - o v e r   s c o r e s   a n d   p u t   i n t o   t h e   c r a w l i n g   q u e u e .   S i m i l a r   t o   t h e   P a g e   R a n k   [ 6 ] ,   t h e   c r o s s - o v e r   o p e r a t i o n   f a v o r s   U R L s   t h a t   h a v e   b e e n   c i t e d   b y   m o r e   h i g h - q u a l i t y   p a g e s   w i t h   m u c h   l e s s   c o m p u t a t i o n a l l y   c o s t .   I n   g e n e r a l ,   c r o s s - o v e r   o p e r a t o r   s u p p o r t s   e x p l o i t a t i o n   o f   p r o m i s i n g   l o c a l   l i n k s   a n d   i t   i s   s i m i l a r   t o   t h e   b e s t - f i r s t   s e a r c h   p r o c e s s .     S t e p   4 .   M u t a t i o n   b a s e d   o n   m e t a - s e a r c h   I t   i s   a i m e d   a t   g i v i n g   t h e   c r a w l e r   a b i l i t y   t o   e x p l o r e   m u l t i p l e   s u i t a b l e   W e b   c o m m u n i t i e s   c o m p r e h e n s i v e l y .   R a n d o m   k e y w o r d s   a r e   e x t r a c t e d   f r o m   t h e   l e x i c o n ,   w h i c h   d e s c r i b e s   s t a r t i n g   U R L s .   T h e   s e l e c t e d   k e y w o r d s   r u n   a s   q u e r y   f o r   t h r e e   w e l l - k n o w n   s e a r c h   e n g i n e s ,   G o o g l e   o n l i n e   a t   h t t p : / / w w w . g o o g l e . c o m ,   M S N   o n l i n e   a t   h t t p : / / w w w . b i n g . c o m ,   a n d   Y a h o o   o n l i n e   a t   h t t p : / / s e a r c h . y a h o o . c o m .   G A - c r a w l e r   d i d   n o t   e x p a n d   i n i t i a l   k e y w o r d s   [ 1 6 - 1 7 ] ,   b u t   i t   c o u l d   o n l y   c h a n g e   t h e   k e y w o r d s   c o m p o s i t i o n   b a s e d   o n   t h e   p r o b a b i l i t y   o f   m u t a t i o n .   T h e   c r a w l e r   i s   p r e v e n t e d   t o   e x p l o r e   b r o a d e r   s e a r c h   s p a c e s   f o r   i m p r o v i n g   t h e   c r a w l i n g   r a t e .   T o p   r e s u l t s   f r o m   t h o s e   s e a r c h   e n g i n e s   a r e   c o m b i n e d   t o   b u i l d   a   c r a w l e r s   q u e u e   a l o n g s i d e   w i t h   U R L s   f r o m   c r o s s - o v e r   p h a s e .   G i v e n   a   f a c t   t h a t   s e a r c h   i n d e x e s   o f   d i f f e r e n t   m a j o r   s e a r c h   e n g i n e s   h a v e   l i t t l e   o v e r l a p   a n d   t h e i r   c o m b i n a t i o n   c o v e r s   a   v e r y   l a r g e   p o r t i o n   o f   t h e   W e b ,   i t   i s   l i k e l y   t h a t   m u t a t i o n   o p e r a t o r   a d d s   d i v e r s e   U R L s   f r o m   m a n y   d i f f e r e n t   a n d   r e l e v a n t   W e b   c o m m u n i t i e s .   F u r t h e r m o r e ,   a s   m a j o r   s e a r c h   e n g i n e s   o f t e n   i n c l u d e   h i g h l y   c o - c i t e d   U R L s   i n   t h e i r   s e a r c h   r e s u l t s ,   m u t a t i o n   p h a s e   c a n   m a k e   t h e   e x p l o r a t i o n   o f   i n d i v i d u a l   r e l e v a n t   c o m m u n i t i e s   m o r e   e x t e n s i v e   b y   a d d i n g   t h o s e   c o - c i t e d   U R L s   i n t o   t h e   c o l l e c t i o n .   Evaluation Warning : The document was created with Spire.PDF for Python.
                                        I S S N :   1 6 9 3 - 6 9 3 0   T E L K O M N I K A     V o l .   9 ,   N o .   3 ,     D e c e m b e r   2 0 1 1   :     4 0 3     4 1 0   4 0 8 C o m p a r e d   t o   p r e v i o u s l y   s u g g e s t e d   a p p r o a c h   a s   u s i n g   m o r e   s t a r t i n g   U R L s ,   t h e   p r o p o s e d   G A   a p p r o a c h   h a s   n u m e r o u s   a d v a n t a g e s .   F o r   i n s t a n c e ,   a   l i s t   o f   d o m a i n - s p e c i f i c   q u e r i e s   i s   r e q u i r e d ,   t h a t   i s   m u c h   e a s i e r   t o   c o m p o s e   t h a n   a   l i s t   o f   h i g h - q u a l i t y   s t a r t i n g   U R L s .   M o r e o v e r ,   t h e   l i s t   o f   q u e r i e s   c a n   b e   u p d a t e d   b y   a d d i n g   f r e q u e n t l y   u s e d   q u e r i e s   f o u n d   i n   s e a r c h   e n g i n e s   s e a r c h   l o g .   T h i s   w i l l   n o t   o n l y   m a k e   t h e   c o l l e c t i o n   b u i l d i n g   p r o c e s s   e a s i e r ,   b u t   a l s o   a l l o w   t h e   f i n a l   c o l l e c t i o n   t o   a d d r e s s   u s e r s   i n f o r m a t i o n   n e e d s   m o r e   e f f e c t i v e l y .   T h e   p r o p o s e d   a p p r o a c h   a l s o   s h o w s   a d v a n t a g e s   o v e r   t u n n e l i n g   m e t h o d .   A s   a   g l o b a l   s e a r c h i n g   a l g o r i t h m ,   G A   a l l o w s   c r a w l e r   t o   f i n d   n e w   c o m p a t i b l e   W e b   c o m m u n i t i e s   w i t h o u t   a n y   d i s t a n c e   l i m i t   a n d   i t   d o e s   n o t   i n t r o d u c e   n o i s e   i n t o   t h e   p a g e s   c o l l e c t i o n s .       3 .     R e s e a r c h   M e t h o d   T h e   r e s e a r c h   i s   s p e c i a l i z e d   t o   i n v e s t i g a t e   h o w   d i f f e r e n t   c r a w l i n g   a l g o r i t h m s   a n d   h e u r i s t i c s   c a n   b e   a p p l i e d   s o   t h a t   c r a w l e r   c a n   r e t r i e v e   s u i t a b l e   i n f o r m a t i o n   f r o m   t h e   W e b   m o r e   e f f e c t i v e l y .   I n   o r d e r   t o   r e a c h   t h e   o b j e c t i v e ,   a n   a p p l i c a t i o n   c a l l e d   G A - c r a w l e r   w a s   w r i t t e n   i n   C #   u s i n g   M S   V S   C #   8 . 0   c o m p i l e r ,   t o   s e a r c h   a n d   c o l l e c t   W e b   p a g e s   f r o m   t h e   I n t e r n e t .   H e n c e ,   t h e   s o f t w a r e   m u s t   b e   c o n n e c t e d   t o   t h e   I n t e r n e t   t h r o u g h   a n y   I n t e r n e t   S e r v i c e   P r o v i d e r   ( I S P ) .   G A - C r a w l e r   a u t o m a t i c a l l y   s e a r c h e s   f o r   W e b   p a g e s   w i t h   r e l a t i v e l y   h i g h   J a c c a r d s   s c o r e s   w h i c h   m e a n s   m o r e   s i m i l a r   t o   t h e   l e x i c o n .   W e b   p a g e s   t h a t   h a d   b e e n   v i s i t e d   d u r i n g   e x p l o r a t i o n   o f   t h e   W e b   w i l l   b u i l d   a   p o p u l a t i o n   f o r   G A s   s e l e c t i o n .   T h e y   a r e   k e p t   i n   a   q u e u e   c a l l e d   f r o n t i e r s .   L a t e r   W e b   p a g e s   w h i c h   h a d   b e e n   c h o s e n   o n   r o u l e t t e - w h e e l   s e l e c t i o n   w o u l d   b e   d o w n l o a d e d   t o   l o c a l   r e p o s i t o r y   a n d   s a v e d   i n   d a t a b a s e .   F i n a l l y   t h e   G A - c r a w l e r   w o u l d   g e n e r a t e   a n   H T M L   r e p o r t i n g   p a g e   w h e n   i t   h a s   f i n i s h e d   c r a w l i n g   t h e   W e b .   I n t e r e s t i n g   f e a t u r e   t h a t   h a s   b e e n   a d d e d   t o   t h e   c r a w l e r   i s   t h a t   i t   w o u l d   b e   a b l e   t o   d o w n l o a d   s i n g l e   d i s t i n c t   W e b   p a g e s   r e s o u r c e s   s u c h   a s   i m a g e s ,   s c r i p t s ,   a n d   c a s c a d i n g   s t y l e   s h e e t s   ( C S S s )   f o r   e a c h   d o m a i n .   G A - C r a w l e r   d i f f e r e n t i a t e s   r e s o u r c e s   u s i n g   i t s   t y p e   a n d   n a m e .   I t   w i l l   d e l i v e r   a   f a i r l y   l a r g e   l o c a l   r e s o u r c e s   s a v i n g .   T o   e v a l u a t e   t h e   e f f e c t i v e n e s s   o f   t h e   p r o p o s e d   c o l l e c t i o n   b u i l d i n g   m e t h o d ,   s o m e   b e n c h m a r k i n g   e x p e r i m e n t s   w e r e   c o n d u c t e d .   A   c o n v e n t i o n a l   b e s t - f i r s t   s e a r c h   ( B F S )   c r a w l e r   c o u l d   b e   m a d e   b y   d i s a b l i n g   t h e   m u t a t i o n   p h a s e   i n   t h e   G A - c r a w l e r .   T w o   s m a l l   c o l l e c t i o n s   c o n s i s t   o f   a b o u t   3 , 3 0 0   W e b   p a g e s   i n   e a c h   c o l l e c t i o n   w e r e   b u i l t   b y   t w o   c r a w l e r s   u s i n g   i d e n t i c a l   s e t t i n g s .   L a t e r   t h e   p e r f o r m a n c e   o f   t h o s e   c r a w l e r s   w e r e   c o m p a r e d   e a c h   o t h e r .       4 .     R e s u l t s   a n d   A n a l y s i s   T h e   n u m b e r s   o f   c o l l e c t i o n s   i n   d i f f e r e n t   c a t e g o r i e s   w e r e   c o m p a r e d .   T h e   c o l l e c t i o n s   b u i l t   f r o m   t h e   t r a d i t i o n a l   f o c u s e d   c r a w l e r   c o n t a i n e d   a b o u t   3 , 0 0 0   n o d e s   ( W e b   p a g e ) .   T h e y   w e r e   d i v i d e d   i n t o   f i v e   d i f f e r e n t   c a t e g o r i e s .   W h i l e   t h e   c o l l e c t i o n s   b u i l t   f r o m   G A - c r a w l e r   c o n t a i n e d   a b o u t   3 , 3 0 0   n o d e s   w e r e   a l s o   d i v i d e d   i n t o   f i v e   d i f f e r e n t   c a t e g o r i e s .   T h o s e   a d d i t i o n a l   W e b   p a g e s   h a d   b e e n   d e r i v e d   b y   m u t a t i o n   p h a s e   i n   G A .   T h e   G A - c r a w l e r   w a s   e x p e c t e d   t o   v i s i t   m o r e   c o m p a t i b l e   W e b   c o m m u n i t i e s   t h a n   t h e   b e s t - f i r s t   s e a r c h   c r a w l e r   a n d   t r a d i t i o n a l   f o c u s e d   c r a w l e r .   S o m e   i n d i c a t o r s   o f   t h e   c r a w l e r s   p e r f o r m a n c e   a r e   W e b   s e a r c h i n g   p r e c i s i o n   o r   t h e   W e b   p a g e s   r e l e v a n c e   w h i c h   i s   c o l l e c t e d   b y   t h e   c r a w l e r s ,   W e b   c r a w l i n g s   s c o p e ,   s p e e d   a n d   r o b u s t n e s s ,   a n d   a l s o   t h e   t o t a l   n u m b e r   o f   r e s o u r c e s   u s e d   i n   c r a w l i n g   t h e   W e b .   S e v e r a l   e x p e r i m e n t s   w e r e   c o n d u c t e d   u s i n g   d i f f e r e n t   s t a r t i n g   U R L   a n d   k e y w o r d s   f o r   e a c h   c a t e g o r y .   T h e y   w e r e   t a k e n   p l a c e   o n   a n   I n t e l   D u a l   C o r e   C P U   T 4 2 0 0   r u n n i n g   a t   2 . 0   G H z ,   1   G B   R A M   a n d   a n   e n h a n c e d   3 G   n e t w o r k   o r   3 . 5 G   n e t w o r k   c a l l e d   H i g h   S p e e d   D o w n l o a d   P a c k e t   A c c e s s   ( H S D P A )   w h i c h   s u p p o r t s   d o w n - l i n k   s p e e d s   u p   t o   3 . 6   M b p s   f o r   t h e   I n t e r n e t   c o n n e c t i o n .   T h e   f i r s t   1 0 0   W e b   p a g e s   w i t h i n   e a c h   c a t e g o r y   a r e   e x a m i n e d   t o   c a l c u l a t e   t h e   p r e c i s i o n   o f   t h e   c r a w l i n g   p r o c e s s .   T h e   c r a w l e r s   p r e c i s i o n   w a s   m e a s u r e d   b y   c h e c k i n g   t h e   W e b   p a g e s   r e l e v a n c e   c o m p a r e d   t o   t h e   s t a r t i n g   U R L   a n d   c a t e g o r y   o r   k e y w o r d   w h i c h   w a s   p r e s e n t e d .   T a b l e   1   d e p i c t s   t h e   p r e c i s i o n   o f   W e b   c r a w l i n g   b e t w e e n   t h o s e   t w o   c r a w l e r s   i n   f i v e   d i f f e r e n t   c a t e g o r i e s   u s i n g   s o m e   k e y w o r d s .   A l t h o u g h   t h e   G A - c r a w l e r   c o u l d   a c h i e v e   h i g h e r   p r e c i s i o n   o f   W e b   c r a w l i n g   t h a n   t h e   B F S   o n e ,   i t   m u s t   b e   r e c k o n e d   t h a t   G A - c r a w l e r s   f i l t e r i n g   r a t e   t o   s e l e c t   W e b   p a g e s   i s   q u i t e   b i g ,   a t   a b o u t   6 3 % .   I n   o t h e r   w o r d s ,   G A - c r a w l e r   r e t r i e v e d   o n l y   6 3   W e b   p a g e s   f o r   e v e r y   1 0 0   l i n k s   i t   f o u n d e d .   I t   c o u l d   h a v e   m i s s e d   s o m e   s u i t a b l e   W e b   p a g e s   o n   t h e   r o a d .   E v e n   t h e   s i z e   o f   t h e   c o l l e c t i o n s   w a s   o n l y   a b o u t   3 , 3 0 0   W e b   p a g e s .   I t   w a s   t o o   s m a l l   t o   m a k e   d e c e n t   a n a l y s i s   a n d   c o n c l u s i o n .   Evaluation Warning : The document was created with Spire.PDF for Python.
T E L K O M N I K A     I S S N :   1 6 9 3 - 6 9 3 0               F o c u s e d   C r a w l e r   O p t i m i z a t i o n   U s i n g   G e n e t i c   A l g o r i t h m   ( B a n u   W i r a w a n   Y o h a n e s )   4 0 9   T a b l e   1 .   T h e   p r e c i s i o n   o f   t h e   W e b   c r a w l e r s   C a t e g o r y   B F S   c r a w l e r s   p r e c i s i o n   G A - c r a w l e r s   p r e c i s i o n   E d u c a t i o n   9 0 %   9 7 %   C o m p u t e r   8 5 %   9 7 %   D i g i t a l   8 0 %   8 2 %   A n a l o g   6 3 %   9 3 %   S p o r t   9 0 %   9 5 %       T h e   s p e e d   o f   t h e   t w o   c r a w l e r s   t o   p r o c e s s   a   W e b   p a g e   w a s   a l s o   e v a l u a t e d .   G A - c r a w l e r s   a v e r a g e   c r a w l i n g   r a t e   a t   1 9 - 1 0 3   s e c o n d s   p e r   p a g e   w a s   l e s s   t h a n   t h e   B F S   c r a w l e r   a t   1 0 - 4 0   s e c o n d s   o n   t h e   s a m e   I n t e r n e t   c o n n e c t i o n .   I t   w a s   b e c a u s e   G A - c r a w l e r   n e e d s   m o r e   t i m e   t o   a c c o m p l i s h   t h e   s e l e c t i o n ,   c r o s s - o v e r ,   a n d   m u t a t i o n   m e t h o d s   i n   o r d e r   t o   l o o k   f o r   b e t t e r   l i n k s .   D u e   t o   l a c k   o f   s t a t i s t i c a l   a n a l y s i s   a n d   t h e   s m a l l   s i z e   o f   t h e   c o l l e c t i o n s ,   t h e   h y p o t h e s i s   w a s   n o t   f u l l y   s u p p o r t e d   b y   t h e   e x p e r i m e n t s   r e s u l t s .   G A - c r a w l e r   r e l a t i v e l y   h a s   a   b e t t e r   c h a n c e   t o   v i s i t   m o r e   s u i t a b l e   W e b   c o m m u n i t i e s   t h a n   t h e   B F S   c r a w l e r   a n d   t r a d i t i o n a l   f o c u s e d   c r a w l e r .   I n   g e n e r a l ,   t h e   r e s e a r c h   o b t a i n e d   s o m e   p r o m i s i n g   r e s u l t s   f r o m   t h e   b e n c h m a r k   s t u d y .       5 .     C o n c l u s i o n   I t   i s   i m p o r t a n t   t o   b u i l d   h i g h - q u a l i t y   d o m a i n   s p e c i f i c   s e a r c h   e n g i n e s ,   a s   t h e   s i z e   o f   t h e   W e b   k e e p s   g r o w i n g .   T h i s   r e s e a r c h   h a d   p r o p o s e d   a   c r a w l i n g   t e c h n i q u e   t o   f o r m   d o m a i n - s p e c i f i c   c o l l e c t i o n s ,   w h i c h   s e r v e   s e a r c h   e n g i n e s   t h a t   i n c o r p o r a t e   G A   a s   a   g l o b a l   s e a r c h i n g   a l g o r i t h m   i n t o   t h e   c r a w l i n g   p r o c e s s .   W i t h   t h e   e f f e c t i v e   c o m b i n a t i o n   o f   c o n t e n t - b a s e d   a n d   l i n k - b a s e d   W e b   a n a l y s i s ,   t o g e t h e r   w i t h   t h e   a b i l i t y   t o   p e r f o r m   g l o b a l   s e a r c h i n g ,   t h e   p r o p o s e d   t e c h n i q u e   h a s   a   c o n s i d e r a b l e   p o t e n t i a l   t o   a d d r e s s   m a n y   p r o b l e m s   t h a t   h a d   p l a g u e d   p r e v i o u s   f o c u s e d   c r a w l i n g   m e t h o d s .   T h e   r e s u l t   s h o w e d   t h a t   t h e   G A - c r a w l e r   c o u l d   t r a v e r s e   t h e   W e b   s e a r c h   s p a c e   m o r e   c o m p r e h e n s i v e l y   t h a n   t r a d i t i o n a l   f o c u s e d   c r a w l e r .   M o r e   e x p e r i m e n t s   o n   l a r g e r   s c a l e s   a r e   r e q u i r e d   f o r   f u r t h e r   s t u d y   t h e   p e r f o r m a n c e   o f   d i f f e r e n t   W e b   s e a r c h i n g   a l g o r i t h m s .       R e f e r e n c e s   [ 1 ]     C h a k r a b a r t i   S ,   v a n   d e n   Be r g   M ,   D o m   B .   F o c u s e d   C r a w l i n g :   a   N e w   Ap p r o a c h   t o   T o p i c - S p e c i f i c   W e b   R e s o u r c e   D i s c o v e r y .   Pr o c e e d i n g s   o f   t h e   8 t h   I n t e r n a t i o n a l   W W W   C o n f e r e n c e .   T o r o n t o ,   C a n a d a .   1 9 9 9 :   5 4 5 - 5 6 2 .   [ 2 ]     C h a u   M ,   C h e n   H .   C o m p a r i s o n   o f   T h r e e   Ve r t i c a l   Se a r c h   Sp i d e r s .   I EEE  C o m p u t e r .   2 0 0 3 ;   3 6 ( 5 ) :   5 6 - 6 2 .   [ 3 ]     Sa l t o n   G .   An o t h e r   L o o k   a t   Au t o m a t i c   T e x t - r e t r i e v a l   Sy s t e m s .   C o m m u n i c a t i o n s   o f   t h e   AC M .   1 9 8 6 ;   2 9 ( 7 ) :   6 4 8 - 6 5 6 .   [ 4 ]     Be r g m a r k   D .   C o l l e c t i o n   Sy n t h e s i s .   Pr o c e e d i n g s   o f   J C D L   2 0 0 2 .   Po r t l a n d ,   O r e g o n ,   U SA.   2 0 0 2 .   [ 5 ]     Ki t s u r e g a w a   M ,   T o y o d a   M ,   P r a m u d i o n o   I .   W e b   C o m m u n i t y   M i n i n g   a n d   W e b   L o g   M i n i n g :   C o m o d i t y   C l u s t e r   Ba s e d   Ex e c u t i o n .   Pr o c e e d i n g s   o f   t h e   1 3 t h   Au s t r a l a s i a n   D a t a b a s e   C o n f e r e n c e .   M e l b o u r n e ,   Au s t r a l i a .   2 0 0 2 .   [ 6 ]     Br i n   S ,   Pa g e   L .   T h e   An a t o m y   o f   a   L a r g e - Sc a l e   H y p e r t e x t u a l   W e b   Se a r c h   En g i n e .   C o m p u t e r   N e t w o r k s   a n d   I SD N   Sy s t e m s .   1 9 9 8 ;   3 0 :   1 - 7 .   [ 7 ]     Kl e i n b e r g   J M .   Au t h o r i t a t i v e   So u r c e s   i n   a   H y p e r l i n k e d   En v i r o n m e n t .   Pr o c e e d i n g s   o f   t h e   AC M - SI A M   Sy m p o s i u m   o n   D i s c r e t e   Al g o r i t h m s .   Sa n   F r a n c i s c o ,   C a l i f o r n i a ,   U SA.   1 9 9 8 :   6 6 8 - 6 7 7 .   [ 8 ]     F l a k e   G W ,   L a w r e n c e   S,   l e e   G i l e s   C .   E f f i c i e n t   I d e n t i f i c a t i o n   o f   W e b   C o m m u n i t i e s .   Pr o c e e d i n g s   o f   t h e   6 t h   AC M   SI G KD D .   Bo s t o n ,   M a s s a c h u s e t t s ,   U SA.   2 0 0 0 .   [ 9 ]     M c C a l l u m   A,   N i g a m   K,   R e n n i e   J ,   S e y m o r e   K.   M a c h i n e   L e a r n i n g   Ap p r o a c h   t o   Bu i l d i n g   D o m a i n - Sp e c i f i c   Se a r c h   E n g i n e s .   Pr o c e e d i n g s   t h e   I n t e r n a t i o n a l   J o i n t   C o n f e r e n c e   o n   Ar t i f i c i a l   I n t e l l i g e n c e   ( I J C AI - 9 9 ) .   1 9 9 9 :   6 6 2 - 6 6 7 .   [ 1 0 ]     C h e n   H ,   C h u n g   Y ,   R a m s e y   M ,   Y a n g   C .   Sm a r t   I t s y - Bi t s y   Sp i d e r   f o r   t h e   W e b .   J ASI S .   1 9 9 8 ;   4 9 ( 7 ) : 6 0 4 - 6 1 8 .   [ 1 1 ]     D e a n   J ,   H e n z i n g e r   M R .   F i n d i n g   R e l a t e d   Pa g e s   i n   t h e   W o r l d   W i d e   W e b .   Pr o c e e d i n g s   o f   t h e   8 t h   I n t e r n a t i o n a l   W W W   C o n f e r e n c e .   T o r o n t o ,   C a n a d a .   1 9 9 9 .   [ 1 2 ]     G i b s o n   D ,   Kl e i n b e r g   J ,   R a g h a v a n   P.   I n f e r r i n g   W e b   C o m m u n i t i e s   f r o m   L i n k   T o p o l o g y .   Pr o c e e d i n g s   o f   t h e   9 t h   AC M   C o n f e r e n c e   o n   H y p e r t e x t   a n d   H y p e r m e d i a .   P i t t s b u r g h ,   Pe n n s y l v a n i a ,   U SA.   1 9 9 8 .   [ 1 3 ]     T o y o d a   M ,   Ki t s u r e g a w a   M .   C r e a t i n g   a   W e b   C o m m u n i t y   C h a r t   f o r   N a v i g a t i n g   R e l a t e d   C o m m u n i t i e s .   Pr o c e e d i n g s   o f   AC M   C o n f e r e n c e   o n   H y p e r t e x t   a n d   H y p e r m e d i a .   År h u s ,   D e n m a r k .   2 0 0 1 .   Evaluation Warning : The document was created with Spire.PDF for Python.
                                        I S S N :   1 6 9 3 - 6 9 3 0   T E L K O M N I K A     V o l .   9 ,   N o .   3 ,     D e c e m b e r   2 0 1 1   :     4 0 3     4 1 0   4 1 0 [ 1 4 ]     Be r g m a r k   D ,   L a g o z e   C ,   Sb i t y a k o v   A.   F o c u s e d   C r a w l s ,   T u n n e l i n g ,   a n d   D i g i t a l   L i b r a r i e s .   P r o c e e d i n g s   o f   t h e   6 t h   EC D L .   R o m e ,   I t a l y .   2 0 0 2 .   [ 1 5 ]     L a w r e n c e   S,   l e e   G i l e s   C .   Se a r c h i n g   t h e   W o r l d   W i d e   W e b .   S c i e n c e .   1 9 9 8 ;   2 8 0 ( 5 3 6 0 ) :   9 8 .   [ 1 6 ]     Sh o k o u h i   M ,   C h u b a k   P,   R a e e s y   Z .   En h a n c i n g   F o c u s e d   C r a w l i n g   w i t h   G e n e t i c   Al g o r i t h m s .   Pr o c e e d i n g s   o f   t h e   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   I n f o r m a t i o n   T e c h n o l o g y :   C o d i n g   a n d   C o m p u t i n g   ( I T C C 0 5 ) .   2 0 0 5 ;   2 :   5 0 3 - 5 0 8 .   [ 1 7 ]     I b r a h i m   SN A,   Se l a m a t   A,   Se l a m a t   M d H .   Sc a l a b l e   E - b u s i n e s s   So c i a l   N e t w o r k   U s i n g   M u l t i C r a w l e r   Ag e n t .   Pr o c e e d i n g s   o f   t h e   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   C o m p u t e r   a n d   C o m m u n i c a t i o n   E n g i n e e r i n g .   Ku a l a   L u m p u r ,   M a l a y s i a .   2 0 0 8 .   [ 1 8 ]     Se n   S,   R o y   P,   C h a k r a b a r t i   A,   Se n g u p t a   S.   G e n e r a t o r   C o n t r i b u t i o n   Ba s e d   C o n g e s t i o n   M a n a g e m e n t   U s i n g   M u l t i o b j e c t i v e   G e n e t i c   Al g o r i t h m .   T EL KO M N I KA   I n d o n e s i a n   J o u r n a l   o f   El e c t r i c a l   En g i n e e r i n g .   2 0 1 1 ;   9 ( 1 ) :   1 - 8 .   [ 1 9 ]     Bh a s k a r   M M ,   Be n e r j i   M ,   Sy d u l u   M .   H y b r i d   G e n e t i c   A l g o r i t h m   Ap p r o a c h   f o r   O p t i m a l   P o w e r   F l o w .   T EL KO M N I KA  I n d o n e s i a n   J o u r n a l   o f   El e c t r i c a l   En g i n e e r i n g .   2 0 1 1 ;   9 ( 2 ) :   2 1 1 - 2 1 6 .   [ 2 0 ]     T a h a m i   M ,   N a d e m i   H ,   R e z a e i   M .   M a x i m u m   T o r q u e   p e r   Am p e r e   C o n t r o l   o f   PM S M   u s i n g   G e n e t i c   Al g o r i t h m .   T EL KO M N I KA  I n d o n e s i a n   J o u r n a l   o f   El e c t r i c a l   En g i n e e r i n g .   2 0 1 1 ;   9 ( 2 ) :   2 3 7 - 2 4 4 .   [ 2 1 ]     G h o z i a   A,   So r o u r   H ,   Ab o s h o s h a   A.   I m p r o v e d   F o c u s e d   C r a w l i n g   U s i n g   Ba y e s i a n   O b j e c t   Ba s e d   Ap p r o a c h .   2 5 t h   N a t i o n a l   R a d i o   Sc i e n c e   C o n f e r e n c e   ( N R SC   2 0 0 8 ) .   Eg y p t .   2 0 0 8 .     Evaluation Warning : The document was created with Spire.PDF for Python.