{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:16:24Z","timestamp":1763468184944,"version":"3.37.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319079585"},{"type":"electronic","value":"9783319079592"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07959-2_14","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T12:44:25Z","timestamp":1402404265000},"page":"162-173","source":"Crossref","is-referenced-by-count":8,"title":["Wear Minimization for Cuckoo Hashing: How\u00a0Not\u00a0to\u00a0Throw\u00a0a\u00a0Lot\u00a0of\u00a0Eggs\u00a0into\u00a0One\u00a0Basket"],"prefix":"10.1007","author":[{"given":"David","family":"Eppstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Pszona","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Alcantara, D.A., Sharf, A., Abbasinejad, F., Sengupta, S., Mitzenmacher, M., Owens, J.D., Amenta, N.: Real-time parallel hashing on the GPU. In: Proc. ACM SIGGRAPH Asia 2009, pp. 154:1\u2013154:9(2009), doi:10.1145\/1661412.1618500","DOI":"10.1145\/1661412.1618500"},{"key":"14_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-02927-1_11","volume-title":"Automata, Languages and Programming","author":"Y. Arbitman","year":"2009","unstructured":"Arbitman, Y., Naor, M., Segev, G.: De-amortized cuckoo hashing: Provable worst-case performance and experimental results. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 107\u2013118. Springer, Heidelberg (2009)"},{"issue":"1","key":"14_CR3","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/S0097539795288490","volume":"29","author":"Y. Azar","year":"1999","unstructured":"Azar, Y., Broder, A., Karlin, A., Upfal, E.: Balanced allocations. SIAM J. Comput.\u00a029(1), 180\u2013200 (1999), doi:10.1137\/S0097539795288490","journal-title":"SIAM J. Comput."},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Baeza-Yates, R., Poblete, P.V.: Searching. In: Algorithms and Theory of Computation Handbook, pp. 2-1\u20132-16. Chapman & Hall\/CRC (2010)","DOI":"10.1201\/9781584888239-c2"},{"key":"14_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/11841036_12","volume-title":"Algorithms \u2013 ESA 2006","author":"A. Ben-Aroya","year":"2006","unstructured":"Ben-Aroya, A., Toledo, S.: Competitive analysis of flash-memory algorithms. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 100\u2013111. Springer, Heidelberg (2006), \n                    \n                      http:\/\/dx.doi.org\/10.1007\/11841036_12\n                    \n                    \n                  , doi:10.1007\/11841036_12"},{"issue":"4","key":"14_CR6","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/JPROC.2003.811702","volume":"91","author":"R. Bez","year":"2003","unstructured":"Bez, R., Camerlenghi, E., Modelli, A., Visconti, A.: Introduction to flash memory. Proc. IEEE\u00a091(4), 489\u2013502 (2003), doi:10.1109\/JPROC.2003.811702","journal-title":"Proc. IEEE"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Chang, L.-P.: On efficient wear leveling for large-scale flash-memory storage systems. In: Proc. ACM Symp. on Applied Computing, pp. 1126\u20131130 (2007), doi:10.1145\/1244002.1244248","DOI":"10.1145\/1244002.1244248"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"Chang, Y.-H., Hsieh, J.-W., Kuo, T.-W.: Endurance enhancement of flash-memory storage, systems: an efficient static wear leveling design. In: Proc. 44th ACM\/IEEE Design Automation Conf. (DAC 2007), pp. 212\u2013217 (2007), doi:10.1145\/1278480.1278533","DOI":"10.1145\/1278480.1278533"},{"issue":"1","key":"14_CR9","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1109\/TC.2009.134","volume":"59","author":"Y.-H. Chang","year":"2010","unstructured":"Chang, Y.-H., Hsieh, J.-W., Kuo, T.-W.: Improving flash wear-leveling by proactively moving static data. IEEE Trans. Comput.\u00a059(1), 53\u201365 (2010), doi:10.1109\/TC.2009.134","journal-title":"IEEE Trans. Comput."},{"key":"14_CR10","unstructured":"Chen, S., Gibbons, P.B., Nath, S.: Rethinking database algorithms for phase change memory. In: Proc. 5th Conf. on Innovative Data Systems Research (CIDR), pp. 21\u201331 (2011), \n                    \n                      http:\/\/www.cidrdb.org\/cidr2011\/Papers\/CIDR11_Paper3.pdf"},{"issue":"4","key":"14_CR11","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0020-0190(02)00500-8","volume":"86","author":"L. Devroye","year":"2003","unstructured":"Devroye, L., Morin, P.: Cuckoo hashing: further analysis. Inform. Process. Lett.\u00a086(4), 215\u2013219 (2003), doi:10.1016\/S0020-0190(02)00500-8","journal-title":"Inform. Process. Lett."},{"key":"14_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/978-3-642-14165-2_19","volume-title":"Automata, Languages and Programming","author":"M. Dietzfelbinger","year":"2010","unstructured":"Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R., Rink, M.: Tight thresholds for cuckoo hashing via XORSAT. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 213\u2013225. Springer, Heidelberg (2010), doi:10.1007\/978-3-642-14165-2_19"},{"issue":"2","key":"14_CR13","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s00224-004-1195-x","volume":"38","author":"D. Fotakis","year":"2005","unstructured":"Fotakis, D., Pagh, R., Sanders, P., Spirakis, P.G.: Space efficient hash tables with worst case constant access time. Theory of Computing Systems\u00a038(2), 229\u2013248 (2005), doi:10.1007\/s00224-004-1195-x","journal-title":"Theory of Computing Systems"},{"key":"14_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/978-3-642-03685-9_37","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A.M. Frieze","year":"2009","unstructured":"Frieze, A.M., Melsted, P., Mitzenmacher, M.: An analysis of random-walk cuckoo hashing. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. LNCS, vol.\u00a05687, pp. 490\u2013503. Springer, Heidelberg (2009)"},{"issue":"2","key":"14_CR15","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1137\/090770928","volume":"40","author":"A.M. Frieze","year":"2011","unstructured":"Frieze, A.M., Melsted, P., Mitzenmacher, M.: An analysis of random-walk cuckoo hashing. SIAM J. Comput.\u00a040(2), 291\u2013308 (2011), doi:10.1137\/090770928","journal-title":"SIAM J. Comput."},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Grupp, L.M., Caulfield, A.M., Coburn, J., Swanson, S., Yaakobi, E., Siegel, P.H., Wolf, J.K.: Characterizing flash memory: anomalies, observations, and applications. In: Proc. 42nd IEEE\/ACM Int. Symp. on Microarchitecture (MICRO 42), pp. 24\u201333 (2009), doi:10.1145\/1669112.1669118","DOI":"10.1145\/1669112.1669118"},{"key":"14_CR17","unstructured":"Hunter, A.: A brief introduction to the design of UBIFS. White paper (2008), \n                    \n                      http:\/\/www.linux-mtd.infradead.org\/doc\/ubifs_whitepaper.pdf"},{"issue":"2","key":"14_CR18","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02835833","volume":"25","author":"S. Irani","year":"1992","unstructured":"Irani, S., Naor, M., Rubinfeld, R.: On the time and space complexity of computation using write-once memory or is pen really much worse than pencil? Mathematical Systems Theory\u00a025(2), 141\u2013159 (1992), doi:10.1007\/BF02835833","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"14_CR19","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0377-0427(01)00464-2","volume":"142","author":"M. Karo\u0144ski","year":"2002","unstructured":"Karo\u0144ski, M., \u0141uczak, T.: The phase transition in a random hypergraph. J. Comput. Appl. Math.\u00a0142(1), 125\u2013135 (2002), doi:10.1016\/S0377-0427(01)00464-2","journal-title":"J. Comput. Appl. Math."},{"issue":"4","key":"14_CR20","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1137\/080728743","volume":"39","author":"A. Kirsch","year":"2009","unstructured":"Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: cuckoo Hashing with a Stash. SIAM J. Comput.\u00a039(4), 1543\u20131561 (2009), doi:10.1137\/080728743","journal-title":"SIAM J. Comput."},{"key":"14_CR21","unstructured":"Knuth, D.E.: The Art of Computer Programming, 2nd edn. Sorting and Searching, vol.\u00a03. Addison Wesley (1998)"},{"key":"14_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1007\/978-3-642-04128-0_60","volume-title":"Algorithms - ESA 2009","author":"E. Lehman","year":"2009","unstructured":"Lehman, E., Panigrahy, R.: 3.5-way cuckoo hashing for the price of 2-and-a-bit. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 671\u2013681. Springer, Heidelberg (2009), doi:10.1007\/978-3-642-04128-0_60"},{"key":"14_CR23","unstructured":"Mavroyanopoulos, N., Schumann, S.: Mhash. Open-source software library, \n                    \n                      http:\/\/mhash.sourceforge.net\/"},{"key":"14_CR24","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Richa, A.W., Sitaraman, R.: The power of two random choices: A survey of techniques and results. In: Handbook of Randomized Computing, vol.\u00a01, pp. 255\u2013312. Kluwer Academic Publishers (2000)","DOI":"10.1007\/978-1-4615-0013-1_9"},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press (2005)","DOI":"10.1017\/CBO9780511813603"},{"issue":"2","key":"14_CR26","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R. Pagh","year":"2003","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms\u00a051(2), 122\u2013144 (2003), doi:10.1016\/j.jalgor.2003.12.002","journal-title":"J. Algorithms"},{"issue":"8","key":"14_CR27","doi-asserted-by":"publisher","first-page":"1248","DOI":"10.1109\/5.622505","volume":"85","author":"P. Pavan","year":"1997","unstructured":"Pavan, P., Bez, R., Olivo, P., Zanoni, E.: Flash memory cells\u2014an overview. Proc. IEEE\u00a085(8), 1248\u20131271 (1997), doi:10.1109\/5.622505","journal-title":"Proc. IEEE"},{"key":"14_CR28","doi-asserted-by":"crossref","unstructured":"Qureshi, M.K., Karidis, J., Franceschini, M., Srinivasan, V., Lastras, L., Abali, B.: Enhancing lifetime and security of PCM-based main memory with start-gap wear leveling. In: Proc. 42nd IEEE\/ACM Int. Symp. on Microarchitecture (MICRO), pp. 14\u201323 (2009), doi:10.1145\/1669112.1669117","DOI":"10.1145\/1669112.1669117"},{"issue":"1","key":"14_CR29","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02579445","volume":"5","author":"J. Schmidt-Pruzan","year":"1985","unstructured":"Schmidt-Pruzan, J., Shamir, E.: Component structure in the evolution of random hypergraphs. Combinatorica\u00a05(1), 81\u201394 (1985), doi:10.1007\/BF02579445","journal-title":"Combinatorica"},{"key":"14_CR30","unstructured":"Sedgewick, R.: Algorithms in Java, Parts 1\u20134: Fundamentals, Data Structures, Sorting, and Searching, 3rd edn., pp. 615\u2013619. Addison Wesley (2003)"},{"key":"14_CR31","unstructured":"Turner, L.: Dylan Moran Interview: On Music Loved & Loathed. The Quietus (November 24, 2009), \n                    \n                      http:\/\/thequietus.com\/articles\/03283-dylan-moran-interview-on-music-loved-loathed"},{"issue":"12","key":"14_CR32","doi-asserted-by":"publisher","first-page":"2201","DOI":"10.1109\/JPROC.2010.2070050","volume":"98","author":"H.-S.P. Wong","year":"2010","unstructured":"Wong, H.-S.P., Raoux, S., Kim, S., Liang, J., Reifenberg, J.P., Rajendran, B., Asheghi, M., Goodson, K.E.: Phase change memory. Proc. IEEE\u00a098(12), 2201\u20132227 (2010), \n                    \n                      http:\/\/dx.doi.org\/10.1109\/JPROC.2010.2070050\n                    \n                    \n                  , doi:10.1109\/JPROC.2010.2070050","journal-title":"Proc. IEEE"},{"key":"14_CR33","unstructured":"Woodhouse, D.: JFFS: the journalling flash file system. In: Ottawa Linux Symposium (2001), \n                    \n                      https:\/\/sourceware.org\/jffs2\/jffs2.pdf"},{"key":"14_CR34","doi-asserted-by":"crossref","unstructured":"Wu, M., Zwaenepoel, W.: eNVy: a non-volatile, main memory storage system. In: Proc. 6th Int. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pp. 86\u201397 (1994), doi:10.1145\/195473.195506","DOI":"10.1145\/195473.195506"},{"key":"14_CR35","doi-asserted-by":"crossref","unstructured":"Zukowski, M., H\u00e9man, S., Boncz, P.: Architecture-conscious hashing. In: Proc. 2nd Int. Worksh. on Data Management on New Hardware (DaMoN 2006) (2006), doi:10.1145\/1140402.1140410","DOI":"10.1145\/1140402.1140410"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07959-2_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T21:59:34Z","timestamp":1558907974000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07959-2_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319079585","9783319079592"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07959-2_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}