FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 8 | 9 || 11 | 12 |   ...   | 25 |

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

-- [ Page 10 ] --

The main contribution of this chapter is the presentation of the peer selection approach for MAPS by utilizing novel publisher selection strategies based on a combination of resource selection and behavior prediction. The evaluation of this approach shows that traditional resource selection strategies alone are not sufficient in this setting, and devise a novel method to predict peer publishing behavior based on time series analysis of IR metrics.

This technique allows to improve recall, while monitoring only a small number of publishers.

In addition, this chapter investigates an improvement algorithm called MAPS Selective Method to improve the prediction techniques without additional communication overhead.

An extended experimental evaluation of both methods investigates the usefulness of the proposed approaches in several publishing behaviors and scenarios.

- 51 Chapter 4 Publisher Peer Selection

4.2 Peer Selection Strategy The protocols presented in the previous chapter have shown that the selection of peers is the most critical part of the approximate information filtering approach MAPS. The subscriber only receives notifications about published documents from peers that store the continuous query. In other words: a subscriber monitors a publisher with a continuous query.

To decide which publisher peers should be monitored, the subscription protocol of Section 3.3.2 uses a scoring function to rank peers. In the MAPS approach, the subscriber computes a publisher peer score based on a combination of resource selection 1 and behavior prediction

formulas as shown below:

score(P, q) = α · sel(P, q) + (1 − α) · pred(P, q) (4.1) In this equation, q is a continuous query, P is a certain publisher peer, and sel(P, q) and pred(P, q) are scoring functions based on resource selection and behavior prediction respectively that assign a score to a peer P with respect to query q. Function score(P, q) is used to combine the selection and prediction scores, and decides the final score of a peer P with respect to q. The tunable parameter α affects the balance between authorities (high sel(P, q) scores) and peers with potential to publish matching documents in the future (high pred(P, q) scores). The value of α is from 0 to 1 where α = 1 means that the peer score is only based on resource selection, and α = 0 only considers behavior prediction.

Based on these scores, a ranking of peers is determined and q is forwarded to the highest ranked peers. In this way, the subscriber can monitor the top-k publisher peers concerning its information demand.

Notice that this peer selection strategy is general and can also be used in centralized settings, where a server (instead of the distributed directory) maintains the necessary statistics, and mediates the interaction between publishers and subscribers.

The main contribution of this peer selection approach respect to predicting peer behavior, is to view the IR statistics provided by the (centralized or distributed) directory as time series and use statistical analysis tools to model publisher peer behavior. Time series analysis accounts for the fact that the time series observations have some sort of internal structure (e.g., trend, or seasonality etc.), and uses this observation to analyze older values and predict future ones (see Section 2.4). In the next sections, both resource selection (Section 4.2.1) and novel behavior prediction (Section 4.2.2) are presented and investigated in detail. Section 4.2.3 explains the main reasons why both components of the scoring function are needed to get a satisfying system effectiveness. An extensive discussion of resource selection for one-time search in structured P2P networks is not in the focus of this thesis. Chapter 6 includes some aspects of the Minerva one-time search approach where resource selection is adopted to overlapping P2P collections.

4.2.1 Resource Selection In the literature, resource selection (or database selection or collection selection) is the task to decide to which information source a one-time query should be routed. Obviously, in a distributed system, it is too expensive to query all available information sources such that the decision is critical and strongly influences the retrieval quality (e.g., recall and precision).

1 The term resource selection is also known as database selection or collection selection. Resource selection

is throughout this thesis.

- 52 Chapter 4 Publisher Peer Selection Given the large-scale data distribution of a P2P network, one of the key technical challenges is query routing, which is the process of efficiently selecting the most promising peers (from a potentially very large set of peers storing relevant data) for a particular information need. Query routing is very similar to resource selection that has been studied extensively in the literature in the context of metasearch engines 2. There, approaches are typically designed for a small and rather static set of search engines and did not consider the challenges present in a P2P network, such as peer autonomy, network dynamics and high inter-peer latencies. The interested reader is referred to [MYL02, NF06, BMWZ05] for existing approaches to query routing.

In MAPS, the sel(P, q) function returns a score for a peer P and a query q, and is calculated using standard resource selection algorithms such as tf − idf -based methods, CORI [CLC95, SJCO02], GlOSS [GGM95, GGMT99], the decision-theoretic framework (DTF) [Fuh99, NF03], or Statistical Language Models [SC99, PC98, XC99, ZL01, MLS99].

A P2P setting poses some new requirements to route a one-time query to an appropriate set of selected information sources. Here, the assumption of non-overlapping collections does not hold. In [BMT+ 05a], an overlap-aware query routing approach is presented that considers the novelty of single information sources. The idea behind this approach is that a query initiator should not ask sources that provide similar content concerning a query.

Bloom filters [Blo70] and/or min-wise independent permutations [BCFM00] are used to enrich the distributed directory and to compute a novelty score to combine quality and novelty measures. In addition, correlated key sets as described in [MBN+ 06] are recognized and exploited to further improve peer selection.

Using the scoring function sel(P, q), the MAPS approach identifies authorities specialized in a topic, which, as argued above, is not sufficient for the IF setting. Next, two resource selection strategies are presented in more detail including the well-known CORI approach and a simple approach based on IR statistics. The CORI Approach

The Collection Retrieval Inference Network (CORI) [CLC95, SJCO02] reduces the task of resource selection to a document retrieval task by relying on inference networks. In CORI, a super-document is selected as the representative of a collection of documents, and represents the concatenation of all documents with all distinct keys of this collection. If a key appears in t distinct documents in the collection, the key appears t times in the superdocument. The set of all super-documents forms a special-purpose collection that is used to identify the most promising collections for a given query. In principle, standard approaches (e.g., tf − idf and cosine measure) could now be applied. From the viewpoint of regular document scoring and retrieval, term frequencies are replaced by document frequencies, and document frequencies by collection frequencies, i.e., the number of collections that contain a specific key.

The approach taken by CORI is implemented in the context of the INQUERY [CCH92] retrieval system based on inference networks [TC91] to compute the ranking score of a collection with respect to query q as the estimated belief that the database or information source contains useful documents. The belief is essentially the combined probability that the database contains useful documents for each query key. More specifically, the belief that the information need expressed by a query key k is satisfied by searching the collection

of P is determined by the following equations:

2A metasearch engine is a search engine that sends user requests to several other search engines and/or databases and aggregates the results into a single list or displays them according to their source.

–  –  –

Compared to the original application of inference networks to document scoring, document peers are replaced by the super-documents, yielding a moderate-sized network. The frequency values are typically higher, but that does not affect the computational complexity. However, in a highly dynamic network of (cooperating) peers, the proper estimation of n, clavg, and cf is a non-trivial problem. The MRS Approach

The MAPS Resource Selection approach is based on tf − idf statistics directly available by the distributed directory. This simple strategy (compared to more sophisticated ones as CORI or DTF ) uses the peer document frequency (df ), and the maximum peer term frequency (tf max ) as defined before. The scoring functions sel(P, q) aggregates over all

query keys k as follows:

–  –  –

4.2.2 Behavior Prediction To predict peer behavior MAPS considers time series analysis of IR statistics, thus making a rich repository of techniques from time series analysis [Cha04] applicable to this problem.

These techniques predict future time series values based on past observations and differ in (i) their assumptions about the internal structure of the time series (e.g., whether trends and seasonality can be observed) and (ii) their flexibility to put emphasis on more recent observations. Details about time series analysis including different prediction techniques are presented in this thesis in Section 2.4.

- 54 Chapter 4 Publisher Peer Selection Since the considered IR statistics exhibit trends, for instance, when peers successively crawl sites that belong to similar topics, or, gradually change their thematic focus, the employed time series prediction technique must be able to deal with trends properly. Further, in this scenario it is obvious to put emphasis on a peer’s recent behavior and thus assign higher weight to recent observations when making predictions about its future behavior.

Moving average techniques do not support a higher weight for more recent observations, and single exponential smoothing (SES) is not able to recognize trends.

For this reason, MAPS uses double exponential smoothing (DES) as a prediction technique, since it can both deal with trends and put emphasis on more recent observations.

Section 2.4.

4.2 explains double exponential smoothing and also other techniques. For completeness, notice that there is also triple exponential smoothing (TES) that, in addition, handles seasonality in the observed data. The MAPS setting assumes that many queries are expected to be short-lived so that no seasonality will be observed in the IR statistics time series. For an application with many long-lasting queries, one could use triple exponential smoothing, so that seasonality is taken into account. An example for seasonality could be the continuous query for Christmas gifts. In this case, every year before Christmas, the publication of matching documents would be recognizable.

The function pred(P, q) returns a prediction score for a publisher peer P that represents the likelihood of publishing documents relevant to query q in the future. Using the double exponential smoothing (DES) prediction technique as described before, two values are predicted.

–  –  –

Thus, two aspects of the peer’s behavior are modeled: (i) its potential to publish relˆ evant documents in the future (reflected by δ(df P,k )), and (ii) its overall expected future publishing activity (reflected by δ(cs)). The time series of IR statistics that are needed as ˆ an input to the prediction mechanism are obtained using the distributed directory. The

predicted behavior for peer P is quantified as follows in Equation 4.7:

–  –  –

4.2.3 Why Both Strategies Are Needed A key component of the peer selection procedure and peer ranking function 4.1 is the behavior prediction mechanism introduced in this thesis. Prediction is complementary to well-known resource selection techniques (e.g., MRS or CORI approach). The following example using the characteristics of Table 4.1 will demonstrate the necessity in a filtering setting to combine both components of the ranking function, and shows why an approach that relies only on resource selection is not sufficient. Table 4.1 lists all four possible combinations describing the past 4 and the future 5.

–  –  –

Table 4.1: Different Publisher Characteristics.

Assume a publisher peer P1 that has specialized and become an authority in Sports, but publishes no relevant documents any more. Assume that P1 will not publish any Sportsrelated documents in the future. Another publisher peer P2 is not specialized in Sports, but is currently crawling a sports portal. Imagine a user who wants to stay informed about the upcoming 2008 Olympic Games, and subscribes with the continuous query 2008 Olympic Games. If the ranking function solely relied on resource selection, peer P1 would always be chosen to index the user’s information demand, which would be wrong given that peer P1 no longer publishes Sports-related documents. On the other hand, to have a high ranking score assigned, peer P2 would have to specialize in Sports – a long procedure that is inapplicable in a IF setting which is by definition dynamic. This makes the use of a ranking and selection strategy that recognizes and predicts publishing behaviors an important component.

Pages:     | 1 |   ...   | 8 | 9 || 11 | 12 |   ...   | 25 |

Similar works:

«Nachhaltigkeitsbericht 2011–2010 BOKU Kinderbuch inside INHALT Vorwort der Universitätsleitung 5 1. Strategie und Analyse 7 1.1. Nachhaltigkeitsstrategie der Universität für Bodenkultur Wien 8 1.1.1. Nachhaltigkeitsvision 8 1.1.2. Die Aufgaben und Ziele der Universität 9 1.1.3. Management „Nachhaltige Universität BOKU“ 11 1.1.4. Die BOKU-Umweltleitlinien 13 1.1.5. BOKUMeilensteine und Auszeichnungen 14 1.2. Analyse der Jahre 2010 und 2011 15 1.2.1. Ziele und Erfolge in den Jahren...»

«Az Erdélyi Református Egyházkerület a Királyhágómelléki Református Egyházkerület és az Evangélikus–Lutheránus Egyház hivatalos lapja 4– 1 Százhatodik évfolyam 2013. január–február Alapítás: 1907 Kéthavonta megjelenő teológiai tudományos folyóirat Kiadja az Erdélyi Református Egyházkerület Igazgatótanácsa FŐSZERKESZTŐ Dr. ADORJÁNI ZOLTÁN email: adorjani@proteo.hu, tel.: 0744-989-052 FELELŐS SZERKESZTŐ Dr. BUZOGÁNY DEZSŐ email: buzogany@proteo.hu,...»

«August 2015 Exposure Draft ED/2015/7 Effective Date of Amendments to IFRS 10 and IAS 28 Comments to be received by 9 October 2015 Effective Date of Amendments to IFRS 10 and IAS 28 Comments to be received by 9 October 2015 Exposure Draft ED/2015/7 Effective Date of Amendments to IFRS 10 and IAS 28 is published by the International Accounting Standards Board (IASB) for comment only. The proposals may be modified in the light of the comments received before being issued in final form. Comments...»

«05.025 Botschaft zum Bundesgesetz über die Neuordnung der Pflegefinanzierung vom 16. Februar 2005 Sehr geehrte Herren Präsidenten, sehr geehrte Damen und Herren, Mit dieser Botschaft unterbreiten wir Ihnen einen Entwurf zu einem Bundesgesetz über die Neuordnung der Pflegefinanzierung mit dem Antrag auf Zustimmung.Gleichzeitig beantragen wir, die folgenden parlamentarischen Vorstösse abzuschreiben: 2003 P 02.3626 Transparenz und Kohärenz zwischen den verschiedenen Leistungen der...»

«  Department of Transportation  Office of Aviation Enforcement and Proceedings      )    )  American Airlines  )     February 4, 2013    )   Multiple Price Advertising Violations of   )  49 U.S.C. § 41712 and 14 CFR 399.84(a)   )    )   ...»

«This document compiles two base prospectuses with different categories of securities pursuant Article 22(6) of the Commission Regulation (EC) No 809/2004 of 29 April 2004, as amended (the “Prospectus Regulation”): (i) the base prospectus in respect of non-equity securities within the meaning of No. 4 of Article 22(6) of the Prospectus Regulation (“Non-Equity Securities”), and (ii) the base prospectus in respect of Pfandbriefe as non-equity securities within the meaning of No. 3 of...»

«1 Mitteilungen 3. Quartal 2015 Inhalt nach Rubriken Brief des Präsidenten Neue Mitglieder Jubiläumsveranstaltung „60 Jahre GMDS“ am 28. Oktober 2015 über den Dächern von Köln. Seite 8 Bericht zur 60. GMDS-Jahrestagung vom 6. bis 9. September 2015 in Krefeld conhIT vom 19. bis 21. April 2016 in der Messe Berlin conhIT-Satellitenveranstaltung von GMDS und BVMI am 18. April 2016 in Berlin GMDS-Doktorandensymposium vom 8. bis 11. Oktober 2015 an der Hochschule Ulm. Seite 12 GMDS ab...»

«Materialien Dr. Nils Meyer-Ohlendorf, Michael Mehling, Katharina Umpfenbach Ecologic Institut Analyse der Konjunkturprogramme zur Bewältigung der Finanzund Wirtschaftskrise aus Umweltsicht Expertise für das WBGU-Hauptgutachten „Welt im Wandel: Gesellschaftsvertrag für eine Große Transformation“ Berlin 2009 Konjunkturprogramme in Deutschland, Großbritannien, Südkorea und USA – Schritt in Richtung einer nachhaltigen Entwicklung oder teurer Zement für alte Strukturen? Kurzexpertise...»

«Reality Checks Teaching Reading Comprehension With Nonfiction K 5 Met to archive a collection rang long a etc because drafting place retirement. The schedule being a Reality Checks: Teaching Reading Comprehension with Nonfiction, K-5 card with the plaque is centralized to of a contact. The Reality Checks: Teaching Reading Comprehension with Nonfiction, K-5 most expected post professionals are that the purchase traits and it lasts north at they will guarantee important to guarantee the companies...»

«CHAPTER VII NO NEED FOR PRE-EXISTING CONDITIONS Rav Moshe Feinstein rules in Even Hoezer Book I end of Chapter 79 that whenever the Rabbinical Court is inpotent to force a husband to divorce his wife, the Court annuls his marriage. Otherwise no women, with the exception of very few, would agree to get married to such a man. This position is equally advanced by Rav Eliyohu Klotzkian in Dvar Eliyohu Chapter 48. See also Rav Yitzchok Elchonen Ein Yitzchok Chapter 23: 38, 39,40,41,42. See also Ohel...»

«Földrajzi Értesítő 2002. LI. évf 1-2. füzet, pp. 185-201. A németség etnikai térszerkezetének változásai KomáromEsztergom megye mai területén a 18. századtól napjainkig1 BOTTLIK Z S O L T 2 Zusammenfassung Umwandlung der Ungarndeutschen im Komitat Komárom-Esztergom vom 18. Jh. bis heute Die visuelle Analyse der auf Grund der Daten erstellten Karte gibt eine Möglichkeit, die Räume zu markieren, in denen die deutschsprachige Bevölkerung gelebt hat bzw. noch lebt. Die Karten...»


<<  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.