{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T21:31:10Z","timestamp":1765143070092},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642404498"},{"type":"electronic","value":"9783642404504"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_63","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T03:22:47Z","timestamp":1376623367000},"page":"743-754","source":"Crossref","is-referenced-by-count":4,"title":["Optimal Color Range Reporting in One Dimension"],"prefix":"10.1007","author":[{"given":"Yakov","family":"Nekrich","sequence":"first","affiliation":[]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"63_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: Optimal static range reporting in one dimension. In: Proc. 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 476\u2013482 (2001)","DOI":"10.1145\/380752.380842"},{"key":"63_CR2","doi-asserted-by":"crossref","unstructured":"Arge, L., Samoladas, V., Vitter, J.S.: On two-dimensional indexability and optimal range search indexing. In: Proc. 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 346\u2013357 (1999)","DOI":"10.1145\/303976.304010"},{"issue":"6","key":"63_CR3","doi-asserted-by":"publisher","first-page":"1488","DOI":"10.1137\/S009753970240481X","volume":"32","author":"L. Arge","year":"2003","unstructured":"Arge, L., Vitter, J.S.: Optimal external memory interval management. SIAM J. Comput.\u00a032(6), 1488\u20131508 (2003)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"63_CR4","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/jcss.2002.1822","volume":"65","author":"P. Beame","year":"2002","unstructured":"Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci.\u00a065(1), 38\u201372 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"63_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-642-31155-0_26","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"T.M. Chan","year":"2012","unstructured":"Chan, T.M., Durocher, S., Skala, M., Wilkinson, B.T.: Linear-space data structures for range minority query in arrays. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 295\u2013306. Springer, Heidelberg (2012)"},{"issue":"3","key":"63_CR6","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B.: Filtering search: a new approach to query-answering. SIAM J. Comput.\u00a015(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"63_CR7","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"M.L. Fredman","year":"1994","unstructured":"Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci.\u00a048(3), 533\u2013551 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"63_CR8","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. 16th Annual ACM Symposium on Theory of Computing (STOC 1984), pp. 135\u2013143 (1984)","DOI":"10.1145\/800057.808675"},{"issue":"2","key":"63_CR9","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.H.M.: Further results on generalized intersection searching problems: counting, reporting, and dynamization. Journal of Algorithms\u00a019(2), 282\u2013317 (1995)","journal-title":"Journal of Algorithms"},{"issue":"1","key":"63_CR10","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1142\/S021819599300004X","volume":"3","author":"R. Janardan","year":"1993","unstructured":"Janardan, R., Lopez, M.A.: Generalized intersection searching problems. International Journal of Computational Geometry and Applications\u00a03(1), 39\u201369 (1993)","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"63_CR11","doi-asserted-by":"crossref","unstructured":"Larsen, K.G., Pagh, R.: I\/O-efficient data structures for colored range and prefix reporting. In: Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 583\u2013592 (2012)","DOI":"10.1137\/1.9781611973099.49"},{"key":"63_CR12","unstructured":"Larsen, K.G., van Walderveen, F.: Near-optimal range reporting structures for categorical data. In: Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (to appear, 2013)"},{"issue":"2","key":"63_CR13","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"E.M. McCreight","year":"1985","unstructured":"McCreight, E.M.: Priority search trees. SIAM J. Comput.\u00a014(2), 257\u2013276 (1985)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"63_CR14","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."},{"key":"63_CR15","unstructured":"Mortensen, C.W.: Generalized static orthogonal range searching in less space. Technical report, IT University Technical Report Series 2003-33 (2003)"},{"key":"63_CR16","doi-asserted-by":"crossref","unstructured":"Mortensen, C.W., Pagh, R., Patrascu, M.: On dynamic range reporting in one dimension. In: Proc. 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 104\u2013111 (2005)","DOI":"10.1145\/1060590.1060606"},{"key":"63_CR17","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 657\u2013666 (2002)"},{"key":"63_CR18","doi-asserted-by":"crossref","unstructured":"Nekrich, Y.: Space-efficient range reporting for categorical data. In: Proc. 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pp. 113\u2013120 (2012)","DOI":"10.1145\/2213556.2213575"},{"key":"63_CR19","doi-asserted-by":"crossref","unstructured":"Nekrich, Y., Vitter, J.S.: Optimal color range reporting in one dimension. CoRR, abs\/1306.5029 (2013)","DOI":"10.1007\/978-3-642-40450-4_63"},{"issue":"3","key":"63_CR20","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. Inf. Process. Lett.\u00a095(3), 382\u2013388 (2005)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"63_CR21","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M. Thorup","year":"1999","unstructured":"Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J. ACM\u00a046(3), 362\u2013394 (1999)","journal-title":"J. ACM"},{"key":"63_CR22","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Math. Sys. Theory\u00a010, 99\u2013127 (1977)","journal-title":"Math. Sys. Theory"},{"issue":"3","key":"63_CR23","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1137\/S0097539797322425","volume":"29","author":"D.E. Willard","year":"2000","unstructured":"Willard, D.E.: Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree. SIAM J. Comput.\u00a029(3), 1030\u20131049 (2000)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_63","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T17:11:55Z","timestamp":1558026715000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_63"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_63","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}