waashk/dblp huggingface dataset:
bgp-lens: patterns and anomalies in internet routing updates. the border gateway protocol (bgp) is one of the fundamental computer communication protocols. monitoring and mining bgp update messages can directly reveal the health and stability of internet routing. here we make two contributions: firstly we find patterns in bgp updates, like self-similarity, power-law and lognormal marginals; secondly using these patterns, we find anomalies. specifically, we develop bgp-lens, an automated bgp updates analysis tool, that has three desirable properties: (a) it is effective, able to identify phenomena that would otherwise go unnoticed, such as a peculiar 'clothesline' behavior or prolonged 'spikes' that last as long as 8 hours; (b) it is scalable, using algorithms are all linear on the number of time-ticks; and (c) it is admin-friendly, giving useful leads for phenomenon of interest. we showcase the capabilities of bgp-lens by identifying surprising phenomena verified by syadmins, over a massive trace of bgp updates spanning 2 years, from the publicly available site datapository.net.
wherenext: a location predictor on trajectory pattern mining. the pervasiveness of mobile devices and location based services is leading to an increasing volume of mobility data.this side eect provides the opportunity for innovative methods that analyse the behaviors of movements. in this paper we propose wherenext, which is a method aimed at predicting with a certain level of accuracy the next location of a moving object. the prediction uses previously extracted movement patterns named trajectory patterns, which are a concise representation of behaviors of moving objects as sequences of regions frequently visited with a typical travel time. a decision tree, named t-pattern tree, is built and evaluated with a formal training and test process. the tree is learned from the trajectory patterns that hold a certain area and it may be used as a predictor of the next location of a new trajectory finding the best matching path in the tree. three dierent best matching methods to classify a new moving object are proposed and their impact on the quality of prediction is studied extensively. using trajectory patterns as predictive rules has the following implications: (i) the learning depends on the movement of all available objects in a certain area instead of on the individual history of an object; (ii) the prediction tree intrinsically contains the spatio-temporal properties that have emerged from the data and this allows us to define matching methods that striclty depend on the properties of such movements. in addition, we propose a set of other measures, that evaluate a priori the predictive power of a set of trajectory patterns. this measures were tuned on a real life case study. finally, an exhaustive set of experiments and results on the real dataset are presented.
a lrt framework for fast spatial anomaly detection. given a spatial data set placed on an n x n grid, our goal is to find the rectangular regions within which subsets of the data set exhibit anomalous behavior. we develop algorithms that, given any user-supplied arbitrary likelihood function, conduct a likelihood ratio hypothesis test (lrt) over each rectangular region in the grid, rank all of the rectangles based on the computed lrt statistics, and return the top few most interesting rectangles. to speed this process, we develop methods to prune rectangles without computing their associated lrt statistics.
beyond blacklists: learning to detect malicious web sites from suspicious urls. malicious web sites are a cornerstone of internet criminal activities. as a result, there has been broad interest in developing systems to prevent the end user from visiting such sites. in this paper, we describe an approach to this problem based on automated url classification, using statistical methods to discover the tell-tale lexical and host-based properties of malicious web site urls. these methods are able to learn highly predictive models by extracting and automatically analyzing tens of thousands of features potentially indicative of suspicious urls. the resulting classifiers obtain 95-99% accuracy, detecting large numbers of malicious web sites from their urls, with only modest false positives.
predicting bounce rates in sponsored search advertisements. this paper explores an important and relatively unstudied quality measure of a sponsored search advertisement: bounce rate. the bounce rate of an ad can be informally defined as the fraction of users who click on the ad but almost immediately move on to other tasks. a high bounce rate can lead to poor advertiser return on investment, and suggests search engine users may be having a poor experience following the click. in this paper, we first provide quantitative analysis showing that bounce rate is an effective measure of user satisfaction. we then address the question, can we predict bounce rate by analyzing the features of the advertisement? an affirmative answer would allow advertisers and search engines to predict the effectiveness and quality of advertisements before they are shown. we propose solutions to this problem involving large-scale learning methods that leverage features drawn from ad creatives in addition to their keywords and landing pages.
clustering event logs using iterative partitioning. the importance of event logs, as a source of information in systems and network management cannot be overemphasized. with the ever increasing size and complexity of today's event logs, the task of analyzing event logs has become cumbersome to carry out manually. for this reason recent research has focused on the automatic analysis of these log files. in this paper we present iplom (iterative partitioning log mining), a novel algorithm for the mining of clusters from event logs. through a 3-step hierarchical partitioning process iplom partitions log data into its respective clusters. in its 4th and final stage iplom produces cluster descriptions or line formats for each of the clusters produced. unlike other similar algorithms iplom is not based on the apriori algorithm and it is able to find clusters in data whether or not its instances appear frequently. evaluations show that iplom outperforms the other algorithms statistically significantly, and it is also able to achieve an average f-measure performance 78% when the closest other algorithm achieves an f-measure performance of 10%.
dynammo: mining and summarization of coevolving sequences with missing values. given multiple time sequences with missing values, we propose dynammo which summarizes, compresses, and finds latent variables. the idea is to discover hidden variables and learn their dynamics, making our algorithm able to function even when there are missing values. we performed experiments on both real and synthetic datasets spanning several megabytes, including motion capture sequences and chlorine levels in drinking water. we show that our proposed dynammo method (a) can successfully learn the latent variables and their evolution; (b) can provide high compression for little loss of reconstruction accuracy; (c) can extract compact but powerful features for segmentation, interpretation, and forecasting; (d) has complexity linear on the duration of sequences.
incorporating site-level knowledge for incremental crawling of web forums: a list-wise strategy. we study in this paper the problem of incremental crawling of web forums, which is a very fundamental yet challenging step in many web applications. traditional approaches mainly focus on scheduling the revisiting strategy of each individual page. however, simply assigning different weights for different individual pages is usually inefficient in crawling forum sites because of the different characteristics between forum sites and general websites. instead of treating each individual page independently, we propose a list-wise strategy by taking into account the site-level knowledge. such site-level knowledge is mined through reconstructing the linking structure, called sitemap, for a given forum site. with the sitemap, posts from the same thread but distributed on various pages can be concatenated according to their timestamps. after that, for each thread, we employ a regression model to predict the time when the next post arrives. based on this model, we develop an efficient crawler which is 260% faster than some state-of-the-art methods in terms of fetching new generated content; and meanwhile our crawler also ensure a high coverage ratio. experimental results show promising performance of coverage, bandwidth utilization, and timeliness of our crawler on 18 various forums.
augmenting the generalized hough transform to enable the mining of petroglyphs. rock art is an archaeological term for human-made markings on stone. it is believed that there are millions of petroglyphs in north america alone, and the study of this valued cultural resource has implications even beyond anthropology and history. surprisingly, although image processing, information retrieval and data mining have had large impacts on many human endeavors, they have had essentially zero impact on the study of rock art. in this work we identify the reasons for this, and introduce a novel distance measure and algorithms which allow efficient and effective data mining of large collections of rock art.
adapting the right measures for k-means clustering. clustering validation is a long standing challenge in the clustering literature. while many validation measures have been developed for evaluating the performance of clustering algorithms, these measures often provide inconsistent information about the clustering performance and the best suitable measures to use in practice remain unknown. this paper thus fills this crucial void by giving an organized study of 16 external validation measures for k-means clustering. specifically, we first introduce the importance of measure normalization in the evaluation of the clustering performance on data with imbalanced class distributions. we also provide normalization solutions for several measures. in addition, we summarize the major properties of these external measures. these properties can serve as the guidance for the selection of validation measures in different application scenarios. finally, we reveal the interrelationships among these external measures. by mathematical transformation, we show that some validation measures are equivalent. also, some measures have consistent validation performances. most importantly, we provide a guide line to select the most suitable validation measures for k-means clustering.
feature shaping for linear svm classifiers. linear classifiers have been shown to be effective for many discrimination tasks. irrespective of the learning algorithm itself, the final classifier has a weight to multiply by each feature. this suggests that ideally each input feature should be linearly correlated with the target variable (or anti-correlated), whereas raw features may be highly non-linear. in this paper, we attempt to re-shape each input feature so that it is appropriate to use with a linear weight and to scale the different features in proportion to their predictive value. we demonstrate that this pre-processing is beneficial for linear svm classifiers on a large benchmark of text classification tasks as well as uci datasets.
mining brain region connectivity for alzheimer's disease study via sparse inverse covariance estimation. effective diagnosis of alzheimer's disease (ad), the most common type of dementia in elderly patients, is of primary importance in biomedical research. recent studies have demonstrated that ad is closely related to the structure change of the brain network, i.e., the connectivity among different brain regions. the connectivity patterns will provide useful imaging-based biomarkers to distinguish normal controls (nc), patients with mild cognitive impairment (mci), and patients with ad. in this paper, we investigate the sparse inverse covariance estimation technique for identifying the connectivity among different brain regions. in particular, a novel algorithm based on the block coordinate descent approach is proposed for the direct estimation of the inverse covariance matrix. one appealing feature of the proposed algorithm is that it allows the user feedback (e.g., prior domain knowledge) to be incorporated into the estimation process, while the connectivity patterns can be discovered automatically. we apply the proposed algorithm to a collection of fdg-pet images from 232 nc, mci, and ad subjects. our experimental results demonstrate that the proposed algorithm is promising in revealing the brain region connectivity differences among these groups.
a multi-relational approach to spatial classification. spatial classification is the task of learning models to predict class labels based on the features of entities as well as the spatial relationships to other entities and their features. spatial data can be represented as multi-relational data, however it presents novel challenges not present in multi-relational problems. one such problem is that spatial relationships are embedded in space, unknown a priori, and it is part of the algorithm's task to determine which relationships are important and what properties to consider. in order to determine when two entities are spatially related in an adaptive and non-parametric way, we propose a voronoi-based neighbourhood definition upon which spatial literals can be built. properties of these neighbourhoods also need to be described and used for classification purposes. non-spatial aggregation literals already exist within the multi-relational framework, but are not sufficient for comprehensive spatial classification. a formal set of additions to the multi-relational data mining framework is proposed, to be able to represent spatial aggregations as well as spatial features and literals. these additions allow for capturing more complex interactions and spatial occurrences such as spatial trends. in order to more efficiently perform the rule learning and exploit powerful multi-processor machines, a scalable parallelized method capable of reducing the runtime by several factors is presented. the method is compared against existing methods by experimental evaluation on a real world crime dataset which demonstrate the importance of the neighbourhood definition and the advantages of parallelization.
data mining at nasa: from theory to applications. nasa has some of the largest and most complex data sources in the world, with data sources ranging from the earth sciences, space sciences, and massive distributed engineering data sets from commercial aircraft and spacecraft. this talk will discuss some of the issues and algorithms developed to analyze and discover patterns in these data sets. we will also provide an overview of a large research program in integrated vehicle health management. the goal of this program is to develop advanced technologies to automatically detect, diagnose, predict, and mitigate adverse events during the flight of an aircraft. a case study will be presented on a recent data mining analysis performed to support the flight readiness review of the space shuttle mission sts-119.
metafac: community discovery via relational hypergraph factorization. this paper aims at discovering community structure in rich media social networks, through analysis of time-varying, multi-relational data. community structure represents the latent social context of user actions. it has important applications in information tasks such as search and recommendation. social media has several unique challenges. (a) in social media, the context of user actions is constantly changing and co-evolving; hence the social context contains time-evolving multi-dimensional relations. (b) the social context is determined by the available system features and is unique in each social media website. in this paper we propose metafac (metagraph factorization), a framework that extracts community structures from various social contexts and interactions. our work has three key contributions: (1) metagraph, a novel relational hypergraph representation for modeling multi-relational and multi-dimensional social data; (2) an efficient factorization method for community extraction on a given metagraph; (3) an on-line method to handle time-varying relations through incremental metagraph factorization. extensive experiments on real-world social data collected from the digg social media website suggest that our technique is scalable and is able to extract meaningful communities based on the social media contexts. we illustrate the usefulness of our framework through prediction tasks. we outperform baseline methods (including aspect model and tensor analysis) by an order of magnitude.
regret-based online ranking for a growing digital library. the most common environment in which ranking is used takes a very specific form. users sequentially generate queries in a digital library. for each query, ranking is applied to order a set of relevant items from which the user selects his favorite. this is the case when ranking search results for pages on the world wide web or for merchandize on an e-commerce site. in this work, we present a new online ranking algorithm, called noregret klrank. our algorithm is designed to use "clickthrough" information as it is provided by the users to improve future ranking decisions. more importantly, we show that its long term average performance will converge to the best rate achievable by any competing fixed ranking policy selected with the benefit of hindsight. we show how to ensure that this property continues to hold as new items are added to the set thus requiring a richer class of ranking policies. finally, our empirical results show that, while in some context noregret klrank might be considered conservative, a greedy variant of this algorithm actually outperforms many popular ranking algorithms.
constant-factor approximation algorithms for identifying dynamic communities. we propose two approximation algorithms for identifying communities in dynamic social networks. communities are intuitively characterized as "unusually densely knit" subsets of a social network. this notion becomes more problematic if the social interactions change over time. aggregating social networks over time can radically misrepresent the existing and changing community structure. recently, we have proposed an optimization-based framework for modeling dynamic community structure. also, we have proposed an algorithm for finding such structure based on maximum weight bipartite matching. in this paper, we analyze its performance guarantee for a special case where all actors can be observed at all times. in such instances, we show that the algorithm is a small constant factor approximation of the optimum. we use a similar idea to design an approximation algorithm for the general case where some individuals are possibly unobserved at times, and to show that the approximation factor increases twofold but remains a constant regardless of the input size. this is the first algorithm for inferring communities in dynamic networks with a provable approximation guarantee. we demonstrate the general algorithm on real data sets. the results confirm the efficiency and effectiveness of the algorithm in identifying dynamic communities.
on burstiness-aware search for document sequences. as the number and size of large timestamped collections (e.g. sequences of digitized newspapers, periodicals, blogs) increase, the problem of efficiently indexing and searching such data becomes more important. term burstiness has been extensively researched as a mechanism to address event detection in the context of such collections. in this paper, we explore how burstiness information can be further utilized to enhance the search process. we present a novel approach to model the burstiness of a term, using discrepancy theory concepts. this allows us to build a parameter-free, linear-time approach to identify the time intervals of maximum burstiness for a given term. finally, we describe the first burstiness-driven search framework and thoroughly evaluate our approach in the context of different scenarios.
learning dynamic temporal graphs for oil-production equipment monitoring system. learning temporal graph structures from time series data reveals important dependency relationships between current observations and histories. most previous work focuses on learning and predicting with "static" temporal graphs only. however, in many applications such as mechanical systems and biology systems, the temporal dependencies might change over time. in this paper, we develop a dynamic temporal graphical models based on hidden markov model regression and lasso-type algorithms. our method is able to integrate two usually separate tasks, i.e. inferring underlying states and learning temporal graphs, in one unified model. the output temporal graphs provide better understanding about complex systems, i.e. how their dependency graphs evolve over time, and achieve more accurate predictions. we examine our model on two synthetic datasets as well as a real application dataset for monitoring oil-production equipment to capture different stages of the system, and achieve promising results.
social influence analysis in large-scale networks. in large social networks, nodes (users, entities) are influenced by others for various reasons. for example, the colleagues have strong influence on one's work, while the friends have strong influence on one's daily life. how to differentiate the social influences from different angles(topics)? how to quantify the strength of those social influences? how to estimate the model on real large networks? to address these fundamental questions, we propose topical affinity propagation (tap) to model the topic-level social influence on large networks. in particular, tap can take results of any topic modeling and the existing network structure to perform topic-level influence propagation. with the help of the influence analysis, we present several important applications on real data sets such as 1) what are the representative nodes on a given topic? 2) how to identify the social influences of neighboring nodes on a particular node? to scale to real large networks, tap is designed with efficient distributed learning algorithms that is implemented and tested under the map-reduce framework. we further present the common characteristics of distributed learning algorithms for map-reduce. finally, we demonstrate the effectiveness and efficiency of tap on real large data sets.
collaborative filtering with temporal dynamics. customer preferences for products are drifting over time. product perception and popularity are constantly changing as new selection emerges. similarly, customer inclinations are evolving, leading them to ever redefine their taste. thus, modeling temporal dynamics is essential for designing recommender systems or general customer preference models. however, this raises unique challenges. within the ecosystem intersecting multiple products and customers, many different characteristics are shifting simultaneously, while many of them influence each other and often those shifts are delicate and associated with a few data instances. this distinguishes the problem from concept drift explorations, where mostly a single concept is tracked. classical time-window or instance decay approaches cannot work, as they lose too many signals when discarding data instances. a more sensitive approach is required, which can make better distinctions between transient effects and long-term patterns. we show how to model the time changing behavior throughout the life span of the data. such a model allows us to exploit the relevant components of all data instances, while discarding only what is modeled as being irrelevant. accordingly, we revamp two leading collaborative filtering recommendation approaches. evaluation is made on a large movie-rating dataset underlying the netflix prize contest. results are encouraging and better than those previously reported on this dataset. in particular, methods described in this paper play a significant role in the solution that won the netflix contest.