{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T18:12:42Z","timestamp":1672337562449},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,10,13]],"date-time":"2007-10-13T00:00:00Z","timestamp":1192233600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2007,12,6]]},"DOI":"10.1007\/s00453-007-9098-2","type":"journal-article","created":{"date-parts":[[2007,10,12]],"date-time":"2007-10-12T13:18:13Z","timestamp":1192195093000},"page":"357-385","source":"Crossref","is-referenced-by-count":3,"title":["Accuracy vs. Lifetime: Linear Sketches for Aggregate Queries in Sensor Networks"],"prefix":"10.1007","volume":"49","author":[{"given":"Vasundhara","family":"Puttagunta","sequence":"first","affiliation":[]},{"given":"Konstantinos","family":"Kalpakis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,13]]},"reference":[{"key":"9098_CR1","doi-asserted-by":"crossref","unstructured":"Acharya, S., Gibbons, P.B., Poosala, V., Ramaswamy, S.: Join synopses for approximate query answering. In: Proceedings ACM SIGMOD International Conference on Management of Data, pp.\u00a0275\u2013286, 1999","DOI":"10.1145\/304182.304207"},{"key":"9098_CR2","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. In: STOC \u201996: Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, New York, NY, USA, pp.\u00a020\u201329, 1996"},{"key":"9098_CR3","unstructured":"Alon, N., Gibbons, P.B., Matias, Y., Szegedy, M.: Tracking join and self-join sizes in limited storage. In: PODS \u201999: Proceedings of the Eighteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, New York, NY, USA, pp.\u00a010\u201320, 1999"},{"key":"9098_CR4","doi-asserted-by":"crossref","unstructured":"Babu, S., Widom, J.: Continuous queries over data streams. Technical report, Stanford University (2001)","DOI":"10.1145\/603867.603884"},{"key":"9098_CR5","unstructured":"Chang, J.-H., Tassiulas, L.: Energy conserving routing in wireless ad-hoc networks. In: Proceedings of IEEE INFOCOM, vol.\u00a01, pp.\u00a022\u201331, 2000"},{"key":"9098_CR6","doi-asserted-by":"crossref","unstructured":"Considine, J., Li, F., Kollios, G., Byers, J.W.: Approximate aggregation techniques for sensor databases. In: Proceedings of the 20th International Conference on Data Engineering (ICDE), pp.\u00a0449\u2013460, 2004","DOI":"10.1109\/ICDE.2004.1320018"},{"issue":"1","key":"9098_CR7","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G. Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55(1), 58\u201375 (2005)","journal-title":"J. Algorithms"},{"key":"9098_CR8","unstructured":"Dasgupta, S., Gupta, A.: An elementary proof of the Johnson-Lindenstrauss Lemma. Technical Report TR-99-006, University of California, Berkeley, CA, 1999"},{"key":"9098_CR9","volume-title":"Circulant Matrices","author":"P.J. Davis","year":"1979","unstructured":"Davis, P.J.: Circulant Matrices. Wiley, New York (1979)"},{"issue":"2","key":"9098_CR10","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","volume":"31","author":"P. Flajolet","year":"1985","unstructured":"Flajolet, P., Martin, G.N.: Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. 31(2), 182\u2013209 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"9098_CR11","doi-asserted-by":"crossref","unstructured":"Gibbons, P.B., Matias, Y.: New sampling-based summary statistics for improving approximate query answers. In: SIGMOD \u201998: Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, New York, NY, USA, pp.\u00a0331\u2013342, 1998","DOI":"10.1145\/276304.276334"},{"key":"9098_CR12","unstructured":"Gibbons, P.B., Matias, Y.: Synopsis data structures for massive data sets. In: DIMACS: Series in Discrete Mathematics and Theoretical Computer Science: Special Issue on External Memory Algorithms and Visualization, vol.\u00a0A, 1999"},{"key":"9098_CR13","unstructured":"Gibbons, P.B., Matias, Y., Poosala, V.: Aqua project white paper. Technical report, Information Sciences Research Center, Bell Laboratories (1997)"},{"key":"9098_CR14","unstructured":"Gibbons, P.B., Matias, Y., Poosala, V.: Fast incremental maintenance of approximate histograms. In: Proc. 23rd Int. Conf. Very Large Data Bases, VLDB, pp.\u00a0466\u2013475, 1997"},{"key":"9098_CR15","unstructured":"Gilbert, A.C., Kotidis, Y., Muthukrishnan, S., Strauss, M.: QuickSAND: quick summary and analysis of network data. Technical report, DIMACS (2001)"},{"key":"9098_CR16","unstructured":"Gilbert, A.C., Kotidis, Y., Muthukrishnan, S., Strauss, M.: Surfing wavelets on streams: one-pass summaries for approximate aggregate queries. In: VLDB \u201901: Proceedings of the 27th International Conference on Very Large Data Bases, San Francisco, CA, USA, pp.\u00a079\u201388, 2001"},{"key":"9098_CR17","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Kotidis, Y., Muthukrishnan, S., Strauss, M.: How to summarize the universe: dynamic maintenance of quantiles. In: VLDB, pp.\u00a0454\u2013465, 2002","DOI":"10.1016\/B978-155860869-6\/50047-0"},{"key":"9098_CR18","doi-asserted-by":"crossref","unstructured":"Guha, S., Indyk, P., Muthukrishnan, S., Strauss, M.: Histogramming data streams with fast per-item processing. In: ICALP 2002, pp.\u00a0681\u2013692, 2002","DOI":"10.1007\/3-540-45465-9_58"},{"key":"9098_CR19","unstructured":"Haas, P.J., Naughton, J.F., Seshadri, S., Stokes, L.: Sampling-based estimation of the number of distinct values of an attribute. In: VLDB\u201995, Proceedings of 21th International Conference on Very Large Data Bases, Zurich, Switzerland, pp.\u00a0311\u2013322, 1995"},{"key":"9098_CR20","doi-asserted-by":"crossref","unstructured":"Heinzelman, W.R., Chandrakasan, A., Balakrishnan, H.: Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Hawaii International Conference on System Sciences, vol.\u00a08, 2000","DOI":"10.1109\/HICSS.2000.926982"},{"key":"9098_CR21","unstructured":"Hellerstein, J.M., Hong, W., Madden, S., Stanek, K.: Beyond average: toward sophisticated sensing with queries. In: Proceedings of 2nd International Workshop on Information Processing in Sensor Networks (IPSN), pp.\u00a063\u201379, 2003"},{"issue":"6","key":"9098_CR22","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1016\/S1389-1286(03)00212-3","volume":"42","author":"K. Kalpakis","year":"2003","unstructured":"Kalpakis, K., Dasgupta, K., Namjoshi, P.: Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks. Comput. Netw. 42(6), 697\u2013716 (2003)","journal-title":"Comput. Netw."},{"key":"9098_CR23","unstructured":"Kalpakis, K., Dasgupta, K., Namjoshi, P.: Improving the lifetime of sensor networks via intelligent selection of data aggregation trees. In: Proceedings of Communication Networks and Distributed Systems Modeling and Simulation Conference (CNDS\u201903), pp.\u00a0139\u2013147, 2003"},{"key":"9098_CR24","doi-asserted-by":"crossref","unstructured":"Krishnamachari, B., Estrin, D., Wicker, S.B.: The impact of data aggregation in wireless sensor networks. In: Proceedings of International Workshop on Distributed Event-Based Systems, pp.\u00a0575\u2013578, 2002","DOI":"10.1109\/ICDCSW.2002.1030829"},{"key":"9098_CR25","series-title":"A Series of Monographs and Textbooks, vol.\u00a0Computer Science and Applied Mathematics","volume-title":"The Theory of Matrices with Applications","author":"P. Lancaster","year":"1985","unstructured":"Lancaster, P., Tismenetsky, M.: The Theory of Matrices with Applications, 2nd edn. A Series of Monographs and Textbooks, vol.\u00a0Computer Science and Applied Mathematics. Academic Press, Orlando (1985)","edition":"2"},{"key":"9098_CR26","unstructured":"LANDSAT Image Gallery: http:\/\/landsat.gsfc.nasa.gov\/images\/gallery.html . Previously at http:\/\/www.nnic.noaa.gov\/SOCC\/gallery.htm"},{"key":"9098_CR27","doi-asserted-by":"crossref","unstructured":"Lindsay, S., Raghavendra, C.S., Sivalingam, K.M.: Data gathering in sensor networks using the energy*delay metric. In: IPDPS \u201901: Proceedings of the 15th International Parallel & Distributed Processing Symposium, Washington, DC, USA, p.\u00a0188, 2001","DOI":"10.1109\/IPDPS.2001.925196"},{"key":"9098_CR28","doi-asserted-by":"crossref","unstructured":"Madden, S., Franklin, M.J.: Fjording the stream: an architecture for queries over streaming sensor data. In: Proceedings of the 18th International Conference on Data Engineering (ICDE\u201902), p.\u00a0555, 2002","DOI":"10.1109\/ICDE.2002.994774"},{"key":"9098_CR29","doi-asserted-by":"crossref","unstructured":"Madden, S., Szewczyk, R., Franklin, M.J., Culler, D.: Supporting aggregate queries over ad-hoc wireless sensor networks. In: WMCSA \u201902: Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications, Washington, DC, USA, p.\u00a049, 2002","DOI":"10.1109\/MCSA.2002.1017485"},{"key":"9098_CR30","unstructured":"Madden, S.R., Franklin, M.J., Hellerstein, J.M., Hong, W.: TAG: a tiny aggregation service for ad-hoc sensor networks. In: Proceedings of the ACM Symposium on Operating System Design and Implementation (OSDI), 2002"},{"key":"9098_CR31","doi-asserted-by":"crossref","unstructured":"Nath, S., Gibbons, P.B., Seshan, S., Anderson, Z.R.: Synopsis diffusion for robust aggregation in sensor networks. In: SenSys \u201904: Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, New York, NY, USA, pp.\u00a0250\u2013262, 2004","DOI":"10.1145\/1031495.1031525"},{"key":"9098_CR32","unstructured":"Poosala, V.: Histogram-based estimation techniques in database systems. Ph.D. thesis, University of Wisconsin, Madison, Wisconsin, USA (1997)"},{"key":"9098_CR33","unstructured":"Puttagunta, V., Kalpakis, K.: Answering approximate aggregate queries using linear sketches. Technical Report TR-CS-03-29, University of Maryland Baltimore County (2003)"},{"key":"9098_CR34","unstructured":"Strang, G.: Mathematical methods for engineers I: supplementary material. http:\/\/www-math.mit.edu\/18085 . Four Special Matrices (applmath1_1.pdf), Solutions (applmath1_1sols.pdf), Eigenvalues and Eigenvectors (applmath1_5.pdf), The Stiffness Matrix (applmath2_1.pdf)"},{"key":"9098_CR35","volume-title":"Introduction to Applied Mathematics","author":"G. Strang","year":"1986","unstructured":"Strang, G.: Introduction to Applied Mathematics. Wellesley\u2013Cambridge Press, Wellesley (1986)"},{"key":"9098_CR36","doi-asserted-by":"crossref","unstructured":"Thaper, N., Guha, S., Indyk, P., Koudas, N.: Dynamic multidimensional histograms. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp.\u00a0428\u2013439, 2002","DOI":"10.1145\/564691.564741"},{"key":"9098_CR37","unstructured":"Yao, Y., Gehrke, J.E.: Query processing in sensor networks. In: Proceedings of the First Biennial Conference on Innovative Data Systems Research (CIDR), 2003"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9098-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9098-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9098-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:00Z","timestamp":1559123100000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9098-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,13]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,12,6]]}},"alternative-id":["9098"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9098-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,13]]}}}