{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T18:59:19Z","timestamp":1784573959608,"version":"3.55.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[1994,9,1]],"date-time":"1994-09-01T00:00:00Z","timestamp":778377600000},"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":[[1994,9]]},"DOI":"10.1007\/bf01185209","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T12:46:54Z","timestamp":1108730814000},"page":"170-181","source":"Crossref","is-referenced-by-count":9,"title":["Locality-preserving hash functions for general purpose parallel computation"],"prefix":"10.1007","volume":"12","author":[{"given":"A.","family":"Chin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01185209_CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, A. K. Chandra, and M. Snir, On communication latency in PRAM computations,Proc. First ACM Symp. on Parallel Algorithms and Architectures, 1989, pp. 11\u201321.","DOI":"10.1145\/72935.72937"},{"key":"BF01185209_CR2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(90)90188-N","volume":"71","author":"A. Aggarwal","year":"1990","unstructured":"A. Aggarwal, A. K. Chandra, and M. Snir, Communication complexity of PRAMs,Theoret. Comput. Sci. 71 (1990), 3\u201328.","journal-title":"Theoret. Comput. Sci."},{"issue":"9","key":"BF01185209_CR3","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"A. Aggarwal and J. S. Vitter, The input\/output complexily of sorting and related problems,Comm. ACM 31(9) (1988), 1116\u20131127.","journal-title":"Comm. ACM"},{"key":"BF01185209_CR4","doi-asserted-by":"crossref","unstructured":"W. Aiello, T. Leighton, B. Maggs, and M. Newman, Fast algorithms for bit-serial routing on a hypercube,Proc. 2nd Annual ACM Symp. on Parallel Algorithms and Architectures, 1990, pp. 55\u201364.","DOI":"10.1145\/97444.97459"},{"key":"BF01185209_CR5","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J. L. Carter","year":"1979","unstructured":"J. L. Carter and M. N. Wegman, Universal classes of hash functions,J. Comput. System Sci. 18 (1979), 143\u2013154.","journal-title":"J. Comput. System Sci."},{"key":"BF01185209_CR6","unstructured":"A. Chin, Complexity issues in general-purpose parallel computation, D.Phil, thesis, Oxford University, 1991."},{"key":"BF01185209_CR7","volume-title":"Proc. Internat. Conf. on Sets, Graphs and Numbers","author":"A. Chin","year":"1992","unstructured":"A. Chin, Latency hiding for fault-tolerant PRAM computations,Proc. Internat. Conf. on Sets, Graphs and Numbers, D. Miklos, ed., North-Holland, Amsterdam, 1992."},{"key":"BF01185209_CR8","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0020-0190(93)90218-X","volume":"45","author":"A. Chin","year":"1993","unstructured":"A. Chin, Permutations on the Block PRAM,Inform. Process. Lett. 45 (1993), 69\u201373.","journal-title":"Inform. Process. Lett."},{"key":"BF01185209_CR9","doi-asserted-by":"crossref","unstructured":"R. Cole and O. Zajicek, The APRAM: incorporating asynchrony into the PRAM model,Proc. First Annual ACM Symp. on Parallel Algorithms and Architectures, 1989, pp. 169\u2013178.","DOI":"10.1145\/72935.72954"},{"key":"BF01185209_CR10","doi-asserted-by":"crossref","unstructured":"M. Dietzfelberger and F. Meyer auf der Heide, How to distribute a dictionary in a complete network,Proc. 22nd Annual ACM Symp. on Theory Computing, 1990, pp. 117\u2013127.","DOI":"10.1145\/100216.100229"},{"key":"BF01185209_CR11","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-1-4684-2001-2_10","volume-title":"Complexity of Computer Calculations","author":"R. W. Floyd","year":"1972","unstructured":"R. W. Floyd, Permuting information in idealized two-level storage, inComplexity of Computer Calculations, R. Miller and J. Thatcher, eds., Plenum, New York, 1972, pp. 105\u2013109."},{"key":"BF01185209_CR12","volume-title":"Computer Solution of Linear Algebraic Systems","author":"G. E. Forsythe","year":"1967","unstructured":"G. E. Forsythe and C. B. Moler,Computer Solution of Linear Algebraic Systems, Prentice-Hall, Englewood Cliffs, NJ, 1967."},{"key":"BF01185209_CR13","volume-title":"Efficient Parallel Algorithms","author":"A. M. Gibbons","year":"1988","unstructured":"A. M. Gibbons and W. Rytter,Efficient Parallel Algorithms, Cambridge University Press, Cambridge, 1988."},{"key":"BF01185209_CR14","volume-title":"Ph.D. thesis","author":"P. Gibbons","year":"1989","unstructured":"P. Gibbons, The asynchronous PRAM: a semi-synchronous model for shared memory MIMD machines, Ph.D. thesis, University of California at Berkeley, 1989."},{"key":"BF01185209_CR15","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, T. Leighton, and M. Newman, Fast computation using faulty hypercubes,Proc. 21st Annual ACM Symp. on Theory of Computing, 1989, pp. 251\u2013263.","DOI":"10.21236\/ADA211910"},{"key":"BF01185209_CR16","unstructured":"T. Heywood and S. Ranka, A practical hierarchical model of parallel computation: the model, Technical Report SU-CIS-91-06, Syracuse University, Syracuse, NY 10991."},{"key":"BF01185209_CR17","doi-asserted-by":"crossref","unstructured":"P. Kanellakis and A. Shvartsman, Efficient parallel algorithms can be made robust,Proc. 8th Annual ACM Symp. on Principles of Distributed Computing, 1989, pp. 211\u2013222.","DOI":"10.1145\/72981.72996"},{"key":"BF01185209_CR18","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1145\/48014.350550","volume":"35","author":"A. Karlin","year":"1988","unstructured":"A. Karlin and E. Upfal, Parallel hashing: an efficient implementation of shared memory,J. Assoc. Comput. Mach. 35 (1988), 876\u2013892.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01185209_CR19","doi-asserted-by":"crossref","unstructured":"R. M. Karp, M. Luby, and F. Meyer auf der Heide, Efficient PRAM simulation on a distributed memory machine,Proc. 24th Annual ACM Symp. on Theory of Computing, 1992, pp. 318\u2013326.","DOI":"10.1145\/129712.129743"},{"key":"BF01185209_CR20","first-page":"869","volume-title":"Handbook of Theoretical Computer Science","author":"R. M. Karp","year":"1990","unstructured":"R. M. Karp and V. Ramachandran, Parallel algorithms for shared-memory machines,Handbook of Theoretical Computer Science (J. van Leeuwen, ed.), North-Holland, Amsterdam, 1990, pp. 869\u2013942."},{"key":"BF01185209_CR21","doi-asserted-by":"crossref","unstructured":"Z. M. Kedem, K. V. Palem, and P. G. Spirakis, Efficient robust parallel computations,Proc. 22nd Annual ACM Symp. on Theory of Computing, 1990, pp. 138\u2013148.","DOI":"10.1145\/100216.100231"},{"key":"BF01185209_CR22","doi-asserted-by":"crossref","unstructured":"F. T. Leighton and C. G. Plaxton, A (fairly) simple circuit that (usually) sorts,Proc. 31st Annual IEEE Symp. on Foundations of Computer Science, 1990, pp. 264\u2013274.","DOI":"10.1109\/FSCS.1990.89545"},{"key":"BF01185209_CR23","doi-asserted-by":"crossref","unstructured":"Y.-D. Lyuu, Fast fault-tolerant parallel communication and on-line maintenance using information dispersal,Proc. Second ACM Symp. on Parallel Algorithms and Architectures, 1990, pp. 378\u2013387.","DOI":"10.1145\/97444.97705"},{"key":"BF01185209_CR24","first-page":"337","volume-title":"Lectures on Parallel Computation","author":"W. F. McColl","year":"1993","unstructured":"W. F. McColl, General purpose parallel computing, inLectures on Parallel Computation, A. Gibbons and P. Spirakis, eds., Cambridge University Press, Cambridge, 1993, pp. 337\u2013391."},{"key":"BF01185209_CR25","unstructured":"C. Martel, A. Park, and R. Subramonian, Optimal asynchronous algorithms for shared-memory parallel computers, Technical Report CSE-89-8, University of California at Davis, 1989."},{"key":"BF01185209_CR26","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF00264615","volume":"21","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn and U. Vishkin, Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories,Acta Inform. 21 (1984), 339\u2013374.","journal-title":"Acta Inform."},{"key":"BF01185209_CR27","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0020-0190(91)90216-5","volume":"37","author":"J. K. Mullin","year":"1991","unstructured":"J. K. Mullin, A caution on universal classes of hash functions,Inform. Process. Lett. 37 (1991), 247\u2013256.","journal-title":"Inform. Process. Lett."},{"key":"BF01185209_CR28","doi-asserted-by":"crossref","unstructured":"N. Nishimura, Asynchronous shared memory parallel computation,Proc. Second Annual ACM Symp. on Parallel Algorithms and Architectures, 1990, pp. 76\u201384.","DOI":"10.1145\/97444.97672"},{"key":"BF01185209_CR29","doi-asserted-by":"crossref","unstructured":"A. G. Ranade, How to emulate shared memory,Proc. 28th Annual IEEE Symp. on Foundations of Computer Science, 1987, pp. 185\u2013194.","DOI":"10.1109\/SFCS.1987.32"},{"key":"BF01185209_CR30","doi-asserted-by":"crossref","unstructured":"A. Siegel, On universal classes of fast high-performance hash functions, their time-space tradeoff, and their applications,Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 20\u201325.","DOI":"10.1109\/SFCS.1989.63450"},{"key":"BF01185209_CR31","doi-asserted-by":"crossref","unstructured":"E. Upfal and A. Wigderson, How to share memory in a distributed system,Proc. 25th Annual IEEE Symp. on Foundations of Computer Science, 1984, pp. 171\u2013180.","DOI":"10.21236\/ADA327912"},{"key":"BF01185209_CR32","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"L. G. Valiant","year":"1990","unstructured":"L. G. Valiant, A bridging model for parallel computation,Comm. ACM 33 (1990), 103\u2013111.","journal-title":"Comm. ACM"},{"key":"BF01185209_CR33","first-page":"103","volume-title":"Handbook of Theoretical Computer Science","author":"L. G. Valiant","year":"1990","unstructured":"L. G. Valiant, General purpose parallel architectures,Handbook of Theoretical Computer Science (J. van Leeuwen, ed.), North-Holland, Amsterdam, 1990, pp. 103\u2013110."},{"key":"BF01185209_CR34","doi-asserted-by":"crossref","unstructured":"L. G. Valiant and G. J. Brebner, Universal schemes for parallel communication,Proc. 13th Annual ACM Symp. on Theory of Computing, 1981, pp. 263\u2013277.","DOI":"10.1145\/800076.802479"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01185209.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01185209\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01185209","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T21:00:38Z","timestamp":1586120438000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01185209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":34,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["BF01185209"],"URL":"https:\/\/doi.org\/10.1007\/bf01185209","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,9]]}}}