{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T14:14:48Z","timestamp":1778249688685,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540742074","type":"print"},{"value":"9783540742081","type":"electronic"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"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":[[2007]]},"DOI":"10.1007\/978-3-540-74208-1_44","type":"book-chapter","created":{"date-parts":[[2007,8,27]],"date-time":"2007-08-27T14:52:26Z","timestamp":1188226346000},"page":"609-623","source":"Crossref","is-referenced-by-count":3,"title":["Sublinear Algorithms for Approximating String Compressibility"],"prefix":"10.1007","author":[{"given":"Sofya","family":"Raskhodnikova","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Smith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"44_CR1","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci.\u00a058(1), 137\u2013147 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"44_CR2","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1145\/380752.380810","volume-title":"Proceedings of the thirty-third annual ACM symposium on Theory of computing","author":"Z. Bar-Yossef","year":"2001","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Sampling algorithms: lower bounds and applications. In: Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp. 266\u2013275. ACM Press, New York (2001)"},{"issue":"1","key":"44_CR3","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1137\/S0097539702403645","volume":"35","author":"T. Batu","year":"2005","unstructured":"Batu, T., Dasgupta, S., Kumar, R., Rubinfeld, R.: Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, and Ronitt Rubinfeld. SIAM Journal on Computing\u00a035(1), 132\u2013150 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"44_CR4","doi-asserted-by":"crossref","unstructured":"Benedetto, D., Caglioti, E., Loreto, V.: Language trees and zipping. Phys. Rev. Lett. 88(4) (2002). (See comment by Khmelev DV, Teahan WJ, Phys Rev Lett. 90(8):089803, (2003) and the reply Phys Rev Lett. 90(8):089804, 2003)","DOI":"10.1103\/PhysRevLett.90.089804"},{"key":"44_CR5","unstructured":"Brautbar, M., Samorodnitsky, A.: Approximating the entropy of large alphabets. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2007)"},{"key":"44_CR6","unstructured":"Bunge, J.: Bibligraphy on estimating the number of classes in a population, http:\/\/www.stat.cornell.edu\/~bunge\/bibliography.htm"},{"key":"44_CR7","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/335168.335230","volume-title":"PODS","author":"M. Charikar","year":"2000","unstructured":"Charikar, M., Chaudhuri, S., Motwani, R., Narasayya, V.R.: Towards estimation error guarantees for distinct values. In: PODS, pp. 268\u2013279. ACM, New York (2000)"},{"issue":"4","key":"44_CR8","doi-asserted-by":"publisher","first-page":"1523","DOI":"10.1109\/TIT.2005.844059","volume":"51","author":"R. Cilibrasi","year":"2005","unstructured":"Cilibrasi, R., Vit\u00e1nyi, P.M.B.: Clustering by compression. IEEE Transactions on Information Theory\u00a051(4), 1523\u20131545 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"key":"44_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/11750321_2","volume-title":"Theory and Applications of Models of Computation","author":"R. Cilibrasi","year":"2006","unstructured":"Cilibrasi, R., Vit\u00e1nyi, P.M.B.: Similarity of objects and the meaning of words. In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol.\u00a03959, pp. 21\u201345. Springer, Heidelberg (2006)"},{"key":"44_CR10","doi-asserted-by":"publisher","DOI":"10.1002\/0471200611","volume-title":"Elements of Information Theory","author":"T. Cover","year":"1991","unstructured":"Cover, T., Thomas, J.: Elements of Information Theory. Wiley & Sons, Chichester (1991)"},{"key":"44_CR11","unstructured":"Kukushkina, O.V., Polikarpov, A.A., Khmelev, D.V.: Using literal and grammatical statistics for authorship attribution. Prob. Peredachi Inf.\u00a037(2), 96\u201398 (2000) [Probl. Inf. Transm. ( Engl. Transl.) 37, 172\u2013184 (2001)]"},{"key":"44_CR12","unstructured":"Lehman, E., Shelat, A.: Approximation algorithms for grammer-based compression. In: Proc. 18th Annual Symp. on Discrete Algorithms, pp. 205\u2013212 (2002)"},{"key":"44_CR13","doi-asserted-by":"crossref","unstructured":"Li, M., Chen, X., Li, X., Ma, B., Vit\u00e1nyi, P.M.B.: The similarity metric. IEEE Transactions on Information Theory\u00a050(12), 3250\u20133264 (2004) (Prelim. version in SODA 2003)","DOI":"10.1109\/TIT.2004.838101"},{"key":"44_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M. Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and Its Applications. Springer, Heidelberg (1997)"},{"key":"44_CR15","unstructured":"Loewenstern, D., Hirsh, H., Noordewier, M., Yianilos, P.: DNA sequence classification using compression-based induction. Technical Report 95-04, Rutgers University, DIMACS (1995)"},{"key":"44_CR16","unstructured":"Raskhodnikova, S., Ron, D., Rubinfeld, R., Shpilka, A., Smith, A.: Sublinear algorithms for approximating string compressibility and the distribution support size. Electronic Colloquium on Computational Complexity, TR05-125 (2005)"},{"key":"44_CR17","doi-asserted-by":"crossref","unstructured":"Raskhodnikova, S., Ron, D., Rubinfeld, R., Smith, A.: Sublinear algorithms for approximating string compressibility. Full version of this paper, in preparation, Arxiv Report 0706.1084 [cs.DS] (June 2007)","DOI":"10.1007\/978-3-540-74208-1_44"},{"key":"44_CR18","unstructured":"Raskhodnikova, S., Ron, D., Shpilka, A., Smith, A.: On the difficulty of approximating the support size of a distribution (Manuscript 2007)"},{"key":"44_CR19","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Transactions on Information Theory\u00a023, 337\u2013343 (1977)","journal-title":"IEEE Transactions on Information Theory"},{"key":"44_CR20","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J. Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory\u00a024, 530\u2013536 (1978)","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74208-1_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,22]],"date-time":"2021-08-22T11:22:54Z","timestamp":1629631374000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74208-1_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540742074","9783540742081"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74208-1_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007]]}}}