{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T11:57:46Z","timestamp":1648555066398},"reference-count":5,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2011,4]]},"abstract":"<jats:p> In this paper we consider the operator mapping problem for in-network stream processing applications. In-network stream processing consists in applying a tree of operators in steady-state to multiple data objects that are continually updated at various locations on a network. Examples of in-network stream processing include the processing of data in a sensor network, or of continuous queries on distributed relational databases. We study the operator mapping problem in a \"constructive\" scenario, i.e., a scenario in which one builds a platform dedicated to the application by purchasing processing servers with various costs and capabilities. The objective is to minimize the cost of the platform while ensuring that the application achieves a minimum steady-state throughput. The first contribution of this paper is the formalization of a set of relevant operator-placement problems, and a proof that even simple versions of the problem are NP-complete. Our second contribution is the design of several polynomial time heuristics, which are evaluated via extensive simulations and compared to theoretical bounds for optimal solutions. <\/jats:p>","DOI":"10.1142\/s012905411100826x","type":"journal-article","created":{"date-parts":[[2011,4,18]],"date-time":"2011-04-18T10:11:52Z","timestamp":1303121512000},"page":"621-638","source":"Crossref","is-referenced-by-count":1,"title":["RESOURCE ALLOCATION STRATEGIES FOR CONSTRUCTIVE IN-NETWORK STREAM PROCESSING"],"prefix":"10.1142","volume":"22","author":[{"given":"ANNE","family":"BENOIT","sequence":"first","affiliation":[{"name":"\u00c9cole Normale Sup\u00e9rieure de Lyon, 46 all\u00e9e d'Italie, 69364 Lyon Cedex 07, France"}]},{"given":"VERONIKA","family":"REHN-SONIGO","sequence":"additional","affiliation":[{"name":"\u00c9cole Normale Sup\u00e9rieure de Lyon, 46 all\u00e9e d'Italie, 69364 Lyon Cedex 07, France"}]},{"given":"YVES","family":"ROBERT","sequence":"additional","affiliation":[{"name":"\u00c9cole Normale Sup\u00e9rieure de Lyon, 46 all\u00e9e d'Italie, 69364 Lyon Cedex 07, France"}]},{"given":"HENRI","family":"CASANOVA","sequence":"additional","affiliation":[{"name":"University of Hawai'i at Manoa, 1680 East-West Road, Honolulu, HI 96822, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2003.1195413"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1145\/234313.234367"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.1042"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105002930"},{"key":"rf20","volume-title":"Computers and Intractability, a Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905411100826X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:23:19Z","timestamp":1565191399000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905411100826X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4]]},"references-count":5,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2011,4]]}},"alternative-id":["10.1142\/S012905411100826X"],"URL":"https:\/\/doi.org\/10.1142\/s012905411100826x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4]]}}}