The problem of record linkage is to cluster the records from several data sources such that each cluster has all the records belonging to one and only one entity. Record linkage has applications in a wide variety of domains including public health, law enforcement, fraud detection, biology, and transportation. Given the typically vast sizes of datasets, existing algorithms suffer from very long runtimes. Hence, it is essential to develop novel algorithms tailored to address this issue. Blocking is a popular technique employed to speed up record linkage algorithms. In this paper, we employ a blocking technique that is based on Soundex encoding. Soundex index is a method of coding names based on their pronunciation rather than their spelling. Soundex has been traditionally used only as a distance metric. In this paper, we show how to use Soundex as a blocking technique. To the best of our knowledge, no one else has done it in the past. In fact, we introduce two novel blocking approaches that utilize Soundex encoding: One stage Soundex blocking and Two stage Soundex blocking.Our approaches exhibit superior linkage performance compared to the state-of-the-art record linkage algorithms, as evidenced by higher F-1 scores and reduced linkage times. The proposed blocking approaches prove to be highly effective.

Given multiple data sets, the problem of record linkage is to cluster them such that each cluster has all the information pertaining to a single entity and does not contain any other information. This problem has numerous applications in domains such as healthcare, law enforcement, medicine, census data analysis, etc. The performance of record linkage algorithms is measured with two metrics, namely, run times and accuracy. Record linkage has been studied extensively and numerous algorithms have been proposed. These algorithms take a very long time especially when the input data sets are large. Many applications of interest call for real-time or very nearly real-time performance. Thus there is a crucial need for the creation of novel record linkage algorithms that are very fast while maintaining a very good accuracy.Blocking is a technique that is typically used to speed up record linkage algorithms. In this paper, we introduce a novel algorithm for blocking called SuperBlocking. We have created novel record linkage algorithms that employ SuperBlocking. Experimental comparisons reveal that our algorithms outperform state-of-the-art algorithms for record linkage. We have also developed parallel versions of our record linkage algorithms and they obtain close to linear speedups.

Record Linkage is the process of consolidating data from several sources and capturing the records that are associated with the same entities, or individuals, where a unique identifier is not available. Record Linkage has applications in several areas such as master data management, law enforcement, health care, social networking, and historical research. Identifying the attributes from the data that are best suitable for performing record linkage in terms of accuracy and linking time is crucial. A straightforward approach of using all the attributes will result in large run times and may not yield a high accuracy. It is thus important to find a subset of the attributes that would give a high accuracy, while also minimizing the linking time. In this paper, we introduce a novel idea of addressing this problem using association analysis. We describe a pipeline to process the data and an algorithm based on association rules mining to find good features using some known rule quality measures. Our experimental results reveal that our approach yields better accuracy and run times than previous algorithms.

The risk posed by Membership Inference Attack (MIA) to deep learning models for Computer Vision (CV) tasks is well known, but MIA has not been addressed or explored fully in the Natural Language Processing (NLP) domain. In this work, we analyze the security risk posed by MIA to NLP models. We show that NLP models are at great risk to MIA, in some cases even more so than models trained on Computer Vision (CV) datasets. This includes an 8.04% increase in attack success rate on average for NLP models (as compared to CV models and datasets). We determine that there are some unique issues in NLP classification tasks in terms of model overfitting, model complexity, and data diversity that make the privacy leakage severe and very different from CV classification tasks. Based on these findings, we propose a novel defense algorithm - Gap score Regularization Integrated Pruning (GRIP), which can protect NLP models against MIA and achieve competitive testing accuracy. Our experimental results show that GRIP can decrease the MIA success rate by as much as 31.25% when compared to the undefended model. In addition, when compared to differential privacy, GRIP offers 7.81% more robustness to MIA and 13.24% higher testing accuracy. Overall our experimental results span four NLP and two CV datasets, and are tested with a total of five different model architectures.

In recent years, convolutional neural networks (CNN) have been successfully employed for performing various tasks due to their high capacity. However, just like a double-edged sword, high capacity results from millions of parameters, which also brings a huge amount of redundancy and dramatically increases the computational complexity. The task of pruning a pretrained network to make it thinner and easier to deploy on resource-limited devices is still challenging. In this paper, we employ the idea of adversarial examples to sparsify a CNN. Adversarial examples were originally designed to fool a network. Rather than adjusting the input image, we view any layer as an input to the layers afterwards. By performing an adversarial attack algorithm, the sensitivity information of the network components could be observed. With this information, we perform pruning in a structured manner to retain only the most critical channels. Empirical evaluations show that our proposed approach obtains the state-of-the-art structured pruning performance.

Higher order spectra (HOS) are a powerful tool in nonlinear time series analysis and they have been extensively used as feature representations in data mining, communications and cosmology domains. However, HOS estimation suffers from high computational cost and memory consumption. Any algorithm for computing the kth order spectra on a dataset of size n needs O(n^k-1 ) time since the output size will be O(n^k-1 ) as well, which makes the direct HOS analysis difficult for long time series, and further prohibits its direct deployment to resource-limited and time-sensitive applications. Existing algorithms for computing HOS are either inefficient or have been implemented on obsolete architectures. Thus it is essential to develop efficient generic algorithms for HOS estimations. In this paper, we present a package of generic sequential and parallel algorithms for computationally and memory efficient HOS estimations which can be employed on any parallel machine or platform. Our proposed algorithms largely reduce the HOS' computational cost and memory usage in spectrum multiplication and smoothing steps through carefully designed prefix sum operations. Moreover, we employ a matrix partitioning technique and design algorithms with optimal memory usage and present the parallel approaches on the PRAM and the mesh models. Furthermore, we implement our algorithms for both bispectrum and trispectrum estimations. We conduct extensive experiments and cross-compare the proposed algorithms' performance. Results show that our algorithms achieve state-of-the-art computational and memory efficiency, and our parallel algorithms achieve close to linear speedups. The code is available at https://github.com/ZigengWang/HOS.

In this paper we address a classical sequence mining problem, namely, that of finding the Closest Pair of Subsequences. Given a sequence A of length n, the problem is to identify two non-overlapping subsequences of length l each in A, such that their distance is minimum from among all such pairs. This is a fundamental problem that has a wide range of applications such as time series data mining, sequence data pattern matching, data signature identification, biological motif mining, metagenomic clustering, etc. To solve this problem, the state-of-the-art algorithm takes advantage of the overlapping parts of consecutive subsequences. By exploiting these overlaps, researchers have developed an algorithm with a run time of O(n2), which is independent of the dimension l. In this paper, we propose a deterministic algorithm called JUMP, which further pushes the limit by skipping unnecessary comparisons and multiplication operations, and improves the running time by a large factor. We have performed extensive experiments using standard benchmark datasets, and found that JUMP outperforms existing O(n2) methods by a factor of up to 100. Our experiments cover different settings of n and l and provide the readers a comprehensive and unbiased comparison under different conditions.

The closest pair problem (CPP) is an important problem that has numerous applications in clustering, graph partitioning, image processing, patterns identification, intrusion detection, etc. Numerous algorithms have been presented for solving the CPP. For instance, on n points there exists an O(n log n) time algorithm for CPP (when the dimension is a constant). There also exist randomized algorithms with an expected linear run time. However these algorithms do not perform well in practice. The algorithms that are employed in practice have a worst case quadratic run time. One of the best performing algorithms for the CPP is MK (originally designed for solving the time series motif finding problem). In this paper we present an elegant exact algorithm called MPR for the CPP that performs better than MK. Also, we present approximation algorithms for the CPP that are faster than MK by up to a factor of more than 40, while maintaining a very good accuracy.

Advances made in sequencing technology have resulted in the sequencing of thousands of genomes. Novel analysis tools are needed to process these data and extract useful information. Such tools could aid in personalized medicine. As an example, we could identify the causes for a disease by comparing the genomes of people who have the disease and those who do not have this disease. Given that human variability happens due to single nucleotide polymorphisms (SNPs), we could focus our attention on these SNPs. Investigations that try to understand human variability using SNPs fall under genome-wide association study (GWAS). A crucial step in GWAS is the identification of the correlation between genotypes (SNPs) and phenotypes (i.e., characteristics such as the presence of a disease). This step can be modeled as the k-locus problem (where k is any integer). A number of algorithms have been proposed in the literature for this problem when k = 2. In this paper we present an algorithm for solving the 2-locus problem that is up to two orders of magnitude faster than the previous best known algorithms.

Using the recent advances in sequencing technology thousands of genomes have been sequenced. This sequence data can be fruitfully employed in diagnosis, drug design, etc. Genome-wide Association Study (GWAS) focuses on this important problem of extracting useful information from genomic data. As an example, a comparison of different genomes could throw light on causes for different diseases. Human variabilities happen due to single nucleotide polymorphisms (SNPs). Thus it might suffice to focus on these SNPs while comparing different genomes. One of the important problems in GWAS is that of identifying the correlation between genotypes (SNPs for example) and phenotypes (i.e., different characteristics such as addiction, the presence of cancer, etc.) Different approaches exist for addressing this problem. One important approach is via modeling this problem as the k-locus problem (k being any integer). The case of k = 1 has been studied widely. Some algorithms also exist for solving the case of k = 2. The real cause for a disease could be more than two SNPs. The case of k > 2 has not been studied in the literature. For the first time, in this paper we present an efficient algorithm for solving the 3-locus problem that is several orders of magnitude faster than the brute force algorithm. All the software can be obtained from: engr.uconn.edu/~rajasek/ThreeLocus.

In this paper, we present a novel algorithm for mining complete frequent itemsets. This algorithm is referred to as the TM (transaction mapping) algorithm from hereon. In this algorithm, transaction ids of each itemset are mapped and compressed to continuous transaction intervals in a different space and the counting of itemsets is performed by intersecting these interval lists in a depth-first order along the lexicographic tree. When the compression coefficient becomes smaller than the average number of comparisons for intervals intersection at a certain level, the algorithm switches to transaction id intersection. We have evaluated the algorithm against two popular frequent itemset mining algorithms, FP-growth and dEclat, using a variety of data sets with short and long frequent patterns. Experimental data show that the TM algorithm outperforms these two algorithms.

In data warehousing applications, numerous OLAP queries involve the processing of holistic operations such as computing the "top N", median, etc. Efficient implementations of these operations are hard to come by. Several algorithms have been proposed in the literature that estimate various quantiles of disk-resident data. Two such recent algorithms are based on sampling. The authors present two novel and efficient quantiling algorithms, Deterministic Bucketing (DB) and Randomized Bucketing (RB). We have analyzed the performance of DB and RE and extended the analysis of the sampling done in prior algorithms. We have conducted extensive experiments to compare all these four algorithms. Our experimental data indicate that our new algorithms outperform prior algorithms not only in the overall run time but also in accuracy. The new algorithms can be used either as one-pass algorithms to accurately estimate quantiles or as algorithms for computing the quantiles exactly.