{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T19:23:32Z","timestamp":1774121012538,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540363217","type":"print"},{"value":"9783540363224","type":"electronic"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11795490_28","type":"book-chapter","created":{"date-parts":[[2007,1,23]],"date-time":"2007-01-23T07:25:18Z","timestamp":1169537118000},"page":"366-380","source":"Crossref","is-referenced-by-count":14,"title":["Skip B-Trees"],"prefix":"10.1007","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James","family":"Aspnes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Yuan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Awerbuch, B., Azar, Y., Malkhi, D., Pavlov, E.: A generic scheme for building overlay networks in adversarial scenarios. In: Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS 2003) (April 2003)","DOI":"10.1109\/IPDPS.2003.1213125"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"Aumann, Y., Bender, M.A.: Fault Tolerant Data Structures. In: Proceedings of the Thirty-Seventh Annual Symposium on Foundations of Computer Science (FOCS), Burlington, VT, USA, pp. 580\u2013589 (October 1996)","DOI":"10.1109\/SFCS.1996.548517"},{"issue":"1","key":"28_CR3","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/S0097539795288490","volume":"29","author":"Y. Azar","year":"2000","unstructured":"Azar, Y., Broder, A.Z., Karlin, A.R., Upfal, E.: Balanced allocations. SIAM J. Comput.\u00a029(1), 180\u2013200 (2000)","journal-title":"SIAM J. Comput."},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Kirsch, J., Krishnamurthy, A.: Load balancing and locality in range-queriable data structures. In: Twenty-Third ACM Symposium on Principles of Distributed Computing, pp. 115\u2013124 (July 2004)","DOI":"10.1145\/1011767.1011785"},{"key":"28_CR5","unstructured":"Aspnes, J., Shah, G.: Skip Graphs. In: Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 384\u2013393 (January 2002) (submitted to Journal of Algorithms)"},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Scheideler, C.: Peer-to-peer Systems for Prefix Search. In: Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing (PODC), Boston, MA, USA (July 2003)","DOI":"10.1145\/872035.872053"},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"Bayer, R.: Symmetric Binary B-trees: Data Structure and Maintainance Algorithms. Acta Informatica, 290\u2013306 (1972)","DOI":"10.1007\/BF00289509"},{"key":"28_CR8","unstructured":"Colbrook, A., Brewer, E.A., Dellarocas, C., Weihl, W.E.: An Algorithm for concurrent search trees. In: Proceedings of the 20th International Conference on Parallel Processing, pp. III138\u2013III141 (1991)"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Crainiceanu, A., Linga, P., Gehrke, J., Shanmugasundaram, J.: P-Tree: A P2P Index for Resource Discovery Applications. In: The 13th International World Wide Web Conference, pp. 390\u2013392 (May 2004)","DOI":"10.1145\/1013367.1013490"},{"key":"28_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/3-540-45749-6_30","volume-title":"Algorithms - ESA 2002","author":"M. Datar","year":"2002","unstructured":"Datar, M.: Butterflies and Peer-to-Peer Networks. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 310\u2013322. Springer, Heidelberg (2002)"},{"key":"#cr-split#-28_CR11.1","unstructured":"Fiat, A., Saia, J.: Censorship Resistant Peer-to-Peer Content Addressable Networks. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, CA, USA, pp. 94???103 (January 2002);"},{"key":"#cr-split#-28_CR11.2","unstructured":"Submitted to a special issue of Journal of Algorithms dedicated to select papers of SODA 2002"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"Gilon, K., Peleg, D.: Compact Deterministic Distributed Dictionaries. In: Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, pp. 81\u201394 (1991)","DOI":"10.1145\/112600.112609"},{"key":"28_CR13","unstructured":"Harvey, N.J.A., Jones, M.B., Saroiu, S., Theimer, M., Wolman, A.: SkipNet: A Scalable Overlay Network with Practical Locality Properties. In: Proceedings of the Fourth USENIX Symposium on Internet Technologies and Systems (USITS), Seattle, WA, USA, pp. 113\u2013126 (March 2003)"},{"key":"28_CR14","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1142\/S0129053394000238","volume":"6","author":"T. Johnson","year":"1994","unstructured":"Johnson, T., Colbrook, A.: A Distributed, Replicated, Data-Balanced Search Structure. International Journal of High Speed Computing\u00a06, 475\u2013500 (1994)","journal-title":"International Journal of High Speed Computing"},{"key":"28_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45172-3_9","volume-title":"Peer-to-Peer Systems II","author":"F. Kaashoek","year":"2003","unstructured":"Kaashoek, F., Karger, D.R.: Koorde: A simple degree-optimal hash table. In: Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003. LNCS, vol.\u00a02735. Springer, Heidelberg (2003)"},{"key":"28_CR16","first-page":"135","volume-title":"SPAA 2005: Proceedings of the 17th annual ACM symposium on Parallelism in algorithms and architectures","author":"K. Kenthapadi","year":"2005","unstructured":"Kenthapadi, K., Manku, G.S.: Decentralized algorithms using both local and random probes for p2p load balancing. In: SPAA 2005: Proceedings of the 17th annual ACM symposium on Parallelism in algorithms and architectures, pp. 135\u2013144. ACM Press, New York (2005)"},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"Karger, D.R., Ruhl, M.: Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems. In: ACM SPAA (2004)","DOI":"10.1145\/1007912.1007919"},{"issue":"2\/3","key":"28_CR18","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1016\/S0019-9958(84)80035-2","volume":"62","author":"J.I. Munro","year":"1984","unstructured":"Munro, J.I., Poblete, P.V.: Fault Tolerance And Storage Reduction In Binary Search Trees. Information and Control\u00a062(2\/3), 210\u2013218 (1984)","journal-title":"Information and Control"},{"key":"28_CR19","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Richa, A.W., Sitaraman, R.: The power of two random choices: A survey of techniques and results (2001)","DOI":"10.1007\/978-1-4615-0013-1_9"},{"issue":"6","key":"28_CR20","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W. Pugh","year":"1990","unstructured":"Pugh, W.: Skip Lists: A Probabilistic Alternative to Balanced Trees. Communications of the ACM\u00a033(6), 668\u2013676 (1990)","journal-title":"Communications of the ACM"},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"Ramabhadran, S., Ratnasamy, S., Hellerstein, J.M., Shenker, S.: Brief Announcement: Prefix Hash Tree. In: Proceedings of ACM PODC, St. Johns, Canada (July 2004)","DOI":"10.1145\/1011767.1011823"},{"key":"28_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-45748-8_26","volume-title":"Peer-to-Peer Systems","author":"J. Saia","year":"2002","unstructured":"Saia, J., Fiat, A., Gribble, S., Karlin, A., Saroiu, S.: Dynamically Fault-Tolerant Content Addressable Networks. In: Druschel, P., Kaashoek, M.F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol.\u00a02429, pp. 270\u2013279. Springer, Heidelberg (2002)"},{"key":"28_CR23","doi-asserted-by":"crossref","unstructured":"Shasha, D., Goodman, N.: Concurrent search structure algorithms. ACM Transactions on Database Systems, 53\u201390 (1988)","DOI":"10.1145\/42201.42204"},{"key":"28_CR24","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1109\/TNET.2002.808407","volume":"11","author":"I. Stoica","year":"2003","unstructured":"Stoica, I., Morris, R., Liben-Nowell, D., Karger, D.R., Kaashoek, M.F., Dabek, F., Balakrishnan, H.: Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. IEEE\/ACM Transactions on Networking\u00a011, 17\u201332 (2003)","journal-title":"IEEE\/ACM Transactions on Networking"}],"container-title":["Lecture Notes in Computer Science","Principles of Distributed Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11795490_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T18:59:30Z","timestamp":1556045970000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11795490_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540363217","9783540363224"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11795490_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}