OpenRaiser/Intern-Atlas huggingface dataset:
Discovery of significant emerging trends
Authors: Saurabh Goorha, Lyle H. Ungar
Venue: KDD
Year: 2010

We describe a system that monitors social and mainstream media to determine shifts in what people are thinking about a product or company. We process over 100,000 news articles, blog posts, review sites, and tweets a day for mentions of items (e.g., products) of interest, extract phrases that are mentioned near them, and determine which of the phrases are of greatest possible interest to, for example, brand managers. Case studies show a good ability to rapidly pinpoint emerging subjects buried deep in large volumes of data and then highlight those that are rising or falling in significance as they relate to the firms interests. The tool and algorithm improves the signal-to-noise ratio and pinpoints precisely the opportunities and risks that matter most to communications professionals and their organizations.
Topic dynamics: an alternative model of bursts in streams of topics
Authors: Dan He, Douglas Stott Parker Jr.
Venue: KDD
Year: 2010

For some time there has been increasing interest in the problem of monitoring the occurrence of topics in a stream of events, such as a stream of news articles. This has led to different models of bursts in these streams, i.e., periods of elevated occurrence of events. Today there are several burst definitions and detection algorithms, and their differences can produce very different results in topic streams. These definitions also share a fundamental problem: they define bursts in terms of an arrival rate. This approach is limiting; other stream dimensions can matter.
Tropical cyclone event sequence similarity search via dimensionality reduction and metric learning
Authors: Shen-Shyang Ho, Wenqing Tang, W. Timothy Liu
Venue: KDD
Year: 2010

The Earth Observing System Data and Information System (EOSDIS) is a comprehensive data and information system which archives, manages, and distributes Earth science data from the EOS spacecrafts. One non-existent capability in the EOSDIS is the retrieval of satellite sensor data based on weather events (such as tropical cyclones) similarity query output.
Versatile publishing for privacy preservation
Authors: Xin Jin, Mingyang Zhang, Nan Zhang, Gautam Das
Venue: KDD
Year: 2010

Motivated by the insufficiency of the existing quasi-identifier/sensitive-attribute (QI-SA) framework on modeling real-world privacy requirements for data publishing, we propose a novel versatile publishing scheme with which privacy requirements can be specified as an arbitrary set of privacy rules over attributes in the microdata table. To enable versatile publishing, we introduce the Guardian Normal Form (GNF), a novel method of publishing multiple sub-tables such that each sub-table is anonymized by an existing QI-SA publishing algorithm, while the combination of all published tables guarantees all privacy rules. We devise two algorithms, Guardian Decomposition (GD) and Utility-aware Decomposition (UAD), for decomposing a microdata table into GNF, and present extensive experiments over real-world datasets to demonstrate the effectiveness of both algorithms.
The next generation of transportation systems, greenhouse emissions, and data mining
Authors: Hillol Kargupta, João Gama, Wei Fan
Venue: KDD
Year: 2010

Controling Greenhouse gas (GHG) emissions for minimizing the impact on the environment is one of the major challenges in front of the human civilization. Although future concentrations, damages and costs are unknown, it
MineFleet®: an overview of a widely adopted distributed vehicle performance data mining system
Authors: Hillol Kargupta, Kakali Sarkar, Michael Gilligan
Venue: KDD
Year: 2010

This paper describes the MineFleet distributed vehicle performance data mining system designed for commercial fleets. MineFleet analyzes high throughput data streams onboard the vehicle, generates the analytics, sends those to the remote server over the wide-area wireless networks and offers them to the fleet managers using stand-alone and web-based user-interface. The paper describes the overall architecture of the system, business needs, and shares experience from successful large-scale commercial deployments. MineFleet is probably one of the first commercially successful distributed data stream mining systems. This patented technology has been adopted, productized, and commercially offered by many large companies in the mobile resource management and GPS fleet tracking industry. This paper offers an overview of the system and offers a detailed analysis of what made it work.
Semi-supervised feature selection for graph classification
Authors: Xiangnan Kong, Philip S. Yu
Venue: KDD
Year: 2010

The problem of graph classification has attracted great interest in the last decade. Current research on graph classification assumes the existence of large amounts of labeled training graphs. However, in many applications, the labels of graph data are very expensive or difficult to obtain, while there are often copious amounts of unlabeled graph data available. In this paper, we study the problem of semi-supervised feature selection for graph classification and propose a novel solution, called gSSC, to efficiently search for optimal subgraph features with labeled and unlabeled graphs. Different from existing feature selection methods in vector spaces which assume the feature set is given, we perform semi-supervised feature selection for graph data in a progressive way together with the subgraph feature mining process. We derive a feature evaluation criterion, named gSemi, to estimate the usefulness of subgraph features based upon both labeled and unlabeled graphs. Then we propose a branch-and-bound algorithm to efficiently search for optimal subgraph features by judiciously pruning the subgraph search space. Empirical studies on several real-world tasks demonstrate that our semi-supervised feature selection approach can effectively boost graph classification performances with semi-supervised feature selection and is very efficient by pruning the subgraph search space using both labeled and unlabeled graphs.
Dynamics of conversations
Authors: Ravi Kumar, Mohammad Mahdian, Mary McGlohon
Venue: KDD
Year: 2010

How do online conversations build? Is there a common model that human communication follows? In this work we explore these questions in detail. We analyze the structure of conversations in three different social datasets, namely, Usenet groups, Yahoo! Groups, and Twitter. We propose a simple mathematical model for the generation of basic conversation structures and then refine this model to take into account the identities of each member of the conversation.
Mining top-k frequent items in a data stream with flexible sliding windows
Authors: Hoang Thanh Lam, Toon Calders
Venue: KDD
Year: 2010

We study the problem of finding the k most frequent items in a stream of items for the recently proposed max-frequency measure. Based on the properties of an item, the max-frequency of an item is counted over a sliding window of which the length changes dynamically. Besides being parameterless, this way of measuring the support of items was shown to have the advantage of a faster detection of bursts in a stream, especially if the set of items is heterogeneous. The algorithm that was proposed for maintaining all frequent items, however, scales poorly when the number of items becomes large. Therefore, in this paper we propose, instead of reporting all frequent items, to only mine the top-k most frequent ones. First we prove that in order to solve this problem exactly, we still need a prohibitive amount of memory (at least linear in the number of items). Yet, under some reasonable conditions, we show both theoretically and empirically that a memory-efficient algorithm exists. A prototype of this algorithm is implemented and we present its performance w.r.t. memory-efficiency on real-life data and in controlled experiments with synthetic data.
Mining positive and negative patterns for relevance feature discovery
Authors: Yuefeng Li, Abdulmohsen Algarni, Ning Zhong
Venue: KDD
Year: 2010

It is a big challenge to guarantee the quality of discovered relevance features in text documents for describing user preferences because of the large number of terms, patterns, and noise. Most existing popular text mining and classification methods have adopted term-based approaches. However, they have all suffered from the problems of polysemy and synonymy. Over the years, people have often held the hypothesis that pattern-based methods should perform better than term-based ones in describing user preferences, but many experiments do not support this hypothesis. The innovative technique presented in paper makes a breakthrough for this difficulty. This technique discovers both positive and negative patterns in text documents as higher level features in order to accurately weight low-level features (terms) based on their specificity and their distributions in the higher level features. Substantial experiments using this technique on Reuters Corpus Volume 1 and TREC topics show that the proposed approach significantly outperforms both the state-of-the-art term-based methods underpinned by Okapi BM25, Rocchio or Support Vector Machine and pattern based methods on precision, recall and F measures.
Negative correlations in collaboration: concepts and algorithms
Authors: Jinyan Li, Qian Liu, Tao Zeng
Venue: KDD
Year: 2010

This paper studies efficient mining of negative correlations that pace in collaboration. A collaborating negative correlation is a negative correlation between two sets of variables rather than traditionally between a pair of variables. It signifies a synchronized value rise or fall of all variables within one set whenever all variables in the other set go jointly at the opposite trend. The time complexity is exponential in mining. The high efficiency of our algorithm is attributed to two factors: (i) the transformation of the original data into a bipartite graph database, and (ii) the mining of transpose closures from a wide transactional database. Applying to a Yeast gene expression data, we evaluate, by using Pearson's correlation coefficient and P-value, the biological relevance of collaborating negative correlations as an example among many real-life domains.
Privacy-preserving outsourcing support vector machines with random transformation
Authors: Keng-Pei Lin, Ming-Syan Chen
Venue: KDD
Year: 2010

Outsourcing the training of support vector machines (SVM) to external service providers benefits the data owner who is not familiar with the techniques of the SVM or has limited computing resources. In outsourcing, the data privacy is a critical issue for some legal or commercial reasons since there may be sensitive information contained in the data. Existing privacy-preserving SVM works are either not applicable to outsourcing or weak in security. In this paper, we propose a scheme for privacy-preserving outsourcing the training of the SVM without disclosing the actual content of the data to the service provider. In the proposed scheme, the data sent to the service provider is perturbed by a random transformation, and the service provider trains the SVM for the data owner from the perturbed data. The proposed scheme is stronger in security than existing techniques, and incurs very little redundant communication and computation cost.
Towards mobility-based clustering
Authors: Siyuan Liu, Yunhuai Liu, Lionel M. Ni, Jianping Fan, Minglu Li
Venue: KDD
Year: 2010

Identifying hot spots of moving vehicles in an urban area is essential to many smart city applications. The practical research on hot spots in smart city presents many unique features, such as highly mobile environments, supremely limited size of sample objects, and the non-uniform, biased samples. All these features have raised new challenges that make the traditional density-based clustering algorithms fail to capture the real clustering property of objects, making the results less meaningful. In this paper we propose a novel, non-density-based approach called mobility-based clustering. The key idea is that sample objects are employed as "sensors" to perceive the vehicle crowdedness in nearby areas using their instant mobility, rather than the "object representatives". As such the mobility of samples is naturally incorporated. Several key factors beyond the vehicle crowdedness have been identified and techniques to compensate these effects are proposed. We evaluate the performance of mobility-based clustering based on real traffic situations. Experimental results show that using 0.3% of vehicles as the samples, mobility-based clustering can accurately identify hot spots which can hardly be obtained by the latest representative algorithm UMicro.
Data mining in the online services industry
Authors: Qi Lu
Venue: KDD
Year: 2010

The online services industry is a rapidly growing industry with a worldwide online ad market projected to grow from $48 billion in 2011 to $67 billion in 2013, of which 47% will come from display advertising and 53% from search advertising. Online Services Division (OSD) within Microsoft is a leader in the consumer cloud space today with a strong portfolio of a set of 3 mutually reinforcing businesses: Search, Portal, Advertising. They are supported by a shared foundational asset of Intent & Knowledge Stores and a shared technology platform supporting large scale data and high performance systems. MSN (Portal) and Bing (Search) generate the content, traffic and data, that make for an exciting fertile environment for large scale data mining practice and system development. Our advertisers are thus given more valuable targeting opportunities and better ROI, which in turn, provide better economics, usability data, and allows for a higher quality services for our advertisers and experience for our users. The ability to transform data into meaningful, actionable insight is an important source of competitive advantage for OSD. The data mining initiatives within the division continue to strive for excellence around the following goals: actionable insights through deep data analysis, data mining and data modeling at scale and with speed, increased productivity from deployed large scale data systems and tools, improved product and service development and decision making gained from effective measurement and experimentation, and a mature data culture in product teams that made the above possible. With many technical and data challenges ahead of us, we are committed to utilizing our huge data asset well to understand the need, intent, and behavior of our users for the purpose of serving them better.
The topic-perspective model for social tagging systems
Authors: Caimei Lu, Xiaohua Hu, Xin Chen, Jung-ran Park, Tingting He, Zhoujun Li
Venue: KDD
Year: 2010

In this paper, we propose a new probabilistic generative model, called Topic-Perspective Model, for simulating the generation process of social annotations. Different from other generative models, in our model, the tag generation process is separated from the content term generation process. While content terms are only generated from resource topics, social tags are generated by resource topics and user perspectives together. The proposed probabilistic model can produce more useful information than any other models proposed before. The parameters learned from this model include: (1) the topical distribution of each document, (2) the perspective distribution of each user, (3) the word distribution of each topic, (4) the tag distribution of each topic, (5) the tag distribution of each user perspective, (6) and the probabilistic of each tag being generated from resource topics or user perspectives. Experimental results show that the proposed model has better generalization performance or tag prediction ability than other two models proposed in previous research.
Fast euclidean minimum spanning tree: algorithm, analysis, and applications
Authors: William B. March, Parikshit Ram, Alexander G. Gray
Venue: KDD
Year: 2010

The Euclidean Minimum Spanning Tree problem has applications in a wide range of fields, and many efficient algorithms have been developed to solve it. We present a new, fast, general EMST algorithm, motivated by the clustering and analysis of astronomical data. Large-scale astronomical surveys, including the Sloan Digital Sky Survey, and large simulations of the early universe, such as the Millennium Simulation, can contain millions of points and fill terabytes of storage. Traditional EMST methods scale quadratically, and more advanced methods lack rigorous runtime guarantees. We present a new dual-tree algorithm for efficiently computing the EMST, use adaptive algorithm analysis to prove the tightest (and possibly optimal) runtime bound for the EMST problem to-date, and demonstrate the scalability of our method on astronomical data sets.
DivRank: the interplay of prestige and diversity in information networks
Authors: Qiaozhu Mei, Jian Guo, Dragomir R. Radev
Venue: KDD
Year: 2010

Information networks are widely used to characterize the relationships between data items such as text documents. Many important retrieval and mining tasks rely on ranking the data items based on their centrality or prestige in the network. Beyond prestige, diversity has been recognized as a crucial objective in ranking, aiming at providing a non-redundant and high coverage piece of information in the top ranked results. Nevertheless, existing network-based ranking approaches either disregard the concern of diversity, or handle it with non-optimized heuristics, usually based on greedy vertex selection.
Generative models for ticket resolution in expert networks
Authors: Gengxin Miao, Louise E. Moser, Xifeng Yan, Shu Tao, Yi Chen, Nikos Anerousis
Venue: KDD
Year: 2010

Ticket resolution is a critical, yet challenging, aspect of the delivery of IT services. A large service provider needs to handle, on a daily basis, thousands of tickets that report various types of problems. Many of those tickets bounce among multiple expert groups before being transferred to the group with the right expertise to solve the problem. Finding a methodology that reduces such bouncing and hence shortens ticket resolution time is a long-standing challenge. In this paper, we present a unified generative model, the Optimized Network Model (ONM), that characterizes the lifecycle of a ticket, using both the content and the routing sequence of the ticket. ONM uses maximum likelihood estimation, to represent how the information contained in a ticket is used by human experts to make ticket routing decisions. Based on ONM, we develop a probabilistic algorithm to generate ticket routing recommendations for new tickets in a network of expert groups. Our algorithm calculates all possible routes to potential resolvers and makes globally optimal recommendations, in contrast to existing classification methods that make static and locally optimal recommendations. Experiments show that our method significantly outperforms existing solutions.
Growing a tree in the forest: constructing folksonomies by integrating structured metadata
Authors: Anon Plangprasopchok, Kristina Lerman, Lise Getoor
Venue: KDD
Year: 2010

Many social Web sites allow users to annotate the content with descriptive metadata, such as tags, and more recently to organize content hierarchically. These types of structured metadata provide valuable evidence for learning how a community organizes knowledge. For instance, we can aggregate many personal hierarchies into a common taxonomy, also known as a folksonomy, that will aid users in visualizing and browsing social content, and also to help them in organizing their own content. However, learning from social metadata presents several challenges, since it is sparse, shallow, ambiguous, noisy, and inconsistent. We describe an approach to folksonomy learning based on relational clustering, which exploits structured metadata contained in personal hierarchies. Our approach clusters similar hierarchies using their structure and tag statistics, then incrementally weaves them into a deeper, bushier tree. We study folksonomy learning using social metadata extracted from the photo-sharing site Flickr, and demonstrate that the proposed approach addresses the challenges. Moreover, comparing to previous work, the approach produces larger, more accurate folksonomies, and in addition, scales better.
Class-specific error bounds for ensemble classifiers
Authors: Ryan J. Prenger, Tracy D. Lemmond, Kush R. Varshney, Barry Y. Chen, William G. Hanley
Venue: KDD
Year: 2010

The generalization error, or probability of misclassification, of ensemble classifiers has been shown to be bounded above by a function of the mean correlation between the constituent (i.e., base) classifiers and their average strength. This bound suggests that increasing the strength and/or decreasing the correlation of an ensemble's base classifiers may yield improved performance under the assumption of equal error costs. However, this and other existing bounds do not directly address application spaces in which error costs are inherently unequal. For applications involving binary classification, Receiver Operating Characteristic (ROC) curves, performance curves that explicitly trade off false alarms and missed detections, are often utilized to support decision making. To address performance optimization in this context, we have developed a lower bound for the entire ROC curve that can be expressed in terms of the class-specific strength and correlation of the base classifiers.
Redefining class definitions using constraint-based clustering: an application to remote sensing of the earth's surface
Authors: Dan Preston, Carla E. Brodley, Roni Khardon, Damien Sulla-Menashe, Mark A. Friedl
Venue: KDD
Year: 2010

Two aspects are crucial when constructing any real world supervised classification task: the set of classes whose distinction might be useful for the domain expert, and the set of classifications that can actually be distinguished by the data. Often a set of labels is defined with some initial intuition but these are not the best match for the task. For example, labels have been assigned for land cover classification of the Earth but it has been suspected that these labels are not ideal and some classes may be best split into subclasses whereas others should be merged. This paper formalizes this problem using three ingredients: the existing class labels, the underlying separability in the data, and a special type of input from the domain expert. We require a domain expert to specify an L × L matrix of pairwise probabilistic constraints expressing their beliefs as to whether the L classes should be kept separate, merged, or split. This type of input is intuitive and easy for experts to supply. We then show that the problem can be solved by casting it as an instance of penalized probabilistic clustering (PPC). Our method, Class-Level PPC (CPPC) extends PPC showing how its time complexity can be reduced from O(N2) to O(NL) for the problem of class re-definition. We further extend the algorithm by presenting a heuristic to measure adherence to constraints, and providing a criterion for determining the model complexity (number of classes) for constraint-based clustering. We demonstrate and evaluate CPPC on artificial data and on our motivating domain of land cover classification. For the latter, an evaluation by domain experts shows that the algorithm discovers novel class definitions that are better suited to land cover classification than the original set of labels.