{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:01Z","timestamp":1725558961240},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_60","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"715-726","source":"Crossref","is-referenced-by-count":7,"title":["On the k-Independence Required by Linear Probing and Minwise Independence"],"prefix":"10.1007","author":[{"given":"Mihai","family":"P\u01cetra\u015fcu","sequence":"first","affiliation":[]},{"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"60_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Nussboim, A.: k-wise independent random graphs. In: Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 813\u2013822 (2008)","DOI":"10.1109\/FOCS.2008.61"},{"key":"60_CR2","unstructured":"Black, J.R., Martel, C.U., Qi, H.: Graph and hashing algorithms for modern architectures: Design and performance. In: Proc. 2nd International Workshop on Algorithm Engineering (WAE), pp. 37\u201348 (1998)"},{"issue":"3","key":"60_CR3","doi-asserted-by":"crossref","first-page":"630","DOI":"10.1006\/jcss.1999.1690","volume":"60","author":"A.Z. Broder","year":"2000","unstructured":"Broder, A.Z., Charikar, M., Frieze, A.M., Mitzenmacher, M.: Min-wise independent permutations. Journal of Computer and System Sciences\u00a060(3), 630\u2013659 (2000); See also STOC 1998","journal-title":"Journal of Computer and System Sciences"},{"key":"60_CR4","first-page":"1157","volume":"29","author":"A.Z. Broder","year":"1997","unstructured":"Broder, A.Z., Glassman, S.C., Manasse, M.S., Zweig, G.: Syntactic clustering of the web. Computer Networks\u00a029, 1157\u20131166 (1997)","journal-title":"Computer Networks"},{"issue":"3","key":"60_CR5","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1006\/jcss.1997.1534","volume":"55","author":"E. Cohen","year":"1997","unstructured":"Cohen, E.: Size-estimation framework with applications to transitive closure and reachability. Journal of Computer and System Sciences\u00a055(3), 441\u2013453 (1997); See also STOC 1994","journal-title":"Journal of Computer and System Sciences"},{"key":"60_CR6","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M.: Universal hashing and k-wise independent random variables via integer arithmetic without primes. In: Proc. 13th Symposium on Theoretical Aspects of Computer Science (STACS), pp. 569\u2013580 (1996)","DOI":"10.1007\/3-540-60922-9_46"},{"key":"60_CR7","unstructured":"Heileman, G.L., Luo, W.: How caching affects hashing. In: Proc. 7th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 141\u2013154 (2005)"},{"issue":"1","key":"60_CR8","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1006\/jagm.2000.1131","volume":"38","author":"P. Indyk","year":"2001","unstructured":"Indyk, P.: A small approximately min-wise independent family of hash functions. Journal of Algorithms\u00a038(1), 84\u201390 (2001); See also SODA 1999","journal-title":"Journal of Algorithms"},{"key":"60_CR9","unstructured":"Knuth, D.E.: Notes on open addressing (1963) (Unpublished memorandum), http:\/\/citeseer.ist.psu.edu\/knuth63notes.html"},{"issue":"3","key":"60_CR10","doi-asserted-by":"crossref","first-page":"1107","DOI":"10.1137\/070702278","volume":"39","author":"A. Pagh","year":"2009","unstructured":"Pagh, A., Pagh, R., Ru\u017ei\u0107, M.: Linear probing with constant independence. SIAM Journal on Computing\u00a039(3), 1107\u20131120 (2009); See also STOC 2007","journal-title":"SIAM Journal on Computing"},{"key":"60_CR11","doi-asserted-by":"crossref","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. Journal of Algorithms\u00a051(2), 122\u2013144 (2004); See also ESA 2001","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"60_CR12","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: The power of simple tabulation-based hashing (2010) (manuscript )","DOI":"10.1145\/1993636.1993638"},{"key":"60_CR13","doi-asserted-by":"crossref","unstructured":"Schmidt, J.P., Siegel, A.: The analysis of closed hashing under limited randomness. In: Proc. 22nd ACM Symposium on Theory of Computing (STOC), pp. 224\u2013234 (1990)","DOI":"10.1145\/100216.100245"},{"issue":"2","key":"60_CR14","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1137\/S089548019223872X","volume":"8","author":"J.P. Schmidt","year":"1995","unstructured":"Schmidt, J.P., Siegel, A., Srinivasan, A.: Chernoff-Hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics\u00a08(2), 223\u2013250 (1995); See also SODA 1993","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"60_CR15","unstructured":"Siegel, A., Schmidt, J.P.: Closed hashing is computable and optimally randomizable with universal hash functions. Technical Report TR1995-687, Currant Institute (1995)"},{"key":"60_CR16","unstructured":"Thorup, M.: Even strongly universal hashing is pretty fast. In: Proc. 11th ACM\/SIAM Symposium on Discrete Algorithms (SODA), pp. 496\u2013497 (2000)"},{"key":"60_CR17","unstructured":"Thorup, M., Zhang, Y.: Tabulation based 4-universal hashing with applications to second moment estimation. In: Proc. 15th ACM\/SIAM Symposium on Discrete Algorithms (SODA), pp. 615\u2013624 (2004)"},{"key":"60_CR18","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zhang, Y.: Tabulation based 5-universal hashing and linear probing. In: Proc. 12th Workshop on Algorithm Engineering and Experiments, ALENEX (2009)","DOI":"10.1137\/1.9781611972900.7"},{"issue":"3","key":"60_CR19","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(81)90033-7","volume":"22","author":"M.N. Wegman","year":"1981","unstructured":"Wegman, M.N., Carter, L.: New classes and applications of hash functions. Journal of Computer and System Sciences\u00a022(3), 265\u2013279 (1981); see also FOCS 1979","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_60.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:48:23Z","timestamp":1606186103000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_60"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_60","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}