{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T09:34:12Z","timestamp":1725701652508},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_50","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T11:29:11Z","timestamp":1346153351000},"page":"575-586","source":"Crossref","is-referenced-by-count":12,"title":["Succinct Data Structures for Path Queries"],"prefix":"10.1007","author":[{"given":"Meng","family":"He","sequence":"first","affiliation":[]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[]},{"given":"Gelin","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"unstructured":"Alon, N., Schieber, B.: Optimal preprocessing for answering on-line product queries. Tech. rep., Tel Aviv University (1987)","key":"50_CR1"},{"key":"50_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/11780441_4","volume-title":"Combinatorial Pattern Matching","author":"J. Barbay","year":"2006","unstructured":"Barbay, J., Golynski, A., Munro, J.I., Rao, S.S.: Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 24\u201335. Springer, Heidelberg (2006)"},{"issue":"4","key":"50_CR3","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/2000807.2000820","volume":"7","author":"J. Barbay","year":"2011","unstructured":"Barbay, J., He, M., Munro, J.I., Rao, S.S.: Succinct indexes for strings, binary relations and multilabeled trees. ACM Transactions on Algorithms\u00a07(4), 52 (2011)","journal-title":"ACM Transactions on Algorithms"},{"issue":"1-3","key":"50_CR4","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.tcs.2004.12.030","volume":"337","author":"P. Bille","year":"2005","unstructured":"Bille, P.: A survey on tree edit distance and related problems. Theor. Comput. Sci.\u00a0337(1-3), 217\u2013239 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"50_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-642-03367-4_9","volume-title":"Algorithms and Data Structures","author":"P. Bose","year":"2009","unstructured":"Bose, P., He, M., Maheshwari, A., Morin, P.: Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) WADS 2009. LNCS, vol.\u00a05664, pp. 98\u2013109. Springer, Heidelberg (2009)"},{"issue":"24","key":"50_CR6","doi-asserted-by":"publisher","first-page":"2588","DOI":"10.1016\/j.tcs.2010.05.003","volume":"412","author":"G.S. Brodal","year":"2011","unstructured":"Brodal, G.S., Gfeller, B., J\u00f8rgensen, A.G., Sanders, P.: Towards optimal range medians. Theor. Comput. Sci.\u00a0412(24), 2588\u20132601 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"50_CR7","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF01840366","volume":"2","author":"B. Chazelle","year":"1987","unstructured":"Chazelle, B.: Computing on a free tree via complexity-preserving mappings. Algorithmica\u00a02, 337\u2013361 (1987)","journal-title":"Algorithmica"},{"key":"50_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-540-69903-3_17","volume-title":"Algorithm Theory \u2013 SWAT 2008","author":"A. Farzan","year":"2008","unstructured":"Farzan, A., Munro, J.I.: A Uniform Approach Towards Succinct Representation of Trees. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol.\u00a05124, pp. 173\u2013184. Springer, Heidelberg (2008)"},{"key":"50_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/978-3-642-02927-1_38","volume-title":"Automata, Languages and Programming","author":"A. Farzan","year":"2009","unstructured":"Farzan, A., Raman, R., Rao, S.S.: Universal Succinct Representations of Trees? In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 451\u2013462. Springer, Heidelberg (2009)"},{"doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Compressing and indexing labeled trees, with applications. J. ACM\u00a057(1) (2009)","key":"50_CR10","DOI":"10.1145\/1613676.1613680"},{"doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Transactions on Algorithms\u00a03(2) (2007)","key":"50_CR11","DOI":"10.1145\/1240233.1240243"},{"issue":"4","key":"50_CR12","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/1198513.1198516","volume":"2","author":"R.F. Geary","year":"2006","unstructured":"Geary, R.F., Raman, R., Raman, V.: Succinct ordinal trees with level-ancestor queries. ACM Transactions on Algorithms\u00a02(4), 510\u2013534 (2006)","journal-title":"ACM Transactions on Algorithms"},{"issue":"1","key":"50_CR13","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1006\/inco.1999.2814","volume":"158","author":"T. Hagerup","year":"2000","unstructured":"Hagerup, T.: Parallel preprocessing for path queries without concurrent reading. Inf. Comput.\u00a0158(1), 18\u201328 (2000)","journal-title":"Inf. Comput."},{"key":"50_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/978-3-540-73420-8_45","volume-title":"Automata, Languages and Programming","author":"M. He","year":"2007","unstructured":"He, M., Munro, J.I., Rao, S.S.: Succinct Ordinal Trees Based on Tree Covering. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 509\u2013520. Springer, Heidelberg (2007)"},{"key":"50_CR15","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)"},{"doi-asserted-by":"crossref","unstructured":"J\u00f8rgensen, A.G., Larsen, K.G.: Range selection and median: Tight cell probe lower bounds and adaptive data structures. In: SODA, pp. 805\u2013813 (2011)","key":"50_CR16","DOI":"10.1137\/1.9781611973082.63"},{"issue":"1","key":"50_CR17","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."},{"doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Lower bounds for 2-dimensional range counting. In: STOC, pp. 40\u201346 (2007)","key":"50_CR18","DOI":"10.1145\/1250790.1250797"},{"issue":"3","key":"50_CR19","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1137\/09075336X","volume":"40","author":"M. P\u01cetra\u015fcu","year":"2011","unstructured":"P\u01cetra\u015fcu, M.: Unifying the landscape of cell-probe lower bounds. SIAM J. Comput.\u00a040(3), 827\u2013847 (2011)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms\u00a03(4) (2007)","key":"50_CR20","DOI":"10.1145\/1290672.1290680"},{"doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: SODA, pp. 134\u2013149 (2010)","key":"50_CR21","DOI":"10.1137\/1.9781611973075.13"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_50.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T07:55:01Z","timestamp":1620114901000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}