MRD Hashing

We propose two new classes of hash functions which are motivated by Maximum Rank Distance (MRD) codes. We analise the security of these schemes. The system setup phase is computationally expensive for general field extensions. To overcome this limitation we derive an algebraic solution which avoids computations in special extension fields in the intended operational range of the hash functions.     

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     

Hashing matrix subscripts

In a recent paper [5] de Villiers and Wilson discuss hashing functions in connection with chained hash storage of sparse matrices. This short communication expands upon some points raised in the cited paper and gives a brief comparison of the storage requirements of open and chained hash tables in this context.     

Two Queues with Weighted One-Way Overflow

We consider an open queueing network consisting of two queues with Poisson arrivals and exponential service times and having some overflow capability from the first to the second queue. Each queue is equipped with a finite number of servers and a waiting room with finite or infinite capacity. Arriving customers may be blocked at one of the queues depending on whether all servers and/or waiting positions are occupied. Blocked customers from the first queue can overflow to the second queue according to specific overflow routines. Using a separation method for the balance equations of the two-dimensional server and waiting room demand process, we reduce the dimension of the problem of solving these balance equations substantially. We extend the existing results in the literature in three directions. Firstly, we allow different service rates at the two queues. Secondly, the overflow stream is weighted with a parameter p ∈ [0,1], i.e., an arriving customer who is blocked and overflows, joins the overflow queue with probability p and leaves the system with probability 1 − p. Thirdly, we consider several new blocking and overflow routines. An erratum to this article can be found at     

Universal Hashing and Geometric Codes

We describe a new application of algebraic coding theory to universal hashing and authentication without secrecy. This permits to make use of the hitherto sharpest weapon of coding theory, the construction of codes from algebraic curves. We show in particular how codes derived from Artin-Schreier curves, Hermitian curves and Suzuki curves yield classes of universal hash functions which are substantially better than those known before.     

Hashing vectors for tabu search

Tabu search as proposed by Glover [3,4] has proven to be a very effective metaheuristic for hard problems. In this paper we propose that hash functions be used to record the solutions encountered during recent iterations of the search in a long list. Hash values of potential solutions can be compared to the values on the list for the purpose of avoiding cycling. This frees the algorithm designer of the need to consider cycling when creating tabu restrictions based on move attributes. We suggest specific functions that result in very good performance.     

Indexing text with approximate q-grams

We present a new index for approximate string matching. The index collects text q-samples, that is, disjoint text substrings of length q, at fixed intervals and stores their positions. At search time, part of the text is filtered out by noticing that any occurrence of the pattern must be reflected in the presence of some text q-samples that match approximately inside the pattern. Hence the index points out the text areas that could contain occurrences and must be verified. The index parameters permit load balancing between filtering and verification work, and provide a compromise between the space requirement of the index and the error level for which the filtration is still efficient. We show experimentally that the index is competitive against others that take more space, being in fact the fastest choice for intermediate error levels, an area where no current index is useful.     

Hashing techniques,a global approach

A new method for more equitable comparison of various hash table techniques is presented. It is applied to some popular techniques: open addressing, coalescent chaining and separate chaining. Another method, indexed sub-tables, is also examined with more details and shown to present some interesting features.     

Text Indexing and Dictionary Matching with One Error

The indexing problem is where a text is preprocessed and subsequent queries of the form “Find all occurrences of pattern P in the text” are answered in time proportional to the length of the query and the number of occurrences. In the dictionary matching problem a set of patterns is preprocessed and subsequent queries of the form “Find all occurrences of dictionary patterns in text T” are answered in time proportional to the length of the text and the number of occurrences.There exist efficient worst-case solutions for the indexing problem and the dictionary matching problem, but none that find approximate occurrences of the patterns, i.e., where the pattern is within a bound edit (or Hamming) distance from the appropriate text location.In this paper we present a uniform deterministic solution to both the indexing and the general dictionary matching problem with one error. We preprocess the data in time O(n log² n), where n is the text size in the indexing problem and the dictionary size in the dictionary matching problem. Our query time for the indexing problem is O(m log n log log n + tocc), where m is the query string size and tocc is the number of occurrences. Our query time for the dictionary matching problem is O(n log³ d log log d + tocc), where n is the text size and d the dictionary size. The time bounds above apply to both bounded and unbounded alphabets.     

Using Signature Hashing for Approximate String Matching

The objective is to demonstrate the expediency of using compressed inverted files with a signature-hashing dictionary for approximate string matching. A comparison of different types of dictionaries is performed and a method based on keyword signature hashing is described. In conclusion, we report the comparative characteristics (search speed, index size, indexing speed) for our search system using compressed inverted files with keyword signature hashing and the Glimpse search freeware.     

New Bounds for Perfect Hashing via Information Theory

A set of sequences of length t from a b-element alphabet is called k-separated if for every k-tuple of the sequences there exists a coordinate in which they all differ. The problem of finding, for fixed t, b, and k, the largest size N(t, b, k) of a k-separated set of sequences is equivalent to finding the minimum size of a (b, k)-family of perfect hash functions for a set of a given size. We shall improve the bounds for N(t, b, k) obtained by Fredman and Komlós [1].Körner [2] has shown that the proof in [1] can be reduced to an application of the sub-additivity of graph entropy [3]. He also pointed out that this sub-additivity yields a method to prove non-existence bounds for graph covering problems. Our new non-existence bound is based on an extension of graph entropy to hypergraphs.     

Improved Dynamic Text Indexing

In the dynamic text indexing problem, a text string has to be maintained under string insertions and deletions in order to answer on-line queries about arbitrary pattern occurrences. By means of some new techniques and data structures, we achieve improved worst-case bounds. We show that finding allpoccoccurrences of a pattern of lengthpin the current text of lengthntakesO(p + pocc + updlog p + log n) time, whereupdis the number of text uptakes performed so far; inserting or deleting a string of lengthsfrom the current text takesO(s log(s + n)) time.     

Overflow and losses in a network queue with a self-similar input

This paper considers a discrete time queuing system that models a communication network multiplexer which is fed by a self-similar packet traffic. The model has a finite buffer of size h, a number of servers with unit service time, and an input traffic which is an aggregation of independent source-active periods having Pareto-distributed lengths and arriving as Poisson batches. The new asymptotic upper and lower bounds to the buffer-overflow and packet-loss probabilities P are obtained. The bounds give an exact asymptotic of log P/log h when h → to ∞. These bounds decay algebraically slow with buffer-size growth and exponentially fast with excess of channel capacity over traffic rate. Such behavior of the probabilities shows that one can better combat traffic losses in communication networks by increasing channel capacity rather than buffer size. A comparison of the obtained bounds and the known upper and lower bounds is done. This revised version was published online in June 2006 with corrections to the Cover Date.     

LSI潜在语义信息检索模型

本文介绍了基于向量空间的信息检索方法 ,检索词和文件之间的关系表示成一个矩阵 ,查寻信息表示为检索词权重的向量 ,通过求查寻和文件向量的夹角余弦确定出数据库中的相关文件 .使用矩阵的 QR分解和奇异值分解 ( SVD)来处理数据库本身的不确定性 ,本文的目的是说明线性代数中的基本概念可以很好解决信息检索 ( IR)问题     

Oja神经网络模型的有限逸时性

O ja连续型全反馈神经网络模型可以有效计算实对称矩阵的主特征向量,该网络的动态行为由描述其模型的微分方程所决定,详细研究了O ja动力系统的稳定性问题.对于非正定实对称矩阵最大特征根为零,且至少有一特征根为负的情形,证明了从单位球外出发的解并不一定必然导致有限逸时,完善了O ja模型计算实对称矩阵主特征向量的收敛性结果,数值实验结果进一步验证了理论分析的正确性.     

Dynamic Text Indexing under String Updates

This paper generalizes the dynamic text indexing problem, introduced in [15], to insertion and deletion of strings. The problem is to quickly answer on-line queries about the occurrences of arbitrary pattern strings in a text that may change due to insertion or deletion of strings from it. To treat strings as atomic objects, we provide new sequential techniques and related data structures, which combine the suffix tree with the naming technique used in parallel computation on strings. We also introduce a geometric interpretation of the problem of finding the occurrences of a pattern in a given substring of the text. As a result, the algorithm allows the insertion in the text of a stringSinO(|S| log(n + |S|)) amortized time, and the deletion from the text of a stringSinO(|S| log n) amortized time, wherenis the length of the current text. A pattern search requiresO(p log p + upd ( + log p) + pocc) worst-case time, wherepis the length of the pattern andpoccis the number of its occurrences in the current text, obtained after the execution ofupdupdate operations. This solution requiresO(n² log n) space, which is not initialized.We also provide a technique to reduce the space toO(n log n), yielding a solution that requiresO((p + upd) log p + pocc) query time in the worst-case,O(|S| log^3/2(|S| + n)) amortized time to insert a stringSin, andO(|S| log^3/2n) amortized time to delete a stringSfrom the current text.Furthermore, we use our techniques to solve the novel on-line dynamic tree matching problem that requires the on-line detection of the occurrences of an arbitrary subtree in a forest of ordered labeled trees. The forest may change due to insertion or deletion of subtrees or by renaming of some nodes. Such a problem is solved by a simple reduction to the dynamic text indexing problem.     

Exact Buffer Overflow Calculations for Queues via Martingales

Let _n be the first time a queueing process like the queue length or workload exceeds a level n. For the M/M/1 queue length process, the mean _n and the Laplace transform e^-sn is derived in closed form using a martingale introduced in Kella and Whitt (1992). For workload processes and more general systems like MAP/PH/1, we use a Markov additive extension given in Asmussen and Kella (2000) to derive sets of linear equations determining the same quantities. Numerical illustrations are presented in the framework of M/M/1 and MMPP/M/1 with an application to performance evaluation of telecommunication systems with long-range dependent properties in the packet arrival process. Different approximations that are obtained from asymptotic theory are compared with exact numerical results.     

Buffer Overflow Probabilities for a Markov-Modulated Fluid Model

Markov modulated fluid models are widely used in modelling communications and computer systems. In the AMS (Annick, Mitra, Sohndi) model, heterogeneous, bursty sources modeled by multidimensional Markov processes are superimposed or multiplexed together to drive a fluid buffer. The performance of the system is measured by the steady state probability that the buffer exceeds a high level. The exact solution to this problem derived by AMS requires too much computation to be used on-line. Here we derive an upper bound for the above probability which is fast to compute and accurate enough for practical use.