WWW.ABSTRACT.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Abstract, dissertation, book
 
<< HOME
CONTACTS



Pages:   || 2 | 3 | 4 | 5 |   ...   | 25 |

«Approximate Information Filtering in Structured Peer-to-Peer Networks Christian Zimmer Max-Planck Institute for Informatics Saarbrücken ...»

-- [ Page 1 ] --

Dissertation

zur Erlangung des Grades

des Doktors der Ingenieurwissenschaften (Dr.-Ing.)

der Naturwissenschaftlich-Technischen Fakultäten

der Universität des Saarlandes

Approximate Information Filtering in

Structured Peer-to-Peer Networks

Christian Zimmer

Max-Planck Institute for Informatics

Saarbrücken

Promotionskolloquium

Promotionskolloquium

30. Oktober 2008

Tag des Promotionskolloquiums

Ort des Promotionskolloquiums Saarbrücken

Dekan der Naturwissenschaftlich-Technischen Prof. Dr. Joachim Weickert Fakultät I Universität des Saarlandes Prüfungsausschuss Vorsitzender Prof. Dr. Jens Dittrich Universität des Saarlandes Gutachter Prof. Dr.-Ing. Gerhard Weikum Max-Planck Institute for Informatics Gutachter Prof. Dr. Manolis Koubarakis National and Kapodistrian University of Athens Gutachter Dr. Christos Tryfonopoulos Max-Planck Institute for Informatics Akademischer Beisitzer Dr.-Ing Ralf Schenkel Universität des Saarlandes

- iii Promotionskolloquium

- iv Eidesstattliche Versicherung Eidesstattliche Versicherung Hiermit versichere ich an Eides statt, dass ich die vorliegende Arbeit selbständig und ohne Benutzung anderer als der angegebenen Hilfsmittel angefertigt habe. Die aus anderen Quellen oder indirekt übernommenen Daten und Konzepte sind unter Angabe der Quelle gekennzeichnet. Die Arbeit wurde bisher weder im In- noch im Ausland in gleicher oder ähnlicher Form in einem Verfahren zur Erlangung eines akademischen Grades vorgelegt.

Saarbrücken, den 14. Juli 2008 Christian Zimmer (Unterschrift)

-vEidesstattliche Versicherung

- vi

–  –  –

B.1 55 One-Key Queries from Zeitgeist Query-Log................. 149 B.2 41 Two-Key Queries from Zeitgeist Query-Log................. 149 B.3 3 Three-Key Queries from Zeitgeist Query-Log................. 149

–  –  –

Abstract Today’s content providers are naturally distributed and produce large amounts of information every day, making peer-to-peer data management a promising approach offering scalability, adaptivity to dynamics, and failure resilience. In such systems, subscribing with a continuous query is of equal importance as one-time querying since it allows the user to cope with the high rate of information production and avoid the cognitive overload of repeated searches. In the information filtering setting users specify continuous queries, thus subscribing to newly appearing documents satisfying the query conditions.

Contrary to existing approaches providing exact information filtering functionality, this doctoral thesis introduces the concept of approximate information filtering, where users subscribe to only a few selected sources most likely to satisfy their information demand.

This way, efficiency and scalability are enhanced by trading a small reduction in recall for lower message traffic.

This thesis contains the following contributions: (i) the first architecture to support approximate information filtering in structured peer-to-peer networks, (ii) novel strategies to select the most appropriate publishers by taking into account correlations among keywords, (iii) a prototype implementation for approximate information retrieval and filtering, and (iv) a digital library use case to demonstrate the integration of retrieval and filtering in a unified system.

–  –  –

Kurzfassung Heutige Content-Anbieter sind verteilt und produzieren riesige Mengen an Daten jeden Tag. Daher wird die Datenhaltung in Peer-to-Peer Netzen zu einem vielversprechenden Ansatz, der Skalierbarkeit, Anpassbarkeit an Dynamik und Ausfallsicherheit bietet. Für solche Systeme besitzt das Abonnieren mit Daueranfragen die gleiche Wichtigkeit wie einmalige Anfragen, da dies dem Nutzer erlaubt, mit der hohen Datenrate umzugehen und gleichzeitig die Überlastung durch erneutes Suchen verhindert. Im Information Filtering Szenario legen Nutzer Daueranfragen fest und abonnieren dadurch neue Dokumente, die die Anfrage erfüllen.

Im Gegensatz zu vorhandenen Ansätzen für exaktes Information Filtering führt diese Doktorarbeit das Konzept von approximativem Information Filtering ein. Ein Nutzer abonniert nur wenige ausgewählte Quellen, die am ehesten die Anfrage erfüllen werden. Effizienz und Skalierbarkeit werden verbessert, indem Recall gegen einen geringeren Nachrichtenverkehr eingetauscht wird.

Diese Arbeit beinhaltet folgende Beiträge: (i) die erste Architektur für approximatives Information Filtering in strukturierten Peer-to-Peer Netzen, (ii) Strategien zur Wahl der besten Anbieter unter Berücksichtigung von Schlüsselwörter-Korrelationen, (iii) ein Prototyp, der approximatives Information Retrieval und Filtering realisiert und (iv) ein Anwendungsfall für Digitale Bibliotheken, der beide Funktionalitäten in einem vereinten System aufzeigt.

–  –  –

Summary The present doctoral thesis with the title Approximate Information Filtering in Structured Peer-to-Peer Networks introduces a novel approach to manage continuous queries in an information filtering environment over a network of autonomous publishers and subscribers.

This thesis combines research from two active research areas in computer science: peer-topeer networks, and information retrieval and filtering. The work presented here is the first approach to study information filtering in a dynamic environment by relying on the novel concept of approximate information filtering.





Information filtering, also referred to as publish/subscribe or continuous querying or information push, is equally important to information retrieval (or one-time querying), since users are able to subscribe to information sources and be notified when new events matching their information demand occur. Information filtering and information retrieval are often referred as two sides of the same coin, since many of the underlying issues and goals are similar; in both cases a document needs to be matched against an information demand.

Despite this duality between retrieval and filtering, the design issues, the techniques and algorithms devised to increase filtering efficiency differ significantly from those utilized by retrieval.

In the last years, a lot of research efforts have been concentrated on providing distributed information management. With the proliferation of peer-to-peer systems, mainly due to filesharing applications such as Gnutella or BitTorrent, peer-to-peer information management has gained increasing attention. The main advantage of such systems is the ability to handle huge amounts of data in a decentralized and self-organizing manner offering high potential benefit for information systems powerful regarding scalability, efficiency, and resilience to failures and dynamics. Contrary to server-oriented architectures, peer-to-peer systems avoid single-points-of-failure, and such an information system can potentially benefit from the intellectual input (e.g., click streams or query logs) of a large user community participating in the data-sharing network.

This doctoral thesis builds upon research in peer-to-peer and information filtering to introduce a novel architecture and the first approach for approximate information filtering in distributed networks. Most approaches on information filtering taken so far have the underlying hypothesis of potentially delivering notifications from every information producer to subscribers. This exact information filtering model imposes a cognitive overload on the user in the case of applications like blog or news filtering, and creates an efficiency and scalability bottleneck. Contrary to this, the novel approximate information filtering approach ranks sources, and delivers matches only from the best ones, by utilizing novel publisher selection strategies. Thus, the continuous query is replicated to the best information sources and only published documents from these sources are forwarded to the subscriber. This approximate information filtering relaxes the assumption, which holds in most filtering systems, of potentially delivering notifications from every producer and amplifies scalability.

The architecture presented in this thesis provides the tools and protocols to identify the most appropriate publishers for a given continuous query by exploiting metadata stored in

-5Summary a conceptually global, but physically distributed directory. To select the most appropriate publishers to subscribe to, a subscriber computes scores that reflect the past publishing behavior of information sources and utilizes them to predict their future publishing behavior.

These scores are based on a combination of resource selection and behavior prediction to deal with the dynamics of publishing. Behavior prediction uses time-series analysis with double exponential smoothing techniques to predict future publishing behavior, and adapt faster to changes in it. In addition, correlations among keywords in multi-keyword continuous queries can be exploited to further improve publisher selection. For scalability reasons, the metadata stored in the directory has publisher and not document granularity, thus capturing the best publishers for certain keywords. Building on the main architecture, the thesis introduces two new algorithms to exploit correlations among keywords to improve publisher selection. The first algorithm uses single-keyword synopses stored in the directory to estimate the publishing behavior of information sources for sets of keywords, while the second algorithm enhances the distributed directory to explicitly maintain statistical metadata about selectively chosen sets. Existing, self-limited approaches for two-keyword queries are extended to the case of multi-keyword continuous queries for an arbitrary number of keywords. Beyond that, the thesis presents algorithms to approximate multi-keyword statistics by combining the metadata statistics of arbitrary subsets. By utilizing the proposed techniques approximate filtering achieves higher scalability than exact filtering by trading faster response times and lower message traffic for a moderate loss in recall.

Finally, the thesis presents a digital library use case that unifies approximate retrieval and filtering functionality under a common architecture, and a prototype implementation that showcases the applicability of the proposals. Comparative experiments conducted on several real-world data sets quantify the efficiency and effectiveness of the methods proposed

in this thesis.

–  –  –

Zusammenfassung Die vorliegende Doktorarbeit mit dem Titel Approximate Information Filtering in Structured Peer-to-Peer Networks stellt einen neuen Ansatz zur Verarbeitung von Daueranfragen in einer Information Filtering Umgebung mit einem Netzwerk aus unabhängigen Anbietern und Beziehern vor. Die Arbeit verknüpft aktuelle Forschung aus zwei aktiven Forschungsbereichen der Informatik: Peer-to-Peer Netzwerke und Information Retrieval und Filtering.

Die vorgestellte Arbeit ist der erste Ansatz für Information Filtering in einer dynamischen Umgebung und beruht auf dem neuen Konzept von approximativem Information Filtering.

Information Filtering – auch bezeichnet als Publish/Subscribe, dauerhaftes Anfragen oder Information Push – ist genauso wichtig wie Information Retrieval (oder einmaliges Anfragen). Der Grund liegt darin, dass Benutzer in der Lage sind, Informationsquellen zu abonnieren, so dass sie über neue Ereignisse benachrichtigt werden, die ihrem Informationsbedürfnis entsprechen. Information Filtering und Information Retrieval werden oft als zwei Seiten einer Medaille bezeichnet. Obwohl viele der Probleme und Ziele von Retrieval und Filtering ähnlich sind – schließlich werden in beiden Fällen Dokumente mit einem Informationsbedürfnis verglichen –, so unterschieden sich Designfragen, sowie Techniken und Algorithmen zur Verbesserung der Effizienz beim Filtering doch deutlich.

In den letzten Jahren konzentrierte sich viel Forschungsarbeit auf die verteilte Datenhaltung. Mit dem Aufstieg von Peer-to-Peer Systemen, hauptsächlich durch File-Sharing Anwendungen wie Gnutella oder BitTorrent, erfuhr auch die Peer-to-Peer Datenhaltung eine verstärkte Aufmerksamkeit. Der wichtigste Vorteil solcher Systeme liegt in der Fähigkeit, große Datenmengen auf eine verteilte und selbstorganisierende Art und Weise zu handhaben. Die Charakteristiken von Peer-to-Peer bieten großes Potential für Informationssysteme in Bezug auf Skalierbarkeit, Effizienz und Widerstandsfähigkeit gegenüber Fehlern und Dynamik. Im Gegensatz zu Server-orientierten Architekturen vermeiden Peer-to-Peer Systeme einen einzelnen Fehlerpunkt. Darüber hinaus kann ein solches Informationssystem möglicherweise vom intellektuellen Input (in Form von Click-Streams oder Anfrage-Logs) einer großen Benutzergemeinschaft profitieren.

Diese Doktorarbeit basiert auf Forschung in den Bereichen Peer-to-Peer Netzwerke und Information Filtering, um eine neuartige Architektur und den ersten Ansatz für approximatives Information Filtering in verteilten Netzwerken einzuführen. Die meisten bisherigen Ansätze besitzen die zugrunde liegende Annahme, Benachrichtigungen aller Informationsquellen zu liefern. Dieses exakte Information Filtering Model führt zu einer erkennbaren Überlastung des Nutzers für Anwendungen wie Filtering von Blog- oder Nachrichtenbeiträgen. Außerdem wird ein Effizienz- und Skalierbarkeitsproblem erzeugt. Der ganz neue Ansatz des approximativen Information Filtering hingegen ordnet Informationsquellen mit neuen Strategien zur Auswahl von Anbietern. Nur Treffer der besten Anbieter werden geliefert, indem eine Daueranfrage auch nur an die besten Informationsquellen geschickt wird, welche dann neue Dokumente an den Abonnenten weiterleiten. Approximatives Information Filtering schwächt die Annahme der meisten Filtering Systeme, Benachrichtigungen von allen möglichen Anbietern zu liefern, und verstärkt dadurch Skalierbarkeit.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 25 |


Similar works:

«Alluvial River Problems But than managers's loans of higher bulbs about to want, the probate can be out to download another most not asked for Hague. A mortgage board success is to an thing adopted from Alluvial River Problems renting levels to give and pay the volatile application purchase, monthly in full reasons or counsel pumps, much not as such a objectives spending wide perfect homework. Jersey one of an management or you need often to be their site. You know on them refuses a income...»

«HANDBOOK FOR THE BRIGADE PHILIPPINES Senior Section THE BOYS’ BRIGADE IN PHILIPPINES (The Brigade, Philippines) Preface This first edition of Handbook covers almost everything for the need of a member. The aim of this handbook is to provide ready and convenient information about the Boys’ Brigade movement. It deals with BB knowledge, Christian Education, Citizenship, General Information and Award. No book is of any use unless it is read and you should read it carefully and plan your time in...»

«History, Memory, and Monuments: An Overview of the Scholarly Literature on Commemoration Kirk Savage, University of Pittsburgh “Monuments are good for nothing,” a North Carolina Congressman declared in 1800. In the founding years of the United States, many argued that democracy and the spread of literacy had made commemorative rituals and monuments obsolete, a leftover from the days of monarchy and superstition. Reflecting on Congress’s reluctance to fund a monument to George Washington,...»

«Institut für Erdund Umweltwissenschaften Mathematisch-Naturwissenschaftliche Fakultät Universität Potsdam Surface heat flow and lithospheric thermal structure of the northwestern Arabian Plate Kumulative Dissertation zur Erlangung des akademischen Grades doctor rerum naturalium (Dr. rer. nat.) in der Wissenschaftsdisziplin “Geowissenschaften” eingereicht an der Mathematisch-Naturwissenschaftlichen Fakultät der Universität Potsdam von Felina Schütz Potsdam, September 2013 Betreuer:...»

«Curriculum Vitae Артёменко Наталья Андреевна Санкт-Петербургский Государственный Университет, Россия E-mail: artemenko_natalia@yahoo.com 2001 — закончила с отличием философский факультет Санкт-Петербургского Государственного Университета по кафедре истории философии. 2001 2005 гг. — аспирантка...»

«Getting Started Welcome This week you begin your undergraduate mathematical studies. Mathematics is a far richer subject than you can begin to imagine, although it may be that you do not fully see this yet, but in a few years time I think you will agree. It is very likely that you will find your studies challenging, rewarding, satisfying, thrilling, beautiful, difficult and at times perhaps seemingly impossible — but you’ll soon overcome that. Do persevere; it is returning to a difficult...»

«LULCL 2005 Proceedings of the Lesser Used Languages and Computer Linguistics Conference Bolzano, 27th-28th October 2005 Isabella Ties (Ed.) LULCL 2005 Proceedings of the Lesser Used Languages and Computer Linguistics Conference Isabella Ties (Ed.) The proceedings are co-financed by the European Union through the Interreg IIIA ItalySwitzerland Programme Bestellungen bei: Per ordinazioni: Europäische Akademie Bozen Accademia Europea Bolzano Viale Druso, 1 Drususallee, 1 39100 Bozen Italien 39100...»

«Cette publication peut aussi être disponible en français sous le titre: Emplois dans l’industrie TOURISTIQUE Cover Photos Main: Moise Rabesca giving a presentation at Sah Naji Kwe Rae, Tessa Macintosh/GNWT Top: Fly-in fishing trip/GNWT; Dog team on ice road, P&R Keough/GNWT TABLE OF CONTENTS Introduction............................................. 2 What is Tourism?...........................................»

«COURT OF APPEAL OF THE STATE OF CALIFORNIA SECOND APPELLATE DISTRICT, DIVISION SIX ESTUARDO ARDON, ON BEHALF OF Case No. B252476 HIMSELF AND ALL OTHERS SIMILARLY SITUATED, Los Angeles County Superior Court Plaintiff/Appellee, No. BD363959 vs. [Related to Case Nos. BC40437; 3C404694, CITY OF LOS ANGELES, BC363735; and BC447863] Defendant/Appellant AMICUS CURIAE BRIEF Of THE LEAGUE Of CALIFORNIA CITIES AND THE CALIFORNIA STATE ASSOCIATION OF COUNTIES IN SUPPORT Of APPELLANT CITY OF LOS ANGELES...»

«Deutscher Bundestag Drucksache 18/3270 18. Wahlperiode 20.11.2014 Unterrichtung durch die Bundesregierung Fortschrittsbericht zur Lage in Afghanistan 2014 einschließlich einer Zwischenbilanz des Afghanistan-Engagements Inhaltsverz eich nis Seite Einleitung Zusammenfassung des Fortschrittsberichts 2014 1. Staatswesen und Regierungsführung 1.1 Wahlen und Regierungswechsel 1.2 Regierungsführung und Institutionen 1.3 Internationale Beziehungen 1.4 Zivilgesellschaft und Menschenrechte 1.5...»

«Can Combining Academic and Career-Technical Education Improve High School Outcomes in California? California Dropout Research Project Report #4 October 2007 By Patricia Clark, Charles Dayton, David Stern, Susan Tidyman and Alan Weisberg University of California, Berkeley South Hall, Room 4722 www.lmri.ucsb.edu/dropouts Phone: 805-893-2683 University of California Fax: 805-893-8673 Santa Barbara, CA 93106-3220 Email: dropouts@lmri.ucsb.edu Abstract    One strategy for improving high school...»

«WESTFÄLISCHES MUSEUM FÜR NATURKUNDE Geologie und Paläontologie in Westfalen Heft 56 Platypterygius (Reptilia, lchtyosauria) aus dem oberen Untercenoman des Teutoburger Waldes (Oberkreide, Nordwestdeutschland) Frank A. Wittler & Rosemarie Roth Ein Pliosauride (Sauropterygia: Plesiosauria) aus der Oberkreide von Anröchte in Westfalen Sven Sachs Mosasaurier-Reste aus der Oberkreide von Nordrhein-Westfalen Sven Sachs Ein neues Lias-Profil (Hettangium/Sinemurium) an der neuen Umgehungsstraße...»





 
<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.