Detecting out-of-scope user utterances is essential for task-oriented dialogues and intent classification. Current methodologies face difficulties with the unpredictable distribution of outliers and often rely on assumptions about data distributions. We present the Dual Encoder for Threshold-Based Re-Classification (DETER) to address these challenges. This end-to-end framework efficiently detects out-of-scope intents without requiring assumptions on data distributions or additional post-processing steps. The core of DETER utilizes dual text encoders, the Universal Sentence Encoder (USE) and the Transformer-based Denoising AutoEncoder (TSDAE), to generate user utterance embeddings, which are classified through a branched neural architecture. Further, DETER generates synthetic outliers using self-supervision and incorporates out-of-scope phrases from open-domain datasets. This approach ensures a comprehensive training set for out-of-scope detection. Additionally, a threshold-based re-classification mechanism refines the model’s initial predictions. Evaluations on the CLINC-150, Stackoverflow, and Banking77 datasets demonstrate DETER’s efficacy. Our model outperforms previous benchmarks, achieving an increase of up to 13% and 5% in F1 score for known and unknown intents on CLINC-150 and Stackoverflow, and 16% for known and 24% for unknown intents on Banking77. The source code has been released at https://github.com/Hossam-Mohammed-tech/Intent_Classification_OOS.

Word representations like GloVe and Word2Vec encapsulate semantic and syntactic attributes and constitute the fundamental building block in diverse Natural Language Processing (NLP) applications. Such vector embeddings are typically stored in float32 format, and for a substantial vocabulary size, they impose considerable memory and computational demands due to the resource-intensive float32 operations. Thus, representing words via binary embeddings has emerged as a promising but challenging solution. In this paper, we introduce BRECS, an autoencoder-based Siamese framework for the generation of enhanced binary word embeddings (from the original embeddings). We propose the use of the novel Binary Cosine Similarity (BCS) regularisation in BRECS, which enables it to learn the semantics and structure of the vector space spanned by the original word embeddings, leading to better binary representation generation. We further show that our framework is tailored with independent parameters within the various components, thereby providing it with better learning capability. Extensive experiments across multiple datasets and tasks demonstrate the effectiveness of BRECS, compared to existing baselines for static and contextual binary word embedding generation. The source code is available at https://github.com/rajbsk/brecs.

Recent work has found that few-shot sentence classification based on pre-trained Sentence Encoders (SEs) is efficient, robust, and effective.In this work, we investigate strategies for domain-specialization in the context of fewshot sentence classification with SEs.We first establish that unsupervised Domain-Adaptive Pre-Training (DAPT) of a base Pre-trained Language Model (PLM) (i.e., not an SE) substantially improves the accuracy of few-shot sentence classification by up to 8.4 points.However, applying DAPT on SEs, on the one hand, disrupts the effects of their (general-domain) Sentence Embedding Pre-Training (SEPT).On the other hand, applying general-domain SEPT on top of a domain-adapted base PLM (i.e., after DAPT) is effective but inefficient, since the computationally expensive SEPT needs to be executed on top of a DAPT-ed PLM of each domain.As a solution, we propose AdaSent, which decouples SEPT from DAPT by training a SEPT adapter on the base PLM.The adapter can be inserted into DAPT-ed PLMs from any domain.We demonstrate AdaSent's effectiveness in extensive experiments on 17 different few-shot sentence classification datasets.AdaSent matches or surpasses the performance of full SEPT on DAPT-ed PLM, while substantially reducing the training costs.The code for AdaSent is available 1 .

Fine-tuning pretrained self-supervised language models is widely adopted for transfer learning to downstream tasks. Fine-tuning can be achieved by freezing gradients of the pretrained network and only updating gradients of a newly added classification layer, or by performing gradient updates on all parameters. Gradual unfreezing makes a trade-off between the two by gradually unfreezing gradients of whole layers during training. This has been an effective strategy to trade-off between storage and training speed with generalization performance. However, it is not clear whether gradually unfreezing layers throughout training is optimal, compared to sparse variants of gradual unfreezing which may improve fine-tuning performance. In this paper, we propose to stochastically mask gradients to regularize pretrained language models for improving overall fine-tuned performance. We introduce GradDrop and variants thereof, a class of gradient sparsification methods that mask gradients during the backward pass, acting as gradient noise. GradDrop is sparse and stochastic unlike gradual freezing. Extensive experiments on the multilingual XGLUE benchmark with XLMR-Large show that GradDrop is competitive against methods that use additional translated data for intermediate pretraining and outperforms standard fine-tuning and gradual unfreezing. A post-analysis shows how GradDrop improves performance with languages it was not trained on, such as under-resourced languages.

Recent work has identified that distillation can be used to create vector quantization based ANN indexes by learning the inverted file index and product quantization. The argued advantage of using a fixed teacher encoder for queries and documents is that the scores produced by the teacher can be used instead of the label judgements that are required when using traditional supervised learning, such as contrastive learning. However, current work only distills the teacher encoder outputs of dot products between quantized query embedddings and product quantized document embeddings. Our work combines the benefits of contrastive learning and distillation by using contrastive distillation whereby the teacher outputs contrastive scores that the student learns from. Our experimental results on MSMARCO passage retrieval and NQ open question answering datasets show that contrastive distillation improves over current state of the art for vector quantized dense retrieval.

Cross-lingual alignment of word embeddings are important in knowledge transfer across languages, for improving machine translation and other multi-lingual applications. Current unsupervised approaches relying on learning structure-preserving transformations, using adversarial networks and refinement strategies, suffer from instability and convergence issues. This paper proposes BioSpere, a novel multi-stage framework for unsupervised mapping of bi-lingual word embeddings onto a shared vector space, by combining adversarial initialization, refinement procedure and point set registration. Experiments for parallel dictionary induction and word similarity demonstrate state-of-the-art unsupervised results for BioSpere on diverse languages – showcasing robustness against variable adversarial performance.

Aspect Based Sentiment Analysis is a dominant research area with potential applications in social media analytics, business, finance, and health.Prior works in this area are primarily based on supervised methods, with a few techniques using weak supervision limited to predicting a single aspect category per review sentence.In this paper, we present an extremely weakly supervised multi-label Aspect Category Sentiment Analysis framework which does not use any labelled data.We only rely on a single word per class as an initial indicative information.We further propose an automatic word selection technique to choose these seed categories and sentiment words.We explore unsupervised language model post-training to improve the overall performance, and propose a multi-label generator model to generate multiple aspect category-sentiment pairs per review sentence.Experiments conducted on four benchmark datasets showcase our method to outperform other weakly supervised baselines by a significant margin. 1

Selecting an appropriate and relevant context forms an essential component for the efficacy of several information retrieval applications like Question Answering (QA) systems. The problem of Answer Sentence Selection (AS2) refers to the task of selecting sentences, from a larger text, that are relevant and contain the answer to users' queries. While there has been a lot of success in building AS2 systems trained on open-domain data (e.g., SQuAD, NQ), they do not generalize well in closed-domain settings, since domain adaptation can be challenging due to poor availability and annotation expense of domain-specific data. This paper proposes SEDAN, an effective self-learning framework to adapt AS2 models for domain-specific applications. We leverage large pre-trained language models to automatically generate domain-specific QA pairs for domain adaptation. We further fine-tune a pre-trained Sentence-BERT architecture to capture semantic relatedness between questions and answer sentences for AS2. Extensive experiments demonstrate the effectiveness of our proposed approach (over existing state-of-the-art AS2 baselines) on different Question Answering benchmark datasets.

Question Answering (QA) has become a foundational research area in Natural Language Understanding (NLU) with widespread applications in search, personal digital assistance, and conversational systems. Despite the success in open-domain question answering, existing extractive question answering models pre-trained using Wikipedia articles (e.g., SQuAD data) perform rather poorly in closed-domain and industrial scenarios. Further, a major limitation in adapting question answering systems to such contexts is the poor availability and the expensive annotation of domain-specific data. Thus, wide applicability of QA models are severely hampered in enterprise systems.In this paper, we aim to address the above challenges by introducing a novel QA framework, Qasar, using self-supervised learning for efficient domain adaptation. We show, for the first time, the advantage of fine-tuning pre-trained QA models for closed-domains by synthetically generated domain-specific questions and answers (from relevant documents) from large language models like T5. Further, we also propose a novel context retrieval component based on question-context semantic relatedness to further boost the accuracy of the Qasar QA framework. Experimental results show significant performance improvements on both open-and closed-domain QA datasets, while requiring no labelling efforts, which we believe will contribute to the ease of deployment of such systems in enterprise settings. The different modules of our framework (synthetic data generation, context retrieval, and question answering) can be fully reproduced by fine-tuning publicly available language models and QA models on SQuAD dataset as discussed in the paper.

With the advancements of Natural Language Understanding (NLU), diverse industrial applications like user intent classification, smart chatbots, sentiment analysis and question answering have be-come a primary paradigm. Transformers-based multi-lingual language models such as XLM have performed significantly well in diverse semantic understanding and classification tasks. However, fine-tuning such large pre-trained architectures is resource and compute intensive, limiting its wide adoption in enterprise environments.We present a novel efficient and light-weight frame-work based on sentence embeddings to obtain enhanced multi-lingual text representations for domain-specific NLU applications. Our framework combines the concepts of up-projection, alignment and meta-embeddings enhancing the textual semantic similarity knowledge of smaller sentence embedding architectures. Extensive experiments on diverse cross-lingual classification tasks showcase the proposed framework to be comparable to state-of-the-art large language models (in mono-lingual and zero-shot settings), even with lesser training and resource requirements.

Natural Language Understanding (NLU) has become a primary paradigm in enterprise settings for myriad industrial applications like user intent classification, smarter chatbots, sentiment analysis, and duplicate detection to name a few. With the advent of globalization, significant advancements have been recently achieved in transformers-based multi-lingual language models such as XLM and its variants for downstream multi-lingual sentence or short text classification tasks. However, fine-tuning such large pre-trained language models is highly resource-intensive as it assumes the adaptation of the full model, hampering its wide adoption in production grade applications due to the demanding computational and memory requirements.In this paper, we present a practical and efficient framework based on fusing various pre-trained sentence encoders leveraging the multi-lingual knowledge distillation approach. We demon-strate, for the first time, the practicality of utilizing such multi-lingual sentence embeddings for supervised learning tasks with a focus on sentence classification scenarios. We experimented our proposed framework on a wide range of open source classification datasets and exhibit very competitive performance compared to fine-tuning large pre-trained language models. We showcase that our light-weight framework provides the advantage of ease of training within minutes on a single CPU, competitive inference time, and robustness to parameter settings. In hope of facilitating and democratizing practical research focused on NLP, we are planning to release our code as well as a new pre-trained sentence embeddings for XLM-R-large model.

Approximate subgraph matching, an important primitive for many applications like question answering, community detection, and motif discovery, often involves large labeled graphs such as knowledge graphs, social networks, and protein sequences. Effective methods for extracting matching subgraphs, in terms of label and structural similarities to a query, should depict accuracy, computational efficiency, and robustness to noise. In this paper, we propose VerSaChI for finding the top-k most similar subgraphs based on 2-hop label and structural overlap similarity with the query. The similarity is characterized using Chebyshev's inequality to compute the chi-square statistical significance for measuring the degree of matching of the subgraphs. Experiments on real-life graph datasets showcase significant improvements in terms of accuracy compared to state-of-the-art methods, as well as robustness to noise.

Multilingual sentence embeddings capture rich semantic information not only for measuring similarity between texts but also for catering to a broad range of downstream crosslingual NLP tasks.State-of-the-art multilingual sentence embedding models require large parallel corpora to learn efficiently, which confines the scope of these models.In this paper, we propose a novel sentence embedding framework based on an unsupervised loss function for generating effective multilingual sentence embeddings, eliminating the need for parallel corpora.We capture semantic similarity and relatedness between sentences using a multitask loss function for training a dual encoder model mapping different languages onto the same vector space.We demonstrate the efficacy of an unsupervised as well as a weakly supervised variant of our framework on STS, BUCC and Tatoeba benchmark tasks.The proposed unsupervised sentence embedding framework outperforms even supervised stateof-the-art methods for certain under-resourced languages on the Tatoeba dataset and on a monolingual benchmark.Further, we show enhanced zero-shot learning capabilities for more than 30 languages, with the model being trained on only 13 languages.Our model can be extended to a wide range of languages from any language family, as it overcomes the requirement of parallel corpora for training.

Automated Frequently Asked Question (FAQ) retrieval provides an effective procedure to provide prompt responses to natural language based queries, providing an efficient platform for large-scale service-providing companies for presenting readily available information pertaining to customers' questions.We propose DTAFA, a novel multi-lingual FAQ retrieval system that aims at improving the top-1 retrieval accuracy with the least number of parameters.We propose two decoupled deep learning architectures trained for (i) candidate generation via text classification for a user question, and (ii) learning fine-grained semantic similarity between user questions and the FAQ repository for candidate refinement.We validate our system using real-life enterprise data as well as open source dataset.Empirically we show that DTAFA achieves better accuracy compared to existing state-of-the-art while requiring nearly 30× lesser number of training parameters.

Subgraph querying is one of the most important primitives in many applications. Although the field is well studied for deterministic graphs, in many situations, the graphs are probabilistic in nature. In this paper, we address the problem of subgraph querying in large probabilistic labeled graphs. We employ a novel algorithmic framework, called ChiSeL, that uses the idea of statistical significance for approximate subgraph matching on uncertain graphs that have uncertainty in edges. For each candidate matching vertex in the target graph that matches a query vertex, we compute its statistical significance using the chi-squared statistic. The search algorithm then proceeds in a greedy manner by exploring the vertex neighbors having the largest chi-square score. In addition to edge uncertainty, we also show how ChiSeL can handle uncertainty in labels and/or vertices. Experiments on large real-life graphs show the efficiency and effectiveness of our algorithm.

We propose a simple, powerful, and flexible machine learning framework for (i) reducing the search space of computationally difficult enumeration variants of subset problems and (ii) augmenting existing state-of-the-art solvers with informative cues arising from the input distribution. We instantiate our framework for the problem of listing all maximum cliques in a graph, a central problem in network analysis, data mining, and computational biology. We demonstrate the practicality of our approach on real-world networks with millions of vertices and edges by not only retaining all optimal solutions, but also aggressively pruning the input instance size resulting in several fold speedups of state-of-the-art algorithms. Finally, we explore the limits of scalability and robustness of our proposed framework, suggesting that supervised learning is viable for tackling NP-hard problems in practice.

With the increasing impetus on globalization, workplace modernization, and employee welfare, modern organizations are focusing more and more resources in developing their pool of human capital. Employee attrition poses a major challenge for organizations - be it in terms of operational cost or loss of talent. We present CLARA (CLustering for Analysis and Remedial of Attrition), a deployed end-to-end system applying descriptive, predictive, and prescriptive analytics, providing as output actionable remedial actions to be used by HR departments to improve employee retention. We propose a coupling between clustering and frequent pattern based scoring measure to identify candidate employees at a high risk of attrition, and subsequently recommend suggestive actions to improve their retention. Using publicly available IBM human resource (HR) dataset, we show that CLARA demonstrates comparable performance (compared to state-of-the-art techniques) in identifying such “high risk” employees. We further validate the quality of the recommendations provided by the framework in reducing the overall rate of human capital loss, and discuss the real-life implementation of the framework within our organization. CLARA attains up to 65% precision, on IBM HR dataset, in predicting employee attrition and, thanks to the remedial actions, up to 22.5% reduction in the predictive attrition score for the top-5 identified employees.

The maximum clique extraction problem finds extensive application in diverse domains like community discovery in social networks, brain connectivity networks, motif discovery, gene expression in bioinformatics, anomaly detection, road networks and expert graphs. Since the problem is NP-hard, known algorithms for finding a maximum clique can be expensive for large real-life graphs. Current heuristics also fail to provide high accuracy and run-time efficiency for dense networks, quite common in the above domains. In this paper, we propose the ALTHEA heuristic to efficiently extract a maximum clique from a dense graph. We show that ALTHEA, based on chi-square statistical significance, is able to dramatically prune the search space for finding a maximum clique, thereby providing run-time efficiency. Further, experimental results on both real and synthetic graph datasets demonstrate that ALTHEA is highly accurate and robust in detecting a maximum clique.

With the advent of Big Data paradigm, filtering, retrieval, and linking of unstructured multi-modal data has become a necessity. Assigning topic labels to contents, that accurately capture the meaning and contextual information, is a fundamental problem in organizing unstructured data. The usage of manually-assigned tags for this purpose introduces inconsistencies because of different "surface forms". On the other hand, existing automated approaches either use hierarchical multi-label classification, or are unsupervised and rely on (undirected) graph measures leveraging taxonomies. While the former requires large training data set to learn the characteristics of each topic class, the latter lacks the flexibility to learn broad range of related topics and are less accurate.We propose a novel framework, ANNOTATE based on a small set of features and directed traversal of taxonomies to learn a broad spectrum of related topics using limited training data. We also show that our approach provides accurate labels for several domains without the need for re-training. For instance, the framework, trained on a small set of BBC news articles, exhibits close matches to user-generated tags for Quora documents. Experimental results, on the same model, for news classification and identifying aspects of Amazon product reviews, based on Amazon Mechanical Turk evaluation show our approach to be significantly better than state-of-the-art.We further present real-life case studies of our proposed framework for automatically tagging Quora posts, and topically segmenting, indexing and linking related YouTube videos (using our publicly available Chrome browser extension).

The rising need to harvest domain specific knowledge in several applications is largely limited by the ability to dynamically grow structured knowledge representations, due to the increasing emergence of new concepts and their semantic relationships with existing ones. Such enrichment of existing hierarchical knowledge sources with new information to better model the "changing world" presents two-fold challenges: (1) Detection of previously unknown entities or concepts, and (2) Insertion of the new concepts into the knowledge structure, respecting the semantic integrity of the created relationships. To this end we propose a novel framework, ETF, to enrich large-scale, generic taxonomies with new concepts from resources such as news and research publications. Our approach learns a high-dimensional embedding for the existing concepts of the taxonomy, as well as for the new concepts. During the insertion of a new concept, this embedding is used to identify semantically similar neighborhoods within the existing taxonomy. The potential parent-child relationships linking the new concepts to the existing ones are then predicted using a set of semantic and graph features. Extensive evaluation of ETF on large, real-world taxonomies of Wikipedia and WordNet showcase more than 5% F1-score improvements compared to state-of-the-art baselines. We further demonstrate that ETF can accurately categorize newly emerging concepts and question-answer pairs across different domains.

Labeled graphs provide a natural way of representing entities, relationships and structures within real datasets such as knowledge graphs and protein interactions. Applications such as question answering, semantic search, and motif discovery entail efficient approaches for subgraph matching involving both label and structural similarities. Given the NP-completeness of subgraph isomorphism and the presence of noise, approximate graph matching techniques are required to handle queries in a robust and real-time manner. This paper presents a novel technique to characterize the subgraph similarity based on statistical significance captured by chi-square statistic. The statistical significance model takes into account the background structure and label distribution in the neighborhood of vertices to obtain the best matching subgraph and, therefore, robustly handles partial label and structural mismatches. Based on the model, we propose two algorithms, VELSET and NAGA, that, given a query graph, return the top-k most similar subgraphs from a (large) database graph. While VELSET is more accurate and robust to noise, NAGA is faster and more applicable for scenarios with low label noise. Experiments on large real-life graph datasets depict significant improvements in terms of accuracy and running time in comparison to the state-of-the-art methods.

Cross-document co-reference resolution (CCR) computes equivalence classes over textual mentions denoting the same entity in a document corpus.Named-entity linking (NEL) disambiguates mentions onto entities present in a knowledge base (KB) or maps them to null if not present in the KB.Traditionally, CCR and NEL have been addressed separately.However, such approaches miss out on the mutual synergies if CCR and NEL were performed jointly.This paper proposes C3EL, an unsupervised framework combining CCR and NEL for jointly tackling both problems.C3EL incorporates results from the CCR stage into NEL, and vice versa: additional global context obtained from CCR improves the feature space and performance of NEL, while NEL in turn provides distant KB features for already disambiguated mentions to improve CCR.The CCR and NEL steps are interleaved in an iterative algorithm that focuses on the highest-confidence still unresolved mentions in each iteration.Experimental results on two different corpora, news-centric and web-centric, demonstrate significant gains over state-of-the-art baselines for both CCR and NEL.

With increasing popularity of Netflix, Yahoo! Video, etc., interactive multimedia services such as video-on-demand (VoD) provide an interesting and rich field of research. The advent of smarter wireless devices has surged the need for such services through wireless connectivity. However, personalization of individual user needs, reducing latency, coupled with maintaining low operational costs provides a challenging problem. In this paper, we propose an efficient VoD system, for wireless mobile devices, based on a novel caching algorithm, Intelligent Network Caching Algorithm (INCA) using analytics-driven look ahead scheme for both prefetch and replacement policies to deliver higher performance. This enables enhanced Quality Of Experience (QoE) of users with limited infrastructural changes and low operational cost. Alongside, we develop theoretical formulation of the QoE optimization problem that lies at the intersection of MPC (Markov Predictive Control) and MDP (Markov Decision Process). Empirical analysis over realistic user video query logs demonstrate better cache hit rate and QoE with low prefetch bandwidth, compared to existing caching schemes.

Identifying and linking named entities across information sources is the basis of knowledge acquisition and at the heart of Web search, recommendations, and analytics. An important problem in this context is cross-document co-reference resolution (CCR): computing equivalence classes of textual mentions denoting the same entity, within and across documents. Prior methods employ ranking, clustering, or probabilistic graphical models using syntactic features and distant features from knowledge bases. However, these methods exhibit limitations regarding run-time and robustness. This paper presents the CROCS framework for unsupervised CCR, improving the state of the art in two ways. First, we extend the way knowledge bases are harnessed, by constructing a notion of semantic summaries for intra-document co-reference chains using co-occurring entity mentions belonging to different chains. Second, we reduce the computational cost by a new algorithm that embeds sample-based bisection, using spectral clustering or graph partitioning, in a hierarchical clustering process. This allows scaling up CCR to large corpora. Experiments with three datasets show significant gains in output quality, compared to the best prior methods, and the run-time efficiency of CROCS.

The unparalleled growth and popularity of the Internet coupled with the advent of diverse modern applications such as search engines, on-line transactions, climate warning systems, etc., has catered to an unprecedented expanse in the volume of data stored world-wide. Efficient storage, management, and processing of such massively exponential amount of data has emerged as a central theme of research in this direction. Detection and removal of redundancies and duplicates in real-time from such multi-trillion record-set to bolster resource and compute efficiency constitutes a challenging area of study. The infeasibility of storing the entire data from potentially unbounded data streams, with the need for precise elimination of duplicates calls for intelligent approximate duplicate detection algorithms. The literature hosts numerous works based on the well-known probabilistic bitmap structure, Bloom Filter and its variants. In this paper we propose a novel data structure, Streaming Quotient Filter, (SQF) for efficient detection and removal of duplicates in data streams. SQF intelligently stores the signatures of elements arriving on a data stream, and along with an eviction policy provides near zero false positive and false negative rates. We show that the near optimal performance of SQF is achieved with a very low memory requirement, making it ideal for real-time memory-efficient de-duplication applications having an extremely low false positive and false negative tolerance rates. We present detailed theoretical analysis of the working of SQF, providing a guarantee on its performance. Empirically, we compare SQF to alternate methods and show that the proposed method is superior in terms of memory and accuracy compared to the existing solutions. We also discuss Dynamic SQF for evolving streams and the parallel implementation of SQF.

Enterprise clouds today support an on demand resource allocation model and can provide resources requested by applications in a near online manner using virtual machine resizing or cloning. However, in order to take advantage of an on demand resource model, enterprise applications need to be automatically scaled in a way that makes the most efficient use of resources. In this work, we present the SmartScale automated scaling framework. SmartScale uses a combination of vertical (adding more resources to existing VM instances) and horizontal (adding more VM instances) scaling to ensure that the application is scaled in a manner that optimizes both resource usage and the reconfiguration cost incurred due to scaling. The SmartScale methodology is proactive and ensures that the application converges quickly to the desired scaling level even when the workload intensity changes significantly. We evaluate SmartScale using real production traces on Olio, an emerging cloud benchmark, running on a kvm-based cloud testbed. We present both theoretical and experimental evidence that comprehensively establish the effectiveness of SmartScale.

With the explosion of information stored world-wide, data intensive computing has emerged as a central area of research. Efficient management and processing of this massively exponential amount of data from diverse sources, such as telecommunication call data records, telescope imagery, online transaction records, web pages, stock markets, medical records (monitoring critical health conditions of patients), climate warning systems, etc., has become a necessity. Removing redundancy from such huge (multi-billion records) datasets results in resource and compute efficiency for downstream processing and constitutes an important area of study. "Intelligent compression" or deduplication in streaming scenarios, for precise identification and elimination of duplicates from the unbounded data stream is a greater challenge given the real-time nature of data arrival. Stable Bloom Filters (SBF) [13] address this problem to a certain extent. However, SBF suffers from a high false negative rate and slow convergence rate, thereby rendering it inefficient for applications with low false negative rate tolerance.

Cloud computing has emerged as an exciting hosting paradigm to drive up server utilization and reduce data center operational costs. Even though clouds present a single unified homogeneous resource pool view to end users, the underlying server landscape may differ in terms of functionality and reconfiguration capabilities (e.g., support for shared processors, live migration). In a private cloud setting where information on the resources as well as workloads are available, the placement of applications on clouds can leverage it to achieve better consolidation with performance guarantees. In this work, we present the design and implementation of CloudMap, a provisioning system for private clouds. Given an application's resource usage patterns, we match it with a server cluster with the appropriate level of reconfiguration capability. In this cluster, we place the application on a server that has existing workloads with complementary resource usage profile. CloudMap is implemented using a hybrid architecture with a global server cluster selection module and local cluster-specific server selection modules. Using production traces from live data centers, we demonstrate the effectiveness of CloudMap over existing placement methodologies.