Search

Hashing is a useful technique for fast nearest neighbor search due to its low storage cost and fast query speed. Unsupervised hashing aims at learning binary hash codes for the original features so that the pairwise distances can be best preserved. While several works have targeted on this task, the results are not satisfactory mainly due to the over-simplified model. In this paper, we propose a unified and concise unsupervised hashing framework, called binary multidimensional scaling , which is able to learn the hash code for distance preservation in both batch and online mode. In the batch mode, unlike most existing hashing methods, we do not need to simplify the model by predefining the form of hash map. Instead, we learn the binary codes directly based on the pairwise distances among the normalized original features by alternating minimization. This enables a stronger expressive power of the hash map. In the online mode, we consider the holistic distance relationship between current query example and those we have already learned, rather than only focusing on current data chunk. It is useful when the data come in a streaming fashion. Empirical results show that while being efficient for training, our algorithm outperforms state-of-the-art methods by a large margin in terms of distance preservation, which is practical for real-world applications.

Hashing-based methods have been widely applied in large scale image retrieval problem due to its high efficiency. In real world applications, it is difficult to require all images in a large database being labeled while unsupervised methods waste information from labeled images. Therefore, semi-supervised hashing methods are proposed to use partially labeled database to train hash functions using both the semantic and the unsupervised information. Multi-hashing methods achieve better precision-recall in comparison to single hashing method. However, current boosting-based multi-hashing methods do not improve performance after a small number of hash tables are created. Therefore, a bagging–boosting-based semi-supervised multi-hashing with query-adaptive re-ranking (BBSHR) is proposed in this paper. In the proposed method, an individual hash table of multi-hashing is trained using the boosting-based BSPLH, such that each hash bit corrects errors made by previous bits. Moreover, we propose a new semi-supervised weighting scheme for the query-adaptive re-ranking. Experimental results show that the proposed method yields better precision and recall rates for given numbers of hash tables and bits.

International audience; Boosted by recent legislations, data anonymizationis fast becoming a norm. However, as of yet no generic solutionhas been found to safely release data. As a consequence, datacustodians often resort to ad-hoc means to anonymize datasets.Both past and current practices indicate that hashing is oftenbelieved to be an effective way to anonymize data. Unfortunately,in practice it is only rarely effective. This paper is a tutorialto explain the limits of cryptographic hash functions as ananonymization technique. Anonymity set is the best privacymodel that can be achieved by hash functions. However, thismodel has several shortcomings. We provide three case studiesto illustrate how hashing only yields a weakly anonymized data.The case studies include MAC and email address anonymizationas well as the analysis of Google Safe Browsing.Boosted by recent legislations, data anonymizationis fast becoming a norm. However, as of yet no generic solutionhas been found to safely release data. As a consequence, datacustodians often resort to ad-hoc means to anonymize datasets.Both past and current practices indicate that hashing is oftenbelieved to be an effective way to anonymize data. Unfortunately,in practice it is only rarely effective. This paper is a tutorialto explain the limits of cryptographic hash functions as ananonymization technique. Anonymity set is the best privacymodel that can be achieved by hash functions. However, thismodel has several shortcomings. We provide three case studiesto illustrate how hashing only yields a weakly anonymized data.The case studies include MAC and email address anonymizationas well as the analysis of Google Safe Browsing.

When executing a program or storing data in a medical Internet of Things (mIoT) system, physical side-channels analysis, such as recent-timing, cold-reboot, and virtual-machine attacks, might obtain partial information about internal sensitive medical data/states in memory that the attacker can gain partial privacy information. Leakage-resilient cryptography has led to better implementation of many cryptographic primitives that can be proven secure against attackers who can obtain limited sensitive information about private keys , randomness , and other internal states , and therefore prevents from breaking the security. In this paper, to tolerate the sensitive information leakage in mIoT, we first present a leakage-resilient public-key encryption mechanism that is semantically secure against adaptively chosen-ciphertext attacks in the presence of key leakage under standard decisional Diffie–Hellman assumption. Our construction employs a special universal hashing in multiplicative group to provide an efficient strong extractor, and a key derivation function to derive one or more symmetric keys from a single value. Also, the plaintext space of the scheme is extended to the full domain field of group so as to provide a larger space for the message. We emphasis that our scheme can be deployed in mIoT since the limited power and energy budgets, the communication and computation cost, and the leakage attack are taken into account. Using the first scheme as a building block, we also give a protocol construction to achieve the security resilient to randomness leakage and key leakage. Our schemes feature with a shorter key size and a larger plaintext space. Concretely, the private-key contains only four elements in the finite field, and the allowable key-leakage rate is 25%, which provides a higher leakage rate than Naor Segev (leakage rate is 16.7%) and its variants. It is worth highlighting of the construction resilient to both key leakage and randomness leakage, simultaneously, and is flexible to deploy in easy-to-attack outdoor nodes such as in medical IoT and smart grids, since in these nodes the private keys and randomness are either stored or generated in outdoor privacy-aware environments.

Weights on the edges of a graph can show interactions among members of a social network, emails exchanged in any organization, and traffic flow on roads. However, mining hidden patterns is difficult when the size of the graph is large. Creating a compact summary is useful if it preserves the structural and edge weight information of its underlying graph. Existing work in this context provides a pairwise compression strategy to create a summary whose decompressed version has minimum difference in edge weights compared to its initial state. The resultant summary graph is compact, but the solution has quadratic time complexity due to exhaustive pairwise searching. Therefore, we present a set-based summarization approach that aggregates sets of nodes. We avoid explicit similarity computations and directly identify the required sets via Locality Sensitive Hashing (LSH). LSH accelerates the summarization process, but its hashing scheme cannot consider the edge weights. Considering the edge weight during hashing is necessary when the objective of the required summary is altered to a personalized view. Hence, we propose a non-parametric hashing scheme for LSH to generate candidate similar nodes from the weighted neighborhood of each node. We perform comparisons with state-of-the-art solutions and obtain better results using various experimental criteria.

Due to the significant reduction in computational cost and storage, hashing techniques have gained increasing interests in facilitating large-scale cross-view retrieval tasks. Most cross-view hashing methods are developed by assuming that data from different views are well paired, e.g., text-image pairs. In real-world applications, however, this fully-paired multiview setting may not be practical. The more practical yet challenging semi-paired cross-view retrieval problem, where pairwise correspondences are only partially provided, has less been studied. In this paper, we propose an unsupervised hashing method for semi-paired cross-view retrieval, dubbed semi-paired discrete hashing (SPDH). In specific, SPDH explores the underlying structure of the constructed common latent subspace, where both paired and unpaired samples are well aligned. To effectively preserve the similarities of semi-paired data in the latent subspace, we construct the cross-view similarity graph with the help of anchor data pairs. SPDH jointly learns the latent features and hash codes with a factorization-based coding scheme. For the formulated objective function, we devise an efficient alternating optimization algorithm, where the key binary code learning problem is solved in a bit-by-bit manner with each bit generated with a closed-form solution. The proposed method is extensively evaluated on four benchmark datasets with both fully-paired and semi-paired settings and the results demonstrate the superiority of SPDH over several other state-of-the-art methods in term of both accuracy and scalability.

Hashing compresses high-dimensional features into compact binary codes. It is one of the promising techniques to support efficient mobile image retrieval, due to its low data transmission cost and fast retrieval response. However, most of existing hashing strategies simply rely on low-level features. Thus, they may generate hashing codes with limited discriminative capability. Moreover, many of them fail to exploit complex and high-order semantic correlations that inherently exist among images. Motivated by these observations, we propose a novel unsupervised hashing scheme, called topic hypergraph hashing (THH), to address the limitations. THH effectively mitigates the semantic shortage of hashing codes by exploiting auxiliary texts around images. In our method, relations between images and semantic topics are first discovered via robust collective non-negative matrix factorization. Afterwards, a unified topic hypergraph, where images and topics are represented with independent vertices and hyperedges, respectively, is constructed to model inherent high-order semantic correlations of images. Finally, hashing codes and functions are learned by simultaneously enforcing semantic consistence and preserving the discovered semantic relations. Experiments on publicly available datasets demonstrate that THH can achieve superior performance compared with several state-of-the-art methods, and it is more suitable for mobile image retrieval.

Hashing has been attracting much attention in computer vision recently, since it can provide efficient similarity comparison in massive multimedia databases with fast query speed and low storage cost. Since the distance metric is an explicit description of similarity, in this paper, a novel hashing method is proposed for image retrieval, dubbed Isometric Hashing (IH). IH aims to minimize the difference between the distance in input space and the distance of the corresponding binary codes. To tackle the discrete optimization in a computationally tractable manner, IH adopts some mathematical tricks to transform the original problem into a multi-objective optimization problem. The usage of linear-projection-based hash functions enables efficient generating hash codes for unseen data points. Furthermore, utilizing different distance metrics could produce corresponding hashing algorithms, thus IH can be seen as a framework for developing new hashing methods. Extensive experiments performed on four benchmark datasets validate that IH can achieve comparable to or even better results than some state-of-the-art hashing methods.

To overcome the barrier of storage and computation when dealing with gigantic-scale data sets, compact hashing has been studied extensively to approximate the nearest neighbor search. Despite the recent advances, critical design issues remain open in how to select the right features, hashing algorithms, and/or parameter settings. In this paper, we address these by posing an optimal hash bit selection problem, in which an optimal subset of hash bits are selected from a pool of candidate bits generated by different features, algorithms, or parameters. Inspired by the optimization criteria used in existing hashing algorithms, we adopt the bit reliability and their complementarity as the selection criteria that can be carefully tailored for hashing performance in different tasks. Then, the bit selection solution is discovered by finding the best tradeoff between search accuracy and time using a modified dynamic programming method. To further reduce the computational complexity, we employ the pairwise relationship among hash bits to approximate the high-order independence property, and formulate it as an efficient quadratic programming method that is theoretically equivalent to the normalized dominant set problem in a vertex- and edge-weighted graph. Extensive large-scale experiments have been conducted under several important application scenarios of hash techniques, where our bit selection framework can achieve superior performance over both the naive selection methods and the state-of-the-art hashing algorithms, with significant accuracy gains ranging from 10% to 50%, relatively.

Hashing has attracted a great deal of research in recent years due to its effectiveness for the retrieval and indexing of large-scale high-dimensional multimedia data. In this paper, we propose a novel ranking-based hashing framework that maps data from different modalities into a common Hamming space where the cross-modal similarity can be measured using Hamming distance. Unlike existing cross-modal hashing algorithms where the learned hash functions are binary space partitioning functions, such as the sign and threshold function, the proposed hashing scheme takes advantage of a new class of hash functions closely related to rank correlation measures which are known to be scale-invariant, numerically stable, and highly nonlinear. Specifically, we jointly learn two groups of linear subspaces, one for each modality, so that features' ranking orders in different linear subspaces maximally preserve the cross-modal similarities. We show that the ranking-based hash function has a natural probabilistic approximation which transforms the original highly discontinuous optimization problem into one that can be efficiently solved using simple gradient descent algorithms. The proposed hashing framework is also flexible in the sense that the optimization procedures are not tied up to any specific form of loss function, which is typical for existing cross-modal hashing methods, but rather we can flexibly accommodate different loss functions with minimal changes to the learning steps. We demonstrate through extensive experiments on four widely-used real-world multimodal datasets that the proposed cross-modal hashing method can achieve competitive performance against several state-of-the-arts with only moderate training and testing time.

Hashing techniques show significant advantage in dealing with enormous high-dimensional image and multimedia data. Specifically, learning based hashing methods attract a lot of attention from researchers thanks to its great performance in image retrieval. But discrete constraint problem of learning based hashing methods makes the optimization extremely difficult, which can be shown to be NP hard. Thus, most of learning based hashing methods relax the constraint and get a suboptimal result. Recently, some researchers propose discrete optimization hashing techniques to learn hash bits without any relaxation and achieve promising results. But, discrete optimization hashing method like Supervised Discrete Hashing (SDH) roughly renews all binary codes and leads to a time-consuming problem. In this paper, we propose an adaptive discrete cyclic coordinate descent (ACC) method to effectively solve discrete optimization problem. The specific objective of our study is to boost the efficiency of discrete hash optimization with equivalent performance. We evaluate the proposed method on image and multimedia databases: CIFAR-10, NUS-WIDE and MIRFLickr-25k and show that our method achieves speed-up over compared the state-of-the-art methods, while having on-par and in some cases even better performance.

The past decade has been marked by the (continued) explosion of diverse data content and the fast development of intelligent data analytics techniques. One problem we identified in the mid-2000s was similarity search of feature-rich data. The challenge here was achieving both high accuracy and high efficiency in high-dimensional spaces. Locality sensitive hashing (LSH), which uses certain random space partitions and hash table lookups to find approximate nearest neighbors, was a promising approach with theoretical guarantees. But LSH alone was insufficient since a large number of hash tables were required to achieve good search quality. Building on an idea of Panigrahy, our multi-probe LSH method introduced the idea of intelligent probing. Given a query object, we strategically probe its neighboring hash buckets (in a query-dependent fashion) by calculating the statistical probabilities of similar objects falling into each bucket. Such intelligent probing can significantly reduce the number of hash tables while achieving high quality. In this paper, we revisit the problem motivation, the challenges, the key design considerations of multi-probe LSH, as well as discuss recent developments in this space and some questions for further research.

The approximate nearest neighbor (ANN) search problem is important in applications such as information retrieval. Several hashing-based search methods that provide effective solutions to the ANN search problem have been proposed. However, most of these focus on similarity preservation and coding error minimization, and pay little attention to optimizing the precision-recall curve or receiver operating characteristic curve. In this paper, we propose a novel projection-based hashing method that attempts to maximize precision and recall. We first introduce an uncorrelated component analysis (UCA) transformation by examining precision and recall, and then propose a UCA-based hashing method. The proposed method is evaluated with a variety of data sets. The results show that UCA-based hashing outperforms state-of-the-art methods, and has computationally efficient training and encoding processes.

Recent years, we have witnessed the growing popularity of integrating nearest neighbor search with hashing for effective and efficient similarity search. However, most of the previous cross-modal hashing methods didn’t consider the semantic correlation between multi-modal representations and directly project the heterogeneous data into a joint space using a linear projection. To address these challenges and bridge the semantic gap more efficiently. We proposed a method named kernel based latent semantic sparse hashing (KLSSH) in this paper. We firstly capture high-level latent semantic information and then use the equivalence between optimizing the code inner products and the Hamming distances. More specifically, KLSSH firstly employs sparse coding for obtaining primary latent features of image and matrix factorization for generating features of text concepts to learn latent semantic features in a high level abstraction space. Next, it maps the latent semantic feature to compact binary codes using kernel method. Kernel scheme ensures to sequentially and efficiently train the hash functions one bit at a time and then generate very short and discriminative hash codes. Moreover, it reduces the quantization loss obviously at the same time and makes the retrieval performance better. Experiments conducted on three benchmark multi-modal datasets demonstrate the superiority of our proposed method compared with the state-of-the-art techniques.

Hashing learning has attracted increasing attention these years with the explosive increase in data volume. Most existing hashing learning methods can be divided into two stages. Firstly, obtain low-dimensional representation of the original data. Secondly, quantize the low-dimensional representation of each sample and map them to binary codes. This two-stage hashing framework separates projection operation and quantization operation apart, and the original data structure cannot be well preserved after this kind of two-stage operation. Considering this, global similarity preserving hashing (GSPH) is proposed, which utilizes a joint hashing framework to directly project the original data to hamming space, and reduces the projection error and the quantization loss simultaneously. Moreover, GSPH presents a global similarity-based data sample reconstruction method, which describes the intrinsic manifold structure of original data more precisely. The image retrieval experimental results on Corel, CIFAR, LabelMe and NUS-WIDE datasets illustrate that our algorithm outperforms several other state-of-the-art methods.

We study the security of authenticated encryption based on a stream cipher and a universal hash function. We consider ChaCha20-Poly1305 and generic constructions proposed by Sarkar, where the generic constructions include 14 AEAD (authenticated encryption with associated data) schemes and 3 DAEAD (deterministic AEAD) schemes. In this paper, we analyze the integrity of these schemes both in the standard INT-CTXT (integrity of ciphertext) notion and in the RUP (releasing unverified plaintext) setting called INT-RUP notion. We present INT-CTXT attacks against 3 out of the 14 AEAD schemes and 1 out of the 3 DAEAD schemes. We then show INT-RUP attacks against 1 out of the 14 AEAD schemes and the 2 remaining DAEAD schemes. Next, we consider ChaCha20-Poly1305 and show that it is provably secure in the INT-RUP notion. Finally, we show that the remaining 10 AEAD schemes are provably secure in the INT-RUP notion.

Learning to hash is receiving increasing research attention due to its effectiveness in addressing the large-scale similarity search problem. Most of the existing hashing algorithms are focused on learning hash functions in the form of numeric quantization of some projected feature space. In this work, we propose a novel hash learning method that encodes features’ relative ordering instead of quantizing their numeric values in a set of low-dimensional ranking subspaces. We formulate the ranking-based hash learning problem as the optimization of a continuous probabilistic error function using softmax approximation and present an efficient learning algorithm to solve the problem. As a generalization of Winner-Take-All (WTA) hashing, the proposed algorithm naturally enjoys the numeric stability benefits of rank correlation measures while being optimized to achieve high precision with very compact code. Additionally, the proposed method can also be easily extended to nonlinear kernel spaces to discover ranking structures that can not be revealed in linear subspaces. We demonstrate through extensive experiments that the proposed method can achive competitive performances as compared to a number of state-of-the-art hashing methods.

Robust image hashing is a promising technique to represent image’s perceptual content. However, when it comes to image authentication, tradeoff between robustness and discrimination is a non-negligible issue. The allowed content preserving operations and sensitive malicious manipulations on images are quite subjective to human’s perception. So it needs tactics to design good hashing methods. In this paper we incorporate the novel concept of core alignment into hashing, where the proposed core alignment improves the performances of balance. First, we formulize the hashing as a supervised minimal optimization problem based on Locality Sensitive Hashing, in which p-stable distribution is exploited to maintain high dimensional locality features. Then we solve this problem by two sub-optimization problems, i.e., searching for optimal shift and searching for optimal quantization intervals. By using particle swarm optimization and simulated annealing programming approaches we develop two stochastic solutions to those two problems, respectively. Experimental results show that our proposed hashing optimizations can find optimal solutions with limited steps, and the hashing method is superior to other state-of-the-art methods in terms of authentication and robustness.

Cross-modal hashing can effectively solve the large-scale cross-modal retrieval by integrating the advantages of traditional cross-modal analysis and hashing techniques. In cross-modal hashing, preserving semantic correlation is important and challenging. However, current hashing methods cannot well preserve the semantic correlation in hash codes. Supervised hashing requires labeled data which is difficult to obtain, and unsupervised hashing cannot effectively learn semantic correlation from multi-modal data. In order to effectively learn semantic correlation to improve hashing performance, we propose a novel approach: Semi-Supervised Semantic Factorization Hashing (S3FH), for large-scale cross-modal retrieval. The main purpose of S3FH is to improve semantic labels and factorize it into hash codes. It optimizes a joint framework which consists of three interactive parts, including semantic factorization, multi-graph learning and multi-modal correlation. Then, an efficient alternating algorithm is derived for optimizing S3FH. Extensive experiments on two real world multi-modal datasets demonstrate the effectiveness of S3FH.

Hashing techniques have been widely adopted for cross-modal retrieval due to their low storage cost and fast query speed. Recently, some unimodal hashing methods have tried to directly optimize the objective function with discrete binary constraints. Inspired by these methods, the authors propose a novel supervised cross-modal hashing method called Discrete Cross-Modal Hashing (DCMH) to learn the binary codes without relaxing them. DCMH is formulated through semantic similarity reconstruction, and it learns binary codes for use as ideal features for classification. Furthermore, DCMH alternately updates binary codes for each modality, and its discrete hashing codes are learned efficiently, bit by bit, which is quite promising for large-scale datasets. To evaluate the effectiveness of the proposed discrete optimization, the authors optimize their objective function in a relax-and-threshold manner. Extensive empirical results on both image-text and image-tag datasets demonstrate that DCMH is a significant improvement over previous approaches in terms of training time and retrieval performance.

Hashing based strategies have recently been widely used in fast similarity search on large scale datasets. Data-independent methods such as Locality Sensitive Hashing (LSH) usually adopt random projections as hash functions, with theoretical guarantees that the performance improves with the increasing code length. Thus they require relatively long codes, making them less effective than data-dependent methods. On the other hand, in many data-dependent hashing methods, Principal Component Analysis (PCA) is widely used to generate compact hash codes. However, PCA based methods tend not to be effective for generating long codes because projections with small variances may induce certain redundancy and noise. In order to address these deficiencies, we present a R 2 PCAH framework that conducts two-fold random transformations based on principal projections for hash code learning. Specifically, only the top PCA projections of the training data are extracted and two-fold random transformations, i.e. random rotations and random shifts are performed on the projected data to generate several pieces of component short codes. The multiple component short codes are then concatenated into one piece of long code. We observe that our method shares the advantages of both LSH and PCA based hashing methods. Extensive experiments demonstrate the effectiveness of the proposed method.

We present a new method to generate efficient multi-level hashing codes for image retrieval based on the deep siamese convolutional neural network (DSCNN). Conventional deep hashing methods trade off the capability of capturing highly complex and nonlinear semantic information of images against very compact hash codes, usually leading to high retrieval efficiency but with deteriorated accuracy. We alleviate the restrictive compactness requirement of hash codes by extending them to a two-level hierarchical coding scheme, in which the first level aims to capture the high-level semantic information extracted by the deep network using a rich encoding strategy, while the subsequent level squeezes them to more global and compact codes. At running time, we adopt an attention-based mechanism to select some of its most essential bits specific to each query image for retrieval instead of using the full hash codes of the first level. The attention-based mechanism is based on the guides of hash codes generated by the second level, taking advantage of both local and global properties of deep features. Experimental results on various popular datasets demonstrate the advantages of the proposed method compared to several state-of-the-art methods.

We propose a novel hashing scheme, namely DH, for high-dimensional video data.Feature disaggregation is proposed by exploiting correlations among dimensions.Hash function is learned independently on feature clusters by greedy optimization.DH can significantly reduce the computational complexity and memory usage.DH outperforms the state-of-the-art methods on three realistic action datasets. Learning based hashing methods, which aim at learning similarity-preserving binary codes for efficient nearest neighbor search, have been actively studied recently. A majority of the approaches address hashing problems for image collections. However, due to the extra temporal information, videos are usually represented by much higher dimensional (thousands or even more) features compared with images, causing high computational complexity for conventional hashing schemes. In this paper, we propose a simple and efficient hashing scheme for high-dimensional video data. This method, called Disaggregation Hashing (DH), exploits the correlations among different feature dimensions. An intuitive feature disaggregation method is first proposed, followed by a novel hashing algorithm based on different feature clusters. Additionally, a kernelized version of DH is proposed for better performance. We demonstrate the efficiency and effectiveness of our method by theoretical analysis and exploring its application on action retrieval from video databases. Extensive experiments show the superiority of our binary coding scheme over state-of-the-art hashing methods.

In the past few years, researchers have introduced several sorting algorithms to enhance time complexity, space complexity, and stability. A double hashing methodology first collects statistics about element distribution and then maps between elements of the array and indexes based on the knowledge collected during the first hashing.

In recent years, learning based hashing becomes an attractive technique in large-scale image retrieval due to its low storage and computation cost. Hashing methods map each high-dimensional vector onto a low-dimensional hamming space by projection operators. However, when processing high dimensional data retrieval, many existing methods including hashing cost a majority of time on projection operators. In this paper, we solve this problem by implementing a sparsity regularizer. On one hand, due to the sparse property of the projection matrix, our method effectively lower both the storage and computation cost. On the other hand, we reduce the effective number of parameters involved in the learned projection matrix according to sparsity regularizer, which helps avoid overfitting problem. Without relaxing binary constraints, an iterative scheme jointly optimizing the objective function directly was given, which helps to obtain effective and efficient binary codes. We evaluate our method on three databases and compare it with some state-of-the-art hashing methods. Experimental results demonstrate that our method outperforms the comparison approaches.

Hashing based approximate nearest neighbors (ANN) search has drawn considerable attraction owing to its low-memory storage and hardware-level logical computing which is doomed to be greatly applicable to quantities of large-scale and practical scenarios, such as information retrieval, computer vision and natural language processing. However, most existing hashing methods concentrate either on images only or on pairwise image-texts (labels, short documents) and rarely utilize more common sentences. In this paper, we propose D iversity R egularized L atent S emantic M atch for H ashing (DRLSMH), a new multimodal hashing method that projects images and sentences into a shared latent semantic space with label-supervised semantic constraints to proceed on multimodal retrieval. Notably, soft orthogonality is induced as a novel regularizer to preserve diverse hashing functions for compact and accurate representations; what's more, this kind of regularization also benefits the derivations of closed-form solutions with some proper relaxations under iterative optimization framework. Extensive experiments on two public datasets demonstrate the advantages of our method over some state-of-the-art baselines under cross-modal retrieval both on image-query-image, image-query-text and text-query-image tasks.

Fast nearest neighbor search is becoming more and more crucial given the advent of large-scale data in many computer vision applications. Hashing approaches provide both fast search mechanisms and compact index structures to address this critical need. In image retrieval problems where labeled training data is available, supervised hashing methods prevail over unsupervised methods. Most state-of-the-art supervised hashing approaches employ batch-learners. Unfortunately, batch-learning strategies may be inefficient when confronted with large datasets. Moreover, with batch-learners, it is unclear how to adapt the hash functions as the dataset continues to grow and new variations appear over time. To handle these issues, we propose OSH: an Online Supervised Hashing technique that is based on Error Correcting Output Codes. We consider a stochastic setting where the data arrives sequentially and our method learns and adapts its hashing functions in a discriminative manner. Our method makes no assumption about the number of possible class labels, and accommodates new classes as they are presented in the incoming data stream. In experiments with three image retrieval benchmarks, our method yields state-of-the-art retrieval performance as measured in Mean Average Precision, while also being orders-of-magnitude faster than competing batch methods for supervised hashing. Also, our method significantly outperforms recently introduced online hashing solutions.

Due to the query effectiveness and efficiency, cross-modal similarity search based on hashing has acquired extensive attention in the multimedia community. Most existing methods do not explicitly employ the ranking information when learning hash functions, which is quite important for building practical retrieval systems. To solve this issue, this paper proposes a rank-order preserving hashing (RoPH) method with a novel regression-based rank-order preserving loss that has provable large margin property and is easy to optimize. Moreover, we jointly learn the binary codes and hash functions instead of using any relaxation trick. To solve the induced optimization problem, the alternating descent technique is adopted and each subproblem can be solved conveniently. Specifically, we show that the involved binary quadratic programming subproblem with respect to an introduced auxiliary binary variable satisfies submodularity, enabling us to use the off-the-shelf graph-cut algorithms to solve it exactly and efficiently. Extensive experiments on three benchmarks demonstrate that RoPH significantly improves the ranking quality over the state of the arts.

Existing hashing methods normally define certain specific forms of hash functions, after which an objective function can be formulated to optimize the loss on training set to learn the parameters. However, in this way, the hash function will be tightly coupled with the generated objective in most cases. Moreover, since the objectives are generally formulated with binary quantization, most of them are nonconvex, which makes the optimization difficult and consequently decreases the similarity preserving performance of hashing. To solve this problem, we propose a novel pairwise correlation preserving framework to learn compact binary codes for hashing. First, we project each data into a metric space and represent it as a vector encoding the underlying local and global structure by pairwise correlation learning. Afterwards, pairwise correlation reconstruction (PCR), is further proposed to preserve the correlations of data between the metric space and the hamming space to learn binary codes. The PCR model is convex. Moreover, no specific hash functions are needed to be predefined and the steps of correlation learning and reconstruction are independent. The above characteristics make the optimization of PCR easily and efficiently, and thus leads to better preservation of data similarity in hamming space.

Recent years have witnessed more and more success of hash methods for building efficient classifiers, but less for prediction in machine learning. In this paper, we propose a hash based method for large scale nonparallel support vector machine prediction(HNPSVM). Our key idea of this method is that we use an approximal decision function instead of exact decision function by computing the Hamming distance between hashing the normal to the hyperplane of the classifier and the features. This method benefits nonparallel support vector(NPSVM) prediction in three aspects. First, it enhances the prediction accuracy using an flexible and general method. Second, the proposed HNPSVM reduce storage cost owing to the compact binary hash representation. Last, HNPSVM can speed up the computation of classification function. Moreover, we prove that the classification results of a hash based NPSVM classifier converge to the results of the exact NPSVM classifier as the number of binary hash functions tends to infinity. Several experiments on large scale data sets show the efficient of our method.

Digital forensic tool is a software used by digital evidence investigators to extract data and information from a digital evidence. The integrity of the digital evidence must be maintained through the chain of custody in order to be admissible in court. Most digital extraction tool use either MD5 (Message Digest) or SHA (Secured Hash Algorithm) hashing to check the integrity of digital evidence. The hashing algorithm has been found to have a weakness known as collision in which two different messages have the same hashing values. Although the probability of producing such weakness is very small, this collision can be used to deny the usage of the evidence in court of justice. After the first collision has been found, many cryptanalysts have tried to explore various methods to detect the collisions with shorter and efficient time. This paper is to review the existing methods in digital forensic tools that have been used to create a collision attacks in digital evidence.

Hash-based methods can achieve a fast similarity search by representing high-dimensional data with compact binary codes. However, the spatial structure in row images was always lost in most previous methods. In this paper, a novel Locally Linear Spatial Pyramid Hash(LLSPH) algorithm is developed for the task of fast image retrieval. Unlike the conventional approach, the spatial extent of image features is exploited in our method. The spatial pyramid structure is used both to construct binary hash codes and to increase the discriminability of the description. To generate interpretable binary codes, the proposed LLSPH method captures the spatial characteristics of the original SPM and generates a low-dimensional sparse representation using multi-dictionaries Locality-constrained Linear Coding(MD_LLC). LLSPH then converts the low-dimensional data into Hamming space by the TF-IDF binarization rule. Our experimental results show that our LLSPH method can outperform several state-of-the-art hashing algorithms on the Caltech256 and ImageNet-500 datasets.

Most existing supervised hashing methods learn the affinity-preserving binary codes to represent the high-dimensional data. However, each hashing code is assumed as independent and irrelevant with other codes. In practice, the authors find that there exists context association among hashing bits. This study proposes a novel hashing method dubbed kernelised supervised context hashing, which considers the hashing codes interrelation to reduce the quantisation. In this work, the kernel formulation is employed to tackle the high-dimensional data which is mostly linear inseparable first; and then different distributions are utilised to describe the binary codes context; finally, the hashing codes can be approximated by gradient descent method iteratively. Therefore, the correlation between the hash codes is integrated to redefine the metric measurement (i.e. Hamming affinity) to preserve the data similarity in the raw space. The authors evaluate the proposed method on three image benchmarks CIFAR-10, MNIST and NUS-WIDE for image retrieval, and experimental results show that it achieves better performance than several other state-of-the-art methods.

To reduce the size of hash code and enhance the security of wave atom transform (WAT) based image authentication system, a low-density parity-check code based distributed source coding (DSC) is employed to compress the hash code. With the help of a legitimately modified image, the compressed hash value could be correctly decoded while it will fail with the help of a maliciously attacked image. Therefore, the employed DSC provides a desired robustness to image authentication. Simulation results indicate that the proposed scheme provides a better performance with less hash code than existing WAT based image hash without using DSC. Moreover, the proposed scheme outperforms the random projection based approach in terms of authentication accuracy and data size.

Tweakable block ciphers are important primitives for designing cryptographic schemes with high security. In the absence of a standardized tweakable block cipher, constructions built from classical block ciphers remain an interesting research topic in both theory and practice. Motivated by Mennink’s \(\widetilde{F}[2]\) publication from 2015, Wang et al. proposed 32 optimally secure constructions at ASIACRYPT’16, all of which employ two calls to a classical block cipher each. Yet, those constructions were still limited to n-bit keys and n-bit tweaks. Thus, applications with more general key or tweak lengths still lack support. This work proposes the XHX family of tweakable block ciphers from a classical block cipher and a family of universal hash functions, which generalizes the constructions by Wang et al. First, we detail the generic XHX construction with three independently keyed calls to the hash function. Second, we show that we can derive the hash keys in efficient manner from the block cipher, where we generalize the constructions by Wang et al.; finally, we propose efficient instantiations for the used hash functions.

The combination of universal hashing and encryption is a fundamental paradigm for the construction of symmetric-key MACs, dating back to the seminal works by Wegman and Carter, Shoup, and Bernstein. While fully sufficient for many practical applications, the Wegman-Carter construction, however, is well-known to break if nonces are ever repeated, and provides only birthday-bound security if instantiated with a permutation. Those limitations inspired the community to severals recent proposals that addressed them, initiated by Cogliati et al.’s Encrypted Wegman-Carter Davies-Meyer (EWCDM) construction.

Robustly reusable Fuzzy Extractor (rrFE) considers reusability and robustness simultaneously. We present two approaches to the generic construction of rrFE. Both of approaches make use of a secure sketch and universal hash functions. The first approach also employs a special pseudo-random function (PRF), namely unique-input key-shift (ui-ks) secure PRF, and the second uses a key-shift secure auxiliary-input authenticated encryption (AIAE). The ui-ks security of PRF (resp. key-shift security of AIAE), together with the homomorphic properties of secure sketch and universal hash function, guarantees the reusability and robustness of rrFE. Meanwhile, we show two instantiations of the two approaches respectively. The first instantiation results in the first rrFE from the LWE assumption, while the second instantiation results in the first rrFE from the DDH assumption over non-pairing groups.

Random hashing can provide guarantees regarding the performance of data structures such as hash tables---even in an adversarial setting. Many existing families of hash functions are universal: given two data objects, the probability that they have the same hash value is low given that we pick hash functions at random. However, universality fails to ensure that all hash functions are well behaved. We further require regularity: when picking data objects at random they should have a low probability of having the same hash value, for any fixed hash function. We present the efficient implementation of a family of non-cryptographic hash functions (PM+) offering good running times, good memory usage as well as distinguishing theoretical guarantees: almost universality and component-wise regularity. On a variety of platforms, our implementations are comparable to the state of the art in performance. On recent Intel processors, PM+ achieves a speed of 4.7 bytes per cycle for 32-bit outputs and 3.3 bytes per cycle for 64-bit outputs. We review vectorization through SIMD instructions (e.g., AVX2) and optimizations for superscalar execution.

In the paper we define a notion of quantum resistant ((δ, є)-resistant) hash function which combine together a notion of pre-image (one-way) resistance (δ-resistance) property and the notion of collision resistance (є-resistance) properties. We present a discussion that supports the idea of quantum hashing oriented for cryptographical purposes. We propose a quantum setting of a classical digital signature scheme do demonstrate a theoretical possibilities and restrictions of (δ, є)-hashing. The assumption we use is that a set of qubits (quantum hash) we generate, send, and receive during the execution of a protocol can be stored for a certain (a large enough) amount of time; next, the scheme requires the high degree of entanglement between the qubits which makes such a quantum hash. These properties make quantum hash cryptographically efficient.

By transforming data into binary representation, i.e., Hashing, we can perform high-speed search with low storage cost, and thus, Hashing has collected increasing research interest in the recent years. Recently, how to generate Hashcode for multimodal data (e.g., images with textual tags, documents with photos, and so on) for large-scale cross-modality search (e.g., searching semantically related images in database for a document query) is an important research issue because of the fast growth of multimodal data in the Web. To address this issue, a novel framework for multimodal Hashing is proposed, termed as Collective Matrix Factorization Hashing (CMFH). The key idea of CMFH is to learn unified Hashcodes for different modalities of one multimodal instance in the shared latent semantic space in which different modalities can be effectively connected. Therefore, accurate cross-modality search is supported. Based on the general framework, we extend it in the unsupervised scenario where it tries to preserve the Euclidean structure, and in the supervised scenario where it fully exploits the label information of data. The corresponding theoretical analysis and the optimization algorithms are given. We conducted comprehensive experiments on three benchmark data sets for cross-modality search. The experimental results demonstrate that CMFH can significantly outperform several state-of-the-art cross-modality Hashing methods, which validates the effectiveness of the proposed CMFH.

In this paper, we propose a novel anomaly detection approach based on Locality Sensitive Hashing Filters (LSHF), which hashes normal activities into multiple feature buckets with Locality Sensitive Hashing (LSH) functions to filter out abnormal activities. An online updating procedure is also introduced into the framework of LSHF for adapting to the changes of the video scenes. Furthermore, we develop a new evaluation function to evaluate the hash map and employ the Particle Swarm Optimization (PSO) method to search for the optimal hash functions, which improves the efficiency and accuracy of the proposed anomaly detection method. Experimental results on multiple datasets demonstrate that the proposed algorithm is capable of localizing various abnormal activities in real world surveillance videos and outperforms state-of-the-art anomaly detection methods. HighlightsWe present a locality sensitive hashing filters based method for anomaly detection.Normal activities are hashed by hash functions into buckets to build filters.Abnormality of a test sample is estimated by filter response of its nearest bucket.Online updating mechanism increase the adaptability to scene changes.Searching for optimal hash functions improves the detection accuracy.Our method performs favorably against previous anomaly detection algorithms.

Learning-based hashing methods are becoming the mainstream for approximate scalable multimedia retrieval. They consist of two main components: hash codes learning for training data and hash functions learning for new data points. Tremendous efforts have been devoted to designing novel methods for these two components, i.e., supervised and unsupervised methods for learning hash codes, and different models for inferring hashing functions. However, there is little work integrating supervised and unsupervised hash codes learning into a single framework. Moreover, the hash function learning component is usually based on hand-crafted visual features extracted from the training images. The performance of a content-based image retrieval system crucially depends on the feature representation and such hand-crafted visual features may degrade the accuracy of the hash functions. In this paper, we propose a semi-supervised deep learning hashing (DLH) method for fast multimedia retrieval. More specifically, in the first component, we utilize both visual and label information to learn an optimal similarity graph that can more precisely encode the relationship among training data, and then generate the hash codes based on the graph. In the second stage, we apply a deep convolutional network to simultaneously learn a good multimedia representation and a set of hash functions. Extensive experiments on five popular datasets demonstrate the superiority of our DLH over both supervised and unsupervised hashing methods.