edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Armin Roth
Titel: Efficient query answering in peer data management systems
Gutachter: Ulf Leser; Felix Naumann; Kai-Uwe Sattler
Erscheinungsdatum: 12.03.2012
Volltext: pdf (urn:nbn:de:kobv:11-100200575)
Fachgebiet(e): Informatik
Schlagwörter (ger): Kosten, Anfragebearbeitung, Peer-Daten-Management-Systeme, Vollständigkeit
Schlagwörter (eng): Peer data management systems, Query answering, Completeness, Cost
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Lizenz: Namensnennung - Keine Bearbeitung (CC BY ND)
Zitationshinweis: Roth, Armin: Efficient query answering in peer data management systems; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 12.03.2012, urn:nbn:de:kobv:11-100200575
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.
Diese Seite taggen: Diese Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer ansehen können.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

Abstract (ger):
Peer-Daten-Management-Systeme (PDMS) bestehen aus einer hochdynamischen Menge heterogener, autonomer Peers. Die Peers beantworten Anfragen einerseits gegen lokal gespeicherte Daten und reichen sie andererseits nach einer Umschreibung anhand von Schema-Mappings an benachbarte Peers weiter. Solche aufgrund fehlender zentraler Komponenten eigentlich hoch- flexiblen Systeme leiden bei zunehmender Anzahl von Peers unter erheblichen Effi- zienzproblemen. Die Gründe hierfür liegen in der massiven Redundanz der Pfade im Netzwerk der Peers und im Informationsverlust aufgrund von Projektionen entlang von Mapping-Pfaden. Anwender akzeptieren in hochskalierten Umgebungen zum Datenaustausch in vielen Anwendungsszenarien Konzessionen an die Vollständigkeit der Anfrageergebnisse. Unser Ansatz sieht in der Vollständigkeit ein Optimierungsziel und verfolgt einen Kompromiß zwischen Nutzen und Kosten der Anfragebearbeitung. Hierzu schlagen wir mehrere Strategien für Peers vor, um zu entscheiden, an welche Nachbar-Peers Anfragen weitergeleitet werden. Peers schließen dabei Mappings von der Anfragebearbeitung aus, von denen sie ein geringes Verhältnis von Ergebnisgröße zu Kosten, also geringe Effizienz erwarten. Als Basis dieser Schätzungen wenden wir selbstadaptive Histogramme über die Ergebniskardinalität an und weisen nach, daß diese in dieser hochdynamischen Umgebung ausreichende Genauigkeit aufweisen. Wir schlagen einen Kompromiß zwischen der Nutzung von Anfrageergebnissen zur Anpassung dieser Metadaten-Statistiken und der Beschneidung von Anfrageplänen vor, um den entsprechenden Zielkonflikt aufzulösen. Für eine Optimierungsstrategie, die das für die Anfragebearbeitung verwendete Zeit-Budget limitiert, untersuchen wir mehrere Varianten hinsichtlich des Effizienzsteigerungspotentials. Darüber hinaus nutzen wir mehrdimensionale Histogramme über die Überlappung zweier Datenquellen zur gezielten Verminderung der Redundanz in der Anfragebearbeitung.
Abstract (eng):
Peer data management systems (PDMS) consist of a highly dynamic set of autonomous, heterogeneous peers connected with schema mappings. Queries submitted at a peer are answered with data residing at that peer and by passing the queries to neighboring peers. PDMS are the most general architecture for distributed integrated information systems. With no need for central coordination, PDMS are highly flexible. However, due to the typical massive redundancy in mapping paths, PDMS tend to be very inefficient in computing the complete query result as the number of peers increases. Additionally, information loss is cumulated along mapping paths due to selections and projections in the mappings. Users usually accept concessions on the completeness of query answers in large-scale data sharing settings. Our approach turns completeness into an optimization goal and thus trades off benefit and cost of query answering. To this end, we propose several strategies that guide peers in their decision to which neighbors rewritten queries should be sent. In effect, the peers prune mappings that are expected to contribute few data. We propose a query optimization strategy that limits resource consumption and show that it can drastically increase efficiency while still yielding satisfying completeness of the query result. To estimate the potential data contribution of mappings, we adopted self-tuning histograms for cardinality estimation. We developed techniques that ensure sufficient query feedback to adapt these statistics to massive changes in a PDMS. Additionally, histograms can serve to maintain statistics on data overlap between alternative mapping paths. Building on them, redundant query processing is reduced by avoiding overlapping areas of the multi-dimensional data space.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
PDF: 5 Zugriffe PDF: 7 Zugriffe Startseite: 7 Zugriffe PDF: 5 Zugriffe Startseite: 6 Zugriffe PDF: 3 Zugriffe Startseite: 8 Zugriffe PDF: 6 Zugriffe PDF: 10 Zugriffe PDF: 12 Zugriffe PDF: 3 Zugriffe PDF: 14 Zugriffe Startseite: 1 Zugriffe PDF: 18 Zugriffe Startseite: 1 Zugriffe PDF: 33 Zugriffe Startseite: 1 Zugriffe PDF: 22 Zugriffe PDF: 24 Zugriffe Startseite: 2 Zugriffe PDF: 37 Zugriffe Startseite: 2 Zugriffe PDF: 14 Zugriffe Startseite: 6 Zugriffe PDF: 23 Zugriffe Startseite: 5 Zugriffe PDF: 11 Zugriffe Startseite: 2 Zugriffe PDF: 31 Zugriffe Startseite: 7 Zugriffe PDF: 30 Zugriffe Startseite: 3 Zugriffe PDF: 19 Zugriffe Startseite: 2 Zugriffe PDF: 40 Zugriffe Startseite: 2 Zugriffe PDF: 35 Zugriffe PDF: 37 Zugriffe Startseite: 2 Zugriffe PDF: 54 Zugriffe Startseite: 1 Zugriffe PDF: 30 Zugriffe PDF: 45 Zugriffe Startseite: 4 Zugriffe PDF: 25 Zugriffe
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Monat Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Startseite     7 6 8         1 1 1   2 2 6 5 2 7 3 2 2   2 1   4
PDF 5 7 5 3 6 10 12 3 14 18 33 22 24 37 14 23 11 31 30 19 40 35 37 54 30 45 25

Gesamtzahl der Zugriffe seit Apr 2012:

  • Startseite – 62 (2.48 pro Monat)
  • PDF – 593 (21.96 pro Monat)
 
 
Generiert am 30.07.2014, 15:20:11