{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:50:26Z","timestamp":1725861026723},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540286073"},{"type":"electronic","value":"9783540286080"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-540-28608-0_14","type":"book-chapter","created":{"date-parts":[[2016,7,11]],"date-time":"2016-07-11T14:10:43Z","timestamp":1468246243000},"page":"283-300","source":"Crossref","is-referenced-by-count":1,"title":["Stable Distributions in Streaming Computations"],"prefix":"10.1007","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Indyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,12]]},"reference":[{"key":"14_CR1","volume-title":"Proceedings of the ACM Symposium on Theory of Computing","author":"N. Ailon","year":"2006","unstructured":"N. Ailon, B. Chazelle, Approximate nearest neighbors and the fast Johnson\u2013Lindenstrauss transform, in Proceedings of the ACM Symposium on Theory of Computing (2006)"},{"key":"14_CR2","first-page":"20","volume-title":"Proceedings of the ACM Symposium on Theory of Computing","author":"N. Alon","year":"1996","unstructured":"N. Alon, Y. Matias, M. Szegedy, The space complexity of approximating the frequency moments, in Proceedings of the ACM Symposium on Theory of Computing (1996), pp. 20\u201329. Journal version in J. Comput. Syst. Sci. 58, 137\u2013147 (1999)"},{"key":"14_CR3","first-page":"1","volume-title":"Proceedings of RANDOM 2002","author":"Z. Bar-Yossef","year":"2002","unstructured":"Z. Bar-Yossef, T.S. Jayram, R. Kumar, D. Sivakumar, L. Trevisian, Counting distinct elements in a data stream, in Proceedings of RANDOM 2002 (2002), pp. 1\u201310"},{"key":"14_CR4","first-page":"514","volume-title":"IEEE Conference on Foundations of Computer Science","author":"B. Brinkman","year":"2003","unstructured":"B. Brinkman, M. Charikar, On the impossibility of dimensionality reduction in L 1 $L_{1}$ , in IEEE Conference on Foundations of Computer Science (2003), pp. 514\u2013523"},{"key":"14_CR5","volume-title":"Proceedings of ACM-SIAM Symposium on Discrete Algorithms","author":"A. Chakrabarti","year":"2007","unstructured":"A. Chakrabarti, G. Cormode, A. McGregor, A near-optimal algorithm for computing the entropy of a stream, in Proceedings of ACM-SIAM Symposium on Discrete Algorithms (2007)"},{"issue":"354","key":"14_CR6","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1080\/01621459.1976.10480344","volume":"71","author":"J.M. Chambers","year":"1976","unstructured":"J.M. Chambers, C.L. Mallows, B.W. Stuck, A method for simulating stable random variables. J. Am. Stat. Assoc. 71(354), 340\u2013344 (1976)","journal-title":"J. Am. Stat. Assoc."},{"key":"14_CR7","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1007\/3-540-45465-9_59","volume-title":"Procedings of the International Colloquium on Automata, Languages and Programming (ICALP)","author":"M. Charikar","year":"2002","unstructured":"M. Charikar, K. Chen, M. Farach-Colton, Finding frequent items in data streams, in Procedings of the International Colloquium on Automata, Languages and Programming (ICALP) (2002), pp.\u00a0693\u2013703"},{"key":"14_CR8","first-page":"380","volume-title":"Proceedings of the ACM Symposium on Theory of Computing","author":"M.S. Charikar","year":"2002","unstructured":"M.S. Charikar, Similarity estimation techniques from rounding algorithms, in Proceedings of the ACM Symposium on Theory of Computing (2002), pp. 380\u2013388"},{"key":"14_CR9","unstructured":"G. Cormode, Sequence distance embeddings. PhD thesis, University of Warwick (2003)"},{"key":"14_CR10","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/B978-155860869-6\/50037-8","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"G. Cormode","year":"2002","unstructured":"G. Cormode, M. Datar, P. Indyk, S. Muthukrishnan, Comparing data streams using Hamming norms, in Proceedings of the International Conference on Very Large Data Bases (2002), pp.\u00a0335\u2013345. Journal version in IEEE Trans. Knowl. Data Eng. 15(3), 529\u2013541 (2003)"},{"key":"14_CR11","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1109\/ICDE.2002.994778","volume-title":"Proceedings of the International Conference on Data Engineering","author":"G. Cormode","year":"2002","unstructured":"G. Cormode, P. Indyk, N. Koudas, S. Muthukrishnan, Fast mining of tabular data via approximate distance computations, in Proceedings of the International Conference on Data Engineering (2002), pp. 605\u2013616"},{"key":"14_CR12","first-page":"667","volume-title":"Proceedings of ACM\u2013SIAM Symposium on Discrete Algorithms","author":"G. Cormode","year":"2002","unstructured":"G. Cormode, S. Muthukrishnan, The string edit distance matching problem with moves, in Proceedings of ACM\u2013SIAM Symposium on Discrete Algorithms (2002), pp. 667\u2013676"},{"key":"14_CR13","series-title":"LNCS","volume-title":"Proceedings of the European Symposium on Algorithms (ESA)","author":"G. Cormode","year":"2003","unstructured":"G. Cormode, S. Muthukrishnan, Estimating dominance norms of multiple data streams, in Proceedings of the European Symposium on Algorithms (ESA). LNCS, vol.\u00a02838 (2003)"},{"key":"14_CR14","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1007\/3-540-48224-5_40","volume-title":"Proceedings of 28th International Colloquium on Automata, Languages and Programming","author":"G. Cormode","year":"2001","unstructured":"G. Cormode, S. Muthukrishnan, S.C. \u1e62ahinalp, Permutation editing and matching via embeddings, in Proceedings of 28th International Colloquium on Automata, Languages and Programming, vol.\u00a02076 (2001), pp. 481\u2013492"},{"key":"14_CR15","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1145\/872757.872838","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data","author":"C. Cranor","year":"2003","unstructured":"C. Cranor, T. Johnson, O. Spatscheck, V. Shkapenyuk, Gigascope: a stream database for network applications, in Proceedings of ACM SIGMOD International Conference on Management of Data (2003), pp. 647\u2013651"},{"key":"14_CR16","volume-title":"Symposium on Computational Geometry","author":"M. Datar","year":"2004","unstructured":"M. Datar, N. Immorlica, P. Indyk, V.S. Mirrokni, Locality-sensitive hashing scheme based on p $p$ -stable distributions, in Symposium on Computational Geometry (2004)"},{"key":"14_CR17","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/948205.948225","volume-title":"Proceedings of the Internet Measurement Conference","author":"C. Estan","year":"2003","unstructured":"C. Estan, G. Varghese, M. Fisk, Bitmap algorithms for counting active flows on high speed links, in Proceedings of the Internet Measurement Conference (2003), pp. 153\u2013166"},{"key":"14_CR18","first-page":"501","volume-title":"IEEE Conference on Foundations of Computer Science","author":"J. Feigenbaum","year":"1999","unstructured":"J. Feigenbaum, S. Kannan, M. Strauss, M. Viswanathan, An approximate L 1 $L_{1}$ -difference algorithm for massive data streams, in IEEE Conference on Foundations of Computer Science (1999), pp. 501\u2013511"},{"key":"14_CR19","first-page":"76","volume-title":"IEEE Conference on Foundations of Computer Science","author":"P. Flajolet","year":"1983","unstructured":"P. Flajolet, G.N. Martin, Probabilistic counting, in IEEE Conference on Foundations of Computer Science (1983), pp. 76\u201382. Journal version in J. Comput. Syst. Sci. 31, 182\u2013209 (1985)"},{"key":"14_CR20","first-page":"193","volume-title":"Symposium on Theoretical Aspects of Computer Science (STACS)","author":"J. Fong","year":"2000","unstructured":"J. Fong, M. Strauss, An approximate L p $L_{p}$ -difference algorithm for massive data streams, in Symposium on Theoretical Aspects of Computer Science (STACS) (2000), pp. 193\u2013204"},{"key":"14_CR21","volume-title":"Proceedings of the European Symposium on Algorithms (ESA)","author":"S. Ganguly","year":"2006","unstructured":"S. Ganguly, B. Lakshminath, Estimating entropy over data streams, in Proceedings of the European Symposium on Algorithms (ESA) (2006)"},{"key":"14_CR22","first-page":"143","volume-title":"Proceedings of ACM Principles of Database Systems","author":"M. Garofalakis","year":"2003","unstructured":"M. Garofalakis, A. Kumar, Correlating XML data streams using tree-edit distance embeddings, in Proceedings of ACM Principles of Database Systems (2003), pp. 143\u2013154"},{"key":"14_CR23","first-page":"541","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"P. Gibbons","year":"2001","unstructured":"P. Gibbons, Distinct sampling for highly-accurate answers to distinct values queries and event reports, in Proceedings of the International Conference on Very Large Data Bases (2001), pp.\u00a0541\u2013550"},{"key":"14_CR24","first-page":"281","volume-title":"ACM Symposium on Parallel Algorithms and Architectures (SPAA)","author":"P. Gibbons","year":"2001","unstructured":"P. Gibbons, S. Tirthapura, Estimating simple functions on the union of data streams, in ACM Symposium on Parallel Algorithms and Architectures (SPAA) (2001), pp. 281\u2013290"},{"key":"14_CR25","first-page":"389","volume-title":"Proceedings of the ACM Symposium on Theory of Computing","author":"A. Gilbert","year":"2002","unstructured":"A. Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan, M. Strauss, Fast, small-space algorithms for approximate histogram maintenance, in Proceedings of the ACM Symposium on Theory of Computing (2002), pp. 389\u2013398"},{"key":"14_CR26","first-page":"189","volume-title":"IEEE Conference on Foundations of Computer Science","author":"P. Indyk","year":"2000","unstructured":"P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, in IEEE Conference on Foundations of Computer Science (2000), pp. 189\u2013197"},{"key":"14_CR27","first-page":"10","volume-title":"IEEE Conference on Foundations of Computer Science","author":"P. Indyk","year":"2001","unstructured":"P. Indyk, Algorithmic aspects of geometric embeddings (invited tutorial), in IEEE Conference on Foundations of Computer Science (2001), pp. 10\u201335"},{"key":"14_CR28","volume-title":"Proceedings of the ACM Symposium on Theory of Computing","author":"P. Indyk","year":"2004","unstructured":"P. Indyk, Algorithms for dynamic geometric problems over data streams, in Proceedings of the ACM Symposium on Theory of Computing (2004)"},{"key":"14_CR29","first-page":"604","volume-title":"Proceedings of the ACM Symposium on Theory of Computing","author":"P. Indyk","year":"1998","unstructured":"P. Indyk, R. Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, in Proceedings of the ACM Symposium on Theory of Computing (1998), pp.\u00a0604\u2013613"},{"key":"14_CR30","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W.B. Johnson","year":"1984","unstructured":"W.B. Johnson, J. Lindenstrauss, Extensions of Lipschitz mapping into Hilbert space. Contemp. Math. 26, 189\u2013206 (1984)","journal-title":"Contemp. Math."},{"key":"14_CR31","unstructured":"P. Li, Very sparse stable random projections, estimators and tail bounds for stable random projections. Technical report (2006). arXiv:cs.DS\/0611114"},{"key":"14_CR32","unstructured":"P. Li, T. Hastie, K.W. Church, Nonlinear estimators and tail bounds for dimension reduction in L 1 $L_{1}$ using Cauchy random projections. J. Mach. Learn. Res. (2007)"},{"key":"14_CR33","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matou\u0161ek","year":"2002","unstructured":"J. Matou\u0161ek, Lectures on Discrete Geometry (Springer, Berlin, 2002)"},{"key":"14_CR34","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"R. Motwani, P. Raghavan, Randomized Algorithms (Cambridge University Press, Cambridge, 1995)"},{"key":"14_CR35","volume-title":"Proceedings of ACM\u2013SIAM Symposium on Discrete Algorithms","author":"S. Muthukrishnan","year":"2003","unstructured":"S. Muthukrishnan, Data streams: algorithms and applications, in Proceedings of ACM\u2013SIAM Symposium on Discrete Algorithms (2003)"},{"key":"14_CR36","volume-title":"IEEE Conference on Foundations of Computer Science","author":"A. Naor","year":"2006","unstructured":"A. Naor, G. Schechtman, Planar earthmover is not in L 1 $L_{1}$ , in IEEE Conference on Foundations of Computer Science (2006)"},{"key":"14_CR37","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"N. Nisan","year":"1992","unstructured":"N. Nisan, Pseudorandom generators for space-bounded computation. Combinatorica 12, 449\u2013461 (1992)","journal-title":"Combinatorica"},{"key":"14_CR38","unstructured":"J. Nolan, Stable distributions. Available from http:\/\/academic2.american.edu\/~jpnolan\/stable\/chap1.ps"},{"key":"14_CR39","first-page":"615","volume-title":"Proceedings of ACM-SIAM Symposium on Discrete Algorithms","author":"M. Thorup","year":"2004","unstructured":"M. Thorup, Y. Zhang, Tabulation based 4-universal hashing with applications to second moment estimation, in Proceedings of ACM-SIAM Symposium on Discrete Algorithms (2004), pp. 615\u2013624"},{"key":"14_CR40","doi-asserted-by":"crossref","DOI":"10.1515\/9783110935974","volume-title":"Chance and Stability: Stable Distributions and Their Applications","author":"V.V. Uchaikin","year":"1999","unstructured":"V.V. Uchaikin, V.M. Zolotarev, Chance and Stability: Stable Distributions and Their Applications (VSP, Utrecht, 1999)"},{"key":"14_CR41","first-page":"167","volume-title":"Proceedings of ACM\u2013SIAM Symposium on Discrete Algorithms","author":"D. Woodruff","year":"2004","unstructured":"D. Woodruff, Optimal space lower bounds for all frequency moments, in Proceedings of ACM\u2013SIAM Symposium on Discrete Algorithms (2004), pp. 167\u2013175"},{"key":"14_CR42","series-title":"Translations of Mathematical Monographs","volume-title":"One Dimensional Stable Distributions","author":"V.M. Zolotarev","year":"1983","unstructured":"V.M. Zolotarev, One Dimensional Stable Distributions. Translations of Mathematical Monographs, vol.\u00a065 (Am. Math. Soc., Providence, 1983)"}],"container-title":["Data-Centric Systems and Applications","Data Stream Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-28608-0_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T05:27:29Z","timestamp":1718688449000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-28608-0_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783540286073","9783540286080"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-28608-0_14","relation":{},"ISSN":["2197-9723","2197-974X"],"issn-type":[{"type":"print","value":"2197-9723"},{"type":"electronic","value":"2197-974X"}],"subject":[],"published":{"date-parts":[[2016]]}}}