{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T21:42:39Z","timestamp":1794346959269,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540728443","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72845-0_8","type":"book-chapter","created":{"date-parts":[[2007,6,26]],"date-time":"2007-06-26T08:51:37Z","timestamp":1182847897000},"page":"94-107","source":"Crossref","is-referenced-by-count":11,"title":["On the Cost of Persistence and Authentication in Skip Lists"],"prefix":"10.1007","author":[{"given":"Michael T.","family":"Goodrich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charalampos","family":"Papamanthou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roberto","family":"Tamassia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"8_CR1","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology - CRYPTO \u201998","author":"W. Aiello","year":"1998","unstructured":"Aiello, W., Lodha, S., Ostrovsky, R.: Fast digital identity revocation. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol.\u00a01462, Springer, Heidelberg (1998)"},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/3-540-45439-X_26","volume-title":"Information Security","author":"A. Anagnostopoulos","year":"2001","unstructured":"Anagnostopoulos, A., Goodrich, M.T., Tamassia, R.: Persistent authenticated dictionaries and their applications. In: Davida, G.I., Frankel, Y. (eds.) ISC 2001. LNCS, vol.\u00a02200, pp. 379\u2013393. Springer, Heidelberg (2001)"},{"key":"8_CR3","unstructured":"Brunner, R.J., Csabai, L., Szalay, A.S., Connolly, A., Szokoly, G.P., Ramaiyer, K.: The science archive for the Sloan Digital Sky Survey. In: Proc. Astronomical Data Analysis Software and Systems Conference V (1996)"},{"issue":"3","key":"8_CR4","doi-asserted-by":"crossref","first-page":"273","DOI":"10.3233\/JCS-2002-10304","volume":"10","author":"A. Buldas","year":"2002","unstructured":"Buldas, A., Laud, P., Lipmaa, H.: Eliminating counterevidence with applications to accountable certificate management. Journal of Computer Security\u00a010(3), 273\u2013296 (2002)","journal-title":"Journal of Computer Security"},{"issue":"3","key":"8_CR5","doi-asserted-by":"crossref","first-page":"291","DOI":"10.3233\/JCS-2003-11302","volume":"11","author":"P. Devanbu","year":"2003","unstructured":"Devanbu, P., Gertz, M., Martel, C., Stubblebine, S.G.: Authentic data publication over the Internet. Journal of Computer Security\u00a011(3), 291\u2013314 (2003)","journal-title":"Journal of Computer Security"},{"key":"8_CR6","first-page":"109","volume-title":"Proc. ACM Sympos","author":"J.R. Driscoll","year":"1986","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, S., Tarjan, R.E.: Making data structures persistent. In: Proc. ACM Sympos, pp. 109\u2013121. ACM Press, New York (1986)"},{"key":"8_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/978-3-540-46588-1_23","volume-title":"Public Key Cryptography","author":"I. Gassko","year":"2000","unstructured":"Gassko, I., Gemmell, P.S., MacKenzie, P.: Efficient and fresh certification. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol.\u00a01751, pp. 342\u2013353. Springer, Heidelberg (2000)"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1109\/DISCEX.2001.932160","volume-title":"Proc. DARPA Information Survivability Conference & Exposition II (DISCEX II)","author":"M.T. Goodrich","year":"2001","unstructured":"Goodrich, M.T., Tamassia, R.: Implementation of an authenticated dictionary with skip lists and commutative hashing. In: Proc. DARPA Information Survivability Conference & Exposition II (DISCEX II), pp. 68\u201382. IEEE Press, New York (2001)"},{"key":"8_CR9","volume-title":"Data Structures and Algorithms in Java","author":"M.T. Goodrich","year":"2006","unstructured":"Goodrich, M.T., Tamassia, R.: Data Structures and Algorithms in Java, 4th edn. John Wiley & Sons, New York (2006)","edition":"4"},{"key":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/3-540-36563-X_20","volume-title":"Topics in Cryptology - CT-RSA 2003","author":"M.T. Goodrich","year":"2003","unstructured":"Goodrich, M.T., Tamassia, R., Triandopoulos, N., Cohen, R.: Authenticated data structures for graph and geometric searching. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol.\u00a02612, pp. 295\u2013313. Springer, Heidelberg (2003)"},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1145\/325694.325736","volume-title":"Proc. 27th ACM Symp. on Principles of Programming Languages","author":"C. Gunter","year":"2000","unstructured":"Gunter, C., Jim, T.: Generalized certificate revocation. In: Proc. 27th ACM Symp. on Principles of Programming Languages, pp. 316\u2013329. ACM Press, New York (2000)"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BFb0028258","volume-title":"Algorithms and Data Structures","author":"E.N. Hanson","year":"1991","unstructured":"Hanson, E.N.: The interval skip list: a data structure for finding all intervals that overlap a point. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1991. LNCS, vol.\u00a0519, pp. 153\u2013164. Springer, Heidelberg (1991)"},{"key":"8_CR13","first-page":"278","volume-title":"Proc. ACM Symp. on the Theory of Computing","author":"R.M. Karp","year":"1993","unstructured":"Karp, R.M.: Mapping the genome: Some combinatorial problems arising in molecular biology. In: Proc. ACM Symp. on the Theory of Computing, pp. 278\u2013285. ACM Press, New York (1993)"},{"key":"8_CR14","volume-title":"Network Security: Private Communication in a Public World","author":"C. Kaufman","year":"1995","unstructured":"Kaufman, C., Perlman, R., Speciner, M.: Network Security: Private Communication in a Public World. Prentice-Hall, Englewood Cliffs (1995)"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1007\/BF01178735","volume":"31","author":"P. Kirschenhofer","year":"1994","unstructured":"Kirschenhofer, P., Prodinger, H.: The path length of random skip lists. Acta Informatica\u00a031, 775\u2013792 (1994)","journal-title":"Acta Informatica"},{"key":"8_CR16","unstructured":"Lupton, R., Maley, F.M., Young, N.: Sloan digital sky survey, \n                    \n                      http:\/\/www.sdss.org\/sdss.html"},{"issue":"2","key":"8_CR17","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1006\/jagm.1997.0922","volume":"27","author":"R. Lupton","year":"1998","unstructured":"Lupton, R., Maley, F.M., Young, N.: Data collection for the Sloan Digital Sky Survey\u2014A network-flow heuristic. Journal of Algorithms\u00a027(2), 339\u2013356 (1998)","journal-title":"Journal of Algorithms"},{"issue":"1","key":"8_CR18","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s00453-003-1076-8","volume":"39","author":"C. Martel","year":"2004","unstructured":"Martel, C., Nuckolls, G., Devanbu, P., Gertz, M., Kwong, A., Stubblebine, S.G.: A general model for authenticated data structures. Algorithmica\u00a039(1), 21\u201341 (2004)","journal-title":"Algorithmica"},{"key":"8_CR19","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"K. Mehlhorn","year":"2000","unstructured":"Mehlhorn, K., N\u00e4her, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (2000)"},{"key":"8_CR20","unstructured":"Micali, S.: Efficient certificate revocation. Technical Report TM-542b, MIT Laboratory for Computer Science (1996)"},{"key":"8_CR21","unstructured":"Naor, M., Nissim, K.: Certificate revocation and certificate update. In: Proc. 7th USENIX Security Symposium, Berkeley pp. 217\u2013228 (1998)"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Nuckolls, G.: Verified query results from hybrid authentication trees. In: DBSec, pp. 84\u201398 (2005)","DOI":"10.1007\/11535706_7"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Pang, H., Tan, K.-L.: Authenticating query results in edge computing. In: Proc. Int. Conference on Data Engineering, pp. 560\u2013571 (2004)","DOI":"10.1109\/ICDE.2004.1320027"},{"key":"8_CR24","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/BF01994884","volume":"32","author":"T. Papadakis","year":"1992","unstructured":"Papadakis, T., Munro, J.I., Poblete, P.V.: Average search and update costs in skip lists. BIT\u00a032, 316\u2013332 (1992)","journal-title":"BIT"},{"key":"8_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"554","DOI":"10.1007\/3-540-60313-1_170","volume-title":"Algorithms - ESA \u201995","author":"P.V. Poblete","year":"1995","unstructured":"Poblete, P.V., Munro, J.I., Papadakis, T.: The binomial transform and its application to the analysis of skip lists. In: Spirakis, P.G. (ed.) ESA 1995. LNCS, vol.\u00a0979, pp. 554\u2013569. Springer, Heidelberg (1995)"},{"issue":"6","key":"8_CR26","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. Commun. ACM\u00a033(6), 668\u2013676 (1990)","journal-title":"Commun. ACM"},{"key":"8_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/978-3-540-39658-1_2","volume-title":"Algorithms - ESA 2003","author":"R. Tamassia","year":"2003","unstructured":"Tamassia, R.: Authenticated data structures. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 2\u20135. Springer, Heidelberg (2003)"},{"key":"8_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/11523468_13","volume-title":"Automata, Languages and Programming","author":"R. Tamassia","year":"2005","unstructured":"Tamassia, R., Triandopoulos, N.: Computational bounds on hierarchical data processing with applications to information security. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 153\u2013165. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72845-0_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:05:52Z","timestamp":1605744352000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72845-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540728443"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72845-0_8","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-540-72845-0","asserted-by":"object"}]},"subject":[]}}