Non-Expansive Hashing

non-expansive hashing scheme, similar inputs are stored in memory locations which are close. We develop a non-expansive hashing scheme wherein any set of size from a large universe may be stored in a memory of size (any , and ), and where retrieval takes operations. We explain how to use non-expansive hashing schemes for efficient storage and retrieval of noisy data. A dynamic version of this hashing scheme is presented as well. Received: February 5, 1996     

Interpolation-based index maintenance

A new interpolation-based order preserving hashing algorithm suitable for on-line maintenance of large dynamic external files under sequences of four kinds of operationsinsertion, update, deletion, andorthogonal range query is proposed. The scheme, an adaptation of linear hashing, requires no index or address directory structure and utilizesO(n) space for files containingn records; all of the benefits of linear hashing are inherited by this new scheme. File implementations yielding average successful search lengths much less than 2 and average unsuccessful search lengths much less than 4 for individual records are obtainable; the actual storage required is controllable by the implementor.     

A refinement of a compression-oriented addressing scheme

Chang and Wu have proposed a letter-oriented perfect hashing scheme based on sparse matrix compression. We present a method which is a refinement of the Chang-Wu scheme. By experimental evaluation, we show that the hashing of our refinement has more efficient storage utilization than Chang-Wu's method. Our refinement is valuable in practical implementations of hashing for large sets of keys.     

Optimal dynamic multi-attribute hashing for range queries

This paper examines a partial match retrieval scheme which supports range queries for highly dynamic databases. The scheme relies on order preserving multi-attribute hashing. In general, designing optimal indexes is NP-hard. Greedy algorithms used to determine the optimal indexes for simple partial match queries are not directly applicable because there are a larger number of queries to consider in determining the optimal indexes. In this paper we present heuristic algorithms which provide near-optimal solutions. The optimisation scheme we propose can be used to design other dynamic file structures such as the grid file, BANG file and multilevel grid file to further enhance their retrieval performance taking into consideration the query distribution.     

Numerical solution of singular boundary value problems using Green’s function and improved decomposition method

In this work, an effective technique for solving a class of singular two point boundary value problems is proposed. This technique is based on the Adomian decomposition method (ADM) and Green’s function. The technique relies on constructing Green’s function before establishing the recursive scheme for the solution components. In contrast to the existing recursive schemes based on ADM, the proposed recursive scheme avoids solving a sequence of nonlinear algebraic or transcendental equations for the undetermined coefficients. The approximate solution is obtained in the form of series with easily calculable components. For the completeness, the convergence and error analysis of the proposed scheme is supplemented. Moreover, the numerical examples are included to demonstrate the accuracy, applicability, and generality of the proposed scheme. The results reveal that the method is very effective, straightforward, and simple.     

Multicriteria dynamic programming with an application to the integer case

Fundamental dynamic programming recursive equations are extended to the multicriteria framework. In particular, a more detailed procedure for a general recursive solution scheme for the multicriteria discrete mathematical programming problem is developed. Definitions of lower and upper bounds are offered for the multicriteria case and are incorporated into the recursive equations to aid problem solution by eliminating inefficient subpolicies. Computational results are reported for a set of 0–1 integer linear programming problems.This research was supported in part by CONACYT (Consejo Nacional de Ciencia y Technologia), Mexico City, Mexico.     

Efficient dynamic programming implementations of Newton's method for unconstrained optimal control problems

Naive implementations of Newton's method for unconstrainedN-stage discrete-time optimal control problems with Bolza objective functions tend to increase in cost likeN ³ asN increases. However, if the inherent recursive structure of the Bolza problem is properly exploited, the cost of computing a Newton step will increase only linearly withN. The efficient Newton implementation scheme proposed here is similar to Mayne's DDP (differential dynamic programming) method but produces the Newton step exactly, even when the dynamical equations are nonlinear. The proposed scheme is also related to a Riccati treatment of the linear, two-point boundary-value problems that characterize optimal solutions. For discrete-time problems, the dynamic programming approach and the Riccati substitution differ in an interesting way; however, these differences essentially vanish in the continuous-time limit.This work was supported by the National Science Foundation, Grant No. DMS-85-03746.     

The Adomian decomposition method with Green’s function for solving nonlinear singular boundary value problems

In this paper, we present an efficient numerical algorithm for solving a general class of nonlinear singular boundary value problems. This present algorithm is based on the Adomian decomposition method (ADM) and Green’s function. The method depends on constructing Green’s function before establishing the recursive scheme. In contrast to the existing recursive schemes based on ADM, the proposed numerical algorithm avoids solving a sequence of transcendental equations for the undetermined coefficients. The approximate series solution is calculated in the form of series with easily computable components. Moreover, the convergence analysis and error estimation of the proposed method is given. Furthermore, the numerical examples are included to demonstrate the accuracy, applicability, and generality of the proposed scheme. The numerical results reveal that the proposed method is very effective.     

Auxiliary model based parameter estimation for dual-rate output error systems with colored noise

The dual-rate sampled-data systems can offer better quality of control than the systems with single sampling rate in practice. However, the conventional identification methods run in the single-rate scheme. This paper focuses on the parameter estimation problems of the dual-rate output error systems with colored noises. Based on the dual-rate sampled and noise-contaminated data, two direct estimation algorithms are addressed: the auxiliary model based recursive extended least squares algorithm and the recursive prediction error method. The auxiliary model is employed to estimate the noise-free system output. An example is given to test and illustrate the proposed algorithms.     

Analysis of repeated hashing

A performance analysis of an overflow handling method for hash files, here called repeated hashing, is reported. The basic idea of repeated hashing is to rehash the overflow records into a smaller separate storage area; the overflow records from this area are in turn hashed into a still smaller separate storage area, etc. The expected retrieval performance and the storage requirements are analysed, both for initial loading and steady state. The problem of optimally partitioning the total storage area is considered and the optimal solution is given. It is concluded, however, that the usefulness of repeated hashing is in doubt because there are methods having the same performance but requiring less maintenance.     

Data-driven recursive least squares methods for non-affined nonlinear discrete-time systems

Aiming at identifying nonlinear systems, one of the most challenging problems in system identification, a class of data-driven recursive least squares algorithms are presented in this work. First, a full form dynamic linearization based linear data model for nonlinear systems is derived. Consequently, a full form dynamic linearization-based data-driven recursive least squares identification method for estimating the unknown parameter of the obtained linear data model is proposed along with convergence analysis and prediction of the outputs subject to stochastic noises. Furthermore, a partial form dynamic linearization-based data-driven recursive least squares identification algorithm is also developed as a special case of the full form dynamic linearization based algorithm. The proposed two identification algorithms for the nonlinear nonaffine discrete-time systems are flexible in applications without relying on any explicit mechanism model information of the systems. Additionally, the number of the parameters in the obtained linear data model can be tuned flexibly to reduce computation complexity. The validity of the two identification algorithms is verified by rigorous theoretical analysis and simulation studies.     

A primogenitary linked quad tree approach for solution storage and retrieval in heuristic binary optimization

A data structure, called the primogenitary linked quad tree (PLQT), is used to store and retrieve solutions in heuristic solution procedures for binary optimization problems. Two ways are proposed to use integer vectors to represent solutions represented by binary vectors. One way is to encode binary vectors into integer vectors in a much lower dimension and the other is to use the sorted indices of binary variables with values equal to 0 or equal to 1. The integer vectors are used as composite keys to store and retrieve solutions in the PLQT. An algorithm processing trial solutions for insertion into or retrieval from the PLQT is developed. Examples are provided to demonstrate the way the algorithm works. Another algorithm traversing the PLQT is also developed. Computational results show that the PLQT approach takes only a very tiny portion of the CPU time taken by a linear list approach for the same purpose for any reasonable application. The CPU time taken by the PLQT managing trial solutions is negligible as compared to that taken by a heuristic procedure for any reasonably hard to solve binary optimization problem, as shown in a tabu search heuristic procedure for the capacitated facility location problem. Compared to the hashing approach, the PLQT approach takes the same or less amount of CPU time but much less memory space while completely eliminating collision.     

Algorithm for verifying the equivalence of linear unary recursive programs on ordered semigroup scales

A new method for solving the problem of equivalence of linear unary recursive programs is proposed. The main idea behind this method is to reduce the equivalence problem to known problems on graphs and to problems in group theory. A class of program semantics is singled out for which the problem of the equivalence of the programs in question is solvable in polynomial time by the proposed method.     

Subgradient methods for huge-scale optimization problems

We consider a new class of huge-scale problems, the problems with sparse subgradients. The most important functions of this type are piece-wise linear. For optimization problems with uniform sparsity of corresponding linear operators, we suggest a very efficient implementation of subgradient iterations, which total cost depends logarithmically in the dimension. This technique is based on a recursive update of the results of matrix/vector products and the values of symmetric functions. It works well, for example, for matrices with few nonzero diagonals and for max-type functions. We show that the updating technique can be efficiently coupled with the simplest subgradient methods, the unconstrained minimization method by B.Polyak, and the constrained minimization scheme by N.Shor. Similar results can be obtained for a new nonsmooth random variant of a coordinate descent scheme. We present also the promising results of preliminary computational experiments.     

Products of B-patches

Products and tensor products of multivariate polynomials in B-patch form are viewed as linear combinations of higher degree B-patches. Univariate B-spline segments and certain regions of simplex splines are examples of B-patches. A recursive scheme for transforming tensor product B-patch representations into B-patch representations of more variables is presented. The scheme can also be applied for transforming ann-fold product of B-patch expansions into a B-patch expansion of higher degree. Degree raising formulas are obtained as special cases. The scheme calculates the blossom of the (tensor) product surface and generalizes the pyramidal recursive scheme for B-patches.     

Dynamic hashing

A new file organisation called dynamic hashing is presented. The organisation is based on normal hashing, but the allocated storage space can easily be increased and decreased without reorganising the file, according to the number of records actually stored in the file. The expected storage utilisation is analysed and is shown to be approximately 69% all the time. Algorithms for inserting and deleting a record are presented and analysed. Retrieval of a record is fast, requiring only one access to secondary storage. There are no overflow records. The proposed scheme necessitates maintenance of a relatively small index structured as a forest of binary trees or slightly modified binary tries. The expected size of the index is analysed and a compact representation of the index is suggested.     

Single access hashing with overflow separators for dynamic files

The dynamic external hashing proposed in this paper allocates records according to the spiral storage technique. Separators derived from the signature technique are used for distinguishing primary from overflow records and for subdividing overflow chains into segments allocated into the primary file. Single access retrieval is obtained by means of a main memory index with an entry per bucket and containing separators and pointers. While this method uses a larger index than other recent proposals, it is much more convenient regarding load factor and insertion cost. Furthermore, file expansion is directed by various control parameters, thus allowing the user to choose the most suitable policy for his application.     

Doubly singular boundary value problems with derivative dependent source function: A fast‐converging iterative approach

In this paper, a fast‐converging recursive scheme is presented to approximate the solution of a class of derivative dependent doubly singular boundary value problems (DDSBVP). First, the original problem is reformulated as an equivalent integral equation. The resulting integral equation is then efficiently tackled by an improved homotopy analysis method (IHAM). This method contains a parameter, which greatly accelerates the convergence of the series solution. The convergence of the method is carried out. To illustrate the efficiency and accuracy of the proposed recursive approach, we consider three nonlinear examples, including one physical model problem, which describes stress distribution on a rotationally shallow membrane cap. Results show that our method excels over the existing methods.     

线性Hamilton系统边值问题的保辛数值方法

以Hamilton系统的正则变换和生成函数为基础研究线性时变Hamilton系统边值问题的保辛数值求解算法.根据第二类生成函数系数矩阵与状态传递矩阵的关系,构造了生成函数系数矩阵的区段合并递推算法,并进一步将递推算法推广到线性非齐次边值问题中;然后利用生成函数的性质将边值问题转化为初值问题,最后采用初值问题的保辛算法求解以达到整个Hamilton系统保辛的目的.数值算例表明该方法能够有效地求解线性齐次与非齐次问题,并能很好地保持Hamilton系统的固有特性.     

云计算技术在输电线路状态监测系统中的应用

在分析输电线路状态监测系统特点的基础上,提出了在系统中引入云计算存储与并行处理技术的设计方案,将关系型数据库与开源的Hadoop云计算平台结合使用,解决了关系型数据库在系统使用中存储和访问效率等方面的问题.介绍了所开发的原型系统提供的服务及其主要功能,并针对系统中的典型应用进行了性能测试.测试结果表明所提方案可以满足输电线路状态监测系统对数据存储与读取、分析的性能要求.