e-Commerce has many core problems which can benefit from data mining-constructing recommendations for users, designing product taxonomies in a way that the user finds easy to navigate to, facility allocation for inventory to minimize shipping costs-to name a few. A big component of e-commerce data comprises of search activity. Search as a share of traffic has overtaken direct browsing, and most e-commerce sites generate more search data than browse data. Search session data is also more voluminous than any user aggregated data since it includes anonymous sessions. However, search data is inherently local to a query. Therefore, it is not immediately obvious whether it can be used to build global (i.e., where no query is involved) knowledge to address many of these problems that are of interest. In this paper, we introduce a global structure, namely islands of interest, that is mined from local search data. We show that these concentrations of user search intent are highly relevant to each of the e-commerce problems mentioned earlier. We introduce two algorithms-one based on community detection, and the other on clustering-that can identify islands of interest. We build a framework that can compare the characteristics of the islands identified using these two approaches. We believe that in addition to providing insights into user behavior, islands of interest can be important in tackling lesser researched problems such as the design of product taxonomies.

e-Commerce is burgeoning: in the past five years, both in the USA and the UK, e-commerce retail sales having overtaken brick-and-mortar stores for the first time. Search is a primary means for users engaging in e-commerce. e-commerce companies often perform laborious human-intensive mappings of queries to various categories in their product taxonomies - a process called "relevance banding." This is done in order to improve recall and precision of their search engines. In this paper, we propose fully automated alternatives to this manual process. We use statistical properties of the click-model that is constructed using query-click logs in order to automate this process. We propose two algorithms - probability banding, and entropy banding - that perform banding in a fully automated manner. In large-scale A/B testing, our algorithms demonstrate considerable revenue and orders increase over the manual banding baseline. Our algorithms are now deployed at scale at CorpX - a multibillion dollar e-commerce major.

The problem of distinct value estimation has many applications. Being a critical component of query optimizers in databases, it also has high commercial impact. Many distinct value estimators have been proposed, using various statistical approaches. However, characterizing the errors incurred by these estimators is an open problem: existing analytical approaches are not powerful enough, and extensive empirical studies at large scale do not exist. We conduct an extensive large-scale empirical study of 11 distinct value estimators from four different approaches to the problem over families of Zipfian distributions whose parameters model real-world applications. Our study is the first that scales to the size of a billion-rows that today's large commercial databases have to operate in. This allows us to characterize the error that is encountered in real-world applications of distinct value estimation. By mining the generated data, we show that estimator error depends on a key latent parameter — the average uniform class size — that has not been studied previously. This parameter also allows us to unearth error patterns that were previously unknown. Importantly, ours is the first approach that provides a framework for visualizing the error patterns in distinct value estimation, facilitating discussion of this problem in enterprise settings. Our characterization of errors can be used for several problems in distinct value estimation, such as the design of hybrid estimators. This work aims at the practitioner and the researcher alike, and addresses questions frequently asked by both audiences.

Unstructured textual data has grown rapidly in the past two decades in various domains like enterprises, web, scientific, etc. A question that arises naturally when there is such a surfeit of data is: how valuable is a certain piece of data as compared to another? In an enterprise, the answer to this question would determine how valuable said data is to the enterprise. In this paper, we build a framework using data mining that quantifies the value of data. We first identify a specific notion of "value" that is motivated by applications in Enterprise unstructured Information Management (EIM). Namely, we posit that for several applications in EIM, the value of unstructured data is determined by the associations it captures between concepts. The more such associations in data, the more valuable it is. Next, we build a framework using data mining that "counts" the number of associations in data. Our framework uses clustering and frequent itemsets. It also normalizes for data size. We demonstrate our approach on two of the most widely used text benchmark datasets: Reuters and 20 Newsgroups. Our general intuition is that a corpus of professionally written news articles are more valuable (in the sense of capturing more associations between concepts) than newsgroup postings of variable quality written by non-experts. Our quantitative approach indeed reaches the same inference.

Groupon is a major e-commerce company. It is unique in the sense that it is not only a vendor of goods, but also of local deals (such as restaurants, spas, activities, etc.) that reflect various aspects of a user's interests. In this sense, Groupon has a complete view of its users' lifestyle preferences. This is different from e-commerce goods vendors, who, for instance, may not have direct insight into what restaurants are preferred by their users, or what nightlife they prefer. We may say that Groupon engages the entire "lifestyle persona" of its users. Motivated by this, we consider the large scale problem of mining such "lifestyle personas" from Groupon's activity data collected over 38 million e-commerce users. This includes users drawn from one of the world's largest mobile user bases. Our solution combines domain knowledge from e-commerce with data mining and graph theoretic methods. Since Groupon offers deals and goods across the 360 degree gamut of user preferences, do lifestyle personas in its data also span this gamut? What are some of the significant personas that emerge from this data mining? Are the differences between personas gross or subtle? These are some of the questions we answer conclusively in our study. Our mined personas are both descriptive and distinctive, and offer insights into customer behaviors and lifestyles. Our work is being used to redesign the user experience, as well as to power product recommendations at Groupon.

Customer Relationship Management (CRM) is currently the fastest growing sector of enterprise software, estimated to increase to $36.5B worldwide by 2017. CRM technologies increasingly use data mining primitives across multiple applications. At the same time, the growth of big data has led to the evolution of an open source big data software stack (primarily powered by Apache software) that rivals traditional enterprise database (RDBMS) stacks. New technologies such as Kafka, Storm, HBase have significantly enriched this open source stack, alongside more established technologies such as Hadoop MapReduce and Mahout. Today, enterprises have a choice to make regarding which stack they will choose to power their big data applications. However, there are no published studies in literature on enterprise big data pipelines built using open source components supporting CRM. Specific questions that enterprises have include: how is the data processed and analyzed in such pipelines? What are the building blocks of such pipelines? How long does each step of this processing take? In this work, we answer these questions for a large scale (serving over a 100M customers) industrial CRM pipeline that incorporates data mining, and serves several applications. Our pipeline has, broadly, two parts. The first is a data gathering part that uses Kafka, Storm, and HBase. The second is a data mining part that uses Mahout and Hadoop MapReduce. We also provide timings for common tasks in the second part such as data preprocessing for machine learning, clustering, reservoir sampling, and frequent itemset extraction.

Understanding how specific, ambiguous, or broad the intent of a search query is, across all users of the system, is important in improving search relevance in eCommerce. There is scant literature on such a structural characterization of queries in eCommerce. In this paper, we use query-click log data to address the problem of identifying "atypical queries": these are queries that are extremal in terms of specificity, ambiguity, or breadth of intent. We isolate three components of atypicality: geometric, statistical, and topological. We demonstrate, using query-click logs at Groupon, that certain combinations of these properties render a query atypical, and discuss how search analysts treat such queries differently. Our work is being used to improve search relevance at Groupon.

Naïve Bayes (NB) classifiers are well-suited to several applications owing to their easy interpretability and maintainability. However, text classification is often hampered by the lack of adequate training data. This motivates the question: how can we train NB more effectively whentraining data is very scarce?In this paper, we introduce an established subsampling techniquefrom statistics -- the jackknife -- into machine learning. Our approachjackknifes documents themselves to create new "pseudo-documents." Theunderlying idea is that although these pseudo-documents do not havesemantic meaning, they are equally representative of the underlyingdistribution of terms. Therefore, they could be used to train any classifierthat learns this underlying distribution, namely, any parametric classifiersuch as NB (but not, for example, non-parametric classifiers such as SVMand k-NN). Furthermore, the marginal value of this additional trainingdata should be the highest precisely when the original data is inadequate. We then show that our jackknife technique is related to the questionof additively smoothing NB via an appropriately defined notion of"adjointness." This relation is surprising since it connects a statisticaltechnique for handling scarce data to a question about the NB model. Accordingly, we are able to shed light on optimal values of the smoothingparameter for NB in the very scarce data regime. We validate our approach on a wide array of standard benchmarks -- both binary and multi-class -- for two event models of multinomial NB. Weshow that the jackknife technique can dramatically improve the accuracyfor both event models of NB in the regime of very scarce training data. Inparticular, our experiments show that the jackknife can make NB moreaccurate than SVM for binary problems in the very scarce training dataregime. We also provide a comprehensive characterization of the accuracyof these important classifiers (for both binary and multiclass) in the veryscarce data regime for benchmark text datasets, without feature selectionand class imbalance.

We investigate a frequently occurring issue in search (retrieval) in the age of big unstructured data. Searches conducted on large unstructured corpora result in long results lists. Such results lists are often clustered and reranked for ease of navigation. Should a query be revised during time-critical examinations of such long cluster based reranked lists? This question arises naturally during early stages of commercially important applications of IR such as eDiscovery, but has not yet been given any research attention. Four factors compound the difficulty of this question in the setting of eDiscovery: (a) the query sources (the technical experts) are different from the legal staff that are actually executing the query and using the retrieval system, (b) the retrieved lists for each query tend to be very long, and (c) the user might be accessing these retrieved results through a clustering interface, and (c) all decisions must be transparent and easy to explain due to the litigious nature of the application. Analogous difficulties arise in other applications involving search over large unstructured corpora. We introduce a framework to help users make the decision of “whether to revise.” Our framework consists of two components. First, we introduce a “limited view” which is a summary of a long cluster-based reranked list. This is the first input to the user. This provides the user a summary of the long cluster-based list. Second, we construct query predictors for this limited view, and provide their prediction as a second input to the user. This prediction is used to corroborate the inspection of the summary limited view. The proposed combination of a limited view and query performance prediction can assist search staff in determining whether to pursue an expensive query revision or not, as well as save precious time by precluding inspections of lists with very few relevant documents during the early stages of commercially important applications such as eDiscovery.

Feature selection is a natural choice of technique to scale up clustering. However, feature selection for clustering has received scant research attention compared to the vast literature on feature selection for classification. This is due to the absence of class labels in clustering. The approaches for feature selection for text clustering proposed in literature require (repeated) clustering of the entire corpus. We demonstrate that we can, instead, apply Monte Carlo (MC) techniques to “collect” features by inspecting only tiny portions of the entire dataset at any time. We do not require any global information about features to be computed over the entire dataset. We evaluate the trade-offs between the various cost parameters of the MC with the efficacy of the clustering produced and the time taken to produce it. Doing feature selection using MC, we are able to perform a clustering three to four times faster on standard text benchmarks. Such speed-up can enable near-real time clustering in enterprise workflows using limited memory.

The tasks, challenges, and techniques of Information Retrieval (IR) should reflect the structure of the underlying document-query sets, and the needs of the domain. Are document-query sets obtained from the enterprise domain fundamentally different from standard research corpora gathered from the web? In order to identify, understand, and characterize such structural differences, we build a framework using point set topology to analyze document-query sets. Our framework tailors topological notions such as subbasis, cover, compactness, towards IR. Unlike previous topological approaches, we use the reverse of the relevance map to topologize the set of queries, not the set of documents. We show that the topological approach exposes sharp differences between enterprise and web-collected standard research document-query sets. These differences readily motivate research into new retrieval tasks that are of commercial importance in Enterprise Information Management (EIM).

Consider the problem of finding the Top-k records in a relation based on the sum of their attributes. This problem occurs in various settings in big data management, for example in geographically distributed data centers and clouds, both at the application layer and the storage management layer. We propose a lightweight distributed, order and duplication insensitive approach based on order statistics. The salient feature of our algorithm that makes it extremely lightweight is that it only processes and communicates the items most likely to be in the Top-k. We validate the efficacy of our algorithm on a wide range of datasets.

We formulate a problem that arises in unstructured enterprise information management, and has high commercial impact: retrieve knowledge-rich documents in a large textual collection of technical documents. We call such documents principal documents.

Can we effectively influence aggregate user behavior in a cluster based retrieval (CBR) system by tuning its parameters? This question combines parameter tuning with models of user behavior. To address this question, we propose an approach based on three components: user model, criterion metric, and sensitivity analysis. We then demonstrate this approach on one of the most frequently asked questions to designers and operators of CBR systems in enterprises: namely, "suggest a value for k." Both the users and the system desire a value that is likely to maximize user satisfaction, and sway them towards a cluster based examination of their retrieved result set (rather than prefer the original ranked retrieved list). Based on observed user behavior in CBR systems, we posit a two-stage user model. We isolate its core element, which is a "query coverage metric." We then perform an empirical sensitivity analysis of this metric. Our analysis reveals that this metric is, surprisingly, robust to changes in k (i.e., insensitive to k) in a wide range around its de-facto value. We conclude that in cases where our model approximates user behavior, the system cannot substantially increase the chances of the user resorting to CBR by tuning k. This has practical implications on the design and day-to-day operation of CBR systems. Similar analyses can be carried out for other parameters.

Even today, most interfaces to document clustering present clusters to users and applications as a "bag of descriptive terms"? a technique that was proposed two decades ago. Consequently, users and applications are not able to obtain sophisticated structural knowledge that is indeed lying hidden in document clusters. In particular, the structural information about interaction of concepts that the cluster speaks about is completely missing from the bag of terms presentation. As the needs of unstructured information management increase, this shortcoming is coming into sharper focus. To address this shortcoming, we propose a rich representation of document clusters that surfaces the concept interactions within a cluster into the representation. We show that these interactions give a "shape" to the cluster. This "shape" is conveniently captured using a directed, colored, vertex-weighted graph, called the shape graph or, simply, the shape of the cluster. We show that shapes convey important structural information about document clusters, and can be computed efficiently.

Consider a two-component replica system having constant repair time for faults occurring on either component. Such a system models, for example, a RAID-4/5 storage array where two disks are mirrors of each other, and faults on one are corrected using data from the other. The object of our study is the loss function: namely, the distribution function of losses that result from a failure on the dual component during the time that an error in the first component is being repaired. Most previous studies of such systems make certain simplifying assumptions, in order to reduce them to a Markov system. The benefit of such a simplification is that the mean of the simplified loss function can be readily obtained. An example of such a mean is the frequently used `Mean Time to Data Loss (MTTDL)' for the example of RAID arrays. Such measures are then typically included in an empirical study using data gathered from actual systems. The disadvantage of such an approach is that we lose access to the actual distribution, which could potentially encode important information. In this work, we present a theoretical study of a two-component replica system. The target of the study is the entire loss function: namely, the probability density function (pdf) of the loss event. The obstacle to computing this pdf is that the underlying transition diagram is no longer a Markov chain with exponential transition probabilities. We compute the entire pdf of the loss function. In order to obtain this pdf, we use techniques from transform theory. Once the loss function is derived, information such as the number of times each component goes through repair, the differences in error probabilities at various time periods, etc. may be obtained from it. The exponential transitions in a Markov system are memory-less. There has been considerable debate regarding the suitability of a memoryless assumption on failures in a real-world system. Accordingly, we investigate the memoryless property at various stages of our derivation of the pdf of the loss function. We identify precisely the stages in the derivation of the loss function where a memoryless assumption is made. As expected, the final loss function for the dual-component scheme is not memoryless. However, somewhat surprisingly, it has a natural estimation using a memoryless loss function.

Asynchronous discussion forums are one of the artifacts of the internet age. They occur in a wide variety of applications from distance learning to technical support. Technical support forums have also proliferated in enterprises, and today form a salient feature of many technical interactions in large enterprises. Two interconnected example applications where such forums may be employed are the following: customer pre-sales, where sales teams attempt to answer queries of potential customers; and internal forums where technical staff attempt to provide assistance to sales teams on urgent issues that require immediate attention. In this paper, we report a study of an internal technical support forum for pre-sales in a large Fortune-10 global enterprise. The data being generated on such forums is fast evolving, requires quick and intelligent human (assisted by machine) responses, and is of high value to the enterprise since it directly affects sales. Owing to this, it poses unique challenges. We conduct a two-fold study of the forum. First, we study the metadata in the forum messages to understand the temporal, participant, and length profiles of messages. Second, we use text mining to detect trends in forums using clustering and information-theoretic techniques. To our knowledge, this is the first study of an enterprise internal technical support forum. As a focal point in our study, we describe the problem of identifying “hot” or “urgent” issues early, so that management can take requisite steps to deal with emerging problems. Our results are surprising: we show that threads that bring urgent issues to light have temporal, length, and content profiles that resemble that of non-urgent threads. Therefore, the detection of such threads via metadata and content analysis is difficult. We present a solution to this problem based on participant profiles.

Simple keyword based searches are ubiquitous in today's internet age. It is hard to imagine an information system today that does not permit a simple keyword based search. This method of information retrieval has the obvious benefits of being highly interpretable, and having wide usage. However, a general perception is that keyword search may not be as powerful an information retrieval paradigm as those that utilize data mining technologies. At the same time, the tremendous growth in textual information in various domains has also given impetus to data mining technologies such as document clustering. Document clustering is a powerful technique, having wide applications in enterprise information management (EIM). However, there is a general perception that the clusters it produces are not always easily interpretable. This hampers its usage in certain settings. This leads us to the following question: can we retrieve a cluster (from a corpus) using a keyword search with precision and recall that are reasonable from the point of view of a retrieval system? What is the form of such a keyword search? How many keywords do we require? How do we arrive at these keywords? Not only are these questions natural, they have immediate use in several highly regulated applications in EIM such as eDiscovery and compliance, where document sets must be specified using keywords. In order to answer our question, we construct a framework that uses maximal frequent discriminative item sets. The novelty of our usage of these item sets is that although their definition as frequent item sets is conjunctive, we use them to form a disjunctive query upon the corpus. We then study the results of this query as an information retrieval problem whose target is the cluster. Our study yields a surprising result: most clusters can be retrieved, up to reasonable precision and recall, using a disjunctive query of only three terms. Among other ramifications, this gives us a readily interpretable description of a cluster in terms of the disjunctive query that returns it.

Extending results of Schindler, Hamkins and Welch, we establish in the context of infinite time Turing machines that P is properly contained in NP ∩ co-NP. For higher analogues of these classes, we exhibit positive and negative results.

It is well known that a two-layer perceptron network with threshold neurons is incapable of forming arbitrary decision regions in input space, while a three-layer perceptron has that capability. The effect of replacing the output neuron in a two-layer perceptron with a bithreshold element is studied. The limitations of this modified two-layer perceptron are observed. Results on the separating capabilities of a pair of parallel hyperplanes are obtained. Based on these, a new two-layer neural paradigm based on increasing the dimensionality of the output of the first layer is proposed and is shown to be capable of forming any arbitrary decision region in input space. Then a type of logic called bithreshold logic, based on the bithreshold neuron transfer function, is studied. Results on the limits of switching function realizability using bithreshold gates are obtained.

Since the proof in 1982, by Tsfasman Vladut and Zink of the existence of algebraic-geometric (AG) codes with asymptotic performance exceeding the Gilbert-Varshamov (G-V) bound, one of the challenges in coding theory has been to provide explicit constructions for these codes. In a major step forward during 1995-1996, Garcia and Stichtenoth (GS) provided an explicit description of algebraic curves, such that AG codes constructed on them would have a performance better than the G-V bound. We present the first low-complexity algorithm for obtaining the generator matrix for AG codes on the curves of GS. The symbol alphabet of the AG code is the finite field of q/sup 2/, q/sup 2//spl ges/49, elements. The complexity of the algorithm, as measured in terms of multiplications and divisions over the finite field GF(q/sup 2/), is upper-bounded by [Nlog/sub q/(N)]/sup 3/ where N is the length of the code. An example of code construction using the above algorithm is presented. By concatenating the AG code with short binary block codes, it is possible to obtain binary codes with asymptotic performance close to the G-V bound. Some examples of such concatenation are included.

In this paper, the ability of a binary neural-network comprising only neurons with zero thresholds and binary weights to map given samples of a Boolean function is studied. A mathematical model describing a network with such restrictions is developed. It is shown that this model is quite amenable to algebraic manipulation. A key feature of the model is that it replaces the two input and output variables with a single "normalized" variable. The model is then used to provide a priori criteria, stated in terms of the new variable, that a given Boolean function must satisfy in order to be mapped by a network having one or two layers. These criteria provide necessary, and in the case of a one-layer network, sufficient conditions for samples of a Boolean function to be mapped by a binary neural network with zero thresholds. It is shown that the necessary conditions imposed by the two-layer network are, in some sense, minimal.