I nd o ne s ia n J o urna l o f   E lect rica l En g ineering   a nd   Co m p u t er   Science   Vo l.   10 No .   2 May   201 8 ,   p p .   7 9 8 ~8 0 6   I SS N:  2502 - 4752 DOI : 1 0 . 1 1 5 9 1 / i j ee cs . v 1 0 . i2 . p p 798 - 8 0 6          798       J o ur na l ho m ep a g e h ttp : //ia e s co r e. co m/jo u r n a ls /in d ex . p h p / ijeec s   A Mo del f o Proc ess ing  S k y line  Q u eries in  Cro w d - sourced  Da taba ses       M a rwa   B .   Sw ida n,  Ali A .   Alw a n * ,   Sh er zo d T ura ev ,   Yo ni s   G u lza r   De p a rtme n o f   Co m p u ter S c ien c e ,   Ku ll iy y a h   o f   In f o r m a ti o n   a n d   C o m m u n ica ti o n   T e c h n o l o g y ,   In tern a ti o n a Isla m ic  Un iv e rsit y   M a la y sia Ku a la  L u m p u r,   5 3 1 0 0   M a lay sia       Art icle  I nfo     AB ST RAC T   A r ticle  his to r y:   R ec eiv ed   N ov   15 ,   2 0 1 7   R ev i s ed   J an   2 9 ,   2 0 1 8   A cc ep ted   F eb   11 ,   2 0 1 8       No w a d a y s,  in   m o st  o f   th e   m o d e rn   d a tab a se   a p p li c a ti o n s,  lo ts  o f   c rit ica l   q u e ries   a n d   tas k c a n n o b e   c o m p lete l y   a d d re ss e d   b y   m a c h in e .   Cro w d - so u rc in g   d a tab a se   h a b e c o m e   a   n e w   p a r a d ig m   f o h a rn e ss   h u m a n   c o g n it iv e   a b il it ies   t o   p ro c e ss   th e se   c o m p u t e h a rd   tas k s.   I n   p a rt icu lar,  t h o se   p ro b lem s   th a a re   d iff icu lt   f o m a c h in e s b u e a sie r   f o h u m a n s   c a n   b e   so lv e d   b e tt e th a n   e v e r,   su c h   a e n ti t y   re so lu ti o n ,   f u z z y   m a tch in g   f o p re d ica tes   a n d   jo in s,  a n d   im a g e   re c o g n it io n .   A d d it io n a ll y ,   c ro w d - so u rc in g   d a tab a se   a ll o w s   p e rf o r m in g   d a tab a se   o p e ra t o rs  o n   in c o m p lete   d a ta  a s   h u m a n   w o rk e rs  c a n   b e   i n v o lv e d   to   p ro v id e   e stim a t e d   v a lu e s   d u rin g   ru n - ti m e .   S k y li n e   q u e ries   w h ich   re c e iv e d   f o r m id a b le  a tt e n ti o n   b y   d a tab a se   c o m m u n it y   in   th e   las d e c a d e ,   a n d   e x p lo it e d   in   a   v a riet y   o f   a p p li c a ti o n su c h   a m u lt i - c rit e ria  d e c isio n   m a k in g   a n d   d e c isio n   su p p o r sy ste m s.  V a rio u w o rk s   h a v e   b e e n   a c c o m p li sh e d   a d d re ss   th e   issu e o f   sk y li n e   q u e ry   in   c ro w d - so u rc in g   d a tab a se .   T h is  i n c lu d e a   d a tab a se   w it h   f u ll   a n d   p a rt ial  c o m p lete   d a ta.  Ho w e v e r,   we   a rg u e   th a t   p ro c e ss in g   sk y li n e   q u e ries   w it h   p a rti a in c o m p lete   d a ta  in   c ro wd - so u rc i n g   d a tab a se   h a n o t   re c e iv e d   a n   a p p ro p riate   a tt e n ti o n .   T h e re f o re ,   a n   e ff icie n a p p ro a c h   p ro c e ss in g   sk y li n e   q u e ries   w it h   p a rti a in c o m p lete   d a ta  in   c r o w d - so u rc in g   d a tab a se   is  n e e d e d .   Th is  p a p e a tt e m p ts  to   p re se n a n   e ff icie n t   m o d e tac k li n g   th e   issu e   o p ro c e ss in g   sk y li n e   q u e ries   in   in c o m p lete   c ro w d - so u rc in g   d a tab a se .   T h e   m a in   id e a   o f   th e   p ro p o se d   m o d e is  e x p lo it in g   th e   a v a il a b le  d a ta  in   th e   d a tab a se   to   e stim a te  th e   m issin g   v a lu e s.  Be sid e s,  th e   m o d e tri e to   e x p lo re   th e   c ro w d - so u rc e d   d a tab a se   in   o rd e to   p ro v id e   m o re   a c c u ra te  re su lt s,  w h e n   lo c a d a t a b a se   fa il e d   to   p ro v id e   p re c ise   v a lu e s.  In   o rd e to   e n su re   h ig h   q u a li ty   re su lt   c o u ld   b e   o b tai n e d ,   c e rtain   f a c t o rs  sh o u ld   b e   c o n sid e re d   f o w o rk e se lec ti o n   t o   c a rry   o u th e   tas k   su c h   a w o rk e rs   q u a li ty   a n d   th e   m o n e tar y   c o st.  Oth e c rit ica fa c to rs  sh o u ld   b e   c o n sid e re d   su c h   a s ti m e   late n c y   to   g e n e ra te t h e   re su lt s.   K ey w o r d s :   C r o w d - s o u r ci n g   E s ti m a tin g   m is s i n g   v al u es    I n co m p lete  d ata   Sk y li n q u er y   Co p y rig h ©   201 8   In stit u te o A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e   Al rig h ts re se rv e d .   C o r r e s p o nd ing   A uth o r :   A li  A .   Al w an ,     Dep ar t m en t o f   C o m p u ter   Scie n ce ,   I n ter n atio n al  I s la m ic  U n iv er s it y   Ma la y s ia  I I UM ,   P . O.   B o x   1 0 ,   5 0 7 2 8   Ku ala  L u m p u r ,   Ma la y s ia.   E m ail: a lia m er @ ii u m . ed u . m y           1.   I NT RO D UCT I O N   I n   th r ec en y ea r s ,   cr o w d - s o u r cin g   p ar ad ig m   h as  b ec o m p o w er f u to o to   b r in g   h u m an   in telli g e n ce   in to   in f o r m at io n   p r o ce s s in g .   T h is   m ea n s   u s o f   h u m a n   k n o w led g e,   id ea ,   ex p er ien ce ,   an d   s k ill s   to   s o lv m a n y   p r o b lem s   t h at   ar d if f icu l o r   v er y   e x p en s iv e   to   an s w er   co r r ec tl y   u s in g   m ac h i n e - b ased   alg o r ith m s .   E x a m p les   o f   s u ch   p r o b lem s   in c lu d tr an s latio n ,   h an d w r iti n g   r ec o g n itio n ,   p h o t o   tag g in g   an d   a u d io   tr an s cr ip tio n .   T h p r o ce s s   o f   i n teg r at in g   t h o s p eo p le  to   ca r r y   o u t   th e   co m p u tatio n   w it h   t h s o f t w ar s y s te m s   k n o w n   a s   h y p ed   h u m a n m ac h in s y s te m s   [ 1 ] ,   [ 2 ] .   T h cr o w d - s o u r cin g   d atab ase  ( C S DB )   is   o n o f   m o s t   m o d er n   d atab ases   t h at  co n tai n s   lar g a m o u n o f   h eter o g en eo u s   d ata.   T h d ata  in   cr o w d - s o u r ce   d atab ase   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       A   Mo d el  fo r   P r o ce s s in g   S ky lin Qu eries   in   C r o w d - s o u r ce d   Da ta b a s es  ( Ma r w a   B .   S w id a n )   799   m i g h t   b in   m a n y   f o r m s   an d   v ar ies  b et w ee n   w eb   d ata,   tex t,  i m ag e,   a u d io ,   p er s o n al  d ata  an d   s o   o n   [ 2 ] .   C SDB   u s e s   m an y   a s p ec ts   o f   tr ad iti o n al  d atab ase  s y s te m s   a n d   S QL   s tate m e n ts   f o r   p r o ce s s i n g   co m p le x   q u er ies.   Fu r t h er m o r e,   it  ad d s   th e   cr o w d   f u n ctio n a lit y   in to   DB MS.   T h p er f o r m a n ce   an d   co s o f   d atab ase  q u er y   r el y   o n   cr o w d   w o r k er s   [ 1 ] [ 2 ] .   C r o w d - s o u r ce d   d atab ases   p r o m is p o w er f u s o lu tio n   r el y   o n   h u n d r ed s   o f   th o u s a n d s   o f   o r d in ar y   w o r k er s   ( th e   cr o w d ) .   T h o s wo r k er s   atte m p to   p r o v id i n f o r m atio n   w h ich   is   eit h er   u n a v a ilab le  o r   in ac c u r ate   ex p lo itin g   t h av ai lab le  d ata  in   t h cr o w d   d atab ase.   T h is   i n f o r m atio n   h elp   i n   p er f o r m i n g   v ar io u s   d if f ic u lt   co m p u tatio n   f u n ctio n s   s u c h   as  m a tch i n g ,   r an k i n g ,   o r   ag g r eg ati n g   r es u lt s   b ased   o n   f u zz y   cr iter ia  [ 5 ] .   A cc o m p l is h i n g   tas k s   b y   cr o wd   w o r k er s   m i g h in c u r   m o n e tar y   co s t,  laten c y ,   a n d   th ac cu r ac y   o f   t h q u er ies   s u b j ec t to   th w o r k er s   q u alit y   [ 2 ] .   I n   m o s o f   t h co n te m p o r ar y   d atab ase  ap p licatio n s ,   th i s s u o f   m is s in g   d ata  b ec o m f r eq u en p h en o m e n o n ,   e s p ec iall y   w h en   d atab ases   ar g e n er ated   au to m atica ll y   u s i n g   v ar io u s   in f o r m atio n   ex tr ac tio n   o r   in f o r m atio n   i n teg r atio n   ap p r o ac h es.  T h er ar m a n y   r ea s o n s   th a m ak e   th e   d atab ase  i m p r ec is e,   ex e m p li f y   t h d ata  in teg r at io n   f r o m   d i f f er e n h u g d atab ases .   F u r t h er m o r e,   u s er s   m ig h p r o v id i n co m p lete  in p u b y   ig n o r i n g   s o m d ata  w h et h er   in ten tio n all y   o r   u n i n ten tio n all y   w h e n   w o r k i n g   o n   t h d atab ase.   T h ese  ac tiv it ie s   in f lu e n ce   n eg at iv el y   o n   th d atab ase  co n ten t s   an d   d eter io r ate  th q u alit y   o f   th d atab a s co n te n ts .   T h ese   r ea s o n s   i m p ac t o n   th co m p let en es s   an d   th co r r ec tn e s s   o f   t h q u er y   r esu l t [ 3 ] [ 8 ] - [ 1 0 ] .   I n   th i s   r eg ar d ,   s k y lin q u er ies  h a v g ai n ed   co n s id er ab le   atten tio n   f o r   ass i s ti n g   i n   m u lti - cr iter ia   d ec is io n   m a k i n g   an d   d ec is io n   s u p p o r ap p licatio n s   [ 4 ] [ 23 ] [ 24 ] [ 27 ] [ 2 8 ] .   Sk y li n es  ar th o s t u p les  w h ic h   ar th s u p er io r   a m o n g   all  tu p les  in   t h d atab ase.   T h m ai n   i s s u co n ce r n   w h en   w o r k in g   with   s k y li n q u er ies   is   r ed u ci n g   th e   s ea r ch   s p ac a s   s m all  a s   p o s s ib le  a n d   a v o id   th u n n ec es s ar y   e x h au s ti v p ai r w i s co m p ar is o n s   to   d eter m i n i n g   t h s k y l in e s .   W h en   o p er atin g   o n   h u g d ata b ase  s u c h   as  cr o w d - s o u r ci n g   d atab ase  th ad v an ce d   q u er y   o p er ato r s ,   s u ch   as  s k y li n q u er ies  h elp   to   f ilter   u n n ec ess ar y   i n f o r m atio n   e f f icien tl y   b ef o r co n n ec tin g   w it h   t h cr o w d .   Nev er th e less ,   in co m p lete  d ata  h as  n e g ati v ef f ec o n   th p er f o r m a n ce   o f   th s k y l in q u er y   p r o ce s s   w h ic h   m ig h r ai s s o m is s u es  i n cl u d in g   c y clic  d o m in a n ce   a n d   lo s i n g   t h tr a n s iti v it y   p r o p er ty   o f   s k y li n tech n iq u w h ic h   is   h e ld   o n   all  ex is ti n g   s k y lin tec h n iq u e s .   B esid es,  in ac c u r ate  d ata  m i g h al s o   lead   d ec lin th q u a lit y   o f   th r es u l ts   p r o d u ce d   f r o m   t h cr o w d - s o u r ce d   d atab ase  [ 4 ] .   Ou r   co n tr ib u tio n   in   t h i s   p ap er   ca n   b s u m m ar ized   as f o llo w s :   a.   T o   p r o p o s an   ap p r o ac h   th at  is   ab le  to   r etu r n   s k y li n es  f r o m   p ar tiall y   co m p lete  cr o w d - s o u r cin g   d atab as e   w it h   t h i n te n tio n   o f   r ed u ci n g   th n u m b er   o f   p air w is co m p ar is o n s   b y   e li m in a tin g   t h u n n ec ess ar y   t u p le s   b ef o r ap p ly i n g   t h s k y li n te ch n iq u e.   b.   T o   p r o p o s an   ap p r o ac h   t h at  esti m ates  th e   m is s in g   v al u es   o f   s k y li n es  u til izin g   cr o w d - s o u r cin g   d atab ase.   T h ap p r o ac h   h an d les  th i s   is s u tak in g   in to   ac co u n th r elativ er r o r   p r o d u ce d   w h en   g en er ati n g   th e   esti m ated   v al u es,   th e   m o n etar y   co s o f   es ti m atin g   th v al u es,  r ed u ce   t h ti m late n c y ,   a n d   en s u r h i g h   q u alit y   o f   th s k y li n r es u lts .   c.   T o   p r o p o s m o d el  o f   s k y li n e   q u er ies f o r   in co m p le te  cr o w d - s o u r cin g   d atab ase.   T h r est o f   th i s   p ap er   is   o r g an i ze d   as  f o llo w s .   So m n ec es s ar y   b asic   d ef i n itio n s   an d   n o tatio n s ,   w h ic h   ar u s ed   t h r o u g h o u t   th p ap e r ,   ar r ep o r ted   in   s ec tio n   2 .   T h p r ev io u s   w o r k s   r elate d   t o   th is   r esear c h   ar p r es en ted   an d   ex a m i n ed   in   s e ctio n   3 .   Mo r e o v er ,   th d etail  s tep s   o f   th p r o p o s ed   tech n iq u ar ex p lain ed   in   s ec tio n   4 .   Sectio n   5   d r a w s   th co n clu s io n   o f   t h i s   p ap er .       2.   P RE L I M I NARIE S   T h is   s ec tio n   g i v es  s o m n ec es s ar y   d ef i n itio n s   an d   an n o tatio n s   t h at  ar r elate d   to   s k y li n es  q u er ies  i n   p ar tiall y   co m p lete  cr o w d - s o u r cin g   d atab ase s .   T h ese  d ef i n i tio n s   a n d   n o tatio n s   ar i m p o r tan to   e x p lain   t h e   d etails  o f   o u r   p r o p o s ed   m o d el.   W also   d escr ib th co n ce p ts   r elate d   to   cr o w d - s o u r ci n g   d atab ase,   w h ile  co n ce n tr ati n g   o n   ch alle n g e s   o f   in co m p lete  d ata  o n   d atab ase.   T h is   in cl u d ex p lai n in g   t h r ea s o n s   th a m a k e   th d atab ase  to   b in co m p lete  an d   th m eth o d s   u s ed   to   m a n i p u late  th m i s s i n g   d ata.     2 . 1 .      Cr o w d - So urcing   Da t a ba s e   C r o w d - s o u r ci n g   d atab ase  is   h y b r id   d atab ase  s y s te m   th a au to m a ticall y   u s es  cr o w d - s o u r cin g   to   in te g r ate  h u m an   i n p u f o r   p r o ce s s i n g   q u er ies  t h at  n o r m al   d atab ase  s y s te m   ca n n o an s w er   [ 5 ] .   T h cr o w d - s o u r cin g   s y s te m   co m p r i s es  o f   th r ee   co m p o n e n t s   w o r k   to   p r o v id s er v ices   to   t h u s er s   an d   en s u r r etu r n i n g   a   h ig h - q u al i t y   r es u lt  to   t h u s er .   T h co m p o n en t s   ar e:  ( i)   r eq u ester ,   w h o   s u b m it  t h q u er ie s   to   th cr o w d   an d   w ait s   f o r   t h a n s w er s ,   ( ii)  p lat f o r m   ( q u er y   e x ec u tio n   e n g i n e) ,   w h ic h   i s   r esp o n s ib le  to   m a n a g t h g i v en   q u er y   b y   th u s er   a n d   r etr iev b ac k   th an s w er s   g e n er a ted   b y   th w o r k er s ,   ( ii i)   w o r k er s ,   w h o   i s   r esp o n s ib le  to   r u n   th as s ig n ed   tas k s   a n d   p r ep ar i n g   a n d   d eliv er ed   th r es u lts   to   th tar g et  u s er   [ 5 ] ,   [ 2 5 ] .   C r o w d - s o u r ci n g   d atab ase  co n s is t s   o f   a   co llectio n   o f   e n o r m o u s   h e ter o g en eo u s   d atab ase s   th a ar e   s to r ed   o n   d i f f er e n p lace s   o n   th i n ter n et  a n d   ca n   b ac ce s s ed   th r o u g h   t h cr o w d .   C r o w d - s o u r ce d   d atab ases   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,   Vo l.  10 ,   No .   2 Ma y   2 0 1 8   :   7 9 8     8 0 6   800   ex ten d   tr ad itio n al  d atab ases   t o   s u p p o r m o r t y p es  o f   q u e r ies  b y   m ea n s   o f   t h p o w er   o f   p eo p le,   s u ch   a s   C r o w d DB   [ 5 ] ,   Qu r k   [ 6 ] ,   Dec o   [ 7 ] ,   an d   s o   o n .   T h ese  cr o wd - s o u r ce d   d atab ases   ar as s o ciate d   w it h   ce r tai n   cr o w d - s o u r cin g   m ar k etp lace s ,   s u c h   a s   AM T   ( Am az o n   Me c h an ica T u r k )   [ 5 ] ,   C r o w d Flo wer   [ 2 ]   an d   s o   o n ,   to   attr ac cr o w d s   to   w o r k   f o r   th e m .   Fu r t h er m o r e,   cr o w d - s o u r ci n g   d atab ase  lev er ag e s   m a n y   a s p ec ts   o f   tr ad itio n al  d ata b ase  s y s te m s ,   h o w e v er ,   t h er ar also   s o m d i f f er en ce s   b et w ee n   t h e m   w h ich   ar e x p lain ed   as  f o llo w s .   T r a d itio n al  d atab ases   ar co n s id er ed   as  clo s ed - w o r ld   f o r   q u er y   p r o ce s s i n g .   I n f o r m atio n   t h at  i s   n o i n   t h e   d atab ase  is   co n s id er ed   to   b f alse  o r   n o n - e x i s te n t.  B esid es ,   tr ad itio n al  d atab ases   ar ex t r e m el y   liter al.   Fo r   in s ta n ce ,   u s er s   e x p ec t th a t t h d ata  h as   b ee n   p r o p er l y   clea n e d   an d   v al id ated   b ef o r in s er ti n g   i n to   d atab ase  a n d   d o   n o t n eg ati v el y   to ler ate  in co n s i s te n cies i n   d ata  o r   q u er ies [ 5 ] .   T h er ar th r ee   m ai n   cr itical  f ac to r s   t h at  in f l u e n ce   th d at p r o ce s s in g   i n   cr o w d - s o u r ci n g   s y s te m .   T h is   en co m p a s s es,   m o n etar y   co s t,  ti m e   late n c y ,   a n d   t h ac cu r ac y   o f   t h r es u lt s   [ 1 ] ,   [ 2 ] ,   [ 8 ] ,   [ 9 ] ,   [ 1 0 ] ,   [ 1 1 ] .   T h ese  f ac to r s   ar f u r t h er   elab o r ated   b elo w .     Mo n etar y   C o s t:  E v er y   ta s k   g iv en   b y   t h u s er   s h o u ld   b p aid   as  th cr o w d   is   n o f r ee ,   th er ef o r e,   r eq u ester   n ee d s   to   k n o w   i n   ad v an ce   t h e s ti m ated   co s t o f   t h g iv e n   ta s k   b e f o r ask i n g   t h q u esti o n   a n d   s e n d   it  to   th w o r k er .   Hen ce ,   if   t h n u m b er   o f   ta s k s   ar v er y   lar g e,   t h en   cr o w d - s o u r ci n g   ca n   b v e r y   e x p en s i v [ 1 1 ] .     T im L aten c y T h is   f ac to r   r ep r esen ts   t h r u n n i n g   ti m to   o b tain   an s w er s   f r o m   th cr o w d .   Fo r   ea ch   task ,   th r eq u e s ter   ca n   s et  th ti m b o u n d   ( e. g . ,   6 0   s ec o n d s )   to   an s w er   it,  an d   th w o r k er   m u s an s w er   it   w it h i n   t h s tip u lated   ti m b o u n d .   T h r e q u ester   ca n   also   s et  th ex p ir atio n   ti m o f   th tas k s   if   n ec e s s ar y ,   i.e . ,   th m a x i m u m   ti m th at  t h tas k s   w il l b av ailab le  to   w o r k er s   in   th p lat f o r m   ( e. g . ,   2 4   h o u r s )   [ 2 ] .     A cc u r ac y :   C r o w d - s o u r ci n g   r elies  o n   h u m an   w o r k er s   t o   ac h i ev t h j o b   an d   th q u alit y   o f   th r es u lt s   o b tain ed   is   h i g h l y   i n f l u e n ce d   b y   th w o r k er   q u alit y .   H u m a n s   m o s o f te n   te n d   to   m a k er r o r s ,   p ar ticu lar l y   f o r   h ea v y   ta s k s   t h at  n ee d   lo n g   ti m an d   h i g h   atte n tio n .   T h is ,   in   t u r n ,   lead s   i n   t h w o r s ca s to   p r o v id in ac cu r ate   r esu lt s   to   th e   r eq u ester .   B es id es,  s o m m alicio u s   w o r k er s   a r in ter es ted   to   o b tain   r e w ar d s   a n d   i n ten tio n all y   s u b m it  r an d o m   an s w er s   to   all   q u esti o n s   o r   g i v w r o n g   a n s w er s .   T h is   ca n   s ig n i f ica n tl y   d ec lin th q u a lit y   o f   th r es u lt s .   Mo r eo v er ,   s o m et i m es  th w o r k er   m is u n d er s ta n d s   th ta s k   as s ig n ed   w h ic h   e v en tu a ll y   n e g ati v el y   i m p ac o n   th q u al it y   o f   th t ask   ac co m p li s h ed .   L a s tl y ,   w o r k er s   m a y   h a v d if f er en le v e ls   o f   ex p er tis e,   an d   u n tr ai n ed   w o r k er   m a y   b in ca p ab le  o f   ac co m p lis h i n g   ce r tain   co m p lica ted   tas k s   [ 2 ] .         2 . 2 .       I nco m plet Da t a   T h d atab ase  w it h   in co m p lete   d ata  o r   m i s s i n g   v al u ( also   k n o w n   a s   n u ll  v al u e)   ar b ec o m i n g   v er y   co m m o n   i n   r ea w o r ld   ap p lic atio n s   s u c h   a s   w eb   d atab ase  [ 2 6 ] .   Fo r   ex a m p le,   ce n s u s   d atab ase  th at   allo w s   n u l v a lu e s   f o r   s o m attr ib u tes .   A   s u r v e y   d atab ase  w h er a n s w er s   to   o n q u es tio n   ca u s o t h er   q u est io n s   to   b s k ip p ed .   A ls o ,   a   m ed ical  d ata b ase  th a r elate s   h u m a n   b o d y   an al y s t   ( s u b s ta n ce   t h at   ca n   b m ea s u r ed   i n   t h e   b lo o d   o r   u r in e)   m ea s u r e m e n t s   to   n u m b er   o f   d is ea s es,  o r   p atien r is k   f ac to r s   to   s p ec if ic  d is ea s e.   T h d ef in i tio n   o f   i n co m p lete  d atab ase  is   g i v e n   b elo w   [ 1 4 ] .     I nco m plet Da t a ba s e g i v e n   d atab ase  D( R 1 ,   R 2 ,   . . . ,   R n ),   w h er R i   is   r elatio n   d en o ted   b y   R i (d 1 ,   d 2 . . . ,   d m ) D   is   s aid   to   b in co mp lete   if   an d   o n l y   i f   it  co n tai n s   at  least  t u p le  p j   w i th   m i s s i n g   v al u es  i n   o n o r   m o r d i m en s io n s   d k   ( attr ib u tes ) ; o th er w i s e,   it is   co mp lete .   T h er ar m an y   r ea s o n s   t h at  m ak th d atab ase  to   b i m p er f ec d u to   m is s in g   v alu e s .   T h d ata   in te g r atio n   f r o m   d i f f er e n h u g d atab ases ,   d ep en d   o n   w o r k e r   to   in p u th d ata  th at  also   lead   to   m is s in g   d ata  w h et h er   in te n tio n all y   o r   u n in ten tio n a ll y .   A d d itio n all y ,   s o m t y p e s   o f   d atab ase s   i n   w h ich   d ata  co n s tan t l y   ch an g i n g   s u ch   a s   te m p o r al  d atab ase.   T h ese  ca u s e s   m ig h i m p ac o f   t h co m p le ten e s s   a n d   co r r ec tn ess   o f   t h e   r esu lt p r o d u ce d   [ 1 2 ] ,   [ 1 3 ] .   Miss i n g   d ata  is   al w a y s   u n w a n ted   an d   p r o b lem at ic,   esp ec ia ll y   d u r i n g   q u er y   p r o ce s s i n g .   E v en   i f   t h r ate  o f   th m i s s i n g   v al u es  is   s m al it  m i g h s er io u s l y   b ia s   in f er en ce .   Fro m   th d atab ase  lit er atu r it  ca n   b co n clu d ed   th a m is s in g   d ata  m ec h a n i s m s   ar o f ten   ca te g o r ized   in to   t h r ee   d if f er en ca teg o r ies.  First,  m is s in g   co m p lete l y   at  r an d o m   ( MC AR )   w h ic h   m ea n s   t h er ar n o   s y s te m atic  d i f f er e n ce s   b et w ee n   m is s in g   an d   o b s er v ed   v al u es  o r   p u m o r s i m p l y ,   m is s i n g   v al u e s   ap p ea r   to   b co m p letel y   r an d o m .   Seco n d ,   m i s s i n g   a t   r an d o m   ( MA R )   w h er m is s i n g   d ata  o cc u r   b ased   o n   s o m o b s er v ed   v ar iab les  b u n o t   o n   th v ar iab le  o f   in ter est   o r   th e   v ar iab le   u n d er   s t u d y .   I n   p ar ticu lar   t h is   m ea n s   th at   f o r   ea ch   tu p le   m o s a ttrib u te  v al u es  ar e   av ailab le,   w h ile  j u s s o m ar r an d o m l y   m i s s i n g .   T h ir d ,   m is s i n g   n o at  r a n d o m   ( MN AR ) ,   i n   t h i s   ca te g o r y   m is s i n g   d ata  o cc u r   b ased   o n   n   v ar iab le  o f   in ter e s t o r   th d ep en d en v ar iab le  in   s ta tis tica l te r m s   [ 1 4 ] ,   [ 1 2 ] .   T h m i s s i n g   v al u e s   h a v e   n e g a tiv el y   in f l u e n ce   o n   t h q u alit y   o f   th d atab ase  as  m o r m is s i n g   v al u es   lead   to   h ig h   r ate  o f   p r ef er en c d ata.   T h er ef o r e,   esti m at in g   t h m is s in g   v alu e s   ca n   e n h an c th q u alit y   o f   th e   d atab ase  co n ten ts   b y   tr an s f o r m in g   th d atab ase  s tate  f r o m   in co m p lete  t o   co m p lete.   I n   th is   s ec t io n   w e   h ig h li g h t o n   th e   p r ed ictio n   m e th o d s   o f   h a n d lin g   i n co m p lete   d ata.   W class i f y   th p r ed ictio n   m eth o d s   in to   t w o   m ai n   ca teg o r ies,  n a m e l y s tati s tical  m eth o d s   a n d   m ac h in le ar n in g   m eth o d s   [ 1 3 ] ,   [ 1 4 ] .     Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       A   Mo d el  fo r   P r o ce s s in g   S ky lin Qu eries   in   C r o w d - s o u r ce d   Da ta b a s es  ( Ma r w a   B .   S w id a n )   801   2 . 2 . 1 .       Sta t is t ica M et ho ds \   Statis t ical  m e th o d s   ar th b a s f o r   m a n y   o f   th p r ed ictio n   a p p r o ac h es.  T h m ai n   ai m   o f   t h is   m et h o d   is   p r eser v i n g   t h d i s tr ib u tio n   o f   t h w h o le  d ata   b y   a v o id in g   b ias o n   t h d ata  d is tr ib u tio n .   T h p r ed icted   v alu e s   m a y   b en e f it  u s er   at  t h d atab a s le v el  b u t   n o t   at  t h t u p le  le v el.   I n   m an y   ca s es  u s er s   ar m o r e   co n ce r n   o n   t h e   in d iv id u al  v alu o f   t h attr ib u te  r ath er   t h an   th w h o le  d ata.   T h u s ,   th e s s tati s tical  m e th o d s   m a y   n o b e   ap p r o p r iate  f o r   p r ef er en ce   q u er ies [ 1 2 ] ,   [ 1 4 ] .   T h s tatis tical  m et h o d s   ar as f o ll o w s :   a.   Sin g le  I m p u tatio n   ( SI)   -   I n   th i s   m et h o d ,   th w h o le  m i s s i n g   v alu es  f o r   g iv en   attr ib u te  ar s u b s t itu ted   b y   s in g le  v al u e.   T h m et h o d s   th at   in v o lv s in g le  i m p u tatio n   i n cl u d m ea n ,   m ed ia n ,   m o d e,   m ax i m u m   v al u i n   th attr ib u te  r an g e,   m i n i m u m   v alu e   in   th e   attr ib u te  r a n g e,   a n d   ex p ec tatio n   m ax i m izat io n .   T h is   m et h o d   i s   n o t satiab le  w h en   t h r elev a n er r o r   is   v er y   h i g h .   b.   Mu ltip le  I m p u tatio n s   ( MI )   -   I n   th i s   m et h o d ,   m o r th an   o n esti m ated   v al u es  ar d er iv ed   in   o r d er   to   f ill  in   th m is s i n g   v al u e s .   T h co m p u tatio n   co s o f   th i s   m et h o d   is   h i g h er   t h an   SI,   b u it  i s   m o r ac cu r ate  an d   p r o d u ctiv e.   T h is   m et h o d   also   n ee d s   a n   ap p r o p r iate  m ec h an i s m   to   r e f lect  t h e   u n ce r tai n t y   o f   m is s i n g   d ata  an d   p r ec is el y   est i m a te  t h m is s i n g   v alu e s .   An   i m p o r tan t   ar g u m e n i n   f a v o u r   o f   t h is   a p p r o ac h   is   t h at,   f r eq u en tl y ,   attr ib u te s   h a v r el atio n s h ip s   ( co r r elatio n s )   a m o n g   t h e m s el v es.  I n   t h is   w a y ,   t h o s co r r elatio n s   co u ld   b u s ed   to   cr ea te  p r ed i ctiv m o d el  f o r   cla s s i f icatio n   o r   r eg r ess io n   ( d ep en d i n g   o n   t h attr ib u te  t y p e   w it h   m is s i n g   d ata,   b ein g ,   r esp ec tiv el y ,   n o m in a l o r   co n tin u o u s ) .     2 . 2 . 2 .       M a chine Lea rning   M et ho ds   Ma ch i n lear n in g   ( ML )   m eth o d s   lear n   p r ed ictio n   m o d els  to   h an d le  t h d atab ase  w it h   m i s s in g   v al u es   b ased   o n   th co m p lete  d atab as in s tan ce s .   So m o f   t h M L   m et h o d s   in v o l v p r o b ab ilis tic  ap p r o ac h   to   p r ed ict   th m is s in g   v alu e s .   M L   m e t h o d s   ar n o n - p ar a m etr ic  as  t h e y   d o   n o r el y   o n   d ata  d is t r ib u tio n   d u r i n g   t h e   tr ain i n g   o r   test i n g   p r o ce s s .   T h ese  m et h o d s   ar a ls o   ca ll ed   p a r a mete r - fr ee   m et h o d s   o r   d is tr ib u tio n - fr ee   m et h o d s .   T h is   m e th o d   n ee d l o n g   ti m b ef o r g et ti n g   t h o p ti m al  v alu e s   b ec au s it  r ep ea ts   w o r k   m an y   ti m es   u n t il  it  ca tch es   t h lo w e s r ele v an er r o r .   T h er ar e   s ev er al  ap p r o ac h es  th at  h a v b ee n   p r o p o s ed   w h ich   b elo n g   to   th M L   m et h o d s   w h ich   in c lu d C 4 . 5 ,   A u to cla s s ,   Fra ctio n in g   C ase s ,   C N2 ,   k - n ea r es n eig h b o r   ( k N N)   [ 1 4 ] ,   [ 2 9 ] .     2 . 3 .    Sk y lin Q ueries   Sk y li n q u er ies   h a v b ee n   w i d ely   u s ed   as  a n   attr ac ti v o p er ato r   in   m u lti - cr iter ia  d ec is i o n   m a k i n g   ap p licatio n s ,   w h er m an y   cr it er ia  ar in v o lv ed   in   th e   q u er y   s tate m e n to   s elec th e   m o s s u itab le  a n s w er   th a t   f its   t h u s er   r eq u ir e m en ts .   A n o th er   d o m ai n   th at  ap p lied   th s k y li n q u er ies  is   t h d ec is io n   s u p p o r s y s te m   a n d   r ec o m m e n d er   s y s te m ,   w h er th ese  s y s te m s   co m b in v ar io u s   in ter e s ts   to   h elp   u s er s   b y   r ec o m m e n d i n g   a   s tr ateg ic  d ec is io n .   So m d e f in itio n s   r elate d   to   s k y li n q u er i es  ar g iv e n   i n   th f o llo w in g   [ 4 ] ,   [ 8 ] ,   [ 1 1 ] ,   [ 1 4 ] ,   [ 2 7 ] .   Do m i na nce:   g iv e n   t w o   tu p le p i   an d   p j     d ata  s et  w i th   d i m en s io n s ,   p i   d o m i n ates   p ( th g r ea ter   is   b etter )   ( d en o ted   b y   p i >p j )   if   an d   o n l y   if   t h f o llo w i n g   c o n d itio n   h o ld s :   l j l i l k j k i k d p d p d d d p d p d d . . , . . ,   S k y lin e:   s k y li n tec h n iq u r etr iev es  t h s k y li n e,   S   i n   w a y   s u c h   t h at  a n y   s k y l in i n   S   is   n o d o m i n ated   b y   an y   o th er   t u p le s   in   th d ata  s et.     S k y lin qu er ies:  s elec tu p l p i   f r o m   t h s et  o f   d ata  s et  D   if   an d   o n l y   if   p i   is   as  g o o d   as  p j   ( w h er i     j )   in   all  d im e n s io n s   ( attr ib u t es)  an d   s tr ictly   i n   at  least  o n d i m en s io n   ( attr ib u te) .   W u s S skyline   to   d en o te  th s et  o f   s k y lin t u p le s ,   S skyline   { p i   |   p i ,   p j     D p   p j }.   Co m pa ra ble:   L et  t h t u p le a i   an d   a j     R a i   a n d   a j   ar e   co m p ar ab le  ( d en o ted   b y j i a a )   if   a n d   o n l y   i f   th e y   h a v n o   m i s s i n g   v al u es  i n   at  least  o n id en t ical  d i m e n s io n o th er w i s a i   is   i n co m p ar ab le  to   a j   ( d en o ted   by j i a a ).   Mo s o f   t h s k y li n al g o r ith m s   r el y   o n   t h as s u m p tio n   o f   co m p leten e s s   o f   t h d ata,   i.e .   all   v al u es  o f   p o in ts   ar p r esen an d   k n o w n .   Ho w e v er ,   in   m a n y   ca s es,  th is   ass u m p tio n   d o es  n o h o ld .   T h u s ,   co n v e n tio n a l   s k y li n al g o r ith m s   ca n n o t   b ap p lied   d ir ec tly .   B esid es,  t h in co m p lete n es s   o f   d ata  lead s   to   lo s s   tr an s iti v it y   p r o p er ty   o f   s k y li n tec h n iq u e   w h ic h   i s   h eld   o n   a ll  e x is t in g   s k y li n tec h n iq u e s .   T h is   f u r t h er   lead s   to   c y clic   d o m i n a n ce   b et w ee n   th t u p les  as  s o m tu p le s   ar in co m p ar ab le  w it h   ea ch   o th er   an d   th u s   n o   tu p le  i s   co n s id er ed   as sk y li n [ 4 ] .       3.   RE L AT E WO RK   T h is   s ec tio n   p r esen t s   a n d   r ev ie w s   t h p r ev io u s   ap p r o ac h es   r elate d   to   s k y li n q u er ie s   i n   co m p lete  tr ad itio n al  d atab ase.   Fu r t h er m o r e,   s k y li n q u er ies  i n   i n co m p lete  tr ad itio n al  d atab ase  h av b ee n   d is c u s s ed .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,   Vo l.  10 ,   No .   2 Ma y   2 0 1 8   :   7 9 8     8 0 6   802   L ast l y ,   th e   p r ev io u s   s tr ate g ie s   f o r   s k y li n q u er ies  i n   cr o w d - s o u r ci n g   d atab ases   h a v b ee n   ex p lai n ed   an d   d is cu s s ed   d elib er atel y .     3 . 1 .       S k y lin Q ueries f o Co m p let Da t a   First  to p ic  o f   s k y lin q u er ie s   in   co m p lete  d atab ase  h av b ee n   ad d r ess ed   w it h   t w o   d if f er e n s o lu tio n s   th B lo ck - Ne s ted - L o o p   ( B NL )   an d   Div id e - an d - C o n q u er   ( D& C )   [ 1 5 ] .   I n   2 0 0 2 ,   [ 1 6 ]   p r ese n ted   n e w   o n l in e   s k y li n al g o r ith m   ca l led   Nea r est  Nei g h b o r   ( NN) .   I is   d i f f e r en ab o u t h last   a lg o r it h m s   th at   co m p u ted   th e   Sk y li n i n   b atch ,   b u t h NN  alg o r it h m   r etu r n s   th f i r s r esu lts   i m m ed iatel y ,   a n d   f i n d   m o r r es u lt s   co n tin u o u s l y .   F u r t h er m o r e,   m an y   ap p r o ac h es  h a v b ee n   s u g g e s tio n   f o r   s k y lin q u er ie s   in   co m p lete  d atab ase  in cl u d ed So r t - Fil ter - S k y l in ( SF S)  [ 1 7 ] ,   B r an ch - B o u n d - S k y l in ( B B S)  [ 1 8 ] ,   L in ea r   E li m i n atio n   So r f o r   Sk y li n ( L E SS )   [ 1 9 ] ,   So r a n d   L i m it  Sk y li n al g o r ith m   ( SaL Sa)   [ 2 0 ] ,   C ac h B ased   C o n s tr ain ed   S k y li n e   ( C B C S)  [ 2 1 ] ,   an d   o th er s .     3 . 2 .       Sk y lin Q ueries f o I nc o m p let Da t a   T h er ar n u m er o u s   alg o r it h m s   w h ic h   ap p lied   s k y lin q u er ies  f o r   in co m p lete  d ata b ase.   T h is   in cl u d es  b u t   n o li m ited   t h f ir s w o r k   co n tr ib u ted   i n   [ 4 ]   p r o p o s ed   tw o   al g o r it h m s   f o r   h an d lin g   t h s k y li n e   q u er ies  i n   i n co m p lete  d ata,   n a m e l y :   B u c k et  a n d   I s k y li n e.   Mo r eo v er ,   R ep lace m e n B ased   Sets   S k y li n e   C o m p u tatio n   ( R B S SQ)   [ 2 2 ] ,   s o r t - b ased   I n co m p lete  Data   S k y l in ( SID S)  [ 2 3 ] ,   I n co s k y li n [ 1 4 ]   h av b ee n   p r o p o s ed   to   s o lv th i s s u o f   p r o ce s s i n g   s k y li n q u er ie s   i n   i n co m p lete  d atab ase.   T h p r ev io u s   w o r k s   h as   o n l y   f o cu s ed   o n   h o w   to   tack l th is s u o f   p r o ce s s i n g   s k y l in q u er ies  i n   i n co m p lete  d at a,   ai m in g   at  s o l v i n g   th is s u o f   c y clic  d o m i n a n ce   an d   lo s in g   th tr a n s it iv i t y   p r o p er ty   o f   s k y li n tech n iq u e.   Ho w e v er ,   n o m u c h   atten tio n   h a s   b ee n   p aid   o n   i m p r o v in g   t h q u alit y   o f   t h s k y lin r es u lt s   b y   p r o v id i n g   e s ti m ated   v a lu e s   f o r   t h e   s k y li n es  w i th   in co m p lete  d at a.   Ho w e v er ,   th o n l y   w o r k   t h at  ad d r ess es  th is s u o f   p r ed ictin g   th e   m i s s in g   v alu e s   o f   th s k y lin e s   is   co n tr ib u ted   in   [ 1 4 ]   aim in g   at  m a n i p u latin g   th m is s i n g   v alu e s   b ef o r r etu r n in g   th e   s k y li n es to   th u s er .   A d d itio n a ll y ,   th m o s t o f   w o r k s   d esi g n e d   to   b u s ed   in   tr ad itio n al  d atab ases   o n l y .     3 . 3 .       Sk y lin i n Cr o w d - So urcing   Da t a ba s e   C r o w d - s o u r ci n g   d atab ases   h a s   v ar io u s   u n iq u f ea t u r es  co m p ar ed   w i th   th e   tr ad itio n al   d atab ases .   T h er ef o r e,   it  m i g h n o b p o s s ib le  to   d ir ec tl y   ap p l y   ap p r o a ch es   p r o d u ce d   f o r   tr ad itio n al   d atab ase  in   cr o w d - s o u r cin g   d atab ase s .   T o   th b e s o f   o u r   k n o w led g e,   th er is   n o m u c h   atte n tio n   g i v e n   o n   p r o ce s s in g   o f   s k y li n e   q u er ies  in   cr o w d - s o u r ci n g   d at ab ases   w it h   in co m p lete  d ata.   Mo s o f   th e s s t u d ies  co n ce n tr ate  o n   d esig n in g   s k y li n s tr ate g ies  to   est i m a te  t h m is s in g   v a lu e s   o f   s k y li n r esu lt s   en s u r i n g   lo w   p r o ce s s in g   co s an d   les s   ti m e   laten c y   a n d   h i g h   ac cu r ac y   f o r   th esti m ated   r es u lts .   I n   [ 8 ] ,   [ 9 ]   th ey   h a v p r o p o s ed   h y b r id   ap p r o ac h   co m b in i n g   d y n a m ic  cr o w d - s o u r ci n g   w it h   h e u r is tic   tech n iq u es.  T h id ea   o f   t h p r o p o s ed   ap p r o ac h   r elies  o n   u tili zin g   s et  o f   h e u r is tic  tec h n iq u e s   in   o r d er   to   p r ed ict  th m i s s i n g   v al u e s   f o r   all  tu p les.  I al s o   ex p lo its   th co n ten t s   o f   t h cr o w d   f o r   s o m ca s es  to   i m p r o v e   ac cu r ac y   o f   th est i m ated   v al u es.  A   n e w   a lg o r it h m   n a m ed   C r o w d S k y   h as  b ee n   p r o p o s e d   [ 1 1 ] .   T h alg o r ith m   co n s id er s   th r ee   k e y   f ac to r s   th at  in f lu e n ce   th p r o ce s s   o f   s k y l in w h ic h   ar m in i m izin g   th m o n etar y   co s t,   r ed u cin g   th late n c y ,   a n d   i m p r o v in g   th ac c u r ac y   o f   cr o w d - s o u r ce d   s k y lin e.   A l th o u g h   th w o r k   ass u m ed   th at  t h p r o ce s s   o f   v al u e   esti m atio n   b y   t h cr o w d   w il b ap p lied   o n   s et  o f   v ir tu al  at tr ib u tes.  W h ic h   m ea n s   th i n itial   d atab ase  is   co m p let e,   b u w it h   i n s u f f icien t   d ata  th at  m i g h n o h elp   to   p r o v id a n   ac cu r ate  a n s w er s   f o r   s k y li n q u er ies.  T h er ef o r e,   u til izin g   t h cr o w d   d atab as b y   g e n er ati n g   s o m e   r elev a n v ir tu al  attr ib u tes  a n d   th eir   v al u es a r p r ed icted   b y   t h cr o w d   w o r k er s   to   s u p p o r t th q u er y   r es u lt s .       4.   RE S E ARCH   M E T H O D     I n   th i s   s ec t io n   w p r ese n o u r   p r o p o s ed   m o d el  to   co m p u te   s k y li n es  i n   i n co m p lete  cr o wd - s o u r ci n g   d atab ase.   F ig   1 .   o u tli n es   t h d etails  s tr u ct u r o f   t h m o d el  t h at  co n s i s ts   o f   eig h t   p h ase s .   I n   th is   f r a m e w o r k ,   w ass u m e   tr ad itio n al   lo ca d at s et    co n tai n s   tu p le s   w it h   s o m m i s s i n g   v a lu e s   a n d   th e   u s er   w ill  s u b m it   a   s k y li n q u er y   w it h   s o m p r ed ef i n ed   p r ef er en ce s .   T h u s er   q u er y   m a y   al s o   co n tai n   ad d iti o n al  m eta - d ata  f o r   d escr ib in g   th e   r eq u ir ed   r es u lt   q u alit y ,   m ax i m al   q u er y   b u d g e t,  r esp o n s e   ti m r eq u ir e m e n ts ,   etc.   F u r t h er   d etails   r elate d   to   ea ch   co m p o n e n t a r ex p lain i n g   in   t h f o llo w in g   s u b s ec tio n .     4 . 1 .       D a t a   F iltr a t io   T h is   co m p o n e n an al y ze s   th in itial  d atab ase  in   o r d er   to   id e n ti f y   a n d   r em o v th u n n ec es s ar y   tu p le s   in   th i n it ial  d atab ase.   T h is   p r o ce s s   lead s   to   eli m i n ate  t h d o m in ated   t u p les  b y   ap p l y i n g   t h s k y l in p r o ce s s   o n   th i n co m p lete  d atab ase.   T h er ef o r e,   th i s   p r o ce s s   h elp s   to   r ed u ce   th a m o u n o f   d ata  in   th n e x p r o ce s s es.   Ma n y   d o m in a ted   tu p les  ca n   b s af el y   r e m o v ed   as  t h e y   h a v n o   co n tr ib u tio n   i n   th e   s k y l i n r es u lts .   Do i n g   s o   r esu lt s   in to   m i n i m izi n g   t h m o n etar y   co s t a n d   th ti m late n c y   to   es ti m ate  t h m i s s i n g   v al u es f r o m   t h cr o w d .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       A   Mo d el  fo r   P r o ce s s in g   S ky lin Qu eries   in   C r o w d - s o u r ce d   Da ta b a s es  ( Ma r w a   B .   S w id a n )   803     4 . 2 .       Sa m ple  Se lect o a nd   At t ribute   Ana ly ze r   T h aim   o f   t h i s   co m p o n en is   to   g en er ate  s a m p le  f r o m   t h in itial  d atab ase  to   b u s ed   f o r   an al y z in g   th r elatio n s h ip s   b et w ee n   attr ib u tes.  A n a l y zi n g   th r elatio n s h ip   b et w ee n   t h attr ib u te s   h e lp s   to   esti m ate  t h m is s i n g   v al u e s   i n   t h t u p les.  I is   i m p r ac tical  to   d o   t h is   p r o ce s s   o v er   t h w h o le  d ata  s i n ce   t h n u m b er   o f   tu p les  i n   th in i tial  d atab ase  ar v er y   h u g e.   T h er ef o r e,   a n al y zi n g   th e   attr ib u te   co r r elatio n   d ir ec tl y   o n   t h e   w h o le  d ata  m ig h i n cu r   h i g h   o v er h ea d   an d   co n s u m s i g n i f ican a m o u n o f   ti m e.   He n ce ,   ex tr ac tin g   s m al l   p o r tio n   o f   th d atab ase  f o r   a ttrib u te  an al y s i s   h elp s   to   s p ee d   u p   th p r o ce s s   an d   r ed u ce   th co s w it h o u t   co m p r o m is i n g   t h q u alit y   o f   th esti m ated   v a l u es.  T h s a m p le  w ill  b g en er ated   r an d o m l y   an d   w it h i n   a   p r ed ef in ed   r an g e.   A t tr ib u te  a n al y s i s   ass i s ts   in   g en er ati n g   t h ap p r o x i m ate  f u n ctio n al  d ep en d en cies  b et w ee n   attr ib u tes.  T h is   p r o ce s s   is   f u r t h er   ex p lai n ed   in   t h n e x t s u b s ec tio n .           Fig u r 1 .   T h Pro p o s ed   Mo d el   o f   Sk y li n Qu er ie s   in   C r o w d - So u r cin g   I n co m p le te  Data b ase s       4 . 3 .       Appro x i m a t F un ct io n a l D ependencie s   G e nera t o   T h ai m   o f   t h i s   co m p o n e n t   is   to   d er iv t h r elatio n s h ip   b et w ee n   t h a ttrib u te s .   Fo r   t h is   p u r p o s e,   th e   s y s te m   a n al y zi n g   t h v a lu e s   o n   th s elec ted   s a m p le  tr y i n g   t o   ca p tu r th r elatio n s h ip s   b et w ee n   attr ib u te s   an d   d eter m in h o w   th v al u in   o n attr ib u te  af f ec ts   t h v alu e s   o f   th o t h er   attr ib u tes.      Def ini t io n:  Ap pro x i m a t F u nct io na Depen dency   ( AF D)   Giv e n   r elatio n   R ,   a   s u b s et   X   o f   its   d i m en s io n s ,   an d   s i n g le  d i m en s io n   d i   o f   R ,   w s a y   th a th er is   an   ap p r o x i m ate  f u n ctio n al  d ep en d e n c y   ( A DF)   b et w ee n   an d   d i,  d en o ted   b y   Xf         d i ,   if   th co r r esp o n d in g   f u n ctio n al  d ep en d en c y          di   h o ld s   o n   all  b u t   s m a ll  f r ac tio n   o f   th e   t u p les o f   R.   T h s et   o f   d i m e n s i o n s   X   is   ca lled   a   d etermin in g   s et   o f   d i   d en o ted   b y   Dtr S et( d i )   [ 1 4 ] .     T o   g en er ate  th A FD,  w f ir s t   d iv id th s a m p le  s et  w it h   m is s i n g   v al u es  in to   t w o   s ets.  T h f ir s s e co n tain s   all  v alu e s   t h at  m is s i n g   i n   t h id en t ical  attr ib u te  t h at  n ee d s   to   b esti m ated ,   a n d   th s ec o n d   s et   co n tain s   th r e m ai n in g   v alu es  ( co m p lete) .   T h v al u es  o f   th s ec o n d   s et  ar an a l y z ed   to   ca p tu r th r elatio n s h ip s   b et w ee n   t h attr i b u tes o f   t h r elatio n .   T h en   t h AFD  i s   g en er ated ,   t h at  h elp   u s   in   s p ec if y i n g   h o th v a lu o f   o n attr ib u te  in f l u en ce s   th v al u es  o f   th o t h er   attr ib u tes.  T h en   to   en s u r t h a th d er iv ed   A FD   r ef lects t h r elatio n s h ip s   b et w ee n   attr ib u te s   [ 1 4 ] .     4 . 4 .       Str eng t h o f   P r o ba bil it y   Co rr ela t io ns   E s t i m a t o r   T h ai m   o f   th i s   co m p o n e n is   to   ch o o s th a ttrib u te  t h at  h a s   h i g h   i n f lu e n ce   o n   o th er   attr i b u tes  r el y   o n   th s tr en g t h   o f   p r o b ab ilit y   co r r elatio n s   b et w ee n   attr ib u t e s ,   f o r   in s ta n ce   d i   an d   d j ,   an d   t o   w h ic h   ex te n t h v alu e   o f   d i   i n f l u e n ce s   t h v al u o f   d j .   T h s tr en g th   o f   p r o b a b ilit y   co r r elatio n s   b et w ee n   d i   an d   d j   is   d en o ted   as   P( d i d j )   an d   is   f o r m u lated   as f o llo w s   [ 1 4 ] :   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,   Vo l.  10 ,   No .   2 Ma y   2 0 1 8   :   7 9 8     8 0 6   804   | , | | | ) , ( i j j j i d d d d d P     W h er | . |   r ef er s   to   t h n u m b e r   o f   d is ti n ct  v al u es.  T h v al u o f   P( d i d j )   i n d icate s   th e   s tr en g t h   th at   ev er y   d is ti n ct  v al u in   d j   is   as s o ciate d   w it h   u n iq u v alu i n   d i .     4 . 5 .       M is s ing   v a lues   predict o r   T h is   co m p o n e n is   r esp o n s ib l to   s u b s tit u te  t h m is s i n g   v a lu es  o f   t h d atab ase  w i th   s o m i m p u ted   v alu e s   d er iv ed   u s in g   t h a v ail ab le  d ata  o f   t h d atab ase.   T h i s   is   ac h ie v ed   b ased   o n   co u n ti n g   th e   f r eq u e n c y   o f   th v al u e x is ts   w it h   s e v er al  alter n ati v v al u es  b y   r ep lace   th m i s s i n g   v alu e s   w i th   t h e s ti m ated   v a lu e s .   I n   th is   p r o ce s s   t h er m i g h b m an y   es ti m ated   v al u es  f o r   d i m en s io n   t h at  n ee d   to   b c o n s i d er ed .   H o w ev er ,   in   s o m ca s es  th er m i g h b m o r th an   o n AFD  t h at  ca n   b e   g e n er ated   b et w ee n   th e   d i m e n s io n s .   I n   t h i s   ca s e,   th r esu lts   o f   t h AFDs   ar co m b in ed   to   esti m ate  t h m is s in g   v al u e.       4 . 6 .       Rela t iv er ro r   a nd   t hresh o ld v a lue ident if ier   T h is   co m p o n en co n ce r n s   o n   ch ec k in g   t h ac cu r ac y   o f   t h esti m ated   v al u es  g e n er ated   u s i n g   th e   ex is t in g   d ata   o f   th e   d atab a s e.   Af ter   al m is s i n g   v a lu e s   h as   b ee n   es ti m ated   i n   la s s tag e   o f   t h p r o p o s ed   m o d el,   th s y s te m   co m p u tes  th r elat iv er r o r   w h ic h   i n d icate s   th e   er r o r   r ate  b etw ee n   t h o b tain e d   esti m a ted   v al u e s   w h e n   th e   d atab ase  h a s   s o m m is s i n g   v al u es   in   o n o r   m o r e   d i m en s io n s   a n d   th r ea v al u e s   w h e n   t h d atab ase   is   co m p lete  w i th   n o   m is s in g   v alu e s .   I f   th r elati v er r o r   r ate  is   lar g er   t h a n   t h u s er   d ef i n ed   th r es h o ld   v al u e,   th en   th e s ti m ated   v alu e s   w i ll  b d is ca r d ed .   Oth er w i s e,   a cc ep th esti m ated   v al u es  a n d   u s th e m   i n   t h e   s k y li n r esu lts .   I n   o n ca s e,   t h is   h elp s   u s   to   b en ef i f r o m   t h ex i s ti n g   d ata  i n   p r ed icatin g   th m is s i n g   v al u e s   an d   r ed u ce   t h a m o u n o f   d ata  to   b g en er ated   f r o m   t h cr o w d .   Mo r eo v er ,   it  also   h elp s   to   r ed u ce   t h e   m o n etar y   co s b y   av o id i n g   s en d in g   m an y   r e q u e s to   t h cr o w d   w o r k er s .   I n   o t h er   ca s e,   if   t h q u ali t y   o f   esti m ated   v al u es  is   lo w ,   t h en   w m a y   r e f er   to   th cr o w d - s o u r ce d   d atab ase  to   o b tain   b etter   r esu lts   t h at  m ig h t   b w it h in   t h u s er   d ef i n ed   th r esh o ld   v al u e.   Hen ce ,   w ca n   co n cl u d th at  o u r   m o d el  h as  co n s id er ed   b o th   s ce n ar io s   a n d   en s u r in g   t h co s t a n d   th q u ali t y   o f   th r es u lt s   h av b ee n   m ai n tai n ed .     4 . 7 .       An a cc ura t esti m a t v a lues   g ener a t o   T h is   co m p o n e n i s   r e s p o n s ib l to   g e n er ate  e s ti m ated   v al u es   f o r   t h o s s k y li n e s   w it h   in co m p lete  d ata.   T h p r o c ess   s tar ts   b y   ev a lu at in g   th q u alit y   o f   t h es ti m at ed   v alu e s   th r o u g h   co m p ar i n g   th r elati v er r o r   b et w ee n   t h r ea m is s in g   v al u an d   th e   esti m ated   o n e   ag ai n s t h u s er   d ef i n ed   t h r esh o ld   v alu e.   I f   th r elat iv e   er r o r   p r o d u ce d   less   th a n   th th r es h o ld   v alu e,   t h en   t h esti m ated   v al u es  w il b ac ce p te d   f o r   r ep lace m en t .   Oth er w i s e,   th e   esti m ated   v al u es  w ill   b ig n o r ed   an d   atte m p t   to   ex p lo it  t h d ata  in   th e   cr o w d   to   g e n er ate  m o r e   ac cu r ate  v a lu e s .   W ar g u t h at  u ti lizi n g   th e   lo ca d ata  i n   t h d atab ase  h elp s   to   e s ti m a te   lar g n u m b er   o f   esti m ated   v a lu e s   w it h   h i g h   q u alit y .   T h is   is   b ec au s e   t h v alu esti m ated   ar g en er ated   b ase d   o n   ex p lo iti n g   t h e   ex p licit  r elatio n s h ip   b et w ee n   th d i m e n s io n s   an d   v ia  id en t i f y in g   t h s tr e n g th   o f   t h p r o b ab ilit y   co r r elatio n   b et w ee n   th d i m e n s io n s .   Ho w ev er ,   f o r   ce r tain   ca s es,  p ar ticu lar l y   f o r   d ata  w it h   h i g h   m is s in g   r ate  o r   th d ata  is   in d ep en d en t,  t h e n   it  m i g h b ch alle n g in g   to   est i m a te  ac cu r ate  v alu e s .   T h er ef o r e,   w r e q u est  t h cr o w d   t o   g en er ate  m o r p r ec is e s ti m at ed   v alu e s   w h ic h   r es u lt s   i n to   r elativ er r o r   b elo w   th g i v en   t h r es h o ld   v al u e.   B asicall y ,   th i s   co m p o n e n h as  t w o   s u b - co m p o n e n ts   wh ich   ar lo ca esti m a tio n   a n d   cr o w d - s o u r cin g   esti m atio n .   T h ese  s u b - co m p o n en ts   ar f u r t h er   ex p lai n ed   in   t h f o llo w in g .       4 . 8 .       Sk y lin identif ier   T h is   co m p o n en is   th e   last   co m p o n en i n   t h p r o p o s ed   f r am e w o r k   w h ic h   ai m s   to   id en ti f y   th e   f i n a l   s k y li n es  o f   t h d atab ase  an d   g et  th q u er y   r e s u l t.  T h p air w i s co m p ar is o n   p r o ce s s   w ill   b ap p lied   o n   f in al   co m p lete   d atab ase  to   g et  s k y l in es.  T h is   h elp s   u s er s   i n   s e lec tin g   t h r elev a n s k y li n es   f r o m   s e v er al  ca n d id ate   s k y li n es.       5.   CO NCLU SI O N     Sk y li n q u er y   i s   th p r o ce s s   o f   id en ti f y in g   t h n o n - d o m in a ted   tu p les  in   t h d atab ase  an d   r etu r n i n g   th e m   to   t h en d   u s er   b ased   o n   th u s er   g i v e n   p r ef er en ce .   I is   o n o f   th m o s p r ed o m i n an t   ty p o f   p r ef er en c e   q u er ies  th at  h a v b ee n   in tr o d u ce d   in to   th d atab ase  i n   th e   last   d ec ad e.   T h is   p ap er   atte m p ts   to   in tr o d u ce   a   m o d el  to   p r o ce s s   s k y li n q u er ies  in   cr o w d - s o u r ci n g   d atab ases   w it h   p ar tiall y   co m p let d ata.   T h m o d el   d escr ib es  th n ec e s s ar y   co m p o n en t s   to   p r o ce s s   s k y li n q u e r y   a n d   r etu r n   s k y li n es  o f   th e   d atab ase  w it h   th e   in te n tio n   o f   r ed u c in g   t h n u m b er   o f   p air w i s co m p ar i s o n s   b et w ee n   t u p les   w h ich   r es u lts   in to   r ed u cin g   t h co s t   o f   s k y li n q u er y   p r o ce s s i n g   an d   m in i m ize  t h t i m e   late n c y .   M o s t   i m p o r ta n tl y ,   t h m o d el  co n ce n tr ate s   o n   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       A   Mo d el  fo r   P r o ce s s in g   S ky lin Qu eries   in   C r o w d - s o u r ce d   Da ta b a s es  ( Ma r w a   B .   S w id a n )   805   p r o v id in g   s k y li n es  o f   i n co m p lete  d atab ase  w it h   co m p lete  d ata  d er iv ed   f r o m   t h cr o w d - s o u r cin g   d atab ases .   T h is   is   ac co m p lis h ed   th r o u g h   esti m at in g   t h m i s s i n g   v al u e s   in   t h d atab ase  w h ic h   in   co n s eq u e n ce   p r o v id m o r p r ec is e   r es u lts   h elp i n g   u s er   to   m a k t h m o s ap p r o p r iate  d ec is io n .   W p lan   to   i m p le m en t   t h is   m o d el  an d   ev al u ate  it s   p er f o r m a n c an d   ef f icie n c y   in   p r o v id p r ec is v al u es.  Facto r s   s u c h   as  r elativ e   er r o r s ,   m o n etar y   co s t,  ac cu r ac y   o f   th e   r esu lts ,   ti m late n c y   w ill b ta k en   i n to   co n s id er atio n   w h e n   d ev elo p   th m o d el.       ACK NO WL E D G E M E NT S   T h is   r es ea r ch   is   s u p p o r t ed   b y   th p r o ject   FR GS 1 5 - 205 - 0 4 9 1 ,   Min is tr y   o f   E d u ca t io n ,   Ma la y s ia .       RE F E R E NC E S   [1 ]   A .   P a ra m e s w a ra n ,   a n d   N.   P o ly z o ti s,  A n swe rin g   q u e rie u si n g   h u ma n s,  a lg o rith ms   a n d   d a t a b a se s,”   P re se n ted   a t   th e   5 t h   Bien n ial  C o n f e re n c e   o n   In n o v a ti v e   Da ta S y ste m s R e se a r c h   (CIDR’1 1 ),   A silo m a r,   Ca li f o rn ia,US A ,   2 0 1 1 .   [2 ]   G .   L i,   J.   Wan g ,   Y.  Zh e n g ,   a n d   M .   J.  F ra n k li n ,   Cro w d so u rc e d   d a ta  m a n a g e m e n t:   su rv e y ,   IEE T ra n sa c ti o n o n   Kn o wled g e   a n d   D a ta   En g i n e e rin g ,   2 8 ( 9 ),   2 0 1 6 ,   p p .   2 2 9 6 - 2 3 1 9 .   [3 ]   G . W o lf ,   A .   Ka l a v a g a tt u ,   H.  Kh a tri ,   R.   Ba lak rish n a n ,   B.   Ch o k sh i,   J.  F a n ,   a n d   S .   Ka m b h a m p a ti ,   Q u e ry   p ro c e ss in g   o v e in c o m p lete   a u to n o m o u d a tab a se s:  q u e ry   r e w rit in g   u sin g   lea rn e d   d a ta  d e p e n d e n c ies , ”  VL DB  J o u rn a l - T h e   In ter n a t io n a J o u rn a o n   Ver y   L a rg e   Da ta   Ba se s ,   1 8 ( 5 ),   2 0 0 9 ,   p p . 1 6 7 - 1 1 9 0 .   [4 ]   M .   E.   Kh a lef a ,   M .   F .   M o k b e a n d   J.   J.  L e v a n d o sk i,   S k y li n e   q u e ry   p ro c e ss in g   fo in c o m p lete   d a t a ,   t h e   2 4 t h   In tern a ti o n a C o n f e re n c e   o n   Da ta  En g in e e rin g   (ICDE),   Ca n c u n ,   M e x ico ,   2 0 0 8 ,   p p . 5 5 6 -   5 6 5 .   [5 ]   M .   J.  F ra n k li n ,   D.  Ko ss m a n n ,   T .   Kra sk a ,   S .   Ra m e sh   a n d   R.   Xin ,   Cro w d DB:  a n swe rin g   q u e rie wit h   c ro wd so u rc in g ,   A CM   S IG M OD   In tern a ti o n a Co n f e re n c e   o n   M a n a g e m e n o f   d a ta  S I G M OD ’1 1 ,   A th e n s,  G re e c e ,   2 0 1 1 ,   p p .   6 1 7 2 .   [6 ]   A .   M a r c u s,  E.   W u ,   D.  R.   Ka r g e r ,   S .   M a d d e n   a n d   R.   C.   M il ler,  Cro wd so u rc e d   d a ta b a se s:  q u e ry   p ro c e ss in g   wit h   p e o p le,   th e   5 t h   Bien n ial  Co n f e re n c e   o n   In n o v a ti v e   Da ta S y ste m Re se a rc h   (CIDR ' 1 1 ),   A silo m a r,   C a li f o rn ia,  USA ,   2 0 1 1 ,   p p . 2 1 1 - 2 1 4 .   [7 ]   H.  P a rk ,   H.  G a rc ia - M o li n a ,   R.   P a n g ,   N.  P o ly z o ti s,  A .   P a ra m e s w a ra n ,   a n d   J.  W id o m ,   De c o sy ste fo d e c la ra ti v e   c ro wd s o u rc in g ,   th e   V L DB E n d o wm e n t,   5 (1 2 ),   Ista n b u l,   T u rk e y ,   2 0 1 2 ,   p p . 1 9 9 0 - 1 9 9 3 .   [8 ]   C.   L o f i,   K.  El   M a a rr y   a n d   WT .   Ba lk e ,   S k y li n e   q u e rie o v e in c o mp lete   d a t a - e rr o mo d e ls  fo f o c u se d   c ro wd - so u rc in g ,   t h e   3 2 t h   In ter n a ti o n a Co n f e re n c e   o n   Co n c e p tu a M o d e l in g ,   Ho n g   K o n g ,   C h in a ,   2 0 1 3 ,   p p . 2 9 8 - 3 1 2 .   [9 ]   C.   L o f i,   K.  El   M a a rr y   a n d   WT .   Ba lk e ,   S k y li n e   q u e rie in   c ro wd - e n a b led   d a ta b a se s,”   t h e   1 6 t h   In tern a ti o n a l   Co n f e re n c e   o n   Ex ten d in g   Da tab a se   T e c h n o l o g y   EDB T /ICD T   ' 1 3 ,   G e n o a ,   Ital y ,   2 0 1 3 ,   p p .   4 6 5 - 4 7 6 .   [1 0 ]   K.  El   M a a rr y ,   C.   L o f i,   a n d   W T .   Ba lk ,   Cro w d so u rc in g   f o q u e r y   p ro c e ss in g   o n   w e b   d a ta:  a   c a s e   stu d y   o n   th e   sk y li n e   o p e ra to r,   J o u rn a o f   Co mp u ti n g   a n d   I n fo rm a ti o n   T e c h n o l o g y     CIT ,   2 3 ( 1 ),   2 0 1 5 ,   p p . 4 3 - 60.   [1 1 ]   J.  L e e ,   D.  L e e ,   a n d   S . W .   Kim ,   Cro wd S k y sk y li n e   c o mp u t a ti o n   w it h   c ro wd so u rc in g ,   th e   1 9 th   I n tern a ti o n a l   Co n f e re n c e   o n   Ex ten d in g   Da tab a se   T e c h n o l o g y   (EDB T ),   Bo rd e a u x ,   F ra n c e ,   2 0 1 6 ,   p p . 1 2 5 - 1 3 6 .   [1 2 ]   M .   A .   S o li m a n ,   I.   F .   Ily a a n d   S .   Be n - Da v id ,   S u p p o r ti n g   ra n k in g   q u e ries   o n   u n c e rtain   a n d   in c o m p lete   d a ta,”  th e   Ver y   L a rg e   Da t a b a se   J o u rn a l,   VL DB ,   1 9 (4 ),   2 0 1 0 ,   p p . 4 7 7 -   5 0 1 .   [1 3 ]   L .   W a n g   a n d   R.   Jo n e s,  Big   d a ta  a n a ly ti c f o d isp a ra te  d a ta,”  Ame ric a n   J o u rn a o I n telli g e n S y ste ms ,   7 (2 ) ,   2 0 1 7 ,   p p . 3 9 - 4 6 .   [1 4 ]   A .   A .   A l w a n ,   H.  Ib ra h im ,   N.  I.   U d z ir  a n d   F .   S id i ,   Esti m a ti n g   mis sin g   v a lu e o f   sk y li n e in   i n c o mp l e te  d a ta b a se ,   th e   T h e   S e c o n d   I n tern a ti o n a C o n f e re n c e   o n   Dig it a En ter p rise   a n d   I n f o rm a ti o n   S y ste m (DEI S 2 0 1 3 ) ,   K u a l a   L u m p u r,   M a lay sia ,   2 0 1 3 ,   p p . 2 2 0 - 2 2 9 .   [1 5 ]   S .   Bo rz so n y ,   D.  Ko ss m a n n   a n d   K.  S to c k e r,   T h e   sk y li n e   o p e ra t o r ,   th e   1 7 th   In tern a ti o n a Co n f e re n c e   o n   Da ta  En g in e e rin g   (ICDE0 1 ),   He id e l b e r g ,   G e r m a n y ,   v o l.   3 8 9 6 ,   2 0 0 1 ,   p p .   4 2 1 - 4 3 0 .   [1 6 ]   D.  k o ss m a n n ,   F . Ra m s a k   a n d   S .   R o st,  S h o o t in g   sta rs   in   th e   S k y a n   o n li n e   a l g o rit h f o sk y li n e   q u e rie s,”   th e   2 8 t h   In tern a ti o n a C o n f e re n c e   o n   V e ry   L a rg e   Da ta Bas e s (V L DB’0 2 ),   H o n g   Ko n g ,   Ch i n a ,   2 0 0 2 ,   p p .   2 7 5 -   2 8 6 .   [1 7 ]   J.  Ch o m ick i,   P .   G o d f re y ,   J.  G r y z   a n d   D.  L ian g ,   S k y li n e   wit h   p re so rtin g ,   th e   1 9 t h   In ter n a ti o n a Co n f e re n c e   o n   Da ta E n g in e e rin g   (ICDE0 3 ) ,   Ba n g a lo re ,   In d ia,  2 0 0 3 ,   p p . 7 1 7 - 8 1 6 .   [1 8 ]   D.  P a p a d ias ,   Y.   T a o ,   G .   F u   a n d   B.   S e e g e r,   An   o p ti ma l   a n d   p r o g re ss ive   a lg o rith fo sk y li n e   q u e rie s,”   A CM   Co n f e re n c e   o n   th e   M a n a g e m e n o f   Da ta (S I G M OD ),   S a n   Die g o ,   Ca li f o rn ia,  USA ,   2 0 0 3 ,   p p .   4 4 3 - 4 5 4 .   [1 9 ]   P .   G o d f re y ,   R.   S h ip ley   a n d   J.  G r y z ,   M a x ima v e c to c o mp u ta ti o n   i n   la r g e   d a t a   se ts,”   th e   3 1 st  In tern a ti o n a l   Co n f e re n c e   o n   V e ry   L a rg e   Da ta  Ba se s (V L DB’0 5 ),   T ro n d h e im ,   No rw a y ,   2 0 0 5 ,   p p .   2 2 9 - 2 4 0 .   [2 0 ]   I.   Ba rto li n i ,   P .   Ciac c ia  a n d   M .   P a tella,  S a L S a c o mp u ti n g   th e   sk y li n e   wit h o u sc a n n in g   t h e   wh o le  sk y ,   th e   1 5 t h   In tern a ti o n a Co n f e re n c e   o n   In fo rm a ti o n   a n d   Kn o w led g e   M a n a g e m e n (ICIKM 0 6 ),   A rli n g to n ,   V irg in ia,  USA ,   2 0 0 6 ,   p p .   4 0 5 -   4 1 4 .   [2 1 ]   M .   L .   M o rten se n ,   S .   C h e ste r,   I. A s se n a n d   M .   M a g n a n i,   Ef fi c i e n c a c h i n g   f o c o n str a in e d   sk y li n e   q u e rie s,”   t h e   1 8 t h   In tern a ti o n a Co n f e re n c e   o n   Ex ten d in g   Da tab a se   T e c h n o lo g y   ( EDBT ),   2 0 1 5 ,   p p . 3 3 7 -   3 4 8 .   [2 2 ]   M .   S .   A re f in   a n d   Y.  M o rim o to ,   S k y li n e   se ts  q u e ries   f o in c o m p lete   d a ta,”  In ter n a ti o n a J o u rn a o C o mp u ter   S c ien c e   &   In fo rm a ti o n   T e c h n o l o g y ,   4 (5 ),   2 0 1 2 ,   p p .   6 7 - 8 0 .   [2 3 ]   R.   Bh a ru k a   a n d   S .   P .   Ku m a r,   Fi n d i n g   sk y li n e fo in c o m p lete   d a t a ,   th e   2 4 t h   A u stra las ian   Da tab a se   Co n f e re n c e ,   A d e laid e ,   A u stra li a ,   v o l. 1 3 7 ,   2 0 1 3 ,   p p .   1 0 9 - 1 1 7 .   [2 4 ]   A .   A .   A l w a n ,   H.  Ib ra h im ,   N.  I.   Ud z ir  a n d   F .   S id i ,   A n   e ff ici e n a p p r o a c h   f o p ro c e ss in g   sk y li n e   q u e ries   in   in c o m p lete   m u lt id im e n sio n a d a tab a se ,   Ara b i a n   J o u rn a f o r S c ie n c e   a n d   En g i n e e rin g ,   4 1 ( 8 ),   2 0 1 6 ,   p p . 2 9 2 7 - 2 9 4 3 .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,   Vo l.  10 ,   No .   2 Ma y   2 0 1 8   :   7 9 8     8 0 6   806   [2 5 ]   E.   D.  Dif a ll a h ,   M .   Ca tas ta,  G .   De m a rti n i,   G .   P .   I p e iro ti a n d   P .   Cu d - M a u r o u x ,   T h e   d y n a mic o M icr o - T a sk   c ro wd so u rc in g ,   t h e   2 4 t h   In ter n a ti o n a W o rld   W id e   W e b   Co n f e re n c e   (W WW   2 0 1 5 ),   F l o re n c e ,   Italy ,   2 0 1 5 ,   p p .   238 - 2 4 7 .   [2 6 ]   G .   Ca n a h u a te,  M .   G ib a a n d   H.  F e rh a to sm a n o g lu ,   In d e x in g   in c o mp lete   d a ta b a se s,”   t h e   1 0 th   In tern a t io n a l   Co n f e re n c e   o n   Ex ten d in g   Da tab a se   T e c h n o l o g y   (EDB T ),   M u n ich ,   G e r m a n y ,   2 0 0 6 ,   p p . 8 8 4 - 9 0 1 .   [2 7 ]   Y.  G u lza r,   A .   A .   A l w a n ,   N.  S a ll e h ,   I.   F .   A l - S h a ik h li   a n d   S .   I.   M a iraj  A l v i,   Fra me wo rk   fo Ev a lu a ti n g   S k y li n e   Qu e rie s o v e r In c o mp lete   Da t a ,   P r o c e d ia Co m p u ter S c ien c e ,   9 4 ,   2 0 1 6 ,   p p . 1 9 1 - 1 9 8 .   [2 8 ]   Y.  G u lza r,   A .   A .   A l wa n ,   N.  S a ll e h ,   a n d   I.   F .   A l - S h a ik h li ,   S k y li n e   q u e ry   p ro c e ss in g   fo in c o mp let e   d a ta   i n   c lo u d   e n v iro n me n i n   Z u li k h a ,   J .   &   N.   H.  Z a k a ri a   ( Ed s.),   th e   6 th   I n tern a ti o n a Co n f e re n c e   o n   Co m p u ti n g   &   In f o r m a ti c s,   (ICOCI),  Ku a la L u m p u r,   2 0 1 7 ,   p p . 5 6 7 - 5 7 6 .   [2 9 ]   J.  Qiu ,   Q.  W u ,   G .   Din g ,   Y.  X u ,   a n d   S .   F e n g ,   A   su rv e y   o f   m a c h in e   lea rn i n g   f o b ig   d a ta  p ro c e ss i n g ,   EURA S IP   J o u rn a o n   A d v a n c e s in   S ig n a Pro c e ss in g ,   2 0 1 6 ,   DO 1 0 . 1 1 8 6 /s1 3 6 3 4 - 0 1 6 - 0 3 5 5 - x.       B I O G RAP H I E S   O F   AUTH O RS       M a rw a   B.   S w id a n   is  a   P h s tu d e n a I n tern a ti o n a Isla m ic  Un iv e rsit y   M a la y sia ,   IIUM ,   M a la y sia .   S h e   e a rn e d   h e B. S c .   a n d   M . S c .   d e g re e in   Co m p u ter  S c ien c e   f ro m   T rip o li   Un iv e rsity ,   L ib y a   in   2 0 0 4   a n d   2 0 0 9   re sp e c ti v e l y .   H e re s e a rc h   in tere sts  in c lu d e   c ro w d so u rc in g ,   d a ta  m in in g /ex p lo ra ti o n ,   d a tab a se   sy st e m s a n d   sk y li n e   q u e ries .         A li   A .   Aw a n   is  c u rre n tl y   a n   a ss istan p ro f e ss o a Ku ll iy y a h   (F a c u lt y o f   In f o r m a ti o n   a n d   Co m m u n ica ti o n   T e c h n o l o g y ,   In tern a ti o n a l   Isla m ic  Un iv e rsit y   M a la y sia   (IIUM ),   M a la y sia .   He   re c e iv e d   h is  M a ste o Co m p u te S c ien c e   (2 0 0 9 a n d   P h . i n   C o m p u ter  S c ien c e   (2 0 1 3 f ro m   Un iv e rsiti   P u tra  M a lay si a   (UP M ),   M a lay sia .   His  re se a rc h   in tere sts  in c lu d e   p re f e re n c e   q u e ries ,   sk y li n e   q u e ries ,   p ro b a b il isti c   a n d   u n c e rtain   d a tab a se s,  q u e ry   p ro c e ss in g   a n d   o p ti m iza ti o n   a n d   m a n a g e m e n o in c o m p lete   d a t a ,   d a ta  in teg ra ti o n ,   lo c a ti o n - b a se d   so c ial  n e tw o rk ( L BS N),  re c o m m e n d a ti o n   sy ste m s,  a n d   d a t a   m a n a g e m e n in   c lo u d   c o m p u ti n g .         S h e rz o d   T u ra e v   o b tai n e d   h is P h D   in   Co m p u ter  S c ie n c e   in   2 0 1 0   f ro m   Un iv e r sit y   Ro v ira  V irg il i,   T a rra g o n a ,   S p a in   a n d   P h i n   M a th e m a ti c s   in   2 0 0 1   f ro m   N a ti o n a Un iv e rsit y   o f   Uz b e k istan .   He   w a a   p o stg ra d u a te  re se a rc h e in   Un iv e rsit y   P u tra  M a lay sia   f ro m   2 0 0 9   to   2 0 1 2 .   He   is  a   f a c u lt y   m e m b e a De p a rtme n o f   Co m p u ter  S c ien c e ,   F a c u lt y   o f   In f o rm a ti o n   a n d   Co m m u n ica ti o n   T e c h n o lo g y ,   In tern a ti o n a Isla m ic   Un iv e rsit y   M a la y sia   sin c e   2 0 1 2 .   His  re se a r c h   in tere sts  in c lu d e   g ra p h   th e o ry ,   re g u late d   re w rit in g   s y ste m s,  f o r m a lan g u a g e a n d   a u to m a ta,  b io - c o m p u ti n g ,   m a c h in e   lea rn in g   a n d   in f o rm a ti o n   se c u rit y .           Yo n is  G u lza r   is  c u rre n tl y   a   P h . D .   stu d e n a t   In ter n a ti o n a Isla m ic  Un iv e rsit y   M a la y sia   (IIUM ),   M a la y sia .   He   h a re c e iv e d   h is  M a ste o f   Co m p u ter  A p p li c a t io n ( 2 0 1 3 )   f ro m   Ba n g a lo re   Un iv e rsit y ,   In d ia.  His  re se a rc h   in tere sts  in c lu d e   p re f e re n c e   q u e ries ,   sk y li n e   q u e ries ,   p ro b a b il isti c   a n d   u n c e rtain   d a tab a se s,  q u e ry   p ro c e ss in g   a n d   o p ti m iza ti o n   a n d   m a n a g e m e n o f   in c o m p lete   d a ta,   d a ta i n teg ra ti o n ,   a n d   d a ta m a n a g e m e n in   c l o u d   c o m p u ti n g .     Evaluation Warning : The document was created with Spire.PDF for Python.