{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T02:58:51Z","timestamp":1648695531173},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,11,23]],"date-time":"2011-11-23T00:00:00Z","timestamp":1322006400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,2]]},"DOI":"10.1007\/s00453-011-9594-2","type":"journal-article","created":{"date-parts":[[2011,11,22]],"date-time":"2011-11-22T16:51:07Z","timestamp":1321980667000},"page":"371-390","source":"Crossref","is-referenced-by-count":1,"title":["I\/O Efficient Dynamic Data Structures for Longest Prefix Queries"],"prefix":"10.1007","volume":"65","author":[{"given":"Moshe","family":"Hershcovitch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,11,23]]},"reference":[{"key":"9594_CR1","first-page":"803","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"P.K. Agarwal","year":"2005","unstructured":"Agarwal, P.K., Arge, L., Yi, K.: An optimal dynamic interval stabbing-max data structure. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 803\u2013812 (2005)"},{"issue":"3","key":"9594_CR2","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.M.: Organization and maintenance of large ordered indexes. Acta Inform. 1(3), 173\u2013189 (1972)","journal-title":"Acta Inform."},{"issue":"2","key":"9594_CR3","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/S0097539701389956","volume":"35","author":"M.A. Bender","year":"2005","unstructured":"Bender, M.A., Demaine, E., Farach-Colton, M.: Cache-oblivious B-trees. SIAM J. Comput. 35(2), 341\u2013358 (2005)","journal-title":"SIAM J. Comput."},{"key":"9594_CR4","first-page":"233","volume-title":"Proceedings of the 25th ACM Symposium on Principles of Database Systems (PODS)","author":"M.A. Bender","year":"2006","unstructured":"Bender, M.A., Farach-Colton, M., Kusznaul, B.C.: Cache-oblivious string B-trees. In: Proceedings of the 25th ACM Symposium on Principles of Database Systems (PODS), pp. 233\u2013242 (2006)"},{"key":"9594_CR5","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1145\/1109557.1109621","volume-title":"Proceeding 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"G.S. Brodal","year":"2006","unstructured":"Brodal, G.S., Fagerberg, R.: Cache-oblivious string dictionaries. In: Proceeding 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 581\u2013590 (2006)"},{"key":"9594_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04245-8","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"2000","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications. Springer, Berlin (2000)"},{"key":"9594_CR7","unstructured":"Demaine, E.D., Iacono, J., Langerman, S.: Worst-case optimal tree layout in a memory hierarchy. CoRR, cs.DS\/0410048 (2004)"},{"issue":"2","key":"9594_CR8","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1145\/997150.997160","volume":"34","author":"W. Eatherton","year":"2004","unstructured":"Eatherton, W., Dittia, Z., Varghese, G.: Tree bitmap: hardware\/software IP lookups with incremental updates. ACM SIGCOMM Comput. Commun. Rev. 34(2), 97\u2013122 (2004)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"9594_CR9","first-page":"1193","volume-title":"IEEE International Conference on Computer Communications (INFOCOM)","author":"A. Feldmann","year":"2000","unstructured":"Feldmann, A., Muthukrishnan, S.: Tradeoffs for packet classification. In: IEEE International Conference on Computer Communications (INFOCOM), pp. 1193\u20131202 (2000)"},{"issue":"2","key":"9594_CR10","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1145\/301970.301973","volume":"46","author":"P. Ferragina","year":"1999","unstructured":"Ferragina, P., Grossi, R.: The string B-tree: a\u00a0new data structure for string search in external memory and its applications. J. ACM 46(2), 236\u2013280 (1999)","journal-title":"J. ACM"},{"key":"9594_CR11","first-page":"285","volume-title":"IEEE Symposium on Foundations of Computer Science (FOCS)","author":"M. Frigo","year":"1999","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 285\u2013297 (1999)"},{"key":"9594_CR12","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1109\/ISCA.2006.14","volume-title":"International Symposium on Computer Architecture (ISCA)","author":"J. Hasan","year":"2006","unstructured":"Hasan, J., Cadambi, S., Jakkula, V., Chakradhar, S.: Chisel: a\u00a0storage-efficient, collision-free hash- based network processing architecture. In: International Symposium on Computer Architecture (ISCA), pp. 203\u2013215 (2006)"},{"key":"9594_CR13","first-page":"639","volume-title":"ACM Symposium on Theory of Computing (STOC)","author":"H. Kaplan","year":"2003","unstructured":"Kaplan, H., Molad, E., Tarjan, R.E.: Dynamic rectangular intersection with priorities. In: ACM Symposium on Theory of Computing (STOC), pp. 639\u2013648 (2003)"},{"key":"9594_CR14","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/11780441_8","volume-title":"Combinatorial Pattern Matching (CPM)","author":"P. Ko","year":"2006","unstructured":"Ko, P., Aluru, S.: Obtaining provably good performance from suffix trees in secondary storage. In: Combinatorial Pattern Matching (CPM). LNCS, vol.\u00a04009, pp. 72\u201383. Springer, Berlin (2006)"},{"issue":"3","key":"9594_CR15","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1109\/90.779199","volume":"7","author":"B.W. Lampson","year":"1999","unstructured":"Lampson, B.W., Srinivasan, V., Varghese, G.: IP lookups using multiway and multicolumn search. IEEE\/ACM Trans. Netw. 7(3), 324\u2013334 (1999)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"7","key":"9594_CR16","doi-asserted-by":"crossref","first-page":"813","DOI":"10.1109\/TC.2005.104","volume":"54","author":"H. Lu","year":"2005","unstructured":"Lu, H., Sahni, S.: A B-tree dynamic router-table design. IEEE Trans. Comput. 54(7), 813\u2013824 (2005)","journal-title":"IEEE Trans. Comput."},{"issue":"4","key":"9594_CR17","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"D.R. Morrison","year":"1968","unstructured":"Morrison, D.R.: Patricia: practical algorithm to retrieve information coded in alphanumeric. J. ACM 15(4), 514\u2013534 (1968)","journal-title":"J. ACM"},{"key":"9594_CR18","first-page":"443","volume-title":"IEEE Symposium on Computers and Communications (ISCC)","author":"S. Sahni","year":"2002","unstructured":"Sahni, S., Kim, K.: O(logn) dynamic packet routing. In: IEEE Symposium on Computers and Communications (ISCC), pp. 443\u2013448 (2002)"},{"issue":"3","key":"9594_CR19","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D. Sleator","year":"1983","unstructured":"Sleator, D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"9594_CR20","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. Sleator","year":"1985","unstructured":"Sleator, D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32, 652\u2013686 (1985)","journal-title":"J. ACM"},{"key":"9594_CR21","first-page":"1610","volume-title":"IEEE Global Communications Conference (GLOBECOM)","author":"S. Suri","year":"2001","unstructured":"Suri, S., Varghese, G., Warkhede, P.: Multiway range trees: scalable IP lookup with fast updates. In: IEEE Global Communications Conference (GLOBECOM), pp. 1610\u20131614 (2001)"},{"key":"9594_CR22","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"R.E. Tarjan","year":"1979","unstructured":"Tarjan, R.E.: A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. Syst. Sci. 18, 110\u2013127 (1979)","journal-title":"J. Comput. Syst. Sci."},{"key":"9594_CR23","series-title":"The Morgan Kaufmann Series in Networking","volume-title":"Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices","author":"G. Varghese","year":"2004","unstructured":"Varghese, G.: Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices. The Morgan Kaufmann Series in Networking. Morgan Kaufmann, San Francisco (2004)"},{"issue":"2","key":"9594_CR24","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"J.S. Vitter","year":"2001","unstructured":"Vitter, J.S.: External memory algorithms and data structures: dealing with massive data. ACM Comput. Surv. 33(2), 209\u2013271 (2001)","journal-title":"ACM Comput. Surv."},{"issue":"3","key":"9594_CR25","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.comnet.2003.09.004","volume":"44","author":"P.R. Warkhede","year":"2004","unstructured":"Warkhede, P.R., Suri, S., Varghese, G.: Multiway range trees: scalable IP lookup with fast updates. Comput. Netw. 44(3), 289\u2013303 (2004)","journal-title":"Comput. Netw."},{"key":"9594_CR26","first-page":"42","volume-title":"IEEE International Conference on Computer Communications (INFOCOM)","author":"F. Zane","year":"2003","unstructured":"Zane, F., Narlikar, G., Basu, A.: Coolcams: power-efficient TCAMs for forwarding engines. In: IEEE International Conference on Computer Communications (INFOCOM), pp. 42\u201352 (2003)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9594-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9594-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9594-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T23:17:38Z","timestamp":1560986258000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9594-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,23]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["9594"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9594-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11,23]]}}}