{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,19]],"date-time":"2026-09-19T16:54:56Z","timestamp":1789836896378,"version":"4.0.1"},"reference-count":41,"publisher":"IEEE","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,9]]},"DOI":"10.1109\/allerton.2009.5394919","type":"proceedings-article","created":{"date-parts":[[2010,1,26]],"date-time":"2010-01-26T17:35:50Z","timestamp":1264527350000},"page":"613-619","source":"Crossref","is-referenced-by-count":19,"title":["A locally encodable and decodable compressed data structure"],"prefix":"10.1109","author":[{"given":"Venkat","family":"Chandar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Devavrat","family":"Shah","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gregory W.","family":"Wornell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"263","reference":[{"key":"ref39","first-page":"122","volume":"51","author":"pagh","year":"2004"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75520-3_34"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369909"},{"key":"ref31","first-page":"233","article-title":"Succinct indexable dictionaries with applications to encoding k-ary trees and multisets","author":"raman","year":"2002","journal-title":"Proc 13th Annu ACM\/SIAM Symp Discrete Algorithms (SODA)"},{"key":"ref30","first-page":"205","volume":"39","author":"ian munro","year":"2001","journal-title":"Space efficient suffix trees Journal of Algorithms"},{"key":"ref37","first-page":"823","article-title":"An optimal Bloom filter replacement","author":"pagh","year":"2005","journal-title":"Proc ACM Symposium on Discrete Algorithms (SODA)"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804332"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69903-3_15"},{"key":"ref10","author":"indyk","year":"2008","journal-title":"Practical near-optimal sparse recovery in the 11 norm Allerton"},{"key":"ref40","article-title":"Malleable Coding: Compressed Palimpsests","author":"varshney","year":"0","journal-title":"Preprint"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.834793"},{"key":"ref12","article-title":"Efficient compressive sensing with determinstic guarantees using expander graphs","author":"xu","year":"2007","journal-title":"IEEE Information Theory Workshop"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"},{"key":"ref15","article-title":"Randomness Conductors and Constant Degree Lossless Expanders","author":"capalbo","year":"2002","journal-title":"proceedings of the 34th annual ACM symposium on theory of computing"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"ref17","first-page":"248","article-title":"Constructions of LDPC codes using Ramanujan graphs and ideas from Margulis","author":"rosenthal","year":"2000","journal-title":"Proc of the 38th Allerton Conference on Communication Control and Computing"},{"key":"ref18","volume":"42","author":"sipser","year":"1996","journal-title":"Expander codes IEEE Trans Inform Theory"},{"key":"ref19","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/4347.001.0001","author":"gallager","year":"1963","journal-title":"Low-Density Parity-Check Codes"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"ref27","first-page":"383","article-title":"Efficient suffix trees on secondary storage","author":"clark","year":"1996","journal-title":"Proc ACM Symposium on Discrete Algorithms (SODA)"},{"key":"ref3","author":"cormode","year":"2004","journal-title":"Improved data stream summaries the count-min sketch and its applications"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"ref29","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","author":"ian munro","year":"1996","journal-title":"Proc 16th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS)"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20124"},{"key":"ref8","author":"indyk","year":"2007","journal-title":"Sketching streaming and sublinear-space algorithms Graduate course notes"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250824"},{"key":"ref2","author":"muthukrishnan","year":"2003","journal-title":"Data streams Algorithms and applications"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2008.4595436"},{"key":"ref9","author":"indyk","year":"2008","journal-title":"Explicit constructions for compressed sensing of sparse signals SODA"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.856942"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1145\/781027.781060"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1145\/1375457.1375472"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/1140277.1140314"},{"key":"ref23","article-title":"Analysis of a statistics counter architecture","author":"shah","year":"0","journal-title":"Proc IEEE Hotl 9"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1109\/18.910575"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.83"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1109\/18.910577"}],"event":{"name":"2009 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton)","location":"Monticello, IL, USA","start":{"date-parts":[[2009,9,30]]},"end":{"date-parts":[[2009,10,2]]}},"container-title":["2009 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/5375733\/5394483\/05394919.pdf?arnumber=5394919","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T10:51:01Z","timestamp":1558781461000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/5394919\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":41,"URL":"https:\/\/doi.org\/10.1109\/allerton.2009.5394919","relation":{},"subject":[],"published":{"date-parts":[[2009,9]]}}}