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 r  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 t  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 l  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 s  c a n n o t  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 s  b e c o m e   a   n e w   p a r a d ig m   f o r  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 r  h a rd   tas k s.   I n   p a rt icu lar,  t h o se   p ro b lem s   th a t  a re   d iff icu lt   f o r  m a c h in e s b u t  e a sie r   f o r  h u m a n s   c a n   b e   so lv e d   b e tt e r  th a n   e v e r,   su c h   a s  e n ti t y   re so lu ti o n ,   f u z z y   m a tch in g   f o r  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 t  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 s  su c h   a s  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 t  sy ste m s.  V a rio u s  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 s  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 s  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 l  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 s  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 t  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 l  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 r  a tt e m p ts  to   p re se n t  a n   e ff icie n t   m o d e l  tac k li n g   th e   issu e   o f  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 l  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 l  tri e s  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 r  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 l  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 r  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 r  w o rk e r  se lec ti o n   t o   c a rry   o u t  th e   tas k   su c h   a s  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 r  c rit ica l  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 e  q u er y   Co p y rig h t  ©   201 8   In stit u te o f  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 l  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 e  r ec en t  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 e  a  p o w er f u l  to o l  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 e  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 e  m a n y   p r o b lem s   t h at   ar e  d if f icu l t  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 e  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 e  p r o ce s s   o f   i n teg r at in g   t h o s e  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 e  s o f t w ar e  s y s te m s   k n o w n   a s   a  h y p ed   h u m a n /  m ac h in e  s y s te m s   [ 1 ] ,   [ 2 ] .   T h e  cr o w d - s o u r cin g   d atab ase  ( C S DB )   is   o n e  o f   m o s t   m o d er n   d atab ases   t h at  co n tai n s   a  lar g e  a m o u n t  o f   h eter o g en eo u s   d ata.   T h e  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 e  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 e  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   a  DB MS.   T h e  p er f o r m a n ce   an d   co s t  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 e  a  p o w er f u l  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 e  wo r k er s   atte m p t  to   p r o v id e  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 e  av ai lab le  d ata  in   t h e  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 t  in c u r   a  m o n e tar y   co s t,  laten c y ,   a n d   th e  ac cu r ac y   o f   t h e  q u er ies   s u b j ec t to   th e  w o r k er ’ s   q u alit y   [ 2 ] .   I n   m o s t  o f   t h e  co n te m p o r ar y   d atab ase  ap p licatio n s ,   th e  i s s u e  o f   m is s in g   d ata  b ec o m e  a  f r eq u en t  p h en o m e n o n ,   e s p ec iall y   w h en   d atab ases   ar e  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 e  ar e  m a n y   r ea s o n s   th a t  m ak e   th e   d atab ase  i m p r ec is e,   ex e m p li f y   t h e  d ata  in teg r at io n   f r o m   d i f f er e n t  h u g e  d atab ases .   F u r t h er m o r e,   u s er s   m ig h t  p r o v id e  i n co m p lete  in p u t  b y   ig n o r i n g   s o m e  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 e  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 e  d atab ase  co n ten t s   an d   d eter io r ate  th e  q u alit y   o f   th e  d atab a s e  co n te n ts .   T h ese   r ea s o n s   i m p ac t o n   th e  co m p let en es s   an d   th e  co r r ec tn e s s   o f   t h e  q u er y   r esu l t [ 3 ] ,  [ 8 ] - [ 1 0 ] .   I n   th i s   r eg ar d ,   a  s k y lin e  q u er ies  h a v e  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 t  ap p licatio n s   [ 4 ] ,  [ 23 ] ,  [ 24 ] ,  [ 27 ] ,  [ 2 8 ] .   Sk y li n es  ar e  th o s e  t u p les  w h ic h   ar e  th e  s u p er io r   a m o n g   all  tu p les  in   t h e  d atab ase.   T h e  m ai n   i s s u e  co n ce r n   w h en   w o r k in g   with   s k y li n e  q u er ies   is   r ed u ci n g   th e   s ea r ch   s p ac e  a s   s m all  a s   p o s s ib le  a n d   a v o id   th e  u n n ec es s ar y   e x h au s ti v e  p ai r w i s e  co m p ar is o n s   to   d eter m i n i n g   t h e  s k y l in e s .   W h en   o p er atin g   o n   h u g e  d ata b ase  s u c h   as  cr o w d - s o u r ci n g   d atab ase  th e  ad v an ce d   q u er y   o p er ato r s ,   s u ch   as  s k y li n e  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 e  co n n ec tin g   w it h   t h e  cr o w d .   Nev er th e less ,   in co m p lete  d ata  h as  a  n e g ati v e  ef f ec t  o n   th e  p er f o r m a n ce   o f   th e  s k y l in e  q u er y   p r o ce s s   w h ic h   m ig h t  r ai s e  s o m e  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 e  tr a n s iti v it y   p r o p er ty   o f   s k y li n e  tech n iq u e  w h ic h   is   h e ld   o n   all  ex is ti n g   s k y lin e  tec h n iq u e s .   B esid es,  in ac c u r ate  d ata  m i g h t  al s o   lead   d ec lin e  th e  q u a lit y   o f   th e  r es u l ts   p r o d u ce d   f r o m   t h e  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 e  s u m m ar ized   as f o llo w s :   a.   T o   p r o p o s e  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 e  i n te n tio n   o f   r ed u ci n g   th e  n u m b er   o f   p air w is e  co m p ar is o n s   b y   e li m in a tin g   t h e  u n n ec ess ar y   t u p le s   b ef o r e  ap p ly i n g   t h e  s k y li n e  te ch n iq u e.   b.   T o   p r o p o s e  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 e  ap p r o ac h   h an d les  th i s   is s u e  tak in g   in to   ac co u n t  th e  r elativ e  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 t  o f   es ti m atin g   th e  v al u es,  r ed u ce   t h e  ti m e  late n c y ,   a n d   en s u r e  h i g h   q u alit y   o f   th e  s k y li n e  r es u lts .   c.   T o   p r o p o s e  a  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 e  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 e  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 e  u s ed   t h r o u g h o u t   th e  p ap e r ,   ar e  r ep o r ted   in   s ec tio n   2 .   T h e  p r ev io u s   w o r k s   r elate d   t o   th is   r esear c h   ar e  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 e  d etail  s tep s   o f   th e  p r o p o s ed   tech n iq u e  ar e  ex p lain ed   in   s ec tio n   4 .   Sectio n   5   d r a w s   th e  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 e  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 e  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 e  i m p o r tan t  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 e  also   d escr ib e  th e  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 e  ex p lai n in g   t h e  r ea s o n s   th a t  m a k e   th e  d atab ase  to   b e  in co m p lete  an d   th e  m eth o d s   u s ed   to   m a n i p u late  th e  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   a  h y b r id   d atab ase  s y s te m   th a t  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 t  f o r   p r o ce s s i n g   q u er ies  t h at  a  n o r m al   d atab ase  s y s te m   ca n n o t  an s w er   [ 5 ] .   T h e  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 e  s er v ices   to   t h e  u s er s   an d   en s u r e  r etu r n i n g   a   h ig h - q u al i t y   r es u lt  to   t h e  u s er .   T h e  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 e  q u er ie s   to   th e  cr o w d   an d   w ait s   f o r   t h e  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 e  t h e  g i v en   q u er y   b y   th e  u s er   a n d   r etr iev e  b ac k   th e  an s w er s   g e n er a ted   b y   th e  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 e  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 e  r es u lts   to   th e  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 t  ar e   s to r ed   o n   d i f f er e n t  p lace s   o n   th e  i n ter n et  a n d   ca n   b e  ac ce s s ed   th r o u g h   t h e  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 t  m o r e  t y p es  o f   q u e r ies  b y   m ea n s   o f   t h e  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 e  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 l  T u r k )   [ 5 ] ,   C r o w d Flo wer   [ 2 ]   an d   s o   o n ,   to   attr ac t  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 e  ar e  also   s o m e  d i f f er en ce s   b et w ee n   t h e m   w h ich   ar e  e x p lain ed   as  f o llo w s .   T r a d itio n al  d atab ases   ar e  co n s id er ed   as  a  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 t  i n   t h e   d atab ase  is   co n s id er ed   to   b e  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 e  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 e  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 e  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 e  ar e  th r ee   m ai n   cr itical  f ac to r s   t h at  in f l u e n ce   th e  d at a  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 e  ac cu r ac y   o f   t h e  r es u lt s   [ 1 ] ,   [ 2 ] ,   [ 8 ] ,   [ 9 ] ,   [ 1 0 ] ,   [ 1 1 ] .   T h ese  f ac to r s   ar e  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 e  u s er   s h o u ld   b e  p aid   as  th e  cr o w d   is   n o t  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  e s ti m ated   co s t o f   t h e  g iv e n   ta s k   b e f o r e  ask i n g   t h e  q u esti o n   a n d   s e n d   it  to   th e  w o r k er .   Hen ce ,   if   t h e  n u m b er   o f   ta s k s   ar e  v er y   lar g e,   t h en   cr o w d - s o u r ci n g   ca n   b e  v e r y   e x p en s i v e  [ 1 1 ] .     T im e  L aten c y :  T h is   f ac to r   r ep r esen ts   t h e  r u n n i n g   ti m e  to   o b tain   an s w er s   f r o m   th e  cr o w d .   Fo r   ea ch   task ,   th e  r eq u e s ter   ca n   s et  th e  ti m e  b o u n d   ( e. g . ,   6 0   s ec o n d s )   to   an s w er   it,  an d   th e  w o r k er   m u s t  an s w er   it   w it h i n   t h e  s tip u lated   ti m e  b o u n d .   T h e  r e q u ester   ca n   also   s et  th e  ex p ir atio n   ti m e  o f   th e  tas k s   if   n ec e s s ar y ,   i.e . ,   th e  m a x i m u m   ti m e  th at  t h e  tas k s   w il l b e  av ailab le  to   w o r k er s   in   th e  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 e  t h e  j o b   an d   th e  q u alit y   o f   th e  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 e  w o r k er   q u alit y .   H u m a n s   m o s t  o f te n   te n d   to   m a k e  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 e  an d   h i g h   atte n tio n .   T h is ,   in   t u r n ,   lead s   i n   t h e  w o r s t  ca s e  to   p r o v id e  in ac cu r ate   r esu lt s   to   th e   r eq u ester .   B es id es,  s o m e  m alicio u s   w o r k er s   a r e  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 e  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 e  th e  q u a lit y   o f   th e  r es u lt s .   Mo r eo v er ,   s o m et i m es  th e  w o r k er   m is u n d er s ta n d s   th e  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 t  o n   th e  q u al it y   o f   th e  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 e  d if f er en t  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 e  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 e  Da t a   T h e  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 e  ( also   k n o w n   a s   n u ll  v al u e)   ar e  b ec o m i n g   v er y   co m m o n   i n   r ea l  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,   a  ce n s u s   d atab ase  th at   allo w s   n u l l  v a lu e s   f o r   s o m e  attr ib u tes .   A   s u r v e y   d atab ase  w h er e  a n s w er s   to   o n e  q u es tio n   ca u s e  o t h er   q u est io n s   to   b e  s k ip p ed .   A ls o ,   a   m ed ical  d ata b ase  th a t  r elate s   h u m a n   b o d y   an al y s t   ( a  s u b s ta n ce   t h at   ca n   b e  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   a  n u m b er   o f   d is ea s es,  o r   p atien t  r is k   f ac to r s   to   a  s p ec if ic  d is ea s e.   T h e  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 e  Da t a ba s e :  g i v e n   a  d atab ase  D( R 1 ,   R 2 ,   . . . ,   R n ),   w h er e  R i   is   a  r elatio n   d en o ted   b y   R i (d 1 ,   d 2 ,  . . . ,   d m ) ,  D   is   s aid   to   b e  in co mp lete   if   an d   o n l y   i f   it  co n tai n s   at  least  a  t u p le  p j   w i th   m i s s i n g   v al u es  i n   o n e  o r   m o r e  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 e  ar e  m an y   r ea s o n s   t h at  m ak e  th e  d atab ase  to   b e  i m p er f ec t  d u e  to   m is s in g   v alu e s .   T h e  d ata   in te g r atio n   f r o m   d i f f er e n t  h u g e  d atab ases ,   d ep en d   o n   w o r k e r   to   in p u t  th e  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 e  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 t  i m p ac t  o f   t h e  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 e  r ate  o f   th e  m i s s i n g   v al u es  is   s m al l  it  m i g h t  s er io u s l y   b ia s   in f er en ce .   Fro m   th e  d atab ase  lit er atu r e  it  ca n   b e  co n clu d ed   th a t  m is s in g   d ata  m ec h a n i s m s   ar e  o f ten   ca te g o r ized   in to   t h r ee   d if f er en t  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 e  ar e  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 t  m o r e  s i m p l y ,   m is s i n g   v al u e s   ap p ea r   to   b e  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 e  m is s i n g   d ata  o cc u r   b ased   o n   s o m e  o b s er v ed   v ar iab les  b u t  n o t   o n   th e  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 t  a ttrib u te  v al u es  ar e   av ailab le,   w h ile  j u s t  s o m e  ar e  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 t  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 e  d ep en d en t  v ar iab le  in   s ta tis tica l te r m s   [ 1 4 ] ,   [ 1 2 ] .   T h e  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 e  q u alit y   o f   th e  d atab ase  as  m o r e  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 e  d ata.   T h er ef o r e,   esti m at in g   t h e  m is s in g   v alu e s   ca n   e n h an c e  th e  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 e  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 e  class i f y   th e  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 e  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 e  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 l  M et ho ds \   Statis t ical  m e th o d s   ar e  th e  b a s e  f o r   m a n y   o f   th e  p r ed ictio n   a p p r o ac h es.  T h e  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 e  d i s tr ib u tio n   o f   t h e  w h o le  d ata   b y   a v o id in g   b ias o n   t h e  d ata  d is tr ib u tio n .   T h e  p r ed icted   v alu e s   m a y   b en e f it  u s er   at  t h e  d atab a s e  le v el  b u t   n o t   at  t h e  t u p le  le v el.   I n   m an y   ca s es  u s er s   ar e  m o r e   co n ce r n   o n   t h e   in d iv id u al  v alu e  o f   t h e  attr ib u te  r ath er   t h an   th e  w h o le  d ata.   T h u s ,   th e s e  s tati s tical  m e th o d s   m a y   n o t  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 e  s tatis tical  m et h o d s   ar e  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 e  w h o le  m i s s i n g   v alu es  f o r   a  g iv en   attr ib u te  ar e  s u b s t itu ted   b y   a  s in g le  v al u e.   T h e  m et h o d s   th at   in v o lv e  s in g le  i m p u tatio n   i n cl u d e  m ea n ,   m ed ia n ,   m o d e,   m ax i m u m   v al u e  i n   th e  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 e  r elev a n t  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 e  th an   o n e  esti m ated   v al u es  ar e  d er iv ed   in   o r d er   to   f ill  in   th e  m is s i n g   v al u e s .   T h e  co m p u tatio n   co s t  o f   th i s   m et h o d   is   h i g h er   t h an   SI,   b u t  it  i s   m o r e  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 e  m is s i n g   v alu e s .   An   i m p o r tan t   ar g u m e n t  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 e  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 e  co r r elatio n s   co u ld   b e  u s ed   to   cr ea te  a  p r ed i ctiv e  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 e  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 e  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 e  d atab ase  w it h   m i s s in g   v al u es   b ased   o n   th e  co m p lete  d atab as e  in s tan ce s .   So m e  o f   t h e  M L   m et h o d s   in v o l v e  p r o b ab ilis tic  ap p r o ac h   to   p r ed ict   th e  m is s in g   v alu e s .   M L   m e t h o d s   ar e  n o n - p ar a m etr ic  as  t h e y   d o   n o t  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 e  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 s  l o n g   ti m e  b ef o r e  g et ti n g   t h e  o p ti m al  v alu e s   b ec au s e  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 e  lo w e s t  r ele v an t  er r o r .   T h er e  ar e   s ev er al  ap p r o ac h es  th at  h a v e  b ee n   p r o p o s ed   w h ich   b elo n g   to   th e  M L   m et h o d s   w h ich   in c lu d e  C 4 . 5 ,   A u to cla s s ,   Fra ctio n in g   C ase s ,   C N2 ,   k - n ea r es t  n eig h b o r   ( k N N)   [ 1 4 ] ,   [ 2 9 ] .     2 . 3 .    Sk y lin e  Q ueries   Sk y li n e  q u er ies   h a v e  b ee n   w i d ely   u s ed   as  a n   attr ac ti v e  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 e  m an y   cr it er ia  ar e  in v o lv ed   in   th e   q u er y   s tate m e n t  to   s elec t  th e   m o s t  s u itab le  a n s w er   th a t   f its   t h e  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 e  s k y li n e  q u er ies  is   t h e  d ec is io n   s u p p o r t  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 e  th ese  s y s te m s   co m b in e  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 e  d e f in itio n s   r elate d   to   s k y li n e  q u er i es  ar e  g iv e n   i n   th e  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 s  p i   an d   p j     D  d ata  s et  w i th   d  d i m en s io n s ,   p i   d o m i n ates   p j  ( th e  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 e  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 e  tec h n iq u e  r etr iev es  t h e  s k y li n e,   S   i n   a  w a y   s u c h   t h at  a n y   s k y l in e  i n   S   is   n o t  d o m i n ated   b y   an y   o th er   t u p le s   in   th e  d ata  s et.     S k y lin e  qu er ies:  s elec t  a  tu p l e  p i   f r o m   t h e  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 e  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 e  d i m en s io n   ( attr ib u te) .   W e  u s e  S skyline   to   d en o te  th e  s et  o f   s k y lin e  t u p le s ,   S skyline   =  { p i   |   p i ,   p j     D ,  p i    p j }.   Co m pa ra ble:   L et  t h e  t u p le s  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 e  n o   m i s s i n g   v al u es  i n   at  least  o n e  id en t ical  d i m e n s io n ;  o th er w i s e  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 t  o f   t h e  s k y li n e  al g o r ith m s   r el y   o n   t h e  as s u m p tio n   o f   co m p leten e s s   o f   t h e  d ata,   i.e .   all   v al u es  o f   p o in ts   ar e  p r esen t  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 t  h o ld .   T h u s ,   co n v e n tio n a l   s k y li n e  al g o r ith m s   ca n n o t   b e  ap p lied   d ir ec tly .   B esid es,  t h e  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 e  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 e  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 e  t u p les  as  s o m e  tu p le s   ar e  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 e  [ 4 ] .       3.   RE L AT E D  WO RK   T h is   s ec tio n   p r esen t s   a n d   r ev ie w s   t h e  p r ev io u s   ap p r o ac h es   r elate d   to   s k y li n e  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 e  q u er ies  i n   i n co m p lete  tr ad itio n al  d atab ase  h av e  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 e  q u er ies  i n   cr o w d - s o u r ci n g   d atab ases   h a v e  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 e  Q ueries f o r  Co m p let e  Da t a   First  to p ic  o f   s k y lin e  q u er ie s   in   co m p lete  d atab ase  h av e  b ee n   ad d r ess ed   w it h   t w o   d if f er e n t  s o lu tio n s   th e  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   a  n e w   o n l in e   s k y li n e  al g o r ith m   ca l led   Nea r est  Nei g h b o r   ( NN) .   I t  is   d i f f e r en t  ab o u t  t h e  last   a lg o r it h m s   th at   co m p u ted   th e   Sk y li n e  i n   b atch ,   b u t  t h e  NN  alg o r it h m   r etu r n s   th e  f i r s t  r esu lts   i m m ed iatel y ,   a n d   f i n d   m o r e  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 e  b ee n   s u g g e s tio n   f o r   s k y lin e  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 e  ( SF S)  [ 1 7 ] ,   B r an ch - B o u n d - S k y l in e  ( B B S)  [ 1 8 ] ,   L in ea r   E li m i n atio n   So r t  f o r   Sk y li n e  ( L E SS )   [ 1 9 ] ,   So r t  a n d   L i m it  Sk y li n e  al g o r ith m   ( SaL Sa)   [ 2 0 ] ,   C ac h e  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 e  Q ueries f o r  I nc o m p let e  Da t a   T h er e  ar e  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 e  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 t  li m ited   t h e  f ir s t  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 e  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 t  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 e  ( SID S)  [ 2 3 ] ,   I n co s k y li n e  [ 1 4 ]   h av e  b ee n   p r o p o s ed   to   s o lv e  th e  i s s u e  o f   p r o ce s s i n g   s k y li n e  q u er ie s   i n   i n co m p lete  d atab ase.   T h e  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 e  th e  is s u e  o f   p r o ce s s i n g   s k y l in e  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 e  is s u e  o f   c y clic  d o m i n a n ce   an d   lo s in g   th e  tr a n s it iv i t y   p r o p er ty   o f   s k y li n e  tech n iq u e.   Ho w e v er ,   n o t  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 e  q u alit y   o f   t h e  s k y lin e  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 e  o n l y   w o r k   t h at  ad d r ess es  th e  is s u e  o f   p r ed ictin g   th e   m i s s in g   v alu e s   o f   th e  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 e  m is s i n g   v alu e s   b ef o r e  r etu r n in g   th e   s k y li n es to   th e  u s er .   A d d itio n a ll y ,   th e  m o s t o f   w o r k s   d esi g n e d   to   b e  u s ed   in   tr ad itio n al  d atab ases   o n l y .     3 . 3 .       Sk y lin e  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 e  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 t  n o t  b e  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 e  b e s t  o f   o u r   k n o w led g e,   th er e  is   n o t  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 t  o f   th e s e  s t u d ies  co n ce n tr ate  o n   d esig n in g   s k y li n e  s tr ate g ies  to   est i m a te  t h e  m is s in g   v a lu e s   o f   s k y li n e  r esu lt s   en s u r i n g   lo w   p r o ce s s in g   co s t  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 e  esti m ated   r es u lts .   I n   [ 8 ] ,   [ 9 ]   th ey   h a v e  p r o p o s ed   a  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 e  id ea   o f   t h e  p r o p o s ed   ap p r o ac h   r elies  o n   u tili zin g   a  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 e  m i s s i n g   v al u e s   f o r   all  tu p les.  I t  al s o   ex p lo its   th e  co n ten t s   o f   t h e  cr o w d   f o r   s o m e  ca s es  to   i m p r o v e   ac cu r ac y   o f   th e  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 e  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 e  p r o ce s s   o f   s k y l in e  w h ic h   ar e  m in i m izin g   th e  m o n etar y   co s t,   r ed u cin g   th e  late n c y ,   a n d   i m p r o v in g   th e  ac c u r ac y   o f   a  cr o w d - s o u r ce d   s k y lin e.   A l th o u g h   th e  w o r k   ass u m ed   th at  t h e  p r o ce s s   o f   v al u e   esti m atio n   b y   t h e  cr o w d   w il l  b e  ap p lied   o n   a  s et  o f   v ir tu al  at tr ib u tes.  W h ic h   m ea n s   th e  i n itial   d atab ase  is   co m p let e,   b u t  w it h   i n s u f f icien t   d ata  th at  m i g h t  n o t  h elp   to   p r o v id e  a n   ac cu r ate  a n s w er s   f o r   s k y li n e  q u er ies.  T h er ef o r e,   u til izin g   t h e  cr o w d   d atab as e  b y   g e n er ati n g   s o m e   r elev a n t  v ir tu al  attr ib u tes  a n d   th eir   v al u es a r e  p r ed icted   b y   t h e  cr o w d   w o r k er s   to   s u p p o r t th e  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 e  p r ese n t  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 e  d etails  s tr u ct u r e  o f   t h e  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 e  ass u m e   a  tr ad itio n al   lo ca l  d at a  s et    co n tai n s   tu p le s   w it h   s o m e  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 e  q u er y   w it h   s o m e  p r ed ef i n ed   p r ef er en ce s .   T h e  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 e  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 e  ex p lain i n g   in   t h e  f o llo w in g   s u b s ec tio n .     4 . 1 .       D a t a   F iltr a t io n    T h is   co m p o n e n t  an al y ze s   th e  in itial  d atab ase  in   o r d er   to   id e n ti f y   a n d   r em o v e  th e  u n n ec es s ar y   tu p le s   in   th e  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 e  d o m in ated   t u p les  b y   ap p l y i n g   t h e  s k y l in e  p r o ce s s   o n   th e  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 e  a m o u n t  o f   d ata  in   th e  n e x t  p r o ce s s es.   Ma n y   d o m in a ted   tu p les  ca n   b e  s af el y   r e m o v ed   as  t h e y   h a v e  n o   co n tr ib u tio n   i n   th e   s k y l i n e  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 e  m o n etar y   co s t a n d   th e  ti m e  late n c y   to   es ti m ate  t h e  m i s s i n g   v al u es f r o m   t h e  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 e  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 r  a nd   At t ribute   Ana ly ze r   T h e  aim   o f   t h i s   co m p o n en t  is   to   g en er ate  a  s a m p le  f r o m   t h e  in itial  d atab ase  to   b e  u s ed   f o r   an al y z in g   th e  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 e  r elatio n s h ip   b et w ee n   t h e  attr ib u te s   h e lp s   to   esti m ate  t h e  m is s i n g   v al u e s   i n   t h e  t u p les.  I t  is   i m p r ac tical  to   d o   t h is   p r o ce s s   o v er   t h e  w h o le  d ata  s i n ce   t h e  n u m b er   o f   tu p les  i n   th e  in i tial  d atab ase  ar e  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 t  i n cu r   h i g h   o v er h ea d   an d   co n s u m e  s i g n i f ican t  a m o u n t  o f   ti m e.   He n ce ,   ex tr ac tin g   a  s m al l   p o r tio n   o f   th e  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 e  p r o ce s s   an d   r ed u ce   th e  co s t  w it h o u t   co m p r o m is i n g   t h e  q u alit y   o f   th e  esti m ated   v a l u es.  T h e  s a m p le  w ill  b e  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 e  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 e  n e x t s u b s ec tio n .           Fig u r e  1 .   T h e  Pro p o s ed   Mo d el   o f   Sk y li n e  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 e  F un ct io n a l D ependencie s   G e nera t o r    T h e  ai m   o f   t h i s   co m p o n e n t   is   to   d er iv e  t h e  r elatio n s h ip   b et w ee n   t h e  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 e  v a lu e s   o n   th e  s elec ted   s a m p le  tr y i n g   t o   ca p tu r e  th e  r elatio n s h ip s   b et w ee n   attr ib u te s   an d   d eter m in e  h o w   th e  v al u e  in   o n e  attr ib u te  af f ec ts   t h e  v alu e s   o f   th e  o t h er   attr ib u tes.      Def ini t io n:  Ap pro x i m a t e  F u nct io na l  Depen dency   ( AF D)   Giv e n   a  r elatio n   R ,   a   s u b s et   X   o f   its   d i m en s io n s ,   an d   a  s i n g le  d i m en s io n   d i   o f   R ,   w e  s a y   th a t  th er e  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   X  an d   d i,  d en o ted   b y   Xf         d i ,   if   th e  co r r esp o n d in g   f u n ctio n al  d ep en d en c y   X         di   h o ld s   o n   all  b u t   a  s m a ll  f r ac tio n   o f   th e   t u p les o f   R.   T h e  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 e  A FD,  w e  f ir s t   d iv id e  th e  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 e  f ir s t  s e t  co n tain s   all  v alu e s   t h at  m is s i n g   i n   t h e  id en t ical  attr ib u te  t h at  n ee d s   to   b e  esti m ated ,   a n d   th e  s ec o n d   s et   co n tain s   th e  r e m ai n in g   v alu es  ( co m p lete) .   T h e  v al u es  o f   th e  s ec o n d   s et  ar e  an a l y z ed   to   ca p tu r e  th e  r elatio n s h ip s   b et w ee n   t h e  attr i b u tes o f   t h e  r elatio n .   T h en   t h e  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 w  th e  v a lu e  o f   o n e  attr ib u te  in f l u en ce s   th e  v al u es  o f   th e  o t h er   attr ib u tes.  T h en   to   en s u r e  t h a t  th e  d er iv ed   A FD   r ef lects t h e  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 e  ai m   o f   th i s   co m p o n e n t  is   to   ch o o s e  th e  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 e  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  t h e  v alu e   o f   d i   i n f l u e n ce s   t h e  v al u e  o f   d j .   T h e  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 e  | . |   r ef er s   to   t h e  n u m b e r   o f   d is ti n ct  v al u es.  T h e  v al u e  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 e  in   d j   is   as s o ciate d   w it h   a  u n iq u e  v alu e  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 t  is   r esp o n s ib l e  to   s u b s tit u te  t h e  m is s i n g   v a lu es  o f   t h e  d atab ase  w i th   s o m e  i m p u ted   v alu e s   d er iv ed   u s in g   t h e  a v ail ab le  d ata  o f   t h e  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 e  v al u e  e x is ts   w it h   s e v er al  alter n ati v e  v al u es  b y   r ep lace   th e  m i s s i n g   v alu e s   w i th   t h e  e s ti m ated   v a lu e s .   I n   th is   p r o ce s s   t h er e  m i g h t  b e  m an y   es ti m ated   v al u es  f o r   a  d i m en s io n   t h at  n ee d   to   b e  c o n s i d er ed .   H o w ev er ,   in   s o m e  ca s es  th er e  m i g h t  b e  m o r e  th an   o n e  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 e  r esu lts   o f   t h e  AFDs   ar e  co m b in ed   to   esti m ate  t h e  m is s in g   v al u e.       4 . 6 .       Rela t iv e  er ro r   a nd   t hresh o ld v a lue ident if ier   T h is   co m p o n en t  co n ce r n s   o n   ch ec k in g   t h e  ac cu r ac y   o f   t h e  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 l  m is s i n g   v a lu e s   h as   b ee n   es ti m ated   i n   la s t  s tag e   o f   t h e  p r o p o s ed   m o d el,   th e  s y s te m   co m p u tes  th e  r elat iv e  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 e  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 e  m is s i n g   v al u es   in   o n e  o r   m o r e   d i m en s io n s   a n d   th e  r ea l  v al u e s   w h e n   t h e  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 e  r elati v e  er r o r   r ate  is   lar g er   t h a n   t h e  u s er   d ef i n ed   th r es h o ld   v al u e,   th en   th e  e s ti m ated   v alu e s   w i ll  b e  d is ca r d ed .   Oth er w i s e,   a cc ep t  th e  esti m ated   v al u es  a n d   u s e  th e m   i n   t h e   s k y li n e  r esu lts .   I n   o n e  ca s e,   t h is   h elp s   u s   to   b en ef i t  f r o m   t h e  ex i s ti n g   d ata  i n   p r ed icatin g   th e  m is s i n g   v al u e s   an d   r ed u ce   t h e  a m o u n t  o f   d ata  to   b e  g en er ated   f r o m   t h e  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 t  b y   av o id i n g   s en d in g   m an y   r e q u e s t  to   t h e  cr o w d   w o r k er s .   I n   o t h er   ca s e,   if   t h e  q u ali t y   o f   esti m ated   v al u es  is   lo w ,   t h en   w e  m a y   r e f er   to   th e  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 e  w it h in   t h e  u s er   d ef i n ed   th r esh o ld   v al u e.   Hen ce ,   w e  ca n   co n cl u d e  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 e  co s t a n d   th e  q u ali t y   o f   th e  r es u lt s   h av e  b ee n   m ai n tai n ed .     4 . 7 .       An a cc ura t e  esti m a t e  v a lues   g ener a t o r    T h is   co m p o n e n t  i s   r e s p o n s ib l e  to   g e n er ate  e s ti m ated   v al u es   f o r   t h o s e  s k y li n e s   w it h   in co m p lete  d ata.   T h e  p r o c ess   s tar ts   b y   ev a lu at in g   th e  q u alit y   o f   t h e  es ti m at ed   v alu e s   th r o u g h   co m p ar i n g   th e  r elati v e  er r o r   b et w ee n   t h e  r ea l  m is s in g   v al u e  an d   th e   esti m ated   o n e   ag ai n s t  t h e  u s er   d ef i n ed   t h r esh o ld   v alu e.   I f   th e  r elat iv e   er r o r   p r o d u ce d   less   th a n   th e  th r es h o ld   v alu e,   t h en   t h e  esti m ated   v al u es  w il l  b e  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 e  ig n o r ed   an d   atte m p t   to   ex p lo it  t h e  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 e  ar g u e  t h at  u ti lizi n g   th e   lo ca l  d ata  i n   t h e  d atab ase  h elp s   to   e s ti m a te   a  lar g e  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 e  v alu e  esti m ated   ar e  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 e  d i m e n s io n s   an d   v ia  id en t i f y in g   t h e  s tr e n g th   o f   t h e  p r o b ab ilit y   co r r elatio n   b et w ee n   th e  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 e  d ata  is   in d ep en d en t,  t h e n   it  m i g h t  b e  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 e  r e q u est  t h e  cr o w d   t o   g en er ate  m o r e  p r ec is e  e s ti m at ed   v alu e s   w h ic h   r es u lt s   i n to   a  r elativ e  er r o r   b elo w   th e  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 t  h as  t w o   s u b - co m p o n e n ts   wh ich   ar e  lo ca l  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 e  f u r t h er   ex p lai n ed   in   t h e  f o llo w in g .       4 . 8 .       Sk y lin e  identif ier   T h is   co m p o n en t  is   th e   last   co m p o n en t  i n   t h e  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 e  d atab ase  an d   g et  th e  q u er y   r e s u l t.  T h e  p air w i s e  co m p ar is o n   p r o ce s s   w ill   b e  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 e  r elev a n t  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 e  q u er y   i s   th e  p r o ce s s   o f   id en ti f y in g   t h e  n o n - d o m in a ted   tu p les  in   t h e  d atab ase  an d   r etu r n i n g   th e m   to   t h e  en d   u s er   b ased   o n   th e  u s er   g i v e n   p r ef er en ce .   I t  is   o n e  o f   th e  m o s t  p r ed o m i n an t   ty p e  o f   p r ef er en c e   q u er ies  th at  h a v e  b ee n   in tr o d u ce d   in to   th e  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 e  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 e  d ata.   T h e  m o d el   d escr ib es  th e  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 e  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 e  n u m b er   o f   p air w i s e  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 e  co s t   o f   s k y li n e  q u er y   p r o ce s s i n g   an d   m in i m ize  t h e  t i m e   late n c y .   M o s t   i m p o r ta n tl y ,   t h e  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 e  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 e  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 e  m i s s i n g   v al u e s   in   t h e  d atab ase  w h ic h   in   co n s eq u e n ce   p r o v id e  m o r e  p r ec is e   r es u lts   h elp i n g   u s er   to   m a k e  t h e  m o s t  ap p r o p r iate  d ec is io n .   W e  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 e  an d   ef f icie n c y   in   p r o v id e  p r ec is e  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 e  late n c y   w ill b e  ta k en   i n to   co n s id er atio n   w h e n   d ev elo p   th e  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 e  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 s  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:   A  su rv e y , ”   IEE E  T ra n sa c ti o n s  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 r  in c o m p lete   a u to n o m o u s  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 l  J o u rn a l  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 l  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 r  in c o m p lete   d a t a , ”   t h e   2 4 t h   In tern a ti o n a l  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 s  wit h   c ro wd so u rc in g , ”   A CM   S IG M OD   In tern a ti o n a l  Co n f e re n c e   o n   M a n a g e m e n t  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 s  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 :  A  sy ste m  fo r  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 s  o v e r  in c o mp lete   d a t a - e rr o r  mo d e ls  fo r  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 l  Co n f e re n c e   o n   Co n c e p tu a l  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 s  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 r  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 l  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 s  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 s  f o r  d isp a ra te  d a ta,”  Ame ric a n   J o u rn a l  o f  I n telli g e n t  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 s  o f   sk y li n e s  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 l  C o n f e re n c e   o n   Dig it a l  En ter p rise   a n d   I n f o rm a ti o n   S y ste m s  (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 l  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 m  f o r  sk y li n e   q u e rie s,”   th e   2 8 t h   In tern a ti o n a l  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 l  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 m  fo r  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 t  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 l  v e c to r  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 t  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 l  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 t  (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 t  a n d   M .   M a g n a n i,   “ Ef fi c i e n t  c a c h i n g   f o r  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 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 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 r  in c o m p lete   d a ta,”  In ter n a ti o n a l  J o u rn a l  o f  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 s  fo r  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 t  a p p r o a c h   f o r  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 l  d a tab a se , ”   Ara b i a n   J o u rn a l  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 s  a n d   P .   Cu d ré - M a u r o u x ,   “ T h e   d y n a mic s  o f  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 l  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 s  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,   “ A  Fra me wo rk   fo r  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 r  in c o mp let e   d a ta   i n   c lo u d   e n v iro n me n t  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 l  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 r  b ig   d a ta  p ro c e ss i n g , ”   EURA S IP   J o u rn a l  o n   A d v a n c e s in   S ig n a l  Pro c e ss in g ,   2 0 1 6 ,   DO I  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 D  s tu d e n t  a t  I n 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 .   S h e   e a rn e d   h e r  B. S c .   a n d   M . S c .   d e g re e s  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 r  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 t  p ro f e ss o r  a t  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 r  o f  Co m p u te r  S c ien c e   (2 0 0 9 )  a n d   P h . D  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 t  o f  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 s  ( 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 t  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  i  V irg il i,   T a rra g o n a ,   S p a in   a n d   P h D  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 l  Un iv e rsit y   o f   Uz b e k istan .   He   w a s  a   p o stg ra d u a te  re se a rc h e r  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 r  a t  De p a rtme n t  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 l  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 l  lan g u a g e s  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 t  a t   In ter n 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   h a s  re c e iv e d   h is  M a ste r  o f   Co m p u ter  A p p li c a t io n s  ( 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 t  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 t  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.