A Genetic Algorithm for Obtaining Memory Constrained Near-Perfect Hashing
The problem of fast items retrieval from a fixed collection is often encountered in most computer science areas, from operating system components to databases and user interfaces. We present an approach based on hash tables that focuses on both minimizing the number of comparisons performed during the search and minimizing the total collection size. The standard open-addressing double-hashing approach is improved with a non-linear transformation that can be parametrized in order to ensure a uniform distribution of the data in the hash table. The optimal parameter is determined using a genetic algorithm. The paper results show that near-perfect hashing is faster than binary search, yet uses less memory than perfect hashing, being a good choice for memory-constrained applications where search time is also critical.
Code (0)
등록된 구현이 없습니다.
Tasks
RetrievalSimilar Papers 제목 키워드 기반
Natural Language Processing with Small Feed-Forward Networks
We show that small and shallow feed-forward neural networks can achieve near state-of-the-art results on a range of unstructured and structured language processing tasks while being considerably cheaper in memory and com…
Numerical investigation of Differential Biological Models via RBF collocation Method with Genetic Strategy
In this paper, we use Kansa method for solving the system of differential equations in the area of biology. One of the challenges in Kansa method is picking out an optimum value for Shape parameter in Radial Basis Functi…
A consistent least-squares criterion for calibrating edge lengths in phylogenetic networks
In phylogenetic networks, it is desirable to estimate edge lengths in substitutions per site or calendar time. Yet, there is a lack of scalable methods that provide such estimates. Here we consider the problem of obtaini…
Heuristic algorithms for obtaining Polynomial Threshold Functions with low densities
In this paper we present several heuristic algorithms, including a Genetic Algorithm (GA), for obtaining polynomial threshold function (PTF) representations of Boolean functions (BFs) with small number of monomials. We c…
Constrained Nonlinear Model Predictive Control of an MMA Polymerization Process via Evolutionary Optimization
In this work, a nonlinear model predictive controller is developed for a batch polymerization process. The physical model of the process is parameterized along a desired trajectory resulting in a trajectory linearized pi…
Model Predictive Control