{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:36:20Z","timestamp":1725456980054},"publisher-location":"Berlin\/Heidelberg","reference-count":35,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540528261"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0032070","type":"book-chapter","created":{"date-parts":[[2005,12,11]],"date-time":"2005-12-11T01:05:31Z","timestamp":1134263131000},"page":"729-743","source":"Crossref","is-referenced-by-count":12,"title":["On parallel hashing and integer sorting"],"prefix":"10.1007","author":[{"given":"Yossi","family":"Matias","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uzi","family":"Vishkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"54_CR1","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and analysis of computer algorithms. Addison-Wesley Publishing Company, 1974."},{"key":"54_CR2","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/BF01762122","volume":"3","author":"A. Apostolico","year":"1988","unstructured":"[AIL+88] A. Apostolico, C. Iliopoulos, G.M. Landau, B. Schieber, and U. Vishkin, Parallel construction of a suffix tree. Algorithmica, 3:347\u2013365, 1988.","journal-title":"Algorithmica"},{"key":"54_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di, An O(n log n) sorting network. In Proc. of the 15th Ann. ACM Symp. on Theory of Computing, pages 1\u20139, 1983.","DOI":"10.1145\/800061.808726"},{"key":"54_CR4","first-page":"81","volume":"319","author":"R.J. Anderson","year":"1988","unstructured":"R.J. Anderson and G.L. Miller, Optimal parallel algorithms for list ranking. In AWOC '88, Springer LNCS 319, pages 81\u201390, 1988.","journal-title":"Springer LNCS"},{"key":"54_CR5","first-page":"85","volume":"12","author":"A. Apostolico","year":"1984","unstructured":"A. Apostolico, The myriad virtues of subword trees. in \u201cCombinatorial Algorithms on Words\u201d (A. Apostolico and Z. Galil, Eds.), NATO ASI Series F, Vol. 12, pages 85\u201396, 1984.","journal-title":"NATO ASI Series F"},{"key":"54_CR6","series-title":"Technical Report","volume-title":"Improved deterministic parallel integer sorting","author":"P.C.P. Bhatt","year":"1989","unstructured":"[BDH+89] P.C.P. Bhatt, K. Diks, T. Hagerup, V.C. Prasad, T. Radzik, and S. Saxena, Improved deterministic parallel integer sorting. Technical Report TR 15\/1989, Fachbereich Informatik, Universit\u00e4t des Saarlandes, D-6600 Saarbr\u00fccken, W. Germany, November 1989."},{"key":"54_CR7","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1145\/321812.321815","volume":"21","author":"R.P. Brent","year":"1974","unstructured":"R.P. Brent, The parallel evaluation of general arithmetic expressions. J. Assoc. Comput. Mach., 21:302\u2013206, 1974.","journal-title":"J. Assoc. Comput. Mach."},{"key":"54_CR8","doi-asserted-by":"crossref","unstructured":"B.S. Chlebus, K. Diks, T. Hagerup, and T. Radzik, Efficient simulations between concurrent-read concurrent-write PRAM models. In Math. Found. of Comp. Sc. '88, 1988.","DOI":"10.1007\/BFb0017146"},{"key":"54_CR9","doi-asserted-by":"crossref","unstructured":"R. Cole, Parallel merge sort. In FOCS '86, pages 511\u2013516, 1986.","DOI":"10.1109\/SFCS.1986.41"},{"key":"54_CR10","doi-asserted-by":"crossref","unstructured":"R. Cole and U. Vishkin, Approximate and exact parallel scheduling with applications to list, tree and graph problems. In FOCS '86, pages 478\u2013491, 1986.","DOI":"10.1109\/SFCS.1986.10"},{"key":"54_CR11","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1137\/0217009","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin, Approximate parallel scheduling. Part I: the basic technique with applications to optimal parallel list ranking in logarithmic time. SIAM J. Comput., 17:128\u2013142, 1988.","journal-title":"SIAM J. Comput."},{"key":"54_CR12","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1016\/0890-5401(89)90036-9","volume":"81","author":"R. Cole","year":"1989","unstructured":"R. Cole and U. Vishkin, Faster optimal parallel prefix sums and list ranking. Info. and Comp., 81:334\u2013352, 1989.","journal-title":"Info. and Comp."},{"key":"54_CR13","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide, An optimal parallel dictionary. In SPAA '89, pages 360\u2013368, 1989.","DOI":"10.1145\/72935.72974"},{"key":"54_CR14","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1146\/annurev.cs.03.060188.001313","volume":"3","author":"D. Eppstein","year":"1988","unstructured":"D. Eppstein and Z. Galil, Parallel algorithmic techniques for combinatorial computation. Ann. Rev. Comput. Sci., 3:233\u2013283, 1988.","journal-title":"Ann. Rev. Comput. Sci."},{"key":"54_CR15","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M. L. Fredman","year":"1984","unstructured":"M. L. Fredman, J. Koml\u00f3s, and E. Szemer\u00e9di, Storing a sparse table with O(1) worst case access time. J. of the Association for Computing Machinery, 31:538\u2013544, 1984.","journal-title":"J. of the Association for Computing Machinery"},{"key":"54_CR16","doi-asserted-by":"crossref","unstructured":"Z. Galil, Optimal parallel algorithms for string matching. In STOC '84, pages 240\u2013248, 1984.","DOI":"10.1145\/800057.808687"},{"key":"54_CR17","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0885-064X(88)90008-8","volume":"4","author":"Z. Galil","year":"1988","unstructured":"Z. Galil and R. Giancarlo, Data structures and algorithms for approximate string matching. J. of Complexity, 4:33\u201372, 1988.","journal-title":"J. of Complexity"},{"key":"54_CR18","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0890-5401(87)90062-9","volume":"75","author":"T. Hagerup","year":"1987","unstructured":"T. Hagerup, Towards optimal parallel bucket sorting. Info. and Comp., 75:39\u201351, 1987.","journal-title":"Info. and Comp."},{"key":"54_CR19","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0020-0190(88)90233-5","volume":"29","author":"T. Hagerup","year":"1988","unstructured":"T. Hagerup, On saving space in parallel computation. Info. Proc. Let., 29:327\u2013329, 1988.","journal-title":"Info. Proc. Let."},{"key":"54_CR20","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S0734-189X(88)80033-1","volume":"44","author":"J. Illingworth","year":"1988","unstructured":"J. Illingworth and J. Kittler, A survey of the Hough transform. Computer Vision, Graphics, and Image Processing, 44:87\u2013116, 1988.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"54_CR21","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF01786986","volume":"15","author":"D.B. Johnson","year":"1982","unstructured":"D.B. Johnson, A priority queue in which initialization and queue operations take O(log log D) time. Math. Systems Theory, 15:295\u2013309, 1982.","journal-title":"Math. Systems Theory"},{"key":"54_CR22","volume-title":"The art of computer programming, volume 3, Sorting and searching","author":"D.E. Knuth","year":"1973","unstructured":"D.E. Knuth, The art of computer programming, volume 3, Sorting and searching. Addison-Wesley, Reading, 1973."},{"key":"54_CR23","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0304-3975(83)90023-3","volume":"28","author":"D. Kirkpatrick","year":"1984","unstructured":"D. Kirkpatrick and S. Reisch, Upper bounds for sorting integers on random access machines. Theo. Comp. Sc., 28:263\u2013276, 1984.","journal-title":"Theo. Comp. Sc."},{"key":"54_CR24","unstructured":"R.M. Karp and V. Ramachandran, A survey of parallel algorithms for shared-memory machines. Technical Report UCB\/CSD 88\/408, (EECS) U. C. Berkeley, 1988."},{"key":"54_CR25","first-page":"333","volume":"317","author":"C.P. Kruskal","year":"1988","unstructured":"C.P. Kruskal, L. Rudolph, and M. Snir, A complexity theory of efficient parallel algorithms. In ICALP '88, Springer LNCS 317, pages 333\u2013346, 1988.","journal-title":"Springer LNCS"},{"key":"54_CR26","doi-asserted-by":"crossref","unstructured":"A. Karlin and E. Upfal, Parallel hashing \u2014 an efficient implementation of shared memory. In STOC '86, pages 160\u2013168, 1986.","DOI":"10.1145\/12130.12146"},{"key":"54_CR27","doi-asserted-by":"crossref","unstructured":"Y. Lamdan and H.J. Wolfson, Geometric hashing: a general and efficient model-based recognition scheme. In Proc. 2nd Intl' Conf. on Comp. Vision, FL, pages 238\u2013249, 1988.","DOI":"10.1109\/CCV.1988.589995"},{"key":"54_CR28","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 Informatica, 21:339\u2013374, 1984.","journal-title":"Acta Informatica"},{"key":"54_CR29","unstructured":"Y. Matias and U. Vishkin, On parallel hashing and integer sorting. Technical Report TR-158\/89, Eskenasy Inst. of Computer Sciences, Tel-Aviv Univ., Dec. 1989. Also in UMIACS-TR-90-13, Inst. for Advanced Computer Studies, Univ. of Maryland, Jan. 1990."},{"key":"54_CR30","unstructured":"W.J. Paul and J. Simon, Decision trees and random access machines. In Symp. uber Logic und Algorithmik, 1980."},{"key":"54_CR31","doi-asserted-by":"crossref","unstructured":"A.G. Ranade, How to emulate shared memory. In FOCS '87, pages 185\u2013194, 1987.","DOI":"10.1109\/SFCS.1987.32"},{"key":"54_CR32","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1137\/0218041","volume":"18","author":"S. Rajasekaran","year":"1989","unstructured":"S. Rajasekaran and J.H. Reif, Optimal and sublogarithmic time randomized parallel sorting algorithms. SIAM J. Comput., 18:594\u2013607, 1989.","journal-title":"SIAM J. Comput."},{"key":"54_CR33","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","volume":"2","author":"Y. Shiloach","year":"1981","unstructured":"Y. Shiloach and U. Vishkin, Finding the maximum, merging, and sorting in a parallel computation model. J. Algorithms, 2:88\u2013102, 1981.","journal-title":"J. Algorithms"},{"key":"54_CR34","unstructured":"U. Vishkin, Synchronous parallel computation \u2014 a survey. Technical Report TR 71, Dept. of Computer Science, Courant Institute, New York University, 1983."},{"key":"54_CR35","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"P. van Emde Boas, R. Kaas, and E. Zijlstra, Design and implementation of an efficient priority queue. Math. Systems Theory, 10:99\u2013127, 1977.","journal-title":"Math. Systems Theory"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0032070","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T09:44:35Z","timestamp":1586598275000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0032070"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540528261"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/bfb0032070","relation":{},"subject":[]}}