{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:03Z","timestamp":1725558963709},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_51","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T09:26:02Z","timestamp":1278321962000},"page":"605-616","source":"Crossref","is-referenced-by-count":13,"title":["Cell Probe Lower Bounds and Approximations for Range Mode"],"prefix":"10.1007","author":[{"given":"Mark","family":"Greve","sequence":"first","affiliation":[]},{"given":"Allan Gr\u00f8nlund","family":"J\u00f8rgensen","sequence":"additional","affiliation":[]},{"given":"Kasper Dalgaard","family":"Larsen","sequence":"additional","affiliation":[]},{"given":"Jakob","family":"Truelsen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"51_CR1","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A.C.C. Yao","year":"1981","unstructured":"Yao, A.C.C.: Should tables be sorted? J. ACM\u00a028(3), 615\u2013628 (1981)","journal-title":"J. ACM"},{"issue":"1","key":"51_CR2","first-page":"1","volume":"12","author":"D. Krizanc","year":"2005","unstructured":"Krizanc, D., Morin, P., Smid, M.H.M.: Range mode and range median queries on lists and trees. Nord. J. Comput.\u00a012(1), 1\u201317 (2005)","journal-title":"Nord. J. Comput."},{"key":"51_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1007\/978-3-540-77566-9_36","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"H. Petersen","year":"2008","unstructured":"Petersen, H.: Improved bounds for range mode and range median queries. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol.\u00a04910, pp. 418\u2013423. Springer, Heidelberg (2008)"},{"issue":"4","key":"51_CR4","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.ipl.2008.10.007","volume":"109","author":"H. Petersen","year":"2008","unstructured":"Petersen, H., Grabowski, S.: Range mode and range median queries in constant time and sub-quadratic space. Inf. Process. Lett.\u00a0109(4), 225\u2013228 (2008)","journal-title":"Inf. Process. Lett."},{"key":"51_CR5","doi-asserted-by":"crossref","unstructured":"Bose, P., Kranakis, E., Morin, P., Tang, Y.: Approximate range mode and range median queries. In: Proc. 22nd Symposium on Theoretical Aspects of Computer Science, pp. 377\u2013388 (2005)","DOI":"10.1007\/978-3-540-31856-9_31"},{"key":"51_CR6","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Thorup, M.: Higher lower bounds for near-neighbor and further rich problems. In: Proc. of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 646\u2013654 (2006)","DOI":"10.1109\/FOCS.2006.35"},{"key":"51_CR7","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: (Data) structures. In: Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 434\u2013443 (2008)","DOI":"10.1109\/FOCS.2008.69"},{"key":"51_CR8","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Lower bounds for 2-dimensional range counting. In: Proc. 39th ACM Symposium on Theory of Computing, pp. 40\u201346 (2007)","DOI":"10.1145\/1250790.1250797"},{"key":"51_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1007\/978-3-540-30551-4_49","volume-title":"Algorithms and Computation","author":"J. J\u00e1J\u00e1","year":"2004","unstructured":"J\u00e1J\u00e1, J., Mortensen, C.W., Shi, Q.: Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 558\u2013568. Springer, Heidelberg (2004)"},{"key":"51_CR10","doi-asserted-by":"crossref","unstructured":"Afshani, P.: On dominance reporting in 3D. In: Proc. of the 16th Annual European Symposium on Algorithms, pp. 41\u201351 (2008)","DOI":"10.1007\/978-3-540-87744-8_4"},{"issue":"2","key":"51_CR11","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D.E. Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space theta(n). Inf. Process. Lett.\u00a017(2), 81\u201384 (1983)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"51_CR12","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jcss.1998.1577","volume":"57","author":"P.B. Miltersen","year":"1998","unstructured":"Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On data structures and asymmetric communication complexity. J. Comput. Syst. Sci.\u00a057(1), 37\u201349 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"51_CR13","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput.\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"51_CR14","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"J.R. Driscoll","year":"1989","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. Journal of Computer and System Sciences\u00a038(1), 86\u2013124 (1989)","journal-title":"Journal of Computer and System Sciences"},{"key":"51_CR15","unstructured":"Jacobson, G.J.: Succinct static data structures. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, USA (1988)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T15:40:12Z","timestamp":1558280412000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}