ABSTRACT With examples we provide a minimum theory framework to understand data compression of text files—using Huffman coding—that will also provide a framework in designing experiments involving encoding/decoding. We propose a parallelizable heuristic for the naïve Huffman encoding and decoding which addresses the difficulty in parallelizing the inherently sequential Huffman decoding. While the proposal is amenable to a design of an efficient parallel algorithm for Huffman decoding, it also achieves a better compression ratio in the sense that the fraction of inputs for it works is over 0.83. The results of simulations of the parallel algorithm on a 64‐core machine show that the proposed parallel modified Huffman encoding and decoding results in a faster algorithm when compared to the naïve Huffman scheme and the sequential version of the heuristic proposed. Further, the parallel implementation of the proposed encoding and decoding schemes resulted in a mean speed‐up of and respectively over the naïve Huffman encoding and decoding when processing an input of size on a multi‐core processor with cores.

Workload characterization and subsequent prediction are significant steps in maintaining the elasticity and scalability of resources in Cloud Data Centers. Due to the high variance in cloud workloads, designing a prediction algorithm that models the variations in the workload is a non-trivial task. If the workload predictor is unable to handle the dynamism in the workloads, then the result of the predictor may lead to over-provisioning or under-provisioning of cloud resources. To address this problem, we have created a Super Markov Prediction Model (SMPM) whose behaviour changes as per the change in the workload patterns. As the time progresses, based on the workload pattern SMPM uses different sequence models to predict the future workload. To evaluate the proposed model, we have experimented with Alibaba trace 2018, Google Cluster Trace (GCT), Alibaba trace 2020 and TPC-W workload trace. We have compared SMPM's prediction results with existing state-of-the-art prediction models and empirically verified that the proposed prediction model achieves a better accuracy as quantified using Root Mean Square Error (RMSE) and Mean Absolute Error (MAE).

Learning the inherent meaning of a word in Natural Language Processing (NLP) has motivated researchers to represent a word at various levels of abstraction, namely character-level, morpheme-level, and subword-level vector representations. Syllable-Aware Word Embedding (SAWE) can effectively handle agglutinative and fusion-based NLP tasks. However, research attempts on assessing the SAWE on such extrinsic NLP tasks has been scanty, especially for low-resource languages in the context of code-mixing with English. A model to learn SAWE to extract semantics at fine-grained subunits of a word is proposed in this article, and the representative ability of the embeddings is assessed through sentiment analysis of code-mixed Telugu-English review corpora. Multilingual societies and advancements in communication technologies have accounted for the prolific usage of mixed data, which renders the State-of-the-Art (SOTA) sentiment analysis models developed based on monolingual data ineffective. Social media users in the Indian subcontinent exhibit a tendency to mix English and their respective native language (using the phonetic form of English) in expressing their opinions or sentiments. A code-mixing scenario provides flexibility to borrow words from a foreign language, usage of shorthand notations, elongation of vowels, and usage of words without following syntactic/grammatical rules, which renders the sentiment analysis of code-mixed data challenging to perform. Deep neural architectures like Long Short-Term Memory and Gated Recurrent Unit networks have been shown to be effective in solving several NLP tasks, such as sequence labeling, named entity recognition, and machine translation. In this article, a framework to perform sentiment analysis on a code-mixed Telugu-English review corpus is implemented. Both word embedding and SAWE are input to a unified deep neural network that contains a two-level Bidirectional Long Short-Term Memory/Gated Recurrent Unit network with Softmax as the output layer. The proposed model leverages the advantages of both word embedding and SAWE, which enable the proposed model to outperform existing SOTA code-mixed sentiment analysis models on a Telugu-English code-mixed dataset of the International Institute of Information Technology–Hyderabad and a dataset curated by the authors. The improvement realized by the proposed model on these datasets is [3% increase in F1-score and 2% increase in accuracy] and [7% increase in F1-score and 5% in accuracy], respectively, in comparison with the best-performing SOTA model.

Hidden Markov models (HMMs) belong to the class of double embedded stochastic models which were originally leveraged for speech recognition and synthesis. HMMs subsequently became a generic sequence model across multiple domains like NLP, bio-informatics and thermodynamics to name a few. Literature has several heuristic metrics to compare two HMMs by factoring in their structure and emission probability distributions in HMM nodes. However, typical structure-based metrics overlook the similarity between HMMs having different structures yet similar behavior and typical behavior-based metrics rely on the representativeness of the reference sequence used for assessing the similarity in behavior. Further, little exploration has taken place in leveraging the recent advancements in deep graph neural networks for learning effective representations for HMMs. In this paper, we propose two novel deep neural network based approaches to learn embeddings for HMMs and evaluate the validity of the embeddings based on subsequent clustering and classification tasks. Our proposed approaches use a Graph variational Autoencoder and diffpooling based Graph neural network (GNN) to learn embeddings for HMMs. The graph autoencoder infers latent low-dimensional flat embeddings for HMMs in a task-agnostic manner; whereas the diffpooling based graph neural network learns class-label aware embeddings by inferring and aggregating a hierarchical set of clusters and sub-clusters of graph nodes. Empirical results reveal that the HMM embeddings learnt through the Graph variational autoencoders and diffpooling based GNN outperform the popular heuristics as measured by the cluster quality metrics and the classification accuracy in downstream tasks.

Summary Web directories like Wikipedia and Open Directory Mozilla facilitate efficient information retrieval (IR) of web documents from a huge web corpus. Maintenance of these web directories is understandably a difficult task that requires manual curation by human editors or semi‐automated mechanisms. Research on parallel algorithms for the automated curation of these web directories will be beneficial to the IR domain. Hence, in this article, we propose a parallel algorithm for automatically creating web directories from a corpus of web‐documents. We have used centrality‐based techniques to split the corpus into fine‐grained clusters and subsequently an agglomeration based on locality sensitive hashing to identify coarse‐grained clusters in the web‐directory. Experimental results show that the algorithm generates meaningful hierarchies of the input corpus as measured by cluster‐validity indices, like F‐measure, rand index, and cluster purity. The algorithm achieves a significant speedup and scales well both with the number of processors and the size of the input corpus.

Summary We propose a parallel generalization scheme for Singular Value Decomposition–based clustering algorithms. The scheme enables the clustering algorithm to generate a hierarchy of clusters instead of a flat set of clusters. The generalization scheme infers the number of levels to be formed and the number of clusters per level of the hierarchy automatically without depending on any user‐supplied parameter. The performance of the suggested hierarchical clustering algorithm was evaluated using the web directory taxonomy hosted by the Open Directory DMOZ. Empirical evaluations and statistical tests reveal that the proposed generalization scheme produces a superior cluster hierarchy when compared with two existing generalization techniques in terms of the precision, recall, f‐measure, and the rand index. The generalization scheme is well‐equipped to deal with large datasets and the speed‐up achieved by the parallelized generalization scheme over its sequential variant was measured using a multicore computer.

Summary We propose a distributed parallel algorithm for inferring the hierarchical groups present in a large‐scale text corpus. The algorithm is designed to deal with corpuses that typically do not fit into the main memory of a workstation computer. The key contribution of this paper lies in its proposal and verification of a parallel distributed algorithm that exploits the advantages of two complementary techniques based on (i) localized modularity optimization and (ii) spectral clustering. Based on our experimental observations, these are complementary in the sense that the former excels at finding coarse groups in a large‐scale network, while the latter demands a heavy memory footprint but is effective in inferring tightly knit fine‐grained groups. Empirical evaluation of the distributed implementation scheme shows that the algorithm exhibits a significant speed‐up when compared to existing algorithms like Louvain and, at the same time, produces better quality clusters than either Louvain or spectral clustering algorithms in terms of the F‐score and Rand index.

Summary We propose a parallelization scheme for an existing algorithm for constructing a web‐directory, that contains categories of web documents organized hierarchically. The clustering algorithm automatically infers the number of clusters using a quality function based on graph cuts. A parallel implementation of the algorithm has been developed to run on a cluster of multi‐core processors interconnected by an intranet. The effect of the well‐known Latent Semantic Indexing on the performance of the clustering algorithm is also considered. The parallelized graph‐cut based clustering algorithm achieves an F‐measure in the range [0.69,0.91] for the generated leaf‐level clusters while yielding a precision‐recall performance in the range [0.66,0.84] for the entire hierarchy of the generated clusters. As measured via empirical observations, the parallel algorithm achieves an average speedup of 7.38 over its sequential variant, at the same time yielding a better clustering performance than the sequential algorithm in terms of F‐measure. Copyright © 2015 John Wiley & Sons, Ltd.

Abstract We describe an implementation of a parallel document clustering scheme based on latent semantic indexing, which uses singular value decomposition. Given a set of documents, the clustering algorithm is dynamic in the sense that it automatically infers the number of clusters to be output. The parallel version has been implemented on a LAN and on a dual‐core system. Experimental evaluation of the algorithm shows an average speed‐up of 6.22 for the LAN implementation and an average speed‐up of 3.71 for the dual‐core implementation, while still maintaining a precision and recall in the range [0.85, 1]. To put these implementations in the context of information retrieval, we use the parallel clustering algorithm and develop a document similarity search system. The similarity search system shows good performance in terms of precision and recall. Copyright © 2010 John Wiley & Sons, Ltd.