{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:22:44Z","timestamp":1725664964480},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540631385"},{"type":"electronic","value":"9783540691570"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63138-0_21","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:08:00Z","timestamp":1330279680000},"page":"233-254","source":"Crossref","is-referenced-by-count":1,"title":["Communication efficient parallel searching"],"prefix":"10.1007","author":[{"given":"Armin","family":"B\u00e4umker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Friedhelm Meyer","family":"Heide","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"21_CR1","first-page":"1259","volume":"3","author":"G.M. Adel'son-Velskii","year":"1962","unstructured":"G.M. Adel'son-Velskii and Y.M. Landis, An Algorithm for the organization of information, Soviet Math. Dokl., 3 (1962) 1259\u20131262.","journal-title":"Soviet Math. Dokl."},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, A.K. Chandra and M. Snir, On communication latency in PRAM computations, in: Proc. ACM Symp. on Parallel Algorithms and Architectures (1989) 11\u201321.","DOI":"10.1145\/72935.72937"},{"key":"21_CR3","unstructured":"M.J. Atallah, F. Dehne, R. Miller, A. Rau-Chaplin and J.-J. Tsay, Multisearch techniques for implementing data structures on a mesh-connected computer, in: Proc. ACM Symp. on Parallel Algorithms and Architectures (1991) 204\u2013214."},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"M.J. Atallah and A. Fabri, On the multisearching problem for hypercubes, in: Parallel Architectures and Languages Europe (1994).","DOI":"10.1007\/3-540-58184-7_98"},{"key":"21_CR5","unstructured":"A. B\u00e4umker, W. Dittrich, and F. Meyer auf der Heide, Truly efficient parallel algorithms: c-optimal multisearch for an extension of the BSP model, in: Proc. European Symposium on Algorithms (1995) 17\u201330."},{"key":"21_CR6","unstructured":"A. B\u00e4umker, W. Dittrich, and F. Meyer auf der Heide, Truly efficient parallel algorithms: 1-optimal multisearch for an extension of the BSP model, Technical Report No. tr-rsfb-96-008, Universit\u00e4t-Gesamthochschule Paderborn (1996), accepted for Theoretical Computer Science."},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"A. B\u00e4umker, W. Dittrich, A. Pietracaprina, The deterministic complexity of parallel multisearch, in: Proc. 5th SWAT (1996).","DOI":"10.1007\/3-540-61422-2_149"},{"key":"21_CR8","unstructured":"A. B\u00e4umker and W. Dittrich, Fully dynamic search trees for an extension of the BSP model, in: Proc. 8th SPAA (1996) 233\u2013242."},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"A. B\u00e4umker, W. Dittrich, F. Meyer auf der Heide and I. Rieping, Realistic parallel algorithms: Priority queue operations and selection for the BSP* model, in: Proc. of 2nd Euro-Par (1996).","DOI":"10.1007\/BFb0024725"},{"key":"21_CR10","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. Syst. Sci., 18 (1979) 143\u2013154.","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR11","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms (MIT Press, Massachusetts, 1990)."},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"D. Culler, R. Karp, D. Patterson, A. Sahay, K.E. Schauser, E. Santos, R. Subramonian and T. von Eicken, LogP: Towards a realistic model of parallel computation, in: Proc. ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (1993).","DOI":"10.1145\/155332.155333"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"F. Dehne, A. Fabri and A. Rau-Chaplin, Scalable parallel computational geometry for coarse grained multicomputers, in: Proc. ACM Conference on Comp. Geometry (1993).","DOI":"10.1145\/160985.161154"},{"issue":"No.4","key":"21_CR14","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M. Dietzfelbinger","year":"1994","unstructured":"M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert and R.E. Tarjan, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM J. Comput, Vol. 23, No. 4 (1994) 738\u2013761.","journal-title":"SIAM J. Comput"},{"key":"21_CR15","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide, A new universal class of hash functions and dynamic hashing in real time, in: Proc. 17th ICALP (1990) 6\u201319. Final version in: J. Buchmann, H. Ganzinger and W.J. Paul, eds., Informatik Festschrift zum 60. Geburtstag von G\u00fcnter Hotz (Teubner, Stuttgart, 1992) 95\u2013119."},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"M.L. Fredman, J. Koml\u00f3s, E. Szemeredi, Storing a sparse table with O(1) worst case time, in: Proc. 23nd. FOCS, (1982), 165\u2013169.","DOI":"10.1109\/SFCS.1982.39"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"A.V. Gerbessiotis and L. Valiant, Direct Bulk-Synchronous Parallel Algorithms, Journal of Parallel and Distributed Computing (1994).","DOI":"10.1006\/jpdc.1994.1085"},{"key":"21_CR18","unstructured":"M.T. Goodrich, Randomized fully-scalable BSP techniques for multi-searching and convex hull construction, in: 8th SODA (1997)."},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"W. Hoeffding, Probability inequalities for sums of bounded random variables, American Statistical Association Journal (1963) 13\u201330.","DOI":"10.1080\/01621459.1963.10500830"},{"key":"21_CR20","unstructured":"J. J\u00e1J\u00e1, An Introduction to Parallel Algorithms (Addison-Wesley, 1992)."},{"key":"21_CR21","first-page":"361","volume-title":"Lecture Notes in Computer Science, Vol. I","author":"B.H.H. Juurlink","year":"1996","unstructured":"B.H.H. Juurlink, P.S. Rao and J.F. Sibeyn, Worm-hole gossiping on meshes, in: Proc. Euro-Par'96, Lecture Notes in Computer Science, Vol. I (Springer, Berlin, 1996) 361\u2013369."},{"key":"21_CR22","unstructured":"D.E. Knuth, The Art of computer Programming, Vol. 1: Fundamental Algorithms (Addison-Wesley, 1968)."},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"C.P. Kruskal, L. Rudolph and M. Snir, A complexity theory of efficient parallel algorithms, in: Proc. 15th Int. Coll. on Automata, Languages, and Programming (1988) 333\u2013346.","DOI":"10.1007\/3-540-19488-6_126"},{"key":"21_CR24","unstructured":"W.F. McColl, The BSP approach to architecture independent parallel programming, Technical Report, Oxford University Computing Laboratory, 1S94."},{"key":"21_CR25","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data Structures and Algorithms 1: Sorting and Searching","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn, Data Structures and Algorithms 1: Sorting and Searching (Springer, Berlin, 1984)."},{"key":"21_CR26","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0304-3975(96)00032-1","volume":"162","author":"F. M. Heide auf der","year":"1996","unstructured":"F. Meyer auf der Heide, C. Scheideier and V. Stemann, Exploiting storage redundancy to speed up randomized shared memory simulations, Theoretical Computer Science 162 (1996) 245\u2013281.","journal-title":"Theoretical Computer Science"},{"key":"21_CR27","doi-asserted-by":"crossref","unstructured":"A. Czumaj, F. Meyer auf der Heide and V. Stemann, Shared Memory Simulations with Triple-Logarithmic Delay, in: in: Proc. European Symposium on Algorithms (1995).","DOI":"10.1007\/3-540-60313-1_133"},{"key":"21_CR28","doi-asserted-by":"crossref","unstructured":"W. Paul, U. Vishkin and H. Wagener, Parallel dictionaries on 2\u20133 trees, in: Proc. of the 10th ICALP (1983) 597\u2013609.","DOI":"10.1007\/BFb0036940"},{"key":"21_CR29","doi-asserted-by":"crossref","unstructured":"A. Pietracaprina and G. Pucci, Tight bounds on deterministic PRAM emulations with constant redundancy, in: Proc. 2nd European Symposium on algorithms (1994) 319\u2013400.","DOI":"10.1007\/BFb0049425"},{"key":"21_CR30","doi-asserted-by":"crossref","unstructured":"Abhiram Ranade, Maintaining dynamic ordered sets on processor networks, in: Proc. 4th ACM Symp. on Parallel Algorithms and Architectures (1992) 127\u2013137.","DOI":"10.1145\/140901.140915"},{"issue":"No.3","key":"21_CR31","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1137\/S0097539790184298","volume":"23","author":"J.H. Reif","year":"1994","unstructured":"J.H. Reif and S. Sen, Randomized algorithms for binary search and load balancing on fixed connection networks with geometric applications, SIAM J. Comput., Vol. 23, No. 3 (1994) 633\u2013651.","journal-title":"SIAM J. Comput."},{"key":"21_CR32","doi-asserted-by":"crossref","unstructured":"R. Tamassia and J.S. Vitter, Optimal cooperative search in fractional cascaded data structures, in: Proc. ACM Symp. Computational Geometry (1990) 307\u2013315.","DOI":"10.1145\/97444.97698"},{"key":"21_CR33","doi-asserted-by":"crossref","unstructured":"L. Valiant, A Bridging Model for parallel Computation, Communications of the-ACM, Vol. 33, No. 8 (1994).","DOI":"10.1145\/79173.79181"}],"container-title":["Lecture Notes in Computer Science","Solving Irregularly Structured Problems in Parallel"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63138-0_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:15:52Z","timestamp":1605629752000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63138-0_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540631385","9783540691570"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/3-540-63138-0_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}