waashk/dblp huggingface dataset:
scalable mining of large disk-based graph databases. mining frequent structural patterns from graph databases is an interesting problem with broad applications. most of the previous studies focus on pruning unfruitful search subspaces effectively, but few of them address the mining on large, disk-based databases. as many graph databases in applications cannot be held into main memory, scalable mining of large, disk-based graph databases remains a challenging problem. in this paper, we develop an effective index structure, adi (for <u>ad</u>jacency <u>i</u>ndex), to support mining various graph patterns over large databases that cannot be held into main memory. the index is simple and efficient to build. moreover, the new index structure can be easily adopted in various existing graph pattern mining algorithms. as an example, we adapt the well-known gspan algorithm by using the adi structure. the experimental results show that the new index structure enables the scalable graph pattern mining over large databases. in one set of the experiments, the new disk-based method can mine graph databases with one million graphs, while the original gspan algorithm can only handle databases of up to 300 thousand graphs. moreover, our new method is faster than gspan when both can run in main memory.
suppressing model overfitting in mining concept-drifting data streams. mining data streams of changing class distributions is important for real-time business decision support. the stream classifier must evolve to reflect the current class distribution. this poses a serious challenge. on the one hand, relying on historical data may increase the chances of learning obsolete models. on the other hand, learning only from the latest data may lead to biased classifiers, as the latest data is often an unrepresentative sample of the current class distribution. the problem is particularly acute in classifying rare events, when, for example, instances of the rare class do not even show up in the most recent training data. in this paper, we use a stochastic model to describe the concept shifting patterns and formulate this problem as an optimization one: from the historical and the current training data that we have observed, find the most-likely current distribution, and learn a classifier based on the most-likely distribution. we derive an analytic solution and approximate this solution with an efficient algorithm, which calibrates the influence of historical data carefully to create an accurate classifier. we evaluate our algorithm with both synthetic and real-world datasets. our results show that our algorithm produces accurate and efficient classification.
mining user session data to facilitate user interaction with a customer service knowledge base in rightnow web. rightnow web is an integrated software package for web-based customer service that has, at its core, a database of answers to frequently asked questions (faqs). one major design goal is to facilitate end-user interaction with this dynamic document collection, i.e. make it as easy and efficient as possible for users to browse the collection and locate desired information. to this end, we perform several types of analysis on the session tracking database that records user navigation histories. first, using both explicit and implicit measures of user satisfaction, we infer a "solved count" representing the average utility of an faq. second, using the user navigation patterns we construct a link matrix representing connections between faqs. the technique of building up the link matrix and using it to advise users on related information amounts to a form of the "swarm intelligence" method of finding optimal paths. both solved count and the link matrix are continuously updated as users interact with the site; furthermore, they are periodically "aged" to emphasize recent activity. the synergistic combination of these techniques allows users to learn from the database in a more effective manner, as evidenced by usage statistics.
discovering associations with numeric variables. this paper further develops aumann and lindell's [3] proposal for a variant of association rules for which the consequent is a numeric variable. it is argued that these rules can discover useful interactions with numeric data that cannot be discovered directly using traditional association rules with discretization. alternative measures for identifying interesting rules are proposed. efficient algorithms are presented that enable these rules to be discovered for dense data sets for which application of auman and lindell's algorithm is infeasible.
discovering significant rules. in many applications, association rules will only be interesting if they represent non-trivial correlations between all constituent items. numerous techniques have been developed that seek to avoid false discoveries. however, while all provide useful solutions to aspects of this problem, none provides a generic solution that is both flexible enough to accommodate varying definitions of true and false discoveries and powerful enough to provide strict control over the risk of false discoveries. this paper presents generic techniques that allow definitions of true and false discoveries to be specified in terms of arbitrary statistical hypothesis tests and which provide strict control over the experiment wise risk of false discoveries.
on detecting differences between groups. understanding the differences between contrasting groups is a fundamental task in data analysis. this realization has led to the development of a new special purpose data mining technique, contrast-set mining. we undertook a study with a retail collaborator to compare contrast-set mining with existing rule-discovery techniques. to our surprise we observed that straightforward application of an existing commercial rule-discovery system, magnum opus, could successfully perform the contrast-set-mining task. this led to the realization that contrast-set mining is a special case of the more general rule-discovery task. we present the results of our study together with a proof of this conclusion.
a large-scale analysis of query logs for assessing personalization opportunities. query logs, the patterns of activity left by millions of users, contain a wealth of information that can be mined to aid personalization. we perform a large-scale study of yahoo! search engine logs, tracking 1.35 million browser-cookies over a period of 6 months. we define metrics to address questions such as 1) how much history is available?, 2) how do users' topical interests vary, as reflected by their queries?, and 3) what can we learn from user clicks? we find that there is significantly more expected history for the user of a randomly picked query than for a randomly picked user. we show that users exhibit consistent topical interests that vary between users. we also see that user clicks indicate a variety of special interests. our findings shed light on user activity and can inform future personalization efforts.
semi-supervised time series classification. the problem of time series classification has attracted great interest in the last decade. however current research assumes the existence of large amounts of labeled training data. in reality, such data may be very difficult or expensive to obtain. for example, it may require the time and expertise of cardiologists, space launch technicians, or other domain specialists. as in many other domains, there are often copious amounts of unlabeled data available. for example, the physiobank archive contains gigabytes of ecg data. in this work we propose a semi-supervised technique for building time series classifiers. while such algorithms are well known in text domains, we will show that special considerations must be made to make them both efficient and effective for the time series domain. we evaluate our work with a comprehensive set of experiments on diverse data sources including electrocardiograms, handwritten documents, and video datasets. the experimental results demonstrate that our approach requires only a handful of labeled examples to construct accurate classifiers.
knowledge-based data mining. we describe techniques for combining two types of knowledge systems: expert and machine learning. both the expert system and the learning system represent information by logical decision rules or trees. unlike the classical views of knowledge-base evaluation or refinement, our view accepts the contents of the knowledge base as completely correct. the knowledge base and the results of its stored cases will provide direction for the discovery of new relationships in the form of newly induced decision rules. an expert system called seas was built to discover sales leads for computer products and solutions. the system interviews executives by asking questions, and based on the responses, recommends products that may improve a business' operations. leveraging this expert system, we record the results of the interviews and the program's recommendations. the very same data stored by the expert system is used to find new predictive rules. among the potential advantages of this approach are (a) the capability to spot new sales trends and (b) the substitution of less expensive probabilistic rules that use database data instead of interviews.
a system for real-time competitive market intelligence. a method is described for real-time market intelligence and competitive analysis. news stories are collected online for a designated group of companies. the goal is to detect critical differences in the text written about a company versus the text for its competitors. a solution is found by mapping the task into a non-stationary text categorization model. the overall design consists of the following components: (a) a real-time crawler that monitors newswires for stories about the competitors (b) a conditional document retriever that selects only those documents that meet the indicated conditions (c) text analysis techniques that convert the documents to a numerical format (d) rule induction methods for finding patterns in data (e) presentation techniques for displaying results. the method is extended to combine text with numerical measures, such as those based on stock prices and market capitalizations, that allow for more objective evaluations and projections.
algorithms for estimating relative importance in networks. large and complex graphs representing relationships among sets of entities are an increasingly common focus of interest in data analysis---examples include social networks, web graphs, telecommunication networks, and biological networks. in interactive analysis of such data a natural query is "which entities are most important in the network relative to a particular individual or set of individuals?" we investigate the problem of answering such queries in this paper, focusing in particular on defining and computing the importance of nodes in a graph relative to one or more root nodes. we define a general framework and a number of different algorithms, building on ideas from social networks, graph theory, markov models, and web graph analysis. we experimentally evaluate the different properties of these algorithms on toy graphs and demonstrate how our approach can be used to study relative importance in real-world networks including a network of interactions among september 11th terrorists, a network of collaborative research in biotechnology among companies and universities, and a network of co-authorship relationships among computer science researchers.
privacy-preserving bayesian network structure computation on distributed heterogeneous data. as more and more activities are carried out using computers and computer networks, the amount of potentially sensitive data stored by business, governments, and other parties increases. different parties may wish to benefit from cooperative use of their data, but privacy regulations and other privacy concerns may prevent the parties from sharing their data. privacy-preserving data mining provides a solution by creating distributed data mining algorithms in which the underlying data is not revealed.in this paper, we present a privacy-preserving protocol for a particular data mining task: learning the bayesian network structure for distributed heterogeneous data. in this setting, two parties owning confidential databases wish to learn the structure of bayesian network on the combination of their databases without revealing anything about their data to each other. we give an efficient and privacy-preserving version of the k2 algorithm to construct the structure of a bayesian network for the parties' joint data.
screening and interpreting multi-item associations based on log-linear modeling. association rules have received a lot of attention in the data mining community since their introduction. the classical approach to find rules whose items enjoy high support (appear in a lot of the transactions in the data set) is, however, filled with shortcomings. it has been shown that support can be misleading as an indicator of how interesting the rule is. alternative measures, such as lift, have been proposed. more recently, a paper by dumouchel et al. proposed the use of all-two-factor loglinear models to discover sets of items that cannot be explained by pairwise associations between the items involved. this approach, however, has its limitations, since it stops short of considering higher order interactions (other than pairwise) among the items. in this paper, we propose a method that examines the parameters of the fitted loglinear models to find all the significant association patterns among the items. since fitting loglinear models for large data sets can be computationally prohibitive, we apply graph-theoretical results to divide the original set of items into components (sets of items) that are statistically independent from each other. we then apply loglinear modeling to each of the components and find the interesting associations among items in them. the technique is experimentally evaluated with a real data set (insurance data) and a series of synthetic data sets. the results show that the technique is effective in finding interesting associations among the items involved.
incremental approximate matrix factorization for speeding up support vector machines. traditional decomposition-based solutions to support vector machines (svms) suffer from the widely-known scalability problem. for example, given a one-million training set, it takes about six days for svmlight to run on a pentium-4 sever with 8g-byte memory. in this paper, we propose an incremental algorithm, which performs approximate matrix-factorization operations, to speed up svms. two approximate factorization schemes, kronecker and incomplete cholesky, are utilized in the primal-dual interior-point method (ipm) to directly solve the quadratic optimization problem in svms. we found out that a coarse approximate algorithm enjoys good speedup performance but may suffer from poor training accuracy. conversely, a fine-grained approximate algorithm enjoys good training quality but may suffer from long training time. we subsequently propose an incremental training algorithm, which uses the approximate ipm solution of a coarse factorization to initialize the ipm of a fine-grained factorization. extensive empirical studies show that our proposed incremental algorithm with approximate factorizations substantially speeds up svm training while maintaining high training accuracy. in addition, we show that our proposed algorithm is highly parallelizable on an intel dual-coreprocessor.
formulating distance functions via the kernel trick. tasks of data mining and information retrieval depend on a good distance function for measuring similarity between data instances. the most effective distance function must be formulated in a context-dependent (also application-, data-, and user-dependent) way. in this paper, we propose to learn a distance function by capturing the nonlinear relationships among contextual information provided by the application, data, or user. we show that through a process called the "kernel trick," such nonlinear relationships can be learned efficiently in a projected space. theoretically, we substantiate that our method is both sound and optimal. empirically, using several datasets and applications, we demonstrate that our method is effective and useful.
mining scale-free networks using geodesic clustering. many real-world graphs have been shown to be scale-free---vertex degrees follow power law distributions, vertices tend to cluster, and the average length of all shortest paths is small. we present a new model for understanding scale-free networks based on multilevel geodesic approximation, using a new data structure called a multilevel mesh.using this multilevel framework, we propose a new kind of graph clustering for data reduction of very large graph systems such as social, biological, or electronic networks. finally, we apply our algorithms to real-world social networks and protein interaction graphs to show that they can reveal knowledge embedded in underlying graph structures. we also demonstrate how our data structures can be used to quickly answer approximate distance and shortest path queries on scale-free networks.
the anatomy of a multimodal information filter. the proliferation of objectionable information on the internet has reached a level of serious concern. to empower end-users with the choice of blocking undesirable and offensive websites, we propose a multimodal information filter, named morf. in this paper, we present morf's core components: its confidence-based classifier, a cross-bagging ensemble scheme, and multimodal classification algorithm. empirical studies and initial statistics collected from the morf filters deployed at sites in the u.s. and asia show that morf is both efficient and effective, due to our classification methods.
a refinement approach to handling model misfit in text categorization. text categorization or classification is the automated assigning of text documents to pre-defined classes based on their contents. this problem has been studied in information retrieval, machine learning and data mining. so far, many effective techniques have been proposed. however, most techniques are based on some underlying models and/or assumptions. when the data fits the model well, the classification accuracy will be high. however, when the data does not fit the model well, the classification accuracy can be very low. in this paper, we propose a refinement approach to dealing with this problem of model misfit. we show that we do not need to change the classification technique itself (or its underlying model) to make it more flexible. instead, we propose to use successive refinements of classification on the training data to correct the model misfit. we apply the proposed technique to improve the classification performance of two simple and efficient text classifiers, the rocchio classifier and the na&iuml;ve bayesian classifier. these techniques are suitable for very large text collections because they allow the data to reside on disk and need only one scan of the data to build a text classifier. extensive experiments on two benchmark document corpora show that the proposed technique is able to improve text categorization accuracy of the two techniques dramatically. in particular, our refined model is able to improve the na&iuml;ve bayesian or rocchio classifier's prediction performance by 45% on average.
coherent closed quasi-clique discovery from large dense graph databases. frequent coherent subgraphs can provide valuable knowledge about the underlying internal structure of a graph database, and mining frequently occurring coherent subgraphs from large dense graph databases has been witnessed several applications and received considerable attention in the graph mining community recently. in this paper, we study how to efficiently mine the complete set of coherent closed quasi-cliques from large dense graph databases, which is an especially challenging task due to the downward-closure property no longer holds. by fully exploring some properties of quasi-cliques, we propose several novel optimization techniques, which can prune the unpromising and redundant sub-search spaces effectively. meanwhile, we devise an efficient closure checking scheme to facilitate the discovery of only closed quasi-cliques. we also develop a coherent closed quasi-clique mining algorithm, <b>cocain</b>1 thorough performance study shows that cocain is very efficient and scalable for large dense graph databases.
clicks: an effective algorithm for mining subspace clusters in categorical datasets. we present a novel algorithm called clicks, that finds clusters in categorical datasets based on a search for k-partite maximal cliques. unlike previous methods, clicks mines subspace clusters. it uses a selective vertical method to guarantee complete search. clicks outperforms previous approaches by over an order of magnitude and scales better than any of the existing method for high-dimensional datasets. these results are demonstrated in a comprehensive performance study on real and synthetic datasets.
experimental comparison of scalable online ad serving. online ad servers attempt to find best ads to serve for a given triggering user event. the performance of ads may be measured in several ways. we suggest a formulation in which the ad network tries to maximize revenue subject to relevance constraints. we describe several algorithms for ad selection and review their complexity. we tested these algorithms using microsoft ad network from october 1 2006 to february 8 2007. over 3 billion impressions, 8 million combinations of triggers with ads, and a number of algorithms were tested over this period. we discover curious differences between ad-servers aimed at revenue versus clickthrough rate.
a cross-collection mixture model for comparative text mining. in this paper, we define and study a novel text mining problem, which we refer to as comparative text mining (ctm). given a set of comparable text collections, the task of comparative text mining is to discover any latent common themes across all collections as well as summarize the similarity and differences of these collections along each common theme. this general problem subsumes many interesting applications, including business intelligence and opinion summarization. we propose a generative probabilistic mixture model for comparative text mining. the model simultaneously performs cross-collection clustering and within-collection clustering, and can be applied to an arbitrary set of comparable text collections. the model can be estimated efficiently using the expectation-maximization (em) algorithm. we evaluate the model on two different text data sets (i.e., a news article data set and a laptop review data set), and compare it with a baseline clustering method also based on a mixture model. experiment results show that the model is quite effective in discovering the latent common themes across collections and performs significantly better than our baseline mixture model.