HASHING, SEARCHING, SKETCHING. A DISSERTATION SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE AND THE COMMITTEE ON GRADUATE STUDIES OF STANFORD UNIVERSITY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Rina Panigrahy December 2006 UMI Number: 3242604 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.
Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3242604 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.
ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 © Copyright by Rina Panigrahy 2007 All Rights Reserved 1 I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. Pelee —— (Rajeev Motwani) Principal Adviser I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. (Tim Roughgarden) I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy.
(Amin Saberi) Approved for the University Committee on Graduate Studies. ili Preface The Information Age has enabled the search for information in ways never imagined be- fore. The simplest search function may be an exact search where the input query is expected to exactly match the search object. But some search criteria are fuzzy — for instance im- age search, news search, and similar document search ~ making the search problem much harder.
One common approach is to convert such a search object into a mathematical rep- resentation such as a point (vector) in a high dimensional space. The search for a similar object then becomes a nearest neighbor search in a high dimensional space. Hashing is a simple and effective method for exact search that uses a random hash function to map items into buckets, often viewed as throwing balls into bins. A variant of hashing called locality-sensitive hashing that tends to map similar objects to the same hash bucket, can be used to perform nearest neighbor search.
A related notion is sketching that is used to transform a large complex object into a small ‘sketch’ — often a tiny bitmap — so that similarity between the sketches can be used to estimate the similarity between the original objects. In this thesis we study algorithms for different kinds of search using hashing and sketch- ing, and some fundamental limits of what can be realized using some of these approaches. For exact search, we will see how variants of balls-and-bins processes can be used to de- "rive space efficient methods for maintaining hash tables. For similarity search, we will see a variant of locality-sensitive hashing that uses linear space and how the underlying ideas can be used in the kd-tree data structure for improved performance.
We will also probe the fundamental limits of some of these approaches by showing lower bounds on their performance. iv Acknowledgement I wish to thank my Advisor Rajeev — it was his constant support through the last 9 years that I have been able to maintain in touch with Theory and algorithms while I was working in Industry. I also thank again Prof David Karger MIT for advising me during my years at MIT and for encouraging me to continue working on theory and for introducing me to Prof Motwani after I decided to leave MIT after my masters. I wish to thank all my collaborators — especially when I was away from school — Tomas Feder, Moses Charikar, Suresh Venkatasubramanian, Piotr Indyk, An Zhu, Liadan O’Callaghan, and Gagan Agarwal to name a few.
I wish to thank Samar Sharma at Cisco Systems for interesting research discussions during this period. I would like to thank the students at stanford — Krishnaram Kenthapadi, Dilys Thomas, David Arthur, Ying Xu, Sergei Vassilvitskii, and Shubha Nabar. No amount of gratitude to my parents would be sufficient. I am very fortunate to be where I am today because of their constant support and encouragement.
Contents Preface iv Acknowledgement 1 Introduction 2 Efficient Hashing 2. c c c c Q c k Q nu Q ng g vn kg Và va 2.ẶẶ ẶQQẶ QQ QẶ 11 2.3 Constant Maximum BucketS1Ze.Q HQ V Q vn và 21 2.4 Generalizing to fewermoves. ko ko KH Ha 22 2.1 Ủsingclogn-Dniversal Hash FuncHions. 26 3 Balanced Allocation on Graphs 27 3.2 Two choice Load Balancing on A-regularGraphs .3 Balls and bins with moves.
ee ee ee 36 3.4 Choosing binsin groups 2. Q Q HQ HQ HH Ha 37 3.1 High probability version ofLemma3.2 Construction of the witness graph for balls and bins with moves. 44 vi 4 Better Bloom Filters 46 41 Introduction. ee KV Ko 46 4.1 Bloom Filters and Counting Bloom Flters.2 Related Work on Counting Bloom Filters.
49 43 The d-leftCBF construction. eee ee ee 50 4.2 The Construction of a d-left Counting Bloom Filter.3 Additional Practical Issues. ee eee ee ee 54 4.4 A Comparison with Standard Counting Bloom Filters. ee eee eee ee 56 4.1 A Full Example and Comparison.
eee ee ee eee es 60 5 Entropy based Nearest Neighbor Search 61 5. ee ee ee 61 “`. rrr 64 522 Kd-Trees. ee ee ee eee 65 5.
ee ee ee ee es 65 5.5 Random Instance in Euclidean Space.6 Generalizing to arbitrarysetofpolns .2 Choice of Hash functions for Euclidean Space.02 eee ee eee 82 Vil 5.8 Micellaneous technical details .Ặ Ặ Ốc 83 Nearest Neighbor Search using Trees 85 6. ee ee 85 62 Resuls. CN cv NV ng kg kh kia 86 6.1 Trees vs HashngforNNS.22 New Search AlgorithimonKdtees. cee ee ee ee ee 89 LSH lower bounds 91 7.
kg Ta 93 Frequent Elements in a stream 98 8.2 Bounds for the MostFrequent problem .3 The nđexeđAndproblem.4 Lower bound for the nđexedAnd problem.5 Lower bound for the MostFrequent problem. Bounds for thennerProductproblem. 111 Sketching algorithms for trees 112 9. ee ee ee 112 9.
eee ee ee ee eee 113 9.2 Contributions of this study. eee ee eee 113 Vili 9.2 Models and Definitions .3 Similarity measuresÍOFfif@©€S.4 Sketching algorithmsfortwo-leveltees .1 Propagating one min-hash does not work .2 Propagating multiple min-hashes ateach level.3 Connections to Locality-Sensitive Hashing .5 Sketching algorithms for multleveltrees. ee ee ns 130 Bibliography 131 ix List of Tables 4.1 Simulation results with 67 elements being placed into n buckets using four choices, compared to the differential equations. The simulation results give the fraction of buckets with load at least k for each k up to 9; the results are based on the final distribution of elements after 27° deletions and insertions, averaged over 10000 trials.
No bucket obtained a load of 9 at any time over all 10000 trials.1 Simulation Results: The entries indicate the percentage of times the nearest neighbor os found. As the number of iterations k is increased the success rate increases. ee List of Figures 1.1 Various mathematical abstractions can be used to represent data objects. Embeddings between the different representations can be used to obtain concise sketches forthe data.
2 ee ee ee ee 2.1 Balls and bins: If each ball is thrown into a random bin, the max load is (1 + 0(1)) Inn/InInn. Instead if each ball is inserted into least loaded of 2 randomly chosen bins the max load drops exponentially to log logn + Ó(1) 3.1 Balls and bins: If each ball is thrown into a random bin, the max load is (1 + 0(1)) Inn/InInn. Instead if each ball is inserted into least loaded of d randomly chosen bins the max load drops exponentially to nee + O(1) 28 3.2 Asymmetric load balancing: If ties are broken asymmetrically, say to the left, the max load drops further to oc tele"), This means even for d as small as loglogn will result ina constant maxload.3 Unaligned super-bins: 7 and J are aligned, J’ is unaligned.4 k-step: all bins in the i” super-bin have load k — iif i> k and 0 otherwise.1 Locality sensitive hashing: Nearby points are more likely to hash to same bucket as compared to distantpoints.2 Locality sensitive hashing: Many hash tables are used to increase the chance of finding the near neighbor while searching.3 New Algorithm: Use only one hash table but search for many points in the neighborhood of the query point .2002 eae xi Chapter 1 Introduction The Information Age has enabled the search for information in ways never imagined before. We make use of fast automated search when we perform a web search, database search or a network search.
| In practice, the search criteria for the desired information are usually complex involving many criteria. At an operational level, the simplest search function may be an exact search — for instance, searching for a database record where the key has a specified value. Numerous efficient algorithms exist for exact search and this kind of search is generally easily handled. In other cases we may be performing a range search, say when we search for a restaurant in a certain radius of a location.
But some search criteria are fuzzy — for instance, image search, news search, similar document search. These are search examples where the criteria is often not stated precisely but understood at a subjective level. For example, an image search may involve finding the image of a person that best matches a given photograph. In practice, the search may be complex and involve a conjunction of several criteria: some exact, some range search, some fuzzy, and others operations specific to the problem.
For most search criteria, in terms of data structures and algorithms, there are two pri- mary fundamental underlying approaches: Trees and Hashing 1. Trees: Trees are based upon the idea of recursive pruning of search space; divide the search space into smaller regions at each decision branching point, resulting in about CHAPTER 1. INTRODUCTION 2 O(log n) search ‘depth.’ Several variants of trees have been proposed — binary trees, B-trees, Range trees and Kd-trees to name a few. Hashing: The idea behind hashing is to use an apparently random function that maps objects to an apparently random location in an array of buckets, and hope that not too many objects collide at the same bucket.
This random mapping of objects sig- nificantly reduces the search space in one shot. The objective of these random hash functions is to randomly throw objects (thought of as balls) into buckets (thought of as bins). Analysis of variants of such balls-and-bins techniques has resulted in new improved hashing methods. Since the search time in a bucket depends on the number of items in that bucket, the goal is to obtain as uniform a distribution of balls into bins as possible.
To this end, it has been shown that instead of randomly throwing balls into bins, if each ball picks two bins at random and is placed into the least loaded of the two bins, then this process results in a significant improvement in the uniformity of the distribution. Fuzzy search and the Curse of Dimensionality: The problem becomes much harder when we go from exact to fuzzy search, say image search. One common approach is to convert such a search object into a mathematical representation such as a point (vector) in a high dimensional space.
