Search

A similar waveform search plays a crucial role in seismology for detecting seismic events, such as small earthquakes and low-frequency events. However, the high computational costs associated with waveform cross-correlation calculations represent bottlenecks during the analysis of long, continuous records obtained from numerous stations. In this study, we developed a deep-learning network to obtain 64-bit hash codes containing information on seismic waveforms. Using this network, we performed a similar waveform search for ∼35 million moving windows developed for the 30 min waveforms recorded continuously at 10 MHz sampling rates using 16 acoustic emission transducers during a laboratory hydraulic fracturing experiment. The sampling points of each channel corresponded to those of the 5.8-yr records obtained from typical seismic observations at 100 Hz sampling rates. Of the 35 million windows, we searched for windows with small average Hamming distances among the hash codes of 16 channel waveforms against template hash codes of 6057 events that were catalogued using conventional autoprocessing techniques. The calculation of average Hamming distances is 1430–1530 times faster than that of the corresponding network correlation. This hashing-based template matching enabled the detection of 23   462 additional events. We also demonstrated the feasibility of the hashing-based autocorrelation analysis, where similar event pairs were extracted without templates, by calculating the average Hamming distances for all possible pairs of the ∼35 million windows. This calculation required only 15.5 h under 120 thread parallelization. This deep hashing approach significantly reduced the required memory compared with locality-sensitive hashing approaches based on random permutations, enabling similar waveform searching on a large-scale data set. [ABSTRACT FROM AUTHOR]

In this paper we show that the largest possible size of a subset of F q n avoiding right angles, that is, distinct vectors x , y , z such that x − z and y − z are perpendicular to each other is at most O (n q − 2). This improves on the previously best known bound due to Naslund [13] and refutes a conjecture of Ge and Shangguan [11]. A lower bound of n q / 3 is also presented. It is also shown that a subset of F q n avoiding triangles with all right angles can have size at most O (n 2 q − 2). Furthermore, asymptotically tight bounds are given for the largest possible size of a subset A ⊆ F q n for which x − y is not self-orthogonal for any distinct x , y ∈ A. The exact answer is determined for q = 3 and n ≡ 2 (mod 3). Our methods can also be used to bound the maximum possible size of a binary code where no two codewords have Hamming distance divisible by a fixed prime q. Our lower- and upper bounds are asymptotically tight and both are sharp in infinitely many cases. [ABSTRACT FROM AUTHOR]

Multi-view subspace clustering, which partitions multi-view data into their respective underlying subspaces, has achieved the remarkable clustering performance by extracting abundant complementary information from data of different views. However, existing subspace clustering methods almost suffer from very heavy computational burden that restricts their capacity on computational efficiency for large-scale datasets. Recently, hashing/binary code learning has attracted intensive attentions due to fast Hamming distance computation and much less storage requirement, but existing related research does not explore underlying subspace clustering structure well that widely exists in real-world data. In order to handle the both issues, in this paper, we propose a multi-view subspace clustering method named Hashing Multi-view Sparse Subspace Learning (HMSSL). HMSSL incorporates multi-view binary code learning and binary sparse subspace learning with a "thin" dictionary into a unified framework. HMSSL encodes multi-view real-valued features in the original space into compact common binary codes in the Hamming space for fast Hamming distance computation by multi-view binary code learning and learns the binary sparse subspace representation matrix for exploring the underlying subspace clustering structure efficiently and effectively by binary sparse subspace learning with a "thin" dictionary matrix. All the columns of the dictionary matrix are randomly and uniformly sampled from all the columns of the compact common binary code matrix. We design an effective binary optimization algorithm based on alternating direction multiplier method and analyze its time complexity. Extensive experiments performed on six benchmark multi-view datasets demonstrate the effectiveness of HMSSL in comparison with ten state-of-the-art baselines in this field. [ABSTRACT FROM AUTHOR]

We study codes with parameters of $q$ -ary shortened Hamming codes, i.e., $(n=(q^{m}-q)/(q-1), q^{n-m}, 3)_{q}$. Firstly, we prove the fact mentioned in 1998 by Brouwer et al. that such codes are optimal, generalizing it to a bound for multifold packings of radius-1 balls, with a corollary for multiple coverings. In particular, we show that the punctured Hamming code is an optimal $q$ -fold packing with minimum distance 2. Secondly, for every admissible length starting from $n=20$ , we show the existence of 4-ary codes with parameters of shortened 1-perfect codes that cannot be obtained by shortening a 1-perfect code. [ABSTRACT FROM AUTHOR]

Hashing technology can support large-scale recommendation very effectively due to its advantages of low storage cost and high recommendation efficiency. However, existing hashing-based recommendation methods often suffer from item cold-start problem. This is because they simply consider the user-item interaction and the single content information of the items, but the full interaction history is not always available and the single auxiliary information may be missing. To solve this issue, in this paper we propose a Binary Multi-modal Matrix Factorization (BMMF) method. First, we propose an efficient consensus multi-modal mapping to transform the heterogeneous multi-modal features to the unified factors by exploiting the complementarity of multiple modalities. Then, binary matrix factorization is simultaneously performed on the multi-modal features of the items and past user preferences to learn the compact binary codes of the users/items in a common Hamming space. In addition, inspired by the observation that similar instances often have similar binary codes within a short Hamming distance, we formulate a semantic structure regularization term to preserve the similarities of the items during the binary embedding process. Finally, we develop an effective Discrete Coordinate Descent (DCD) approach to tackle the formulated discrete hash optimization problem directly. Experiments on three publicly available real-world datasets demonstrate the superiority of the proposed method against the state-of-the-art methods. Our source codes and testing datasets are available at https://github.com/pcm1217/BMMF. [ABSTRACT FROM AUTHOR]

The image-text cross-modal retrieval task, which aims to retrieve the relevant image from text and vice versa, is now attracting widespread attention. To quickly respond to the large-scale task, we propose an Unsupervised Deep Relative Neighbor Relationship Preserving Cross-Modal Hashing (DRNPH) to achieve cross-modal retrieval in the common Hamming space, which has the advantages of storage and efficiency. To fulfill the nearest neighbor search in the Hamming space, we demand to reconstruct both the original intra- and inter-modal neighbor matrix according to the binary feature vectors. Thus, we can compute the neighbor relationship among different modal samples directly based on the Hamming distances. Furthermore, the cross-modal pair-wise similarity preserving constraint requires the similar sample pair have an identical Hamming distance to the anchor. Therefore, the similar sample pairs own the same binary code, and they have minimal Hamming distances. Unfortunately, the pair-wise similarity preserving constraint may lead to an imbalanced code problem. Therefore, we propose the cross-modal triplet relative similarity preserving constraint, which demands the Hamming distances of similar pairs should be less than those of dissimilar pairs to distinguish the samples' ranking orders in the retrieval results. Moreover, a large similarity marginal can boost the algorithm's noise robustness. We conduct the cross-modal retrieval comparative experiments and ablation study on two public datasets, MIRFlickr and NUS-WIDE, respectively. The experimental results show that DRNPH outperforms the state-of-the-art approaches in various image-text retrieval scenarios, and all three proposed constraints are necessary and effective for boosting cross-modal retrieval performance. [ABSTRACT FROM AUTHOR]

Background: Protein–protein interaction (PPI) is vital for life processes, disease treatment, and drug discovery. The computational prediction of PPI is relatively inexpensive and efficient when compared to traditional wet-lab experiments. Given a new protein, one may wish to find whether the protein has any PPI relationship with other existing proteins. Current computational PPI prediction methods usually compare the new protein to existing proteins one by one in a pairwise manner. This is time consuming. Results: In this work, we propose a more efficient model, called deep hash learning protein-and-protein interaction (DHL-PPI), to predict all-against-all PPI relationships in a database of proteins. First, DHL-PPI encodes a protein sequence into a binary hash code based on deep features extracted from the protein sequences using deep learning techniques. This encoding scheme enables us to turn the PPI discrimination problem into a much simpler searching problem. The binary hash code for a protein sequence can be regarded as a number. Thus, in the pre-screening stage of DHL-PPI, the string matching problem of comparing a protein sequence against a database with M proteins can be transformed into a much more simpler problem: to find a number inside a sorted array of length M. This pre-screening process narrows down the search to a much smaller set of candidate proteins for further confirmation. As a final step, DHL-PPI uses the Hamming distance to verify the final PPI relationship. Conclusions: The experimental results confirmed that DHL-PPI is feasible and effective. Using a dataset with strictly negative PPI examples of four species, DHL-PPI is shown to be superior or competitive when compared to the other state-of-the-art methods in terms of precision, recall or F1 score. Furthermore, in the prediction stage, the proposed DHL-PPI reduced the time complexity from O (M 2) to O (M log M) for performing an all-against-all PPI prediction for a database with M proteins. With the proposed approach, a protein database can be preprocessed and stored for later search using the proposed encoding scheme. This can provide a more efficient way to cope with the rapidly increasing volume of protein datasets. [ABSTRACT FROM AUTHOR]

Hashing has been widely applied to the large-scale approximate nearest neighbor search problem owing to its high efficiency and low storage requirement. Most investigations concentrate on learning hashing methods in a centralized setting. However, in existing big data systems, data is often stored across different nodes. In some situations, data is even collected in a distributed manner. A straightforward way to solve this problem is to aggregate all the data into the fusion center to obtain the search result (aggregating method). However, this strategy is not feasible because of the prohibitive communication cost. Although a few distributed hashing methods have been proposed to reduce this cost, they only focus on designing a distributed algorithm for a specific global optimization objective without considering scalability. Moreover, existing distributed hashing methods aim at finding a distributed solution to hashing, meanwhile avoiding accuracy loss, rather than improving accuracy. To address these challenges, we propose a Scalable Distributed Hashing (SDisH) model in which most existing hashing methods can be extended to process distributed data with no changes. Furthermore, to improve accuracy, we utilize the search radius as a global variable across different nodes to achieve a global optimum search result for every iteration. In addition, a voting algorithm is presented based on the results produced by multiple iterations to further reduce search errors. Theoretical analyses of communication, computation, and accuracy demonstrate the superiority of the proposed model. Numerical simulations on three large-scale and two relatively small benchmark datasets also show that the SDisH model achieves up to 44.75% and 10.23% accuracy gains compared to the aggregating method and state-of-the-art distributed hashing methods, respectively. [ABSTRACT FROM AUTHOR]

Recommendation efficiency and data sparsity problems have been regarded as two challenges of improving performance for online recommendation. Most of the previous related work focus on improving recommendation accuracy instead of efficiency. In this paper, we propose a Deep Pairwise Hashing (DPH) to map users and items to binary vectors in Hamming space, where a user's preference for an item can be efficiently calculated by Hamming distance, which significantly improves the efficiency of online recommendation. To alleviate data sparsity and cold-start problems, the user-item interactive information and item content information are unified to learn effective representations of items and users. Specifically, we first pre-train robust item representation from item content data by a Denoising Auto-encoder instead of other deterministic deep learning frameworks; then we finetune the entire framework by adding a pairwise loss objective with discrete constraints; moreover, DPH aims to minimize a pairwise ranking loss that is consistent with the ultimate goal of recommendation. Finally, we adopt the alternating optimization method to optimize the proposed model with discrete constraints. Extensive experiments on three different datasets show that DPH can significantly advance the state-of-the-art frameworks regarding data sparsity and item cold-start recommendation. [ABSTRACT FROM AUTHOR]

Approximate Nearest Neighbor(ANN) search is the core problem in many large-scale machine learning and computer vision applications such as multimodal retrieval. Hashing is becoming increasingly popular, since it can provide efficient similarity search and compact data representations suitable for handling such large-scale ANN search problems. Most hashing algorithms concentrate on learning more effective projection functions. However, the accuracy loss in the quantization step has been ignored and barely studied. In this paper, we analyse the importance of various projected dimensions, distribute them into several groups and quantize them with two types of values which can both better preserve the neighborhood structure among data. One is Variable Integer-based Quantization (VIQ) that quantizes each projected dimension with integer values. The other is Variable Codebook-based Quantization (VCQ) that quantizes each projected dimension with corresponding codebook values. We conduct experiments on five common public data sets containing up to one million vectors. The results show that the proposed VCQ and VIQ algorithms can both achieve much higher accuracy than state-of-the-art quantization methods. Furthermore, although VCQ performs better than VIQ, ANN search with VIQ provides much higher search efficiency. [ABSTRACT FROM AUTHOR]

The core of cross-modal hashing methods is to map high dimensional features into binary hash codes, which can then efficiently utilize the Hamming distance metric to enhance retrieval efficiency. Recent development emphasizes the advantages of the unsupervised cross-modal hashing technique, since it only relies on relevant information of the paired data, making it more applicable to real-world applications. However, two problems, that is intro-modality correlation and inter-modality correlation, still have not been fully considered. Intra-modality correlation describes the complex overall concept of a single modality and provides semantic relevance for retrieval tasks, while inter-modality correction refers to the relationship between different modalities. From our observation and hypothesis, the dependency relationship within the modality and between different modalities can be constructed at the object level, which can further improve cross-modal hashing retrieval accuracy. To this end, we propose a Visual-textful Correlation Graph Hashing (OVCGH) approach to mine the fine-grained object-level similarity in cross-modal data while suppressing noise interference. Specifically, a novel intra-modality correlation graph is designed to learn graph-level representations of different modalities, obtaining the dependency relationship of the image region to image region and the tag to tag in an unsupervised manner. Then, we design a visual-text dependency building module that can capture correlation semantic information between different modalities by modeling the dependency relationship between image object region and text tag. Extensive experiments on two widely used datasets verify the effectiveness of our proposed approach. [ABSTRACT FROM AUTHOR]

Diameter perfect codes form a natural generalization for perfect codes. They are based on the code-anticode bound which generalizes the sphere-packing bound. The code-anticode bound was proved by Delsarte for distance-regular graphs and it holds for some other metrics too. In this paper we prove the bound for non-binary constant-weight codes with the Hamming metric and characterize the diameter perfect codes and the maximum size anticodes for these codes. We distinguish between six families of non-binary diameter constant-weight codes and four families of maximum size non-binary constant-weight anticodes. Each one of these families of diameter perfect codes raises some different questions. We consider some of these questions and leave lot of ground for further research. Finally, as a consequence, some $t$ -intersecting families related to the well-known Erdös-Ko-Rado theorem, are constructed. [ABSTRACT FROM AUTHOR]

Let A (n , d) be the size of the maximum binary code of length n and minimum Hamming distance d. A (n , d , w) is defined similarly for binary code with constant weight w. Obviously, finding the value of A (n , d) is equivalent to finding the maximum independent set of the d − 1 th-power of n -dimensional hypercube. Based on this, this paper obtains that A (3 m , 2 m) = 4 , A (m (m + 1) 2 , 2 m − 2 , m) = m + 1 , A (2 m + 1 − 2 , 2 m − 1) = 2 m + 1 , and explores the structure of the maximum code of length 2 m + 2 and minimum Hamming distance 2 m + 1 , where m is an integer. [ABSTRACT FROM AUTHOR]

A fundamental problem in coding theory is to find the values of A (n , d) , i.e., the A (n , d) is the size of the maximum binary code set of length n and minimum Hamming distance d. And A (n , d) can also be viewed as the size of maximum independent set of d − 1 t h -power of the n -dimensional hypercube Q n. In order to further understand and study this problem, we study the distribution of the maximum clique and the structure of the point of Q n d for d ≤ 5. [ABSTRACT FROM AUTHOR]

Image representation and approximate query is always a research challenge and is affected greatly by the dimension and size of images. Since hash-based methods and binary encodings in combination with other techniques, such as kernel tricks, a longer binary code and mapping vectors rotation, can maintain a linear query time and query accuracy, they have been used in this area broadly. This paper develops principal component analysis hashing (PCAH) and unequal length of binary coding to divide images into more categories, denoted as PCA-MD, to improve accuracy of the representation and lookup of images. This paper firstly proves that the eigenvector mapping is locality sensitive, which is the basis for more classes division. For the anisotropy of the eigenvectors, PCA-MD utilizes an unequal length of binary coding and fewer eigenvectors, rather than an equal code, to divide the images mapped on every eigenvector to more categories. Moreover, L1-norm distance is applied to measure the distances of images to avoid the enormous computation of Euclidean distance. Theoretical analysis and extensive experimental results demonstrate that the PCA-MD has a higher query performance and a slight longer run time than the state-of-the-art approaches based on the Hamming distance. This in turn verifies that PCAH is a locality sensitive hash and that partitioning into more categories rather than only two categories is reasonable. [ABSTRACT FROM AUTHOR]

Hashing methods have been widely used in Approximate Nearest Neighbor (ANN) search for big data due to low storage requirements and high search efficiency. These methods usually map the ANN search for big data into the $k$ -Nearest Neighbor ($k$ NN) search problem in Hamming space. However, Hamming distance calculation ignores the bit-level distinction, leading to confusing ranking. In order to further increase search accuracy, various bit-level weights have been proposed to rank hash codes in weighted Hamming space. Nevertheless, existing ranking methods in weighted Hamming space are almost based on exhaustive linear scan, which is time consuming and not suitable for large datasets. Although Multi-Index hashing that is a sub-linear search method has been proposed, it relies on Hamming distance rather than weighted Hamming distance. To address this issue, we propose an exact $k$ NN search approach with Multiple Tables in Weighted Hamming space named WHMT, in which the distribution of bit-level weights is incorporated into the multi-index building. By WHMT, we can get the optimal candidate set for exact $k$ NN search in weighted Hamming space without exhaustive linear scan. Experimental results show that WHMT can achieve dramatic speedup up to 69.8 times over linear scan baseline without losing accuracy in weighted Hamming space. [ABSTRACT FROM AUTHOR]

An additive quaternary [n,k,d]-code (length n, quaternary dimension k, minimum distance d) is a 2k-dimensional F2-vector space of n-tuples with entries in F2 ⊕ F2 (the 2-dimensional vector space over F2) with minimum Hamming distance d. We determine the optimal parameters of additive quaternary codes of dimension k ≤ 3. The most challenging case is dimension k = 2.5. We prove that an additive quaternary [n,2.5,d]-code where d < n−1 exists if and only if 3(n−d) ≥ ⌈d/2⌉ + ⌈d/4⌉ + ⌈d/8⌉. In particular, we construct new optimal 2.5-dimensional additive quaternary codes. As a by-product, we give a direct proof for the fact that a binary linear [3m,5,2e]2-code for e < m−1 exists if and only if the Griesmer bound 3(m−e) ≥e/2⌉ + ⌈e/4⌉ + ⌈e/8⌉ is satisfied. [ABSTRACT FROM AUTHOR]

Content-based histopathology image retrieval can be a useful technique for help in diagnosing various diseases. The process of retrieving images is often time-consuming and challenging due to the need for high-dimensional features when trying to model complex content. Hashing methods can therefore be employed to resolve the challenge by producing binary codes of different lengths. Deep hashing methods are frequently superior to traditional machine learning approaches but are affected by the size of training sets. In addition, back-propagation learning can further complicate the generation of binary values. Hence, this paper proposes a novel Siamese deep hashing model, named histopathology Siamese deep hashing (HSDH), for histopathology image retrieval. Two designed deep hashing models with shared weights and structures are used to generate hash codes. A Hamming distance layer is then applied to evaluate the similarity of the generated values. A highly effective loss function is also introduced that incorporates a modified version of the standard contrastive loss function with an error estimation term to improve both the training and retrieval phases. In the retrieval phase, the trained model compares a query image with all the training images and ranks the most similar images. According to the experimental results on two publicly available databases, BreakHis and Kather, the HSDH model outperforms other state-of-the-art hashing-based methods in histopathology image retrieval. [ABSTRACT FROM AUTHOR]

• To learn compact codes, we force mapping matrix of each view to orthogonalize. • A binary graph structure is embedded into one-step binary multi-view clustering. • An effective solving algorithm based on ADM is proposed for the above model. • Empirical experimental results illustrate that the effectiveness of the method. The multi-view clustering problem has attracted considerable attention over recent years for the remarkable clustering performance due to exploiting complementary information from multiple views. Most existing related research work processes data in the decimal real value space that is not the most compatible space for computers. Binary code learning, also known as hashing technology, is well-known for fast Hamming distance computation, less storage requirement and accurate calculation results. The Hamming space is most enjoyed by computers because of binary/hash codes. Several studies combine multi-view clustering with binary code learning for improving clustering performance. However, there is much redundant information contained in the learned binary codes, which negatively affects the clustering performance, but these studies ignore eliminating redundant information for learning compact codes. In addition, they don't give a unified (one-step) clustering framework with binary graph structure, which doesn't lead to the optimal clustering result due to the information loss during the two-step process. In this paper, to cope with the two issues, we propose an orthogonal mapping binary graph method (OMBG) for the multi-view clustering problem, which makes the mapping matrix of every view orthogonalize for eliminating redundant information and embeds a binary graph structure into the unified binary multi-view clustering framework for extracting local geometric structure information of binary codes and achieving the optimal clustering result. Furthermore, we design an effective optimization algorithm based on alternating direction minimization to solve the model of OMBG. Extensive experiments performed on four frequently-used benchmark multi-view datasets illustrate the superiority of OMBG which is compared with some state-of-the-art clustering baselines. [ABSTRACT FROM AUTHOR]

• A novel center-based deep supervised hashing framework integrating hashing learning and class centers learning for discriminative face image retrieval. • Cluster intra-class samples into a learnable class center for intra-class variance reduction. • Enlarge the Hamming distance between pairwise class centers for inter-class separability. • Regression matrix to enhance binary codes compactness. • State-of-the-art performance on four large-scale datasets under various code lengths and commonly-used evaluation metrics. With the advantages of low storage cost and extremely fast retrieval speed, deep hashing methods have attracted much attention for image retrieval recently. However, large-scale face image retrieval with significant intra-class variations is still challenging. Neither existing pairwise/triplet labels-based nor softmax classification loss-based deep hashing works can generate compact and discriminative binary codes. Considering these issues, we propose a center-based framework integrating end-to-end hashing learning and class centers learning simultaneously. The framework minimizes the intra-class variance by clustering intra-class samples into a learnable class center. To strengthen inter-class separability, it additionally imposes a novel regularization term to enlarge the Hamming distance between pairwise class centers. Moreover, a simple yet effective regression matrix is introduced to encourage intra-class samples to generate the same binary codes, which further enhances the hashing codes compactness. Experiments on four large-scale datasets show the proposed method outperforms state-of-the-art baselines under various code lengths and commonly-used evaluation metrics. [ABSTRACT FROM AUTHOR]