{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:27Z","timestamp":1759637667582},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319024318"},{"type":"electronic","value":"9783319024325"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-02432-5_15","type":"book-chapter","created":{"date-parts":[[2013,9,29]],"date-time":"2013-09-29T20:51:58Z","timestamp":1380487918000},"page":"109-115","source":"Crossref","is-referenced-by-count":2,"title":["Top-k Color Queries on Tree Paths"],"prefix":"10.1007","author":[{"given":"Stephane","family":"Durocher","sequence":"first","affiliation":[]},{"given":"Rahul","family":"Shah","sequence":"additional","affiliation":[]},{"given":"Matthew","family":"Skala","sequence":"additional","affiliation":[]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"15_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-642-40104-6_11","volume-title":"Algorithms and Data Structures","author":"D. Belazzougui","year":"2013","unstructured":"Belazzougui, D., Gagie, T., Navarro, G.: Better space bounds for parameterized range majority and minority. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol.\u00a08037, pp. 121\u2013132. Springer, Heidelberg (2013)"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.jda.2012.07.005","volume":"18","author":"D. Belazzougui","year":"2013","unstructured":"Belazzougui, D., Navarro, G., Valenzuela, D.: Improved compressed indexes for full-text document retrieval. J. Discrete Algorithms\u00a018, 3\u201313 (2013)","journal-title":"J. Discrete Algorithms"},{"key":"15_CR3","unstructured":"Chan, T.M., Durocher, S., Larsen, K.G., Morrison, J., Wilkinson, B.T.: Linear-space data structures for range mode query in arrays. In: Proc. STACS, vol.\u00a014, pp. 291\u2013301 (2012)"},{"key":"15_CR4","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)"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.ic.2012.10.011","volume":"222","author":"S. Durocher","year":"2013","unstructured":"Durocher, S., He, M., Munro, J.I., Nicholson, P.K., Skala, M.: Range majority in constant time and linear space. Inf. & Comp.\u00a0222, 169\u2013179 (2013)","journal-title":"Inf. & Comp."},{"key":"15_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-3-642-40313-2_30","volume-title":"Mathematical Foundations of Computer Science 2013","author":"S. Durocher","year":"2013","unstructured":"Durocher, S., Shah, R., Skala, M., Thankachan, S.V.: Linear-space data structures for range frequency queries on arrays and trees. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol.\u00a08087, pp. 325\u2013336. Springer, Heidelberg (2013)"},{"issue":"3","key":"15_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":"15_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-642-24583-1_29","volume-title":"String Processing and Information Retrieval","author":"T. Gagie","year":"2011","unstructured":"Gagie, T., He, M., Munro, J.I., Nicholson, P.K.: Finding frequent elements in compressed 2D arrays and strings. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol.\u00a07024, pp. 295\u2013300. Springer, Heidelberg (2011)"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.tcs.2012.08.004","volume":"483","author":"T. Gagie","year":"2013","unstructured":"Gagie, T., K\u00e4rkk\u00e4inen, J., Navarro, G., Puglisi, S.J.: Colored range queries and document retrieval. Theor. Comput. Sci.\u00a0483, 36\u201350 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-03784-9_1","volume-title":"String Processing and Information Retrieval","author":"T. Gagie","year":"2009","unstructured":"Gagie, T., Puglisi, S.J., Turpin, A.: Range quantile queries: Another virtue of wavelet trees. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 1\u20136. Springer, Heidelberg (2009)"},{"key":"15_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/978-3-642-02927-1_40","volume-title":"Automata, Languages and Programming","author":"B. Gfeller","year":"2009","unstructured":"Gfeller, B., Sanders, P.: Towards optimal range medians. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 475\u2013486. Springer, Heidelberg (2009)"},{"key":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-642-25591-5_16","volume-title":"Algorithms and Computation","author":"M. He","year":"2011","unstructured":"He, M., Munro, J.I., Zhou, G.: Path queries in weighted trees. In: Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol.\u00a07074, pp. 140\u2013149. Springer, Heidelberg (2011)"},{"key":"15_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/978-3-642-33090-2_50","volume-title":"Algorithms \u2013 ESA 2012","author":"M. He","year":"2012","unstructured":"He, M., Munro, J.I., Zhou, G.: Succinct data structures for path queries. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol.\u00a07501, pp. 575\u2013586. Springer, Heidelberg (2012)"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Shah, R., Vitter, J.S.: Space-efficient framework for top-k string retrieval problems. In: Proc. FOCS, pp. 713\u2013722 (2009)","DOI":"10.1109\/FOCS.2009.19"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Nekrich, Y.: Top-k color queries for document retrieval. In: Proc. SODA, pp. 401\u2013411 (2011)","DOI":"10.1137\/1.9781611973082.32"},{"key":"15_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/978-3-540-24587-2_53","volume-title":"Algorithms and Computation","author":"D. Krizanc","year":"2003","unstructured":"Krizanc, D., Morin, P., Smid, M.: Range mode and range median queries on lists and trees. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol.\u00a02906, pp. 517\u2013526. Springer, Heidelberg (2003)"},{"key":"15_CR17","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proc. SODA, pp. 657\u2013666 (2002)"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Navarro, G., Nekrich, Y.: Top-k document retrieval in optimal time and linear space. In: Proc. SODA, pp. 1066\u20131077 (2012)","DOI":"10.1137\/1.9781611973099.84"},{"key":"15_CR19","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.jda.2012.08.003","volume":"17","author":"M. Patil","year":"2012","unstructured":"Patil, M., Shah, R., Thankachan, S.V.: Succinct representations of weighted trees supporting path queries. J. Discrete Algorithms\u00a017, 103\u2013108 (2012)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"15_CR20","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D.D. Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci.\u00a026(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-02432-5_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T12:41:39Z","timestamp":1558096899000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-02432-5_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319024318","9783319024325"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-02432-5_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}