Search

We introduce a generalization of the concepts of coverings and packings in Hamming space called weighted coverings and packings. We study the existence of perfect weighted codes, discuss connections between weighted coverings and packings, and present many constructions for them. Conventional packings and coverings are arrangements of Hamming spheres of a given radius in the Hamming space. We generalize these concepts by attaching weights to different layers of the Hamming sphere. If several such spheres intersect in a point of the space we define the density at that point as the sum of the weights of the corresponding layers. We study the general problem of weighted packings (coverings) for which the density at each point is at most one (resp. at least one). We can consider several known types of codes, e.g., the uniformly packed codes, list codes, multiple coverings, L-codes, in a uniform way. >

For a Hamming space (/spl Xscr//sub /spl alpha///sup n/,d/sub H/), the set of n-length words over the alphabet /spl Xscr//sub /spl alpha//={0,1,...,/spl alpha/-1} endowed with the distance d/sub H/, which for two words x/sup n/=(x/sub 1/,...,x/sup n/), y/sup n/=(y/sub 1/,...,y/sub n/)/spl isin//spl Xscr//sub /spl alpha///sup n/ counts the number of different components, we determine the maximal cardinality of subsets with a prescribed diameter d or, in another language, anticodes with distance d. We refer to the result as diametric theorem.

We obtain the upper bound on the probability of undetected error which is valid uniformly on choosing the probability of the symbol inversion. This bound is better than previous known bounds. The Hamming space of binary sequences is considered.

Sequence nearest neighbors problemc an be defined as follows. Given a database D of n sequences, preprocess D so that given any query sequence Q, one can quickly find a sequence S in D for which d(S,Q) ? d(S, T) for any other sequence T in D. Here d(S,Q) denotes the "distance" between sequences S and Q, which can be defined as the minimum number of "edit operations" to transform one sequence into the other. The edit operations considered in this paper include single character edits (insertions, deletions, replacements) as well as block (substring) edits (copying, uncopying and relocating blocks).One of the main application domains for the sequence nearest neighbors problem is computational genomics where available tools for sequence comparison and search usually focus on edit operations involving single characters only. While such tools are useful for capturing certain evolutionary mechanisms (mainly point mutations), they may have limited applicability for understanding mechanisms for segmental rearrangements (duplications, translocations and deletions) underlying genome evolution. Recent improvements towards the resolution of the human genome composition suggest that such segmental rearrangements are much more common than what was estimated before. Thus there is substantial need for incorporating similarity measures that capture block edit operations in genomic sequence comparison and search. Unfortunately even the computation of a block edit distance between two sequences under any set of non-trivial edit operations is NP-hard.The first efficient data structure for approximate sequence nearest neighbor search for any set of non-trivial edit operations were described in [11]; the measure considered in this paper is the block edit distance. This method achieves a preprocessing time and space polynomial in size of D and query time near-linear in size of Q by allowing an approximate factor of O(logl(log* l)2). The approach involves embedding sequences into Hamming space so that approximating Hamming distances estimates sequence block edit distances within the approximation ratio above.In this study we focus on simplification and experimental evaluation of the [11] method. We first describe how we implement and test the accuracy of the transformations provided in [11] in terms of estimating the block edit distance under controlled data sets. Then, based on the hamming distance estimator described in [3] we present a data structure for computing approximate nearest neighbors in hamming space; this is simpler than the well-known ones in [9,6]. We finally report on how well the combined data structure performs for sequence nearest neighbor search under block edit distance.

Set value attributes are a concise and natural way to model complex data sets. Modern Object Relational systems support set value attributes and allow various query capabilities on them. In this paper we initiate a formal study of indexing techniques for set value attributes based on similarity, for suitably defined notions of similarity between sets. Such techniques are necessary in modern applications such as recommendations through collaborative filtering and automated advertising. Our techniques are probabilistic and approximate in nature. As a design principle we create structures that make use of well known and widely used data structuring techniques, as a means to ease integration with existing infrastructure.We show how the problem of indexing a collection of sets based on similarity can be reduced to the problem of indexing suitably encoded (in a way that preserves similarity) binary vectors in Hamming space thus, reducing the problem to one of similarity query processing in Hamming space. Then, we introduce and analyze two data structure primitives that we use in cooperation to perform similarity query processing in a Hamming space. We show how the resulting indexing technique can be optimized for properties of interest by formulating constraint optimization problems based on the space one is willing to devote for indexing. Finally we present experimental results from a prototype implementation of our techniques using real life datasets exploring the accuracy and efficiency of our overall approach as well as the quality of our solutions to problems related to the optimization of the indexing scheme.

In this paper the problem for the improvement of the Delsarte bound for Τ-designs in finite polynomial metric spaces is investigated. First we distinguish the two cases of the Hamming and Johnson Q- polynomial metric spaces and give exact intervals, when the Delsarte bound is possible to be improved. Secondly, we derive new bounds for these cases. Analytical forms of the extremal polynomials of degree Τ + 2 for non-antipodal PMS and of degree Τ + 3 for antipodal PMS are given. The new bound is investigated in the following asymptotical process: in Hamming space when Τ and n grow simultaneously to infinity in a proportional manner and in Johnson space when Τ, w and n grow simultaneously to infinity in a proportional manner. In both cases, the new bound has better asymptotical behavior then the Delsarte bound.

We study the possibilities for attaining the best known universal linear programming bounds on the cardinality of codes in polynomial metric spaces (finite or infinite). We show that in many cases these bounds cannot be attained. Applications in different antipodal polynomial metric spaces are considered with special emphasis on the Euclidean sphere and the binary Hamming space.

It is proved that for noncan the Hamming space {0, 1}nbe partitioned into three Hamming spheres of any, not necessarily equal radii. This fact is remarkable, since for everyk≠3 there exist values ofnfor which then-dimensional Hamming space can be partitioned intokspheres.

Self-complementary codes in the Hamming space, i.e., binary codes that together with any vector contain its complement, are considered. The bound on the size of a self-complementary code with a given minimum distance d presented here is in general better than the corresponding bound for arbitrary binary codes in the Hamming space. Some applications of this bound for estimating the minimum distance of self-dual binary codes, the cross-correlation of arbitrary binary codes, the modulus of sums of Legendre symbols of polynomials, and some parameters of randomness properties of binary codes, are given.

A description is given of the scatter code, a new technique for mapping sensor data into a form suitable for processing by associative neural networks. By overthrowing the assumption that the sensor mapping must preserve order in addition to closeness, a mapping can be generated that has much more capacity and flexibility than previous mappings. The first advantage is the practically limitless number of points in the new mapping, which eliminates the need to compress sensor information and lose resolution. The second advantage is the ability to control the radius of association in the mapped sensor data by varying the rate at which points in the Hamming space become orthogonal. The radius of association can be varied within the mapping to take advantage of special cases when information about the sensor or about the expected data point is known

In this paper, we present some new results on the thinnest coverings that can be obtained in Hamming or Euclidean spaces if spheres and ellipsoids are covered with balls of some radius e. In particular, we tighten the bounds currently known for the e-entropy of Hamming spheres of an arbitrary radius r. New bounds for the e-entropy of Hamming balls are also derived. If both parameters e and r are linear in dimension n, then the upper bounds exceed the lower ones by an additive term of order logn. We also present the uniform bounds valid for all values of e and r. In the second part of the paper, new sufficient conditions are obtained, which allow one to verify the validity of the asymptotic formula for the size of an ellipsoid in a Hamming space. Finally, we survey recent results concerning coverings of ellipsoids in Hamming and Euclidean spaces.

The group of automorphisms of a Hamming space is determined. Self dual codes over odd characteristic finite field with respect to bilinear forms are treated. Under the subgroup of the monomial group preserving the inner product, we classify the maximal self dual codes overGF(5) with respect to the inner product of dimension ≤8. The Hamming Weight distribution and the order of the automorphism of the code are given.

This article is a study of the solution set of a discrete isoperimetric problem.Bibliography: 7 titles.

Codes for strong identification are considered. The motivation for these codes comes from locating faulty processors in a multiprocessor system. Constructions and lower bounds on these codes are given. In particular, we provide two infinite families of optimal strongly identifying codes, which can locate up to two malfunctioning processors in a binary hypercube.

We obtain the asymptotic lower bound for the rate of fixed size multiple packing.

The original motivation for identifying codes comes from fault diagnosis in multiprocessor systems. Currently, the subject forms a topic of its own with several possible applications, for example, to sensor networks. In this paper, we concentrate on identification in binary Hamming spaces. We give a new lower bound on the cardinality of r-identifying codes when r>=2. Moreover, by a computational method, we show that M"1(6)=19. It is also shown, using a non-constructive approach, that there exist asymptotically good (r,@?@?)-identifying codes for fixed @?>=2. In order to construct (r,@?@?)-identifying codes, we prove that a direct sum of r codes that are (1,@?@?)-identifying is an (r,@?@?)-identifying code for @?>=2.

We consider the n-dimensional ternary Hamming space, T n = {0, 1, 2} n , and say that a subset L ⊂ T n of three points form a line if they have exactly n - 1 components in common. A subset of T n is called closed if, whenever it contains two points of a line, it contains also the third one. Finally, a generator is a subset, whose closure, the smallest closed set containing it, is T n . In this paper, we investigate several combinatorial properties of closed sets and generators, including the size of generators, and the complexity of generation. The present study was motivated by the problem of storing efficiently origin-destination matrices in transportation systems.

For doubly-extended Reed-Solomon codes over GF( q ) with minimum distance d the covering radius ϱ is either d − 1 or d − 2. For 3⩽ d ⩽ q , it is proved that ϱ = d − 2 if and only if the ( q +1)-arc consisting of the points of a normal rational curve in PG ( d − 2, q ) is complete. For ϱ = d − 1 a characterization of the deep holes of the sphere packing in Hamming space defined by the code is given in terms of their syndromes.

We show that if the collection of all binary vectors of lengthnis partitioned intokspheres, then eitherk⩽2 ork⩾n+2. Moreover, such partitions withk=n+2 are essentially unique.

Let @?, n and r be positive integers. Define F^n={0,1}^n. The Hamming distance between words x and y of F^n is denoted by d(x,y). The ball of radius r is defined as B"r(X)={y@?F^n|@?x@?X:d(x,y)@?r}, where X is a subset of F^n. A code C@?F^n is called (r,@?@?)-identifying if for all X,Y@?F^n such that |X|@?@?, |Y|@?@? and X Y, the sets B"r(X)@?C and B"r(Y)@?C are different. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. In this paper, we present various results concerning (r,@?@?)-identifying codes in the Hamming space F^n. First we concentrate on improving the lower bounds on (r,@?1)-identifying codes for r>1. Then we proceed by introducing new lower bounds on (r,@?@?)-identifying codes with @?>=2. We also prove that (r,@?@?)-identifying codes can be constructed from known ones using a suitable direct sum when @?>=2. Constructions for (r,@?2)-identifying codes with the best known cardinalities are also given.

We present a class of binary (not necessarily linear) codes containing perfect codes, Preparata codes, BCH codes of lengtht 22m+1-1, Hadamard code of length 11, l-error-correcting uniformly packed codes and also some other classes presenting remarkable regularity properties. The points of a code C of order 3 are scattered in the ambiant Hamming space so that for any point x the number of paths of length 3 joining x to the code only depends on the fact that the Hamming distance d(x, C) from x to C is 0, 1 or is greater than 1.

We provide evidence for the following conjecture: a minimal covering of the binary Hamming space F 2 n+2 by spheres of radius t+1 has at most the same cardinality as a minimal covering of F 2 n by spheres of radius t.

Locating faulty processors in a multiprocessor system gives the motivation for locating-dominating codes. We consider these codes in binary hypercubes and generalize the concept for the situation in which we want to locate more than one malfunctioning processor.

We study partitions of the space $\F{n}$ of all the binary $n$-tuples into disjoint sets, where each set is an additive coset of a given set $V$. Such a partition is called a tiling of $\F{n}$ and denoted $(V,A)$, where $A$ is the set of coset representatives. We give a sufficient condition for a set $V$ to be a tile in terms of the cardinality of $V\!+\!V$. We then employ this condition to classify all tilings with sets of small cardinality. Further, periodicity of tilings in $\F{n}$ is discussed, and a simple construction of nonperiodic tilings of $\F{n}$ is presented for all $n \ge 6$. It is also shown that the nonperiodic tiling of $\F{6}$ is unique. A tiling $(V,A)$ is said to be proper if $V$ generates $\F{n}$; it is said to be full rank if both $V$ and $A$ generate $\F{n}$. We show that, in general, the classification of tilings can be reduced to the study of proper tilings. We then prove that any %proper tiling may be decomposed into smaller tilings that are either trivial or have full rank. Existence of full-rank tilings is exhibited by showing that each tiling is uniquely associated with a perfect binary code. Moreover, it is shown that periodic full-rank tilings may be further decomposed into smaller tilings, and then the existence of nonperiodic full-rank tilings is deduced. Finally, we generalize the well-known Lloyd theorem, originally stated for tilings by spheres, for the case of arbitrary tilings.

Due to its low storage cost and fast query speed, hashing has been recognized to accomplish similarity search in large-scale multimedia retrieval applications. Particularly supervised hashing has recently received considerable research attention by leveraging the label information to preserve the pairwise similarities of data points in the Hamming space. However, there still remain two crucial bottlenecks: 1) the learning process of the full pairwise similarity preservation is computationally unaffordable and unscalable to deal with big data; 2) the available category information of data are not well-explored to learn discriminative hash functions. To overcome these challenges, we propose a unified Semantic-Aware DIscrete Hashing (SADIH) framework, which aims to directly embed the transformed semantic information into the asymmetric similarity approximation and discriminative hashing function learning. Specifically, a semantic-aware latent embedding is introduced to asymmetrically preserve the full pairwise similarities while skillfully handle the cumbersome n times n pairwise similarity matrix. Meanwhile, a semantic-aware autoencoder is developed to jointly preserve the data structures in the discriminative latent semantic space and perform data reconstruction. Moreover, an efficient alternating optimization algorithm is proposed to solve the resulting discrete optimization problem. Extensive experimental results on multiple large-scale datasets demonstrate that our SADIH can clearly outperform the state-of-the-art baselines with the additional benefit of lower computational costs., Accepted by The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)

SIFT-like local feature descriptors are ubiquitously employed in such computer vision applications as content-based retrieval, video analysis, copy detection, object recognition, photo-tourism and 3D reconstruction. Feature descriptors can be designed to be invariant to certain classes of photometric and geometric transformations, in particular, affine and intensity scale transformations. However, real transformations that an image can undergo can only be approximately modeled in this way, and thus most descriptors are only approximately invariant in practice. Secondly, descriptors are usually high-dimensional (e.g. SIFT is represented as a 128-dimensional vector). In large-scale retrieval and matching problems, this can pose challenges in storing and retrieving descriptor data. We map the descriptor vectors into the Hamming space, in which the Hamming metric is used to compare the resulting representations. This way, we reduce the size of the descriptors by representing them as short binary strings and learn descriptor invariance from examples. We show extensive experimental validation, demonstrating the advantage of the proposed approach.