I många informationsnätverk, dataobjekt -såsom uppdateringar i sociala nätverk, nyheter som flödar genom sammankopplade RSS-flöden och bloggar, mätningar i sensornätverk, ruttuppdateringar i ad-hoc-nätverk - propagate på ett okoordinerat sätt: noder ofta förmedla information de får till grannar, oberoende av om dessa grannar fick samma information från andra källor eller inte. Denna osamordnade informationsspridning kan leda till betydande, men ändå onödiga omkostnader för kommunikation och behandling, vilket i slutändan kan minska informationsnätverkens nytta. För att lindra de negativa effekterna av denna informationsmångfald föreslår vi att en undergrupp av noder (valda på nyckelpositioner i nätverket) utför ytterligare informationsfiltreringsfunktionalitet. Således, noder är ansvariga för avlägsnande (eller betydande minskning) av överflödiga data objekt förmedlas genom dem. Vi hänvisar till t.ex. noder som filter. Vi definierar formellt problemet med filterplacering som ett kombinatoriskt optimeringsproblem, och studerar dess beräkningskomplexitet för olika typer av grafer. Vi presenterar också polynom-tids approximation algoritmer och skalbara heuristik för problemet. Våra experimentella resultat, som vi fick genom omfattande simuleringar på syntetiska och verkliga informationsflöde nätverk, tyder på att i många miljöer ett relativt litet antal filter är ganska effektivt för att ta bort en stor del av överflödig information.
I filterplacering REF, dessa noder identifieras som är orsaken till maximal informationsmångfald.
The Filter-Placement Problem and its Application to Minimizing Information Multiplicity
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}