Two-way chaining for non-uniform distributions

References

• Angluin , D. and Valiant , L. G. 1979 . Fast probabilistic algorithms for Hamiltonian paths and matchings . J. Comput. Syst. Sci. , 18 : 155 – 193 .
   Web of Science ®Google Scholar
• Azar , Y. , Broder , A. Z. , Karlin , A. R. and Upfal , E. 2000 . Balanced allocations . SIAM J. Comput. , 29 ( 1 ) : 180 – 200 .
   Google Scholar
• Berenbrink , P. , Friedetzky , T. and Mayr , E. W. Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) . Parallel continuous randomized load balancing , pp. 192 – 201 .
   Google Scholar
• Berenbrink , P. , Czumaj , A. , Friedetzky , T. and Vvedenskaya , N. D. Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) . finite parallel job allocations , pp. 99 – 108 .
   Google Scholar
• Berenbrink , P. , Czumaj , A. , Steger , A. and Vöcking , B. 2006 . Balanced allocations: the heavily loaded case . SIAM J. Comput. , 35 ( 6 ) : 1350 – 1385 .
   Google Scholar
• Broder , A. Z. and Karlin , A. Proceedings of the 1st Annual ACM–SIAM Symposium on Discrete Algorithms . Multi-level adaptive hashing , pp. 43 – 53 .
   Google Scholar
• Broder , A. and Mitzenmacher , M. Proceedings of 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2001) . 2001 . Using multiple hash functions to improve IP lookups , pp. 1454 – 1463 . Cambridge, MA : Department of Computer Science, Harvard University . Full version available as Technical Report TR-03-00
   Google Scholar
• Broder , A. Z. and Mitzenmacher , M. Proceedings of the 16th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA) . Multidimensional balanced allocations , pp. 195 – 196 .
   Google Scholar
• Buhler , J. 2001 . Efficient large-scale sequence comparison by locality-sensitive hashing . Bioinformatics , 17 ( 5 ) : 419 – 428 .
   PubMedGoogle Scholar
• Byers , J. , Considine , J. and Mitzenmacher , M. Proceedings of the 16th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) . Geometric generalizations of the power of two choices , pp. 54 – 63 .
   Google Scholar
• Cain , J. 2006 . Random graph processes and optimization , Australia : Department of Mathematics and Statistics, University of Melbourne . Ph.D. thesis
   Google Scholar
• Czumaj , A. and Stemann , V. 2001 . Randomized allocation processes . Random Struct. Algorithms , 18 ( 4 ) June : 297 – 331 .
   Google Scholar
• Dalal , K. , Devroye , L. , Malalla , E. and McLeish , E. 2005 . Two-way chaining with reassignment . SIAM J. Comput. , 35 ( 2 ) : 327 – 340 .
   Google Scholar
• Devroye , L. 1985 . The expected length of the longest probe sequence for bucket searching when the distribution is not uniform . J. Algorithms , 6 : 1 – 9 .
   Google Scholar
• Devroye , L. 1986 . Non-Uniform Random Variate Generation , New York : Springer-Verlag .
   Google Scholar
• Devroye , L. and Györfi , L. 1985 . Nonparametric Density Estimation: The L1 View , New York : John Wiley .
   Google Scholar
• Dietzfelbinger , M. and Weidling , C. 2007 . Balanced allocation and dictionaries with tightly packed constant size bins . Theor. Comput. Sci. , 380 : 47 – 68 .
   Google Scholar
• Dietzfelbinger , M. , Karlin , A. R. , Mehlhorn , K. , Meyer auf der Heide , F. , Rohnert , H. and Tarjan , R. E. 1994 . Dynamic perfect hashing: upper and lower bounds . SIAM J. Comput. , 23 ( 4 ) : 738 – 761 .
   Google Scholar
• Dolev , D. , Harari , Y. , Linial , N. , Nisan , N. and Parnas , M. 2002 . Neighborhood preserving hashing and approximate queries . SIAM J. Discre. Math. , 15 ( 1 ) : 73 – 85 .
   Google Scholar
• Eager , D. L. , Lazowska , E. D. and Zahorjan , J. 1986 . Adaptive load sharing in homogeneous distributed systems . IEEE Trans. Software Eng. , 12 : 662 – 675 .
   Web of Science ®Google Scholar
• Fredman , M. L. , Komlós , J. and Szemerédi , E. 1988 . Storing a sparse table with O(1) worst case access time . J. ACM , 31 : 538 – 544 .
   Google Scholar
• Garg , A. K. and Gotlieb , C. C. 1986 . Order-preserving key transformations . ACM Trans. Database Syst. , 11 ( 2 ) : 213 – 234 .
   Google Scholar
• Gionis , A. , Indyk , P. and Motwani , R. Proceedings of the International Conference on Very Large Data Bases . Similarity searching in high dimensions via hashing , pp. 518 – 529 .
   Google Scholar
• Gonnet , G. H. 1981 . Expected length of the longest probe sequence in hash code searching . J. ACM , 28 : 289 – 304 .
   Google Scholar
• Gonnet , G. H. , Rogers , L. D. and George , J. A. 1980 . An algorithmic and complexity analysis of interpolation search . Acta Inform. , 39 : 39 – 52 .
   Google Scholar
• Grimmett , G. R. and Stirzaker , D. R. 2001 . Probability and Random Processes , Oxford : Oxford University Press .
   Google Scholar
• Hart , J. C. , Cochran , W. O. and Flynn , P. J. 1997 . Similarity hashing: a computer vision solution to the inverse problem of linear fractals . Fractals , 5 : 39 – 50 .
   Google Scholar
• Indyk , P. and Thaper , N. Proceedings of the 3rd International Workshop on Statistical and Computational Theories of Vision . Fast image retrieval via embeddings ,
   Google Scholar
• Indyk , P. , Motwani , R. , Raghavan , P. and Vempala , S. Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC) . Locality-preserving hashing in multidimensional spaces , pp. 618 – 625 .
   Google Scholar
• Johnson , N. L. and Kotz , S. 1977 . Urn Models and their Application: An Approach to Modern Discrete Probability Theory , New York, NY : John Wiley & Sons .
   Google Scholar
• Karp , R. , Luby , M. and Meyer auf der Heide , F. 1996 . Efficient PRAM simulation on a distributed memory machine . Algorithmica , 16 : 245 – 281 .
   Google Scholar
• Knuth , D. E. 1973 . The Art of Computer Programming, Vol. 3: Sorting and Searching , Reading, MA : Addison-Wesley .
   Google Scholar
• Kolchin , V. F. , Sevast'yanov , B. A. and Chistyakov , V. P. 1978 . Random Allocations , Washington, DC : V. H. Winston & Sons .
   Google Scholar
• Linial , N. and Sasson , O. Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC) . Non-expansive hashing , pp. 509 – 517 .
   Google Scholar
• Lumetta , S. and Mitzenmacher , M. Using the power of two choices to improve Bloom filters , submitted. A prelimenry version of the paper can be found in http://www.eecs.harvard.edu/~michaelm/postscripts/bftwo.ps
   Google Scholar
• Luczak , M. L. and Upfal , E. Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS) . Reducing network congestion and blocking probability through balanced allocation , pp. 587 – 595 .
   Google Scholar
• Ma , V. C.H. and McCool , M. D. 2002 . “ Low latency photon mapping using block hashing ” . In SIGGRAPH/Eurographics Graphics Hardware Workshop , 89 – 98 . School of Computer Science, University of Waterloo . Full version is available as Technical Report CS-2002-15
   Google Scholar
• Malalla , E. 2004 . Two-way hashing with separate chaining and linear probing , School of Computer Science, McGill University . Ph.D. thesis
   Google Scholar
• McDiarmid , C. 1989 . “ On the method of bounded differences ” . In Surveys in Combinatorics , Vol. 141 , 148 – 188 . Cambridge : London Mathematical Society Lecture Notes Series, Cambridge University Press .
   Google Scholar
• Mitzenmacher , M. D. 1996 . The power of two choices in randomized load balancing , Berkeley : Computer Science Department, University of California . Ph.D. thesis
   Google Scholar
• Mitzenmacher , M. 1999 . Studying balanced allocations with differential equations . Combinator. Probab. Comput. , 8 : 473 – 482 .
   Google Scholar
• Mitzenmacher , M. and Vöcking , B. Proceedings of the 37th Annual Allerton Conference on Communication, Control, and Computing . The asymptotics of selecting the shortest of two, improved , pp. 326 – 327 .
   Google Scholar
• Mitzenmacher , M. D. , Richa , A. and Sitaraman , R. 2000 . “ The power of two random choices: a survey of the techniques and results ” . In Handbook of Randomized Computing Edited by: Pardalos , P. , Rajasekaran , S. and Rolim , J. 255 – 305 .
   Google Scholar
• Raab , M. and Steger , A. Proceedings of the 2nd Workshop on Randomization and Approximation Techniques in Computer Science . Balls and bins – a simple and tight analysis , pp. 159 – 170 . Springer-Verlag . LNCS 1518
   Google Scholar
• Robinson , J. T. Proceedings of the 5th ACM SIGACT–SIGMOD Symposium on Principles of Database Systems . Order preserving linear hashing using dynamic key statistics , pp. 91 – 99 .
   Google Scholar
• Schickinger , T. and Steger , A. Proceedings of the 27th Annual Conference on Current Trends in Theory and Practice of Informatics . Simplified witness tree arguments , pp. 71 – 87 . Springer-Verlag . LNCS 1963
   Google Scholar
• Shakhnarovich , G. , Viola , P. and Darrell , T. Proceedings of the 9th IEEE International Conference on Computer Vision . Fast pose estimation with parameter sensitive hashing , Vol. 2 , pp. 750 – 760 .
   Google Scholar
• Stoica , I. , Morris , R. , Liben-Nowell , D. , Karger , D. R. , Kaashoek , M. F. , Dabek , F. and Balakrishnan , H. 2003 . Chord: a scalable peer-to-peer lookup protocol for internet applications . IEEE/ACM Trans. Network , 11 ( 1 ) : 17 – 32 .
   Web of Science ®Google Scholar
• Vitter , J. S. and Flajolet , P. 1990 . “ Average-case analysis of algorithms and data structures ” . In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity , Edited by: van Leeuwen , J. 431 – 524 . Amsterdam : MIT Press .
   Google Scholar
• Vöcking , B. Proceedings of the 2nd ARACNE Workshop . Symmetric vs. asymmetric multiple-choice algorithms , pp. 7 – 15 . Aarhus .
   Google Scholar
• Vöcking , B. 2003 . How asymmetry helps load balancing . J. ACM , 50 ( 4 ) : 568 – 589 .
   Google Scholar
• Weidling , C. 2004 . Space efficient hash tables with ensured constant access time , Computer Science Department, Technical University of Ilmenau . Ph.D. thesis
   Google Scholar