Önszerveződő adatbázisok

Önszerveződő adatbázisok

High Speed Networks Laboratory

1/40

Önszerveződő adatbázisok Hosszu Éva

Önszerveződő adatbázisok 1.

Paradigmaváltás az adatbázisokban • Megtervezett adatbázis → Evolúció alkotta adatbázis

2. 3.

Önszerveződő adatbázis: struktúra, lekérdezés Struktúra: a hálózatot meghatározó jellemzők • Méret, átmérő • Kisvilág tulajdonság • Skálafüggetlen hálózatok • Preferenciális kapcsolódás

4.

Lekérdezés • Lekérdezés önszerveződő adatbázisokban • Internetes keresőmotorok működésének alapjai

2/40


Paradigmaváltás az adatbázisokban • Mennyi zenét tárolsz a

számítógépeden? • Régen: rengeteg zene a

számítógépen • Hatalmas adatbázisban • Viszonylag struktúrálva • Most: Kevés zene a gépen, csak

amire azonnal szükség van • Túlnyomó részben: YouTube & Google • Egy struktúrálatlan halmazból keressük ki 3/40


Paradigmaváltás az adatbázisokban • Eddig • Relációs adatbázis • Elosztott adatbázis • Lekérdezés: erősen megnövelte a

kommunikációs költségek részarányát az adatbázis-kezelés költségein belül • Ötlet: próbáljuk meg az adatokat a felhasználás közelében elhelyezni. • Osztott adatbázisok. • Az osztott adatbázis egy fizikailag

megosztott, de logikailag egységes adatbázis.

4/40


Amerre mozdul a világ: • Megtervezett adatbázis → evolúció alkotta adatbázis • Elosztott adatbázisok: • A kommunikációs költségek csökkenése. • Mindenki a számára ismerős adatokat gondozza. • Egy-egy csomópont kiesése esetén a többi adatai továbbra is

elérhetőek. • Lehetséges a moduláris tervezés, a rugalmas konfigurálás. • Rugalmasabb adatstruktúra kell

• Önszerveződő adatbázisok: • A kapcsolódást nem egy központi egység határozza meg • A csomópontok saját maguk döntik el, hova kapcsolódnak 5/40




2. 3.

Önszerveződő adatbázis: struktúra, lekérdezés Struktúra: a hálózatot meghatározó jellemzők • Méret, átmérő • Kisvilág tulajdonság • Skálafüggetlen hálózatok • Preferenciális kapcsolódás

4.


6/40


Mit az önszerveződő adatbázis? • A szó tág értelmében • Önszerveződő adatbázis = (struktúra,lekérdezés) • Az adatbázis önszerevződő jellege meghatározza a kialakuló topológiát • A topológia meghatározza, milyen a hatékony keresés • Önszerveződő adatbázis példák: • Internet • Blogok • Google Fordító • Szocális hálózat • P2P hálózat • Folding@home

7/40


Önszerveződő hálózat: Az Internet • Általános értelemben: Nagy bonyolult hálózatok • Hálózat komplexitása • Sok csomópont • Sok kapcsolat • Heterogén csomópont típusok és kapcsolattípusok • Tisztán kivehető tendencia: kommunikációs hálózatok egyre

bonyolultabbakká válnak • Az Internet fejlődési trendek • • • •

Felhasználók számának drámai növekedése Kicsi mobil eszközök Szerteágazó szabványok, sok gyártó  Heterogén eszközök Virtuális hálózatok fizikai hálózakon – VPNs, virtual ISPs

• Milyen struktúra lakozik a komplexitás mögött?

8/40


Pillanatfelvételek • A hálózatok dinamikusak • Még jó, annyira gyorsan változnak az igények • Jelenleg nincs lehetőség a dinamizmus vizsgálatára nagy

léptékben • Legtöbb adatbázis csak a pillanatnyi állapotot tárolja • Ezért egy-egy elemzés csak egy pillanatfelvétel • Előfordulnak statisztikai hibák • Néha később módosított eredmények

9/40




2. 3.

Önszerveződő adatbázis : struktúra, lekérdezés Struktúra: a hálózatot meghatározó jellemzők • Méret, átmérő • Kisvilág tulajdonság • Skálafüggetlen hálózatok • Preferenciális kapcsolódás

4.


10/40


Számunkra jelenleg lényeges paraméterek 1. Hálózat méret: Csomópontok száma • Ezres, milliós, esetleg milliárdos méretek esetén lehet statisztikai adatokkal jól jellemezni egy hálózatot 2. Klaszterezettség: “Csoportosulás” mértéke • A szomszéd node-jaim kapcsolódnak-e egymáshoz? Ha 1 akkor mindig, ha 0 akkor soha! 3. Átmérő: Kis átmérő, rövid utak, “kisvilág” jelleg • Egy rácsban igen nagy átmérők lehetnek, míg pl. a teljes gráf átmérője 1. 4. Hasonlósági paraméter (γ): Mennyire hasonló a

szerepük? (skálafüggetlen szerkezet) •

Ha a szám magas, akkor az egyének nagyon hasonlítanak, ha alacsony akkor (~ 2) akkor erősen eltérő szerepek vannak

5. Fokszámeloszlás: a csúcsok mekkora hányadának k a

fokszáma? • Egyenletes? Binomiális? Valami más?

11/40


Méret és átmérő • Mekkora egy önszerveződő adatbázis? • Csomópontok száma: néhány tíz – milliárdok • Mekkora az adatbázis átmérője? • 1929: Karinthy Frigyes – Láncszemek • Hat lépés távolság • 1967: Milgram—kísérlet (a másik) • Levélküldés nagy távolságra (szociológiai, földrajzi), véletlenszerűen választott emberek • Információk a célszemélyről • Személyes ismeretség esetén azonnal a célhoz • Egyébként olyanhoz aki valószínűleg személyesen ismeri+levél a Harvardra

12/40


Milgram kísérlete (további részletek) • • •

Néha 1-2 lépés elég volt néha kilenc kellett 296 levélből 232 nem ért célba A maradékból az átlagos távolság 5.5-nek adódott (ellentmondott a tapasztalatokkal, és várakozásokkal)

• Az utolsó személy igen sokszor ugyanaz • Legtöbbször gyorsan földrajzi közelbe értek, ahol köröztek, amíg rést nem találtak a célszemély belső köreibe • Problémák • Kevés célbeérkező levél • Emiatt hosszabb láncok kevésbé vannak jelen (alábecslés)

• Többször ismételték •

2002-ben e-mail verzió

•

2008, Microsoft .NET Messenger Service: 6.6

• Hatlépésnyi távolság

13/40


Átmérő

• Példa: Rubik-kocka állapotai

14/40


Átmérő •

15/40


The Anatomy of the Facebook Social Graph • Ugander, Karrer, Backstrom, Marlow • arXiv: 1111.4503v1 [cs.SI] • 2011. májusi állapot elemzése • Aktív felhasználók: 1. Bejelentkezett a vizsgálatot megelőző 28 napban 2. Van legalább 1 ismerőse • 721 millió aktív felhasználó (a Föld

lakossága akkor 6.9 milliárd) • 68.7 milliárd kapcsolat • átlagosan 190 ismerős

16/40


Felhasználók közti átlagos távolság • 4.7 lépés távolság • USÁ-n belül: 4.3

• Független

tanulmány: átmérő ~40 • Az átmérő

önmagában megtévesztő

17/40


Csoportosulás mértéke • A weboldalak jellemzően szoktak egymásra mutatni • Minél több közös oldalra mutatnak, annál nagyobb valószínűséggel

egymásra is • Melyik tűnik hihetőbbnek mint weboldalak hálózata? Miért?

18/40


Klaszterezettségi együttható • Globális: • 𝐶=

ℎá𝑟𝑜𝑚𝑠𝑧ö𝑔𝑒𝑘 𝑠𝑧á𝑚𝑎 𝑡𝑟𝑖𝑝𝑙𝑒𝑡𝑒𝑘 𝑠𝑧á𝑚𝑎

• a háromszögek

számának aránya ahhoz képest, hogy mennyi lehetne

C=1

• Lokális:

a kék csúcsra vonatkozóan ckék=1 • 𝐶𝑖 =

2∗𝑠𝑧𝑜𝑚𝑠𝑧é𝑑𝑜𝑘 𝑘ö𝑧ö𝑡𝑡𝑖 é𝑙𝑒𝑘 , 𝑁 𝑖 ∗(𝑁 𝑖 −1)

ckék=1/3

ckék=0

ahol N(i) = #{i szomszédai} 19/40


Egy adatbázisban

20/40


Kisvilág-tulajdonság •

21/40


Fokszámeloszlás • A csúcsok mekkora hányadának k a fokszáma • nk = hány k fokszámú csúcs van 𝑛 • P(k) = k, n a csúcsok száma 𝑛

• hisztogram

22/40


Fokszámeloszlás • Binomiális

𝑛

• 𝑃 𝑘 = 𝑘 𝑝𝑘 (1 − 𝑝)𝑛−𝑘 • Véletlen hálózat • Nyerőgép

• Hatványfüggvény • 𝑃 𝑘 ~ 𝑘 −γ • γ: Hasonlósági paraméter • Önszerveződő hálózatok

23/40


Skálafüggetlenség • A fokszámeloszlás hatványfüggvényt követ

24/40


Skálafüggetlenség szemléletesen 1.

A hálózatra rázoomolva önhasonló szerkezet • Pont így van a természetben is

2.

Nem heterogén szerepű csomópontok • Néhány központ, sok kis node

25/40


Valós hálózatok

26/40


Hogyan kapcsolódnak új pontok az adatbázishoz? • Egy már meglévő adatbázis melyik

pontjához fogunk kapcsolódni? • P2P hálózatban melyik fájlt töltöd le? • Egy nemzetségen belül melyik fajok szaporodnak el? • Minél népszerűbb • Népszerűség ~ minél több

kapcsolata van eddig

27/40


Preferenciális kapcsolódás • Preferenciális kapcsolódás  A kapcsolódáshoz a jelölt esélye arányos a fokszámmal  Nagyobb fokszámú csúcshoz nagyobb eséllyel kapcsolódik  i csúcsra: 𝑝𝑖 =

𝑓𝑜𝑘𝑠𝑧á𝑚 2∗é𝑙𝑒𝑘 𝑠𝑧á𝑚𝑎

• A gazdag egyre gazdagabb

lesz • Növekedéssel együtt: skálafüggetlen hálózat

28/40


Szűkebb értelemben vett önszerveződő hálózatok

• Speciális értelemben 1. Nem véletlenszerű kapcsolatok, “csoportosuló” 2. Kis átmérő, rövid utak, kisvilág 3. Skálafüggetlen szerkezet: erősen változó szerepek a hálózatban

29/40




2. 3.

Önszerveződő adatbázis : struktúra, lekérdezés Struktúra: a hálózatot meghatározó jellemzők • Méret, átmérő • Kisvilág tulajdonság • Skálafüggetlen hálózatok • Preferenciális kapcsolódás

4.


30/40


Hogyan működnek a keresőmotorok?

31/40


Internetes keresőmotorok • A keresőmotorok két fő funciója 1. Crawling és az oldalak térképének felépítése 2. Válasz a lekérdezésre

1.

Crawling & Indexing • A weben levő dokumentumok, fájlok, oldalak bejárása és indexelése • Indexelés ~ tárgymutató egy könyv végén

2. Válaszadás a felhasználói lekérdezésre • Releváns oldalak listája • Sorrend

32/40


Honnan tud a keresőmotor egy oldalról? 1.

Megmondjuk, hogy létezik • Home page URL-je • www.google.com/addurl • search.yahoo.com/info/submit.html • search.live.com/docs/submit.aspx • XML oldaltérkép

2.

Ha egy másik oldal mutat rá: keresőrobotok beindexelik • Struktúra miatt működik • A kapcsolatok mentén a keresőmotor bejárja = crawling • Ha találnak egy új oldalt: részleteket tárolnak

33/40


Egy Google keresés

34/40


Adjunk választ! • A keresőmotor egy válaszadó gép • Háromféle keresés: • "Do" Tranzakciós keresés – valami végrehajtása: repülőjegy vásárlás, zenehallgatás • "Know" Információs keresés – egy zenekar neve, a város legjobb étterme • "Go" Navigációs keresés – Kifejezetten egy weblap keresése: menj a Facebook-ra, az NFL homepage-re

• Csak az a válasz érdekel, ami relevéns • Hasznosság remélt sorrendjében • A relevancia több, mint hogy “tartalmazza a jó szavakat” • A keresőmotorok első napjaiban ennyi volt • Nem is működött jól • AltaVista → Google 35/40


Search Engine Optimization • Egy weboldal láthatóságának befolyásolása egy keresőmotor találati

listájában • Nem a keresőmotorok kijátszása • Jó felhasználói élmény

• Az oldal szándékainak közvetítése, hogy a releváns kereséseknél

ajánlhassák • robots.txt: amit a keresőrobotok ne járjanak be • Bejelentkezés után látható oldalak • Személyes információt tartalmazó oldalak: vásárlás • Oldalon belüli keresési eredmények • Korai algoritmusok: • Szerepelnek-e a megadott szavak • Kulcsszó-sűrűség • Keyword meta-tag • Könnyű volt kijátszani 36/40


Mennyire fontos egy oldal? • A legtöbb keresőmotornál: fontosság = népszerűség • Minél népszerűbb egy oldal, annál fontosabb kell legyen az infó, ami rajta van • Algoritmusokkal szűrik és rangsorolják az oldalakat relevancia és népszerűség alapján

• Ranking faktorok • Tartalom: Az oldal szövege, címek, ismertetők. • Teljesitmény: Milyen gyors? Jól működik? • Megbizhatóság: Elég jó a tartalom ahhoz, hogy más oldalak ide mutassanak? Más oldalak megjelölik referenciaként? • Felhasználói élmény: Hogy néz ki? Könnyű eligazodni? Magas a bounce rate?

37/40


SEO Success Factors

38/40


Search Engine Optimization • Oda-vissza ható folyamat • Algoritmus → helyezést javító trükkök → új algoritmus → új trükkök → … • Hogy pontosan hogy működik, azt a tapsztalat alapján sejteni lehet

• On-the-page SEO  Ami az oldal szerzőjének befolyása alá tartozik • Tartalom • HTML • Felépítés • Off-the-page SEO  Az olvasókon, látogatókon és a többi oldal szerzőjén múlik • Linkek • Megbízhatóság • Közösségi média • Személyes paraméterek 39/40


Search Engine Optimization • White Hat technikák • A felhasználónak szóljon az oldal, ne a keresőnek • A weboldal struktúráját tagolttá kell tenni, megfelelő header használattal. • •A taget megfelelően kell kitölteni. • •Az oldalon elhelyezett szövegeket is érdemes optimalizálni. • •Helyezzünk el olyan linkeket, amik egyéb aloldalakra mutatnak. • Hosszú távú eredmény<br /> <br /> • Black Hat technikák • Hogyan tévesszük meg a keresőt • Láthatatlan tartalom • Más oldal megjelenítése, ha a kereső kéri = cloaking • Gyors eredmény, de: ha a kereső rájön: büntetés<br /> <br /> 40/40<br /> <br /> </div> </div> </div> </div> </div> </div> </div> </div> <div class="modal fade" id="report" tabindex="-1" role="dialog" aria-hidden="true"> <div class="modal-dialog"> <div class="modal-content"> <form role="form" method="post" action="https://adoc.pub/report/nszervezd-adatbazisok" style="border: none;"> <div class="modal-header"> <button type="button" class="close" data-dismiss="modal" aria-hidden="true">×</button> <h4 class="modal-title">Report "Önszerveződő adatbázisok"</h4> </div> <div class="modal-body"> <div class="form-group"> <label>Your name</label> <input type="text" name="name" required="required" class="form-control" /> </div> <div class="form-group"> <label>Email</label> <input type="email" name="email" required="required" class="form-control" /> </div> <div class="form-group"> <label>Reason</label> <select name="reason" required="required" class="form-control"> <option value="">-Select Reason-</option> <option value="pornographic" selected="selected">Pornographic</option> <option value="defamatory">Defamatory</option> <option value="illegal">Illegal/Unlawful</option> <option value="spam">Spam</option> <option value="others">Other Terms Of Service Violation</option> <option value="copyright">File a copyright complaint</option> </select> </div> <div class="form-group"> <label>Description</label> <textarea name="description" required="required" rows="3" class="form-control" style="border: 1px solid #cccccc;"></textarea> </div> <div class="form-group"> <div style="display: inline-block;"> <div class="g-recaptcha" data-sitekey="6LcEnMcZAAAAAFHzKKgaE-Qh57XzUTzpfRElD4dP"></div> </div> </div> <script src='https://www.google.com/recaptcha/api.js'></script> </div> <div class="modal-footer"> <button type="button" class="btn btn-default" data-dismiss="modal">Close</button> <button type="submit" class="btn btn-primary">Send</button> </div> </form> </div> </div> </div> <script> $(document).ready(function () { var inner_height = $(window).innerHeight() - 250; $('#pdfviewer').css({"height": inner_height + "px"}); }); </script> <footer class="footer" style="margin-top: 60px;"> <div class="container-fluid"> Copyright © 2024 ADOC.PUB. All rights reserved. <div class="pull-right"> <span><a href="https://adoc.pub/about">About Us</a></span> | <span><a href="https://adoc.pub/privacy">Privacy Policy</a></span> | <span><a href="https://adoc.pub/term">Terms of Service</a></span> | <span><a href="https://adoc.pub/copyright">Copyright</a></span> | <span><a href="https://adoc.pub/contact">Contact Us</a></span> | <span><a href="https://adoc.pub/cookie_policy">Cookie Policy</a></span> </div> </div> </footer>  <div class="modal fade" id="login" tabindex="-1" role="dialog" aria-labelledby="myModalLabel"> <div class="modal-dialog" role="document"> <div class="modal-content"> <div class="modal-header"> <button type="button" class="close" data-dismiss="modal" aria-label="Close" on="tap:login.close"><span aria-hidden="true">×</span></button> <h4 class="modal-title" id="add-note-label">Sign In</h4> </div> <div class="modal-body"> <form action="https://adoc.pub/login" method="post"> <div class="form-group"> <label class="sr-only" for="email">Email</label> <input class="form-input form-control" type="text" name="email" id="email" value="" placeholder="Email" /> </div> <div class="form-group"> <label class="sr-only" for="password">Password</label> <input class="form-input form-control" type="password" name="password" id="password" value="" placeholder="Password" /> </div> <div class="form-group"> <div class="checkbox"> <label class="form-checkbox"> <input type="checkbox" name="remember" value="1" /> <i class="form-icon"></i> Remember me </label> <label class="pull-right"><a href="https://adoc.pub/forgot">Forgot password?</a></label> </div> </div> <button class="btn btn-primary btn-block" type="submit">Sign In</button> </form> </div> </div> </div> </div>  <script async src="https://www.googletagmanager.com/gtag/js?id=UA-177279549-1"></script> <script> window.dataLayer = window.dataLayer || []; function gtag(){dataLayer.push(arguments);} gtag('js', new Date()); gtag('config', 'UA-177279549-1'); </script> <script src="https://adoc.pub/assets/js/jquery-ui.min.js"></script> <link rel="stylesheet" href="https://adoc.pub/assets/css/jquery-ui.css"> <script> $(function () { $("#document_search").autocomplete({ source: function (request, response) { $.ajax({ url: "https://adoc.pub/suggest", dataType: "json", data: { term: request.term }, success: function (data) { response(data); } }); }, autoFill: true, select: function( event, ui ) { $(this).val(ui.item.value); $(this).parents("form").submit(); } }); }); </script>  <div id="ADOCPUB_cookie_box" style="z-index:99999; border-top: 1px solid #fefefe; background: #FFC107; width: 100%; position: fixed; padding: 5px 15px; text-align: center; left:0; bottom: 0;"> Our partners will collect data and use cookies for ad personalization and measurement. <a href="https://adoc.pub/cookie_policy" target="_blank">Learn how we and our ad partner Google, collect and use data</a>. <a href="#" class="btn btn-success" onclick="accept_ADOCPUB_cookie_box();return false;">Agree & close</a> </div> <script> function accept_ADOCPUB_cookie_box() { document.cookie = "ADOCPUB_cookie_box_viewed=1;max-age=15768000;path=/"; hide_ADOCPUB_cookie_box(); } function hide_ADOCPUB_cookie_box() { var cb = document.getElementById('ADOCPUB_cookie_box'); if (cb) { cb.parentElement.removeChild(cb); } } (function () { var ADOCPUB_cookie_box_viewed = (function (name) { var matches = document.cookie.match(new RegExp("(?:^|; )" + name.replace(/([\.$?*|{}\[\]\\\/\+^])/g, '\\$1') + "=([^;]*)")); return matches ? decodeURIComponent(matches[1]) : undefined; })('ADOCPUB_cookie_box_viewed'); if (ADOCPUB_cookie_box_viewed) { hide_ADOCPUB_cookie_box(); } })(); </script>  </body> </html>

Önszerveződő adatbázisok

Recommend Documents