Abstract-Overlay nätverksdesign för ämnesbaserade publicerings-/prenumerationssystem är av största betydelse eftersom overlay direkt påverkar systemets prestanda. Bestämma ett ämne-anslutet overlay, där för varje ämne grafen induceras av noder som är intresserade av ämnet är ansluten, är ett grundläggande problem. Befintliga algoritmer för detta problem lider av tre viktiga nackdelar: 1) oöverkomligt höga driftskostnader, 2) krav på fullständig systemkunskap och centraliserad drift och 3) konstruktion av överlägg från grunden. Ur praktisk synvinkel är dessa alla betydande begränsningar. För att ta itu med dessa problem utvecklar vi i detta dokument nya algoritmer som effektivt löser problemet med att dynamiskt ansluta två eller flera ämnesanslutna overlays. Inspirerad av split-and-conquer karaktär av vårt tillvägagångssätt, härleder vi en algoritm som löser det ursprungliga problemet med en bråkdel (upp till 1,7 %) av driftskostnaderna för alternativa lösningar, men på bekostnad av en empiriskt obetydlig ökning av den genomsnittliga nodgraden.
I vårt tidigare arbete REF är en split-and-conquer algoritm utvecklad för MinAvg-TCO, vilket dramatiskt förbättrar körtiden på bekostnad av en mindre ökning av den genomsnittliga nodgraden.
Divide and Conquer Algorithms for Publish/Subscribe Overlay Design
{'venue': '2010 IEEE 30th International Conference on Distributed Computing Systems', 'journal': '2010 IEEE 30th International Conference on Distributed Computing Systems', 'mag_field_of_study': ['Computer Science']}