{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:23:50Z","timestamp":1759638230008},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319084039"},{"type":"electronic","value":"9783319084046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08404-6_20","type":"book-chapter","created":{"date-parts":[[2014,6,25]],"date-time":"2014-06-25T03:55:08Z","timestamp":1403668508000},"page":"229-240","source":"Crossref","is-referenced-by-count":1,"title":["Colored Range Searching in Linear Space"],"prefix":"10.1007","author":[{"given":"Roberto","family":"Grossi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u00f8ren","family":"Vind","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/3-540-45749-6_6","volume-title":"Algorithms - ESA 2002","author":"P.K. Agarwal","year":"2002","unstructured":"Agarwal, P.K., Govindarajan, S., Muthukrishnan, S.M.: Range searching in categorical data: Colored range searching on grid. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 17\u201328. Springer, Heidelberg (2002)"},{"issue":"1","key":"20_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1998.0967","volume":"30","author":"A. Andersson","year":"1999","unstructured":"Andersson, A.: General balanced trees. J. Algorithms\u00a030(1), 1\u201318 (1999)","journal-title":"J. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. (2008)","key":"20_CR3","DOI":"10.1007\/978-3-540-77974-2"},{"key":"20_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/3-540-60084-1_97","volume-title":"Automata, Languages and Programming","author":"P. Bozanis","year":"1995","unstructured":"Bozanis, P., Kitsios, N., Makris, C., Tsakalidis, A.K.: New upper bounds for generalized intersection searching problems. In: F\u00fcl\u00f6p, Z. (ed.) ICALP 1995. LNCS, vol.\u00a0944, pp. 464\u2013474. Springer, Heidelberg (1995)"},{"issue":"1","key":"20_CR5","first-page":"99","volume":"10","author":"P. Emde Boas van","year":"1976","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Theory Comput. Syst.\u00a010(1), 99\u2013127 (1976)","journal-title":"Theory Comput. Syst."},{"doi-asserted-by":"crossref","unstructured":"Gagie, T., K\u00e4rkk\u00e4inen, J., Navarro, G., Puglisi, S.J.: Colored range queries and document retrieval. TCS (2012)","key":"20_CR6","DOI":"10.1016\/j.tcs.2012.08.004"},{"issue":"2","key":"20_CR7","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1006\/jagm.1995.1038","volume":"19","author":"P. Gupta","year":"1995","unstructured":"Gupta, P., Janardan, R., Smid, M.: Further Results on Generalized Intersection Searching Problems: Counting, Reporting, and Dynamization. J. Algorithms\u00a019(2), 282\u2013317 (1995)","journal-title":"J. Algorithms"},{"issue":"5","key":"20_CR8","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/S0020-0190(97)00183-X","volume":"64","author":"P. Gupta","year":"1997","unstructured":"Gupta, P., Janardan, R., Smid, M.: A technique for adding range restrictions to generalized searching problems. Inform. Process. Lett.\u00a064(5), 263\u2013269 (1997)","journal-title":"Inform. Process. Lett."},{"key":"20_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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)"},{"issue":"01","key":"20_CR10","first-page":"39","volume":"3","author":"R. Janardan","year":"1993","unstructured":"Janardan, R., Lopez, M.: Generalized intersection searching problems. IJCGA\u00a03(01), 39\u201369 (1993)","journal-title":"IJCGA"},{"unstructured":"Kaplan, H., Rubin, N., Sharir, M., Verbin, E.: Counting colors in boxes. In: Proc. 18th SODA. pp. 785\u2013794 (2007)","key":"20_CR11"},{"unstructured":"van Kreveld, M.: New results on data structures in computational geometry. PhD thesis, Department of Computer Science, University of Utrecht, Netherlands (1992)","key":"20_CR12"},{"doi-asserted-by":"crossref","unstructured":"Larsen, K.G., Pagh, R.: I\/O-efficient data structures for colored range and prefix reporting. In: Proc. 23rd SODA. pp. 583\u2013592 (2012)","key":"20_CR13","DOI":"10.1137\/1.9781611973099.49"},{"doi-asserted-by":"crossref","unstructured":"Larsen, K.G., van Walderveen, F.: Near-Optimal Range Reporting Structures for Categorical Data. In: Proc. 24th SODA. pp. 265\u2013276 (2013)","key":"20_CR14","DOI":"10.1137\/1.9781611973105.20"},{"issue":"4","key":"20_CR15","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0020-0190(90)90022-P","volume":"35","author":"K. Mehlhorn","year":"1990","unstructured":"Mehlhorn, K., N\u00e4her, S.: Bounded ordered dictionaries in O(loglogN) time and O(n) space. Inform. Process. Lett.\u00a035(4), 183\u2013189 (1990)","journal-title":"Inform. Process. Lett."},{"unstructured":"Mortensen, C.W.: Generalized static orthogonal range searching in less space. Tech. rep., TR-2003-22, The IT University of Copenhagen (2003)","key":"20_CR16"},{"issue":"4","key":"20_CR17","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.comgeo.2008.09.001","volume":"42","author":"Y. Nekrich","year":"2009","unstructured":"Nekrich, Y.: Orthogonal Range Searching in Linear and Almost-linear Space. Comput. Geom. Theory Appl.\u00a042(4), 342\u2013351 (2009)","journal-title":"Comput. Geom. Theory Appl."},{"doi-asserted-by":"crossref","unstructured":"Nekrich, Y.: Space-efficient range reporting for categorical data. In: Proc. 31st PODS. pp. 113\u2013120 (2012)","key":"20_CR18","DOI":"10.1145\/2213556.2213575"},{"issue":"1","key":"20_CR19","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2543924","volume":"39","author":"Y. Nekrich","year":"2014","unstructured":"Nekrich, Y.: Efficient range searching for categorical and plain data. ACM TODS\u00a039(1), 9 (2014)","journal-title":"ACM TODS"},{"key":"20_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1007\/978-3-642-40450-4_63","volume-title":"Algorithms \u2013 ESA 2013","author":"Y. Nekrich","year":"2013","unstructured":"Nekrich, Y., Vitter, J.S.: Optimal color range reporting in one dimension. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol.\u00a08125, pp. 743\u2013754. Springer, Heidelberg (2013)"},{"unstructured":"Overmars, M.H.: Design of Dynamic Data Structures (1987)","key":"20_CR21"},{"doi-asserted-by":"crossref","unstructured":"Patrascu, M.: Lower bounds for 2-dimensional range counting. In: Proc. 39th STOC, pp. 40\u201346 (2007)","key":"20_CR22","DOI":"10.1145\/1250790.1250797"},{"issue":"3","key":"20_CR23","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.ipl.2005.04.008","volume":"95","author":"Q. Shi","year":"2005","unstructured":"Shi, Q., J\u00e1J\u00e1, J.: Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines. Inform. Process. Lett.\u00a095(3), 382\u2013388 (2005)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"20_CR24","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D. Willard","year":"1983","unstructured":"Willard, D.: Log-logarithmic worst-case range queries are possible in space \u0398(N). Inform. Process. Lett.\u00a017(2), 81\u201384 (1983)","journal-title":"Inform. Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: Proc. 44th STOC. pp. 887\u2013898 (2012)","key":"20_CR25","DOI":"10.1145\/2213977.2214056"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08404-6_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T03:44:29Z","timestamp":1558928669000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08404-6_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319084039","9783319084046"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08404-6_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}