{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T06:31:17Z","timestamp":1790922677853,"version":"4.1.0"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2002,1]]},"abstract":"<jats:p>Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and the monitoring and operations of large systems. In network operations, raw data typically arrive in streams, and decisions must be made by algorithms that make one pass over each stream, throw much of the raw data away, and produce \"synopses\" or \"sketches\" for further processing. Moreover, network-generated massive data sets are often distributed: Several different, physically separated network elements may receive or generate data streams that, together, comprise one logical data set; to be of use in operations, the streams must be analyzed locally and their synopses sent to a central operations facility. The enormous scale, distributed nature, and one-pass processing requirement on the data sets of interest must be addressed with new algorithmic techniques.<\/jats:p>\n                  <jats:p>\n                    We present one fundamental new technique here: a space-efficient, one-pass algorithm for approximating the L\n                    <jats:sup>1<\/jats:sup>\n                    -difference $\\sum_i|a_i-b_i|$ between two functions, when the function values a\n                    <jats:sub>i<\/jats:sub>\n                    and b\n                    <jats:sub>i<\/jats:sub>\n                    are given as data streams, and their order is chosen by an adversary. Our main technical innovation, which may be of interest outside the realm of massive data stream algorithmics, is a method of constructing families $\\{V_j(s)\\}$ of limited-independence random variables that are range-summable, by which we mean that $\\sum_{j=0}^{c-1} V_j(s)$ is computable in time polylog(c) for all seeds s. Our L\n                    <jats:sup>1<\/jats:sup>\n                    -difference algorithm can be viewed as a \"sketching\" algorithm, in the sense of [Broder et al., J. Comput. System Sci., 60 (2000), pp. 630--659], and our technique performs better than that of Broder et al. when used to approximate the symmetric difference of two sets with small symmetric difference.\n                  <\/jats:p>","DOI":"10.1137\/s0097539799361701","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"131-151","source":"Crossref","is-referenced-by-count":69,"title":["An Approximate\n                    <i>L<\/i>\n                    <sup>1<\/sup>\n                    -Difference Algorithm for Massive Data Streams"],"prefix":"10.1137","volume":"32","author":[{"given":"Joan","family":"Feigenbaum","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sampath","family":"Kannan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin J.","family":"Strauss","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mahesh","family":"Viswanathan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"R2","unstructured":"N. Alon, P. Gibbons, Y. Matias, and M. Szegedy,\n                      Tracking join and self\u2010join sizes in limited storage\n                      , in Proceedings of the 18th Symposium on Principles of Database Systems, ACM, New York, 1999, pp. 10\u201320."},{"key":"R3","volume-title":"The probabilistic method","author":"Alon Noga","year":"1992"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1690"},{"key":"R5","unstructured":"A. Broder, S. Glassman, M. Manasse, and G. Zweig,\n                      Syntactic clustering of the Web\n                      , in Proceedings of the Sixth International World Wide Web Conference, Santa Clara, CA, World Wide Web Consortium, Cambridge, MA, 1997, pp. 391\u2013404. Also available online from http:\/\/www.scope.gmd.de\/info\/www6\/technical\/[2]paper205\/paper205.html."},{"key":"R6","unstructured":"Cisco NetFlow, 1998."},{"key":"R6","unstructured":"Available online from http:\/\/www.cisco.com\/warp\/public\/732\/netflow\/."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1534"},{"key":"R8","unstructured":"P. Flajolet and G. N. Martin,\n                      Probabilistic counting\n                      , in Proceedings of the 24th Foundations of Computer Science Conference, IEEE Computer Society, Los Alamitos, 1983, pp. 76\u201382."},{"key":"R9","unstructured":"Phillip Gibbons, Yossi Matias, Synopsis data structures for massive data sets, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 50, Amer. Math. Soc., Providence, RI, 1999, 39\u2013702000h:68050"},{"key":"R10","unstructured":"M. R. Henzinger, P. Raghavan, and S. Rajagopalan,\n                      Computing on Data Streams\n                      , Technical Report 1998\u2010011, Digital Equipment Corporation Systems Research Center, Palo Alto, CA, 1998."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60342-3"},{"key":"R12","unstructured":"F. J. MacWilliams and N. J. A. Sloane,\n                      The Theory of Error\u2010Correcting Codes\n                      , North\u2010Holland Math. Library 16, North Holland, New York, 1977."},{"key":"R13","unstructured":"E. Rains and N. J. A. Sloane,\n                      Private communication\n                      ."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539799361701","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:17Z","timestamp":1787336297000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539799361701"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,1]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,1]]}},"alternative-id":["10.1137\/S0097539799361701"],"URL":"https:\/\/doi.org\/10.1137\/s0097539799361701","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,1]]}}}