Donghui Zhang, Yannis Manolopoulos, Yannis Theodoridis et al. · 2014
Linear Hashing is a dynamically updateable disk-based index structure which implements a hashing scheme and which grows or shrinks one bucket at a time. The index is used to support exact match queries, i.e. find the record with a given key. Compared with the B+-tree index which also supports exact match queries (in logarithmic number of I/Os), Linear Hashing has better expected query cost O(1) I/O. Compared with Extendible Hashing, Linear Hashing does not use a bucket directory, and when an overflow occurs it is not always the overflown bucket that is split. The name Linear Hashing is used because the number of buckets grows or shrinks in a linear fashion. Overflows are handled by creating a chain of pages under the overflown bucket. The hashing function changes dynamically and at any given instant there can be at most two hashing functions used by the scheme. HISTORICAL BACKGROUND A hash table is an in-memory data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key, find the corresponding value. It works by transforming the key using a hash function into a hash, a number that is used as an index in an array to locate the desired location where the values should be. Multiple keys may be hashed to the same bucket, and all keys in a bucket should be searched upon a query. Hash tables are often used to implement associative arrays, sets and caches. Like arrays, hash tables have O(1) lookup cost on average.
Cited by 0
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen et al. · 1997
Cited by 0
Donghui Zhang, Yannis Manolopoulos, Yannis Theodoridis et al. · Encyclopedia of Database Systems · 2017
Cited by 0
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen et al. · 1997
Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F . We study how good H is as a class of hash functions, namely we consider hashing a set S of size n into a range having the same cardinality n by a randomly chosen function from H and look at the expected size of the largest hash bucket. H is a universal class of hash functions for any finite field, but with respect to our measure different fields behave differently. If the finite field F has n elements then there is a bad set S ae F 2 of size n with expected maximal bucket size\\Omega\\Gamma n 1=3 ). If n is a perfect square then there is even a bad set with largest bucket size always at least p n. (This is worst possible, since with respect to a universal class of hash functions every set of size n has expected largest bucket size below p n + 1=2.) If, however, we consider the field of two elements then we get much better bounds. The best previously known upper bound on...
Cited by 0
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen et al. · 1999
Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F . We study how good H is as a class of hash functions, namely we consider hashing a set S of size n into a range having the same cardinality n by a randomly chosen function from H and look at the expected size of the largest hash bucket. H is a universal class of hash functions for any finite field, but with respect to our measure different fields behave differently. If the finite field F has n elements then there is a bad set S ae F 2 of size n with expected maximal bucket size\\Omega\\Gamma n 1=3 ). If n is a perfect square then there is even a bad set with largest bucket size always at least p n. (This is worst possible, since with respect to a universal class of hash functions every set of size n has expected largest bucket size below p n + 1=2.) If, however, we consider the field of two elements then we get much better bounds. The best previously known upper bound on...
Cited by 0
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen et al. · 1997
Consider the set ${\cal H}$ of all linear (or affine) transf ormations between two vector spaces over a finite field $F$. We study how good $\cal H$ is as a class of hash functions, namely we consider hashing a set $S$ of size $n$ into a range having the same cardinali ty $n$ by a randomly chosen function from ${\cal H}$ and look at the expected size of the largest hash bucket. $\cal H$ is a universal class of hash functions for any fini te field, but with respect to our measure different fields behave differen tly. \par If the finite field $F$ has $n$ elements then there is a bad set $S\subset F^2$ of size $n$ with expected maximal bucket size $\Omega(n^{1/3})$. If $n$ is a perfect square then there is even a bad set with largest bucket size {\em always} at least $\sqrt n$. (This is worst possible, since with respect to a universal class of hash functions every set of size $n$ has expected largest bucket size below $\sqrt n+1/2$.) \par If, however, we consider the field of two elements then we get much better bounds. The best previously known upper bound on the expected size of the largest bucket for this class was $O( 2^{\sqrt{\log n}})$. We reduce this upper bound to $O(\log n\log\log n)$. Note that this is not far from the guarantee for a random function. There, the average largest bucket would be $\Theta(\log n/\log \log n)$. \par In the course of our proof we develop a tool which may be of independent interest. Suppose we have a subset $S$ of a vector space $D$ over ${\bf Z}_2$, and consider a random linear mapping of $D$ to a smaller vector space $R$. If the cardinality of $S$ is larger than $c_\e|R|\log|R|$ then with probability $1-\e$, the image of $S$ will cover all elements in the range.
Cited by 7
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen et al. · BRICS Report Series · 1997
Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F. We study how good H is as a class of hash functions, namely we consider hashing a set S of size<br />n into a range having the same cardinality n by a randomly chosen function from H and look at the expected size of the largest hash bucket. H is a universal class of hash functions for any finite field, but<br />with respect to our measure different fields behave differently.
Cited by 1Open access
Charles Lins · Springer compass international · 1990
Cited by 2
C. H. Ang, Sun Teck Tan, T.C. Tan · Lecture notes in computer science · 1998
Cited by 2
Zalán Bodó, Lehel Csató · Neurocomputing · 2014
Cited by 9
Carla Schlatter Ellis · 1985
Article Free Access Share on Concurrency and linear hashing Author: Carla Schlatter Ellis View Profile Authors Info & Claims PODS '85: Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1985Pages 1–7https://doi.org/10.1145/325405.325406Published:25 March 1985Publication History 3citation132DownloadsMetricsTotal Citations3Total Downloads132Last 12 Months44Last 6 weeks26 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Cited by 12Open access
Michael Jaber, Vinayak M. Kumar, David Zuckerman · ArXiv.org · 2025
We prove that hashing $n$ balls into $n$ bins via a random matrix over $\mathbf{F}_2$ yields expected maximum load $O(\log n / \log \log n)$. This matches the expected maximum load of a fully random function and resolves an open question posed by Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos (STOC '97, JACM '99). More generally, we show that the maximum load exceeds $r\cdot\log n/\log\log n$ with probability at most $O(1/r^2)$.
Cited by 0Open access
Rathi, Ashok K. · SHAREOK (University of Oklahoma; Oklahoma State University; Central Oklahoma University) · 2015
Computing and Information Science
Cited by 0Open access
Ashok Rathi, Huizhu Lu, G. E. Hedrick · ACM SIGSMALL/PC Notes · 1991
Based on seven assumptions, the following comparison factors are used to compare the performance of linear hashing with extendible hashing: 1. storage utilization; 2. average unsuccessful search cost; 3. average successful search cost; 4. split cost; 5. insertion cost; 6. number of overflow buckets. The simulation is conducted with the bucket sizes of 10, 20, and 50 for both hashing techniques. In order to observe their average behavior, the simulation uses 50,000 keys which have been generated randomly.According to our simulation results, extendible hashing has an advantage of 5% over linear hashing in terms of storage utilization. Successful search, unsuccessful search, and insertions are less costly in linear hashing. However, linear hashing requires a large overflow space to handle the overflow records. Simulation shows that approximately 10% of the space should be marked as overflow space in linear hashing.Directory size is a serious bottleneck in extendible hashing. Based on the simulation results, the authors recommend linear hashing when main memory is at a premium.
Cited by 10Open access
Witold Litwin, Marie-anne Neimat · 2008
RAM and disk files. An LH * file can be created from objects provided by any number of distributed and au-tonomous clients. It can grow gracefully, one bucket at a time, to virtually any number of servers. The number of messages per insertion is one in general, and three in the worst case. The number of messages per retrieval is two in general, and four in the worst case. The load factor can be about constant, 65–95%, depending on the file parameters. The file can also support parallel oper-ations. An LH * file can be much faster than a single site disk file, and/or can hold a much larger number of objects. It can be more efficient than any file with a centralized directory, or a static parallel or distributed hash file. 1
Cited by 0
Mikkel Thorup · Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms · 2009
Linear probing is one of the most popular implementations of dynamic hash tables storing all keys in a single array. When we get a key, we first hash it to a location. Next we probe consecutive locations until the key or an empty location is found. At STOC'07, Pagh et al. presented data sets where the standard implementation of 2-universal hashing leads to an expected number of Ω(log n) probes. They also showed that with 5-universal hashing, the expected number of probes is constant. Unfortunately, we do not have 5-universal hashing for, say, variable length strings. When we want to do such complex hashing from a complex domain, the generic standard solution is that we first do collision free hashing (w.h.p.) into a simpler intermediate domain, and second do the complicated hash function on this intermediate domain. Our contribution is that for an expected constant number of linear probes, it is suffices that each key has O(1) expected collisions with the first hash function, as long as the second hash function is 5-universal. This means that the intermediate domain can be n times smaller, and such a smaller intermediate domain typically means that the overall hash function can be made simpler and at least twice as fast. The same doubling of hashing speed for O(1) expected probes follows for most domains bigger than 32-bit integers, e.g., 64-bit integers and fixed length strings. In addition, we study how the overhead from linear probing diminishes as the array gets larger, and what happens if strings are stored directly as intervals of the array. These cases were not considered by Pagh et al.
Cited by 7
Per-Åke Larson · ACM Transactions on Database Systems · 1985
Linear hashing is a file structure for dynamic files. In this paper, a new, simple method for handling overflow records in connection with linear hashing is proposed. The method is based on linear probing and does not rely on chaining. No dedicated overflow area is required. The expansion sequence of liner hashing is modified to improve the performance, which requires changes in the address computation. A new address computation algorithm and an expansion algorithm are given. The performance of the method is studied by simulation. The algorithms for the basic file operations are very simple, and the overall performance is competitive with that of other variants of linear hashing.
Cited by 34Open access
Yanzhen Liu, Xiao Bai, Cheng Yan et al. · Griffith Research Online (Griffith University, Queensland, Australia) · 2016
The amount of data is exploding with the development of Internet and multimedia technology. Rapid retrieval of mass data is becoming more and more important. To meet the demand of the rapid retrieval, many approximate nearest neighobor methods have been proposed to accelerate the exhaustive search process. Hashing is such an example with great balance of time and accuracy. Hashing methods achieve quick retrieval by converting the high-dimensional raw data into a binary hash code, keeping the similarity of original data in mapped hash codes. Many hashing approaches use the Euclidean distance as similarity measurement. However, data in many datasets are distributed on a non-linear manifold, such that geodesic distance on manifold can represents the semantic similarity of original data points more accurately than the Euclidean distance. This enables better preservation of the sematic similarity in the hash code when mapping the original dataset to low- dimensional space. In this paper, we propose to use Isometric Mapping (ISOMAP) for dimensional reduction and utilize iterative quantization to reduce quantization loss during hashing process. The experiments show that our manifold learning method outperforms several alternative hashing methods. The retrieval performance is further boosted after iterative quantization process is added to the Diffusion Hashing (DH) and Spectral Hashing.
Cited by 0Open access
Andreas Hutflesz, H.-W. Six, Peter Widmayer · 2003
Presents a dynamic, globally order-preserving hashing technique, based on linear hashing, where the spatial proximity of points is preserved beyond data buckets. The method adaptively generates a bucket numbering, which is a flexible variant of the well-known z-ordering. In addition to the standard dictionary operations, the authors' dynamic z-hashing scheme supports the efficient implementation of proximity queries.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 59
Hai-Hao Tang, Hu Chen, Jiangfeng Peng · 2009
Multi-core computers have become increasingly popular, in order to improve the performance of index in database systems on multi-core computers, and this paper presents an alternative algorithm of linear hashing and multithreaded disk buffer on multi-core computers. In this algorithm, records can be inserted into hash table concurrently by different threads. The key of the parallel insertion is to make traditional insertion into batch insertion. Multithreaded disk buffer is developed for multithreaded linear hashing, making multithreads allocate and release memory simultaneously as much as possible. It is applied to maximize memory utilization and to minimize the number of disk accesses. Our experimental result shows that, compared to traditional serial linear hashing, multithread linear hashing achieves a higher performance on multi-core computers.
Cited by 1