Efficient query processing over highly distributed data
Ακριβή Βλάχου · 2008
in GreekH paroÔsa didaktorik diatrib epikentr¸netai ston q¸ro thc epexergasÐac mh paradosiak¸n tÔpwn eperwt sewn se eurèwc katanemhmèna dedomèna ìpwc aut pou sunant¸ntai se dÐktua omìtimwn (peer-to-peer).Ta dÐktua omìtimwn problloun wc èna dunamikì montèlo gia thn anaz thsh kai diaqeÐrish terstiwn posot twn dedomènwn katanemhmènwn se anexrthtec phgèc dedomènwn.En¸diforec arqitektonikèc omìtimwn susthmtwn èqoun protajeÐ sth sqetik bib-liografÐa, se aut th diatrib brÐskontai sto epÐkentro ta adìmhta dÐktua omìtimwn kìmbwn.Orismènoi omìtimoi, pou onomzontai super-peers, èqoun eidikì rìlo lìgw twn idiaÐterwn qarak-thristik¸n touc, ìpwc diajesimìthta, stajerìthta, auxhmènh apojhkeutik dunatìthta kai meglo eÔroc z¸nhc, kai diamorf¸noun èna super-peer dÐktuo.Melet¸ntai diforoi prohgmènoi telestèc eper¸thshc, ìpwc h anaz thsh me bsh thn omoiìthta, oi top-k kai skyline eperwt seic, kaj¸c kai o apodotikìc upologismìc aut¸n se èna super-peer dÐktuo, ìpou ta dedomèna eÐnai orizìntia katatmhmèna stouc omìtimouc.Gia thn epexergasÐa eperwt sewn, oi eperwt seic pr¸ta dromologoÔntai sto dÐktuo twn super-peers, kai sth sunèqeia prowjoÔntai se ekeÐnouc touc omìtimouc pou èqoun sqetik dedomèna.Se aut th diatrib exetzetai h apodotik epexergasÐa eperwt sewn se mia tètoia eurèwc katanemhmènh arqitektonik , qrhsimopoi¸ntac plhroforÐa dromolìghshc se epÐpedo super-peers, me stìqo thn elaqistopoÐhsh twn omìtimwn pou ja epex-ergastoÔn thn eper¸thsh kai tou ìgkou twn dedomènwn pou ja metaferjoÔn.Eidikìtera, gia thn apodotik epexergasia eperwt sewn se adìmhta sust mata omìtimwn kìmbwn, eÐnai shmantikì na lambnontai upìyin ta eidik qarakthristik touc, kai kurÐwc h èlleiyh kajolik c gn¸shc thc plhroforÐac.Skopìc einai h sqedÐash katllhlwn eurethrÐwn dromolìghshc (routing indexes), ¸ste me th qr sh eurethrÐwn, kje kìmboc na dromologeÐ epilektik thn eper¸thsh, mìno se geÐtonec twn opoÐwn ta stoiqeÐa eÐnai pijanì na summetèqoun sto telikì apotèlema thc eper¸thshc.Epeid ta euret ria genik parèqoun mÐa prosèggish twn pragmatik¸n dedomènwn, potè ènac omìtimoc den mporeÐ na eÐnai apolÔtwc sÐgouroc gia to an ènac geÐtonc tou ja suneisfèrei ìqi sto apotèlesma miac sugkekrimènhc eper¸thshc.Upì thn paradoq ìti endiaferìmaste na anakt soume to akribèc apotèlesma kai jewr¸ntac èna statikì stigmiìtupo diktÔou, prèpei na rwthjoÔn ìloi oi omìtimoi gia touc opoÐouc den eÐmaste sÐgouroi, me apotèlesma na mporeÐ na ftsei se exantlhtik anaz thsh tou diktÔou.Gia autì to lìgo eÐnai shmantik h apodotik sqedÐash twn eurethrÐwn.Oi basikoÐ stoqoÐ twn eurethrÐwn dromolìghshc eÐnai:• ElaqistopoÐhsh twn omìtimwn kìmbwn stouc opoÐouc apostèletai h eper¸thsh.Gia thn epiteux tou stìqou autoÔ, skopìc eÐnai h er¸thsh mìno twn omìtimwn kìmbwn pou sumblloun sto telikì apotelèsma.• ElaqistopoÐhsh tou ìgkou dedomènwn pou metakineÐtai sto dÐktuo.Gia thn meÐwsh tou ìgkou pou metakineÐtai sto dÐktuo, skopìc eÐnai h metafor mìno twn dedomènwn pou sumblloun sto telikì apotelèsma.• ElaqistopoÐhsh tou qrìnou epexergasÐac se kje omìtimo kìmbo.Gia thn meÐwsh tou upologis-tikoÔ kìstouc se kje omìtimo kìmbo apaiteÐtai h apodotik epexergasÐa thc eper¸thshc me th qr sh topik¸n eurethrÐwn.• ElaqistopoÐhsh tou olikoÔ qrìnou apìkrishc.O sunolikìc qrìnoc apìkrishc miac eper¸thshc exarttai ousiastik apì to pl joc twn erwthjèntwn omìtimwn kìmbwn, apì ton ìgko dedomènwn pou metafèretai sto dÐktuo kai apì to qrìno pou qreizetai gia ton upologismì thc eper¸thshc topik.Analutikìtera, h suneisfor thc didaktorik c diatrib c se epimèrouc tomeÐc eÐnai: Apodotik epexergasÐa top-k eperwt sewn se eurèwc katanemhmèna dedomèna.H proteinìmenh prosèggish efarmìzetai se orizìntia katatmhmèna dedomèna pou an koun se èna sÔnolo suner-gatik¸n omìtimwn kìmbwn.Se antÐjesh me thn uprqousa ereunhtik ergasÐa sto q¸ro, h opoÐa upojètei kjeth kattmhsh twn dedomènwn (tupik perÐptwsh se plhroforiak sust mata sto DiadÐktuo) jewreÐ th qr sh teqnik¸n proswrin c apoj keushc, h proteinìmenh prosèggish eÐnai eurÔtera efarmìsimh kai uposthrÐzei diaforetikèc kai ìqi upoqrewtik epanalambanìmenec eperwt seic poll¸n qrhst¸n.ApodeiknÔetai h orjìthta tou algìrijmou kai ìti eÐnai bèltistoc wc proc to pl joc twn dedomènwn pou apaiteÐ na metaferjoÔn kat thn epexergasÐa thc eper¸thshc kaj¸c kai wc proc to sÔnolo twn kìmbwn pou erwtoÔntai.EpexergasÐa skyline eperwt sewn se eurèwc katanemhmèna dedomèna.Kaj¸c oi skyline eperwt seic èqoun proselkÔsei to endiafèron thc ereunhtik c koinìthtac thc diaqeÐrishc dedomènwn teleutaÐa, proteÐnontai diforoi algìrijmoi gia thn apodotik epexergasÐa aut¸n se peribllon omìtimwn diktÔwn.UposthrÐzontai eperwt seic pou aforoÔn uposÔnola twn diajèsimwn diastsewn.Oi proteinìmenec parallagèc tou algìrijmou mporoÔn na efarmostoÔn ìtan eÐnai epijumht h elaqistopoÐhsh tou qrìnou apìkrishc (enallaktik) h elaqistopoÐhsh tou katanal¸menou eÔrouc z¸nhc tou diktÔou.Anaz thsh me bsh thn omoiìthta se metrikoÔc q¸rouc gia katanemhmèna dedomèna.ProteÐnetai èna plaÐsio gia apodotik epexergasÐa eperwt sewn me bsh thn omoiìthta, ìtan ta dedomèna brÐskontai se kpoio metrikì q¸ro, kai eÐnai disparta se kìmbouc tou diktÔou.ProteÐnontai algìrijmoi gia apodotik epexergasÐa eperwt sewn diast matoc tim¸n (range queries), ¸ste na eÐnai dunatì na epistrafoÔn akrib apotelèsmata.Epiprìsjeta uposthrÐzontai eperwt seic kontinìterou geÐtona (k-nearest neighbor queries), oi opoÐec metatrèpontai se eperwt seic diast matoc tim¸n me bsh kpoia ektim¸menh aktÐna.EpÐshc, paratÐjetai ekten c peiramatik melèth, me th mèjodo thc prosomoÐwshc, pou anadeiknÔei thn uyhl apìdosh kaj¸c kai thn efiktìthta thc prosèggishc.Kattaxh twn skyline apotelesmtwn qwrÐc thn apaÐthsh rht¸n protim sewn qr sth.Gia thn antimet¸pish tou probl matoc tou uperbolik meglou megèjouc apotelesmtwn gia skyline eperwt seic, idiaÐtera stic uyhlèc diastseic, proteÐnetai mia automatopoihmènh mèjodocwhich are similar to a query point, when a metric distance function dist measures the objects' (dis)similarity.More formally, a metric space is a pair M = (D, dist), where D is a domain of feature values and dist is a distance function with the following properties:1. dist(p, q) > 0, q = p and dist(p, p) = 0 (non negativity), 2. dist(p, q) = dist(q, p) (symmetry),