{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:04:25Z","timestamp":1746331465117,"version":"3.40.4"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>In many information networks, data items -- such as updates in social networks, news flowing through interconnected RSS feeds and blogs, measurements in sensor networks, route updates in ad-hoc networks -- propagate in an uncoordinated manner: nodes often relay information they receive to neighbors, independent of whether or not these neighbors received the same information from other sources. This uncoordinated data dissemination may result in significant, yet unnecessary communication and processing overheads, ultimately reducing the utility of information networks. To alleviate the negative impacts of this<jats:italic>information multiplicity<\/jats:italic>phenomenon, we propose that a subset of nodes (selected at key positions in the network) carry out additional information filtering functionality. Thus, nodes are responsible for the removal (or significant reduction) of the redundant data items relayed through them. We refer to such nodes as<jats:italic>filters<\/jats:italic>. We formally define the Filter Placement problem as a combinatorial optimization problem, and study its computational complexity for different types of graphs. We also present polynomial-time approximation algorithms and scalable heuristics for the problem. Our experimental results, which we obtained through extensive simulations on synthetic and real-world information flow networks, suggest that in many settings a relatively small number of filters are fairly effective in removing a large fraction of redundant information.<\/jats:p>","DOI":"10.14778\/2140436.2140439","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"418-429","source":"Crossref","is-referenced-by-count":10,"title":["The filter-placement problem and its application to minimizing information multiplicity"],"prefix":"10.14778","volume":"5","author":[{"given":"D\u00f3ra","family":"Erd\u00f6s","sequence":"first","affiliation":[{"name":"Boston University, Boston, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vatche","family":"Ishakian","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrei","family":"Lapets","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evimaria","family":"Terzi","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Azer","family":"Bestavros","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,1]]},"reference":[{"volume-title":"YALEU\/DCS\/TR-1295","year":"2004","author":"Aspnes J.","key":"e_1_2_1_1_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1016\/j.socnet.2007.11.001"},{"key":"e_1_2_1_3_1","first-page":"126","volume-title":"ICDE","author":"Chan K.-P.","year":"1999"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1109\/MDM.2009.13"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1109\/TCSVT.2002.808080"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1109\/WCNC.2003.1200685"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/502512.502525"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1287\/opre.26.6.992"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.5555\/1769087.1769096"},{"key":"e_1_2_1_10_1","first-page":"499","volume-title":"SODA '03","author":"Goel A.","year":"2003"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1023\/A:1011122126881"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/502034.502049"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_14_1","first-page":"1650","volume-title":"AAAI","author":"Krause A.","year":"2007"},{"doi-asserted-by":"crossref","unstructured":"B. Krishnamachari D. Estrin and S. Wicker. The impact of data aggregation in wireless sens or networks. ICDCSW page 575 2002. B. Krishnamachari D. Estrin and S. Wicker. The impact of data aggregation in wireless sens or networks. ICDCSW page 575 2002.","key":"e_1_2_1_15_1","DOI":"10.1109\/ICDCSW.2002.1030829"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/1772690.1772751"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/1557019.1557077"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/1281192.1281239"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1109\/TMC.2008.82"},{"volume-title":"Wiley New York","year":"1990","author":"Mirchandani P.","key":"e_1_2_1_20_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1007\/978-3-540-69170-9_22"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1109\/SAHCN.2008.63"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1109\/MEDHOCNET.2010.5546878"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1145\/1073814.1073834"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1109\/TKDE.2003.1262183"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1007\/BF01588971"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1103\/PhysRevE.65.036104"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/1645953.1646063"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1103\/PhysRevB.55.5404"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1145\/775047.775057"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1145\/513800.513825"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2140436.2140439","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T12:53:16Z","timestamp":1746276796000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2140436.2140439"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.14778\/2140436.2140439"],"URL":"https:\/\/doi.org\/10.14778\/2140436.2140439","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}