text:
}

@article{10.1145/1644873.1644878,
author = {Zaki, Mohammed J. and Carothers, Christopher D. and Szymanski, Boleslaw K.},
title = {VOGUE: A Variable Order Hidden Markov Model with Duration Based on Frequent Sequence Mining},
year = {2010},
issue_date = {January 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1644873.1644878},
doi = {10.1145/1644873.1644878},
abstract = {We present VOGUE, a novel, variable order hidden Markov model with state durations, that combines two separate techniques for modeling complex patterns in sequential data: pattern mining and data modeling. VOGUE relies on a variable gap sequence mining method to extract frequent patterns with different lengths and gaps between elements. It then uses these mined sequences to build a variable order hidden Markov model (HMM), that explicitly models the gaps. The gaps implicitly model the order of the HMM, and they explicitly model the duration of each state. We apply VOGUE to a variety of real sequence data taken from domains such as protein sequence classification, Web usage logs, intrusion detection, and spelling correction. We show that VOGUE has superior classification accuracy compared to regular HMMs, higher-order HMMs, and even special purpose HMMs like HMMER, which is a state-of-the-art method for protein classification. The VOGUE implementation and the datasets used in this article are available as open-source.1},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {5},
numpages = {31},
keywords = {higher-order HMM, sequence mining and modeling, Hidden Markov models, HMM with duration, variable-order HMM}
}

@article{10.1145/1644873.1644875,
author = {Syed, Zeeshan and Stultz, Collin and Kellis, Manolis and Indyk, Piotr and Guttag, John},
title = {Motif Discovery in Physiological Datasets: A Methodology for Inferring Predictive Elements},
year = {2010},
issue_date = {January 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1644873.1644875},
doi = {10.1145/1644873.1644875},
abstract = {In this article, we propose a methodology for identifying predictive physiological patterns in the absence of prior knowledge. We use the principle of conservation to identify activity that consistently precedes an outcome in patients, and describe a two-stage process that allows us to efficiently search for such patterns in large datasets. This involves first transforming continuous physiological signals from patients into symbolic sequences, and then searching for patterns in these reduced representations that are strongly associated with an outcome.Our strategy of identifying conserved activity that is unlikely to have occurred purely by chance in symbolic data is analogous to the discovery of regulatory motifs in genomic datasets. We build upon existing work in this area, generalizing the notion of a regulatory motif and enhancing current techniques to operate robustly on non-genomic data. We also address two significant considerations associated with motif discovery in general: computational efficiency and robustness in the presence of degeneracy and noise. To deal with these issues, we introduce the concept of active regions and new subset-based techniques such as a two-layer Gibbs sampling algorithm. These extensions allow for a framework for information inference, where precursors are identified as approximately conserved activity of arbitrary complexity preceding multiple occurrences of an event.We evaluated our solution on a population of patients who experienced sudden cardiac death and attempted to discover electrocardiographic activity that may be associated with the endpoint of death. To assess the predictive patterns discovered, we compared likelihood scores for motifs in the sudden death population against control populations of normal individuals and those with non-fatal supraventricular arrhythmias. Our results suggest that predictive motif discovery may be able to identify clinically relevant information even in the absence of significant prior knowledge.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {2},
numpages = {23},
keywords = {motifs, knowledge discovery, Gibbs sampling, physiological signals, inference, data mining}
}

@article{10.1145/1644873.1644874,
author = {Koren, Yehuda},
title = {Factor in the Neighbors: Scalable and Accurate Collaborative Filtering},
year = {2010},
issue_date = {January 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1644873.1644874},
doi = {10.1145/1644873.1644874},
abstract = {Recommender systems provide users with personalized suggestions for products or services. These systems often rely on collaborating filtering (CF), where past transactions are analyzed in order to establish connections between users and products. The most common approach to CF is based on neighborhood models, which originate from similarities between products or users. In this work we introduce a new neighborhood model with an improved prediction accuracy. Unlike previous approaches that are based on heuristic similarities, we model neighborhood relations by minimizing a global cost function. Further accuracy improvements are achieved by extending the model to exploit both explicit and implicit feedback by the users. Past models were limited by the need to compute all pairwise similarities between items or users, which grow quadratically with input size. In particular, this limitation vastly complicates adopting user similarity models, due to the typical large number of users. Our new model solves these limitations by factoring the neighborhood model, thus making both item-item and user-user implementations scale linearly with the size of the data. The methods are tested on the Netflix data, with encouraging results.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {1},
numpages = {24},
keywords = {collaborative filtering, Recommender systems, Netflix Prize}
}

@article{10.1145/1644873.1644877,
author = {Plantevit, Marc and Laurent, Anne and Laurent, Dominique and Teisseire, Maguelonne and Choong, Yeow WEI},
title = {Mining Multidimensional and Multilevel Sequential Patterns},
year = {2010},
issue_date = {January 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1644873.1644877},
doi = {10.1145/1644873.1644877},
abstract = {Multidimensional databases have been designed to provide decision makers with the necessary tools to help them understand their data. This framework is different from transactional data as the datasets contain huge volumes of historicized and aggregated data defined over a set of dimensions that can be arranged through multiple levels of granularities. Many tools have been proposed to query the data and navigate through the levels of granularity. However, automatic tools are still missing to mine this type of data in order to discover regular specific patterns. In this article, we present a method for mining sequential patterns from multidimensional databases, at the same time taking advantage of the different dimensions and levels of granularity, which is original compared to existing work. The necessary definitions and algorithms are extended from regular sequential patterns to this particular case. Experiments are reported, showing the significance of this approach.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {4},
numpages = {37},
keywords = {Sequential patterns, multidimensional databases, hierarchy, multilevel patterns, frequent patterns}
}

@article{10.1145/1644873.1644876,
author = {Webb, Geoffrey I.},
title = {Self-Sufficient Itemsets: An Approach to Screening Potentially Interesting Associations between Items},
year = {2010},
issue_date = {January 2010},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {4},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1644873.1644876},
doi = {10.1145/1644873.1644876},
abstract = {Self-sufficient itemsets are those whose frequency cannot be explained solely by the frequency of either their subsets or of their supersets. We argue that itemsets that are not self-sufficient will often be of little interest to the data analyst, as their frequency should be expected once that of the itemsets on which their frequency depends is known. We present tests for statistically sound discovery of self-sufficient itemsets, and computational techniques that allow those tests to be applied as a post-processing step for any itemset discovery algorithm. We also present a measure for assessing the degree of potential interest in an itemset that complements these statistical measures.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {3},
numpages = {20},
keywords = {statistical evaluation, association rules, itemset screening, Association discovery, itemset discovery}
}

@article{10.1145/1631162.1631163,
author = {Mannila, Heikki and Gunopulos, Dimitrios},
title = {ACM TKDD Special Issue ACM SIGKDD 2007 and ACM SIGKDD 2008},
year = {2009},
issue_date = {November 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1631162.1631163},
doi = {10.1145/1631162.1631163},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {15},
numpages = {2}
}

@article{10.1145/1631162.1631165,
author = {Chi, Yun and Song, Xiaodan and Zhou, Dengyong and Hino, Koji and Tseng, Belle L.},
title = {On Evolutionary Spectral Clustering},
year = {2009},
issue_date = {November 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1631162.1631165},
doi = {10.1145/1631162.1631165},
abstract = {Evolutionary clustering is an emerging research area essential to important applications such as clustering dynamic Web and blog contents and clustering data streams. In evolutionary clustering, a good clustering result should fit the current data well, while simultaneously not deviate too dramatically from the recent history. To fulfill this dual purpose, a measure of temporal smoothness is integrated in the overall measure of clustering quality. In this article, we propose two frameworks that incorporate temporal smoothness in evolutionary spectral clustering. For both frameworks, we start with intuitions gained from the well-known k-means clustering problem, and then propose and solve corresponding cost functions for the evolutionary spectral clustering problems. Our solutions to the evolutionary spectral clustering problems provide more stable and consistent clustering results that are less sensitive to short-term noises while at the same time are adaptive to long-term cluster drifts. Furthermore, we demonstrate that our methods provide the optimal solutions to the relaxed versions of the corresponding evolutionary k-means clustering problems. Performance experiments over a number of real and synthetic data sets illustrate our evolutionary spectral clustering methods provide more robust clustering results that are not sensitive to noise and can adapt to data drifts.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {17},
numpages = {30},
keywords = {preserving cluster quality, temporal smoothness, Evolutionary spectral clustering, preserving cluster membership}
}

@article{10.1145/1631162.1631169,
author = {Kiernan, Jerry and Terzi, Evimaria},
title = {Constructing Comprehensive Summaries of Large Event Sequences},
year = {2009},
issue_date = {November 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1631162.1631169},
doi = {10.1145/1631162.1631169},
abstract = {Event sequences capture system and user activity over time. Prior research on sequence mining has mostly focused on discovering local patterns appearing in a sequence. While interesting, these patterns do not give a comprehensive summary of the entire event sequence. Moreover, the number of patterns discovered can be large. In this article, we take an alternative approach and build short summaries that describe an entire sequence, and discover local dependencies between event types.We formally define the summarization problem as an optimization problem that balances shortness of the summary with accuracy of the data description. We show that this problem can be solved optimally in polynomial time by using a combination of two dynamic-programming algorithms. We also explore more efficient greedy alternatives and demonstrate that they work well on large datasets. Experiments on both synthetic and real datasets illustrate that our algorithms are efficient and produce high-quality results, and reveal interesting local structures in the data.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {21},
numpages = {31},
keywords = {Event sequences, log mining, summarization}
}

@article{10.1145/1631162.1631164,
author = {Asur, Sitaram and Parthasarathy, Srinivasan and Ucar, Duygu},
title = {An Event-Based Framework for Characterizing the Evolutionary Behavior of Interaction Graphs},
year = {2009},
issue_date = {November 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1631162.1631164},
doi = {10.1145/1631162.1631164},
abstract = {Interaction graphs are ubiquitous in many fields such as bioinformatics, sociology and physical sciences. There have been many studies in the literature targeted at studying and mining these graphs. However, almost all of them have studied these graphs from a static point of view. The study of the evolution of these graphs over time can provide tremendous insight on the behavior of entities, communities and the flow of information among them. In this work, we present an event-based characterization of critical behavioral patterns for temporally varying interaction graphs. We use nonoverlapping snapshots of interaction graphs and develop a framework for capturing and identifying interesting events from them. We use these events to characterize complex behavioral patterns of individuals and communities over time. We show how semantic information can be incorporated to reason about community-behavior events. We also demonstrate the application of behavioral patterns for the purposes of modeling evolution, link prediction and influence maximization. Finally, we present a diffusion model for evolving networks, based on our framework.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {16},
numpages = {36},
keywords = {diffusion of innovations, evolutionary analysis, Dynamic interaction networks}
}

@article{10.1145/1631162.1631168,
author = {Bilgic, Mustafa and Getoor, Lise},
title = {Reflect and Correct: A Misclassification Prediction Approach to Active Inference},
year = {2009},
issue_date = {November 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1631162.1631168},
doi = {10.1145/1631162.1631168},
abstract = {Information diffusion, viral marketing, graph-based semi-supervised learning, and collective classification all attempt to model and exploit the relationships among nodes in a network to improve the performance of node labeling algorithms. However, sometimes the advantage of exploiting the relationships can become a disadvantage. Simple models like label propagation and iterative classification can aggravate a misclassification by propagating mistakes in the network, while more complex models that define and optimize a global objective function, such as Markov random fields and graph mincuts, can misclassify a set of nodes jointly. This problem can be mitigated if the classification system is allowed to ask for the correct labels for a few of the nodes during inference. However, determining the optimal set of labels to acquire is intractable under relatively general assumptions, which forces us to resort to approximate and heuristic techniques. We describe three such techniques in this article. The first one is based on directly approximating the value of the objective function of label acquisition and greedily acquiring the label that provides the most improvement. The second technique is a simple technique based on the analogy we draw between viral marketing and label acquisition. Finally, we propose a method, which we refer to as reflect and correct, that can learn and predict when the classification system is likely to make mistakes and suggests acquisitions to correct those mistakes. We empirically show on a variety of synthetic and real-world datasets that the reflect and correct method significantly outperforms the other two techniques, as well as other approaches based on network structural measures such as node degree and network clustering.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {20},
numpages = {32},
keywords = {viral marketing, label acquisition, information diffusion, collective classification, Active inference}
}

@article{10.1145/1631162.1631166,
author = {Fujiwara, Yasuhiro and Sakurai, Yasushi and Kitsuregawa, Masaru},
title = {Fast Likelihood Search for Hidden Markov Models},
year = {2009},
issue_date = {November 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1631162.1631166},
doi = {10.1145/1631162.1631166},
abstract = {Hidden Markov models (HMMs) are receiving considerable attention in various communities and many applications that use HMMs have emerged such as mental task classification, biological analysis, traffic monitoring, and anomaly detection. This article has two goals; The first goal is exact and efficient identification of the model whose state sequence has the highest likelihood for the given query sequence (more precisely, no HMM that actually has a high-probability path for the given sequence is missed by the algorithm), and the second goal is exact and efficient monitoring of streaming data sequences to find the best model. We propose SPIRAL, a fast search method for HMM datasets. SPIRAL is based on three ideas; (1) it clusters states of models to compute approximate likelihood, (2) it uses several granularities and approximates likelihood values in search processing, and (3) it focuses on just the promising likelihood computations by pruning out low-likelihood state sequences. Experiments verify the effectiveness of SPIRAL and show that it is more than 490 times faster than the naive method.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {18},
numpages = {37},
keywords = {upper bound, likelihood, Hidden Markov model}
}

@article{10.1145/1631162.1631167,
author = {Zhang, Xiang and Zou, Fei and Wang, Wei},
title = {Efficient Algorithms for Genome-Wide Association Study},
year = {2009},
issue_date = {November 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1631162.1631167},
doi = {10.1145/1631162.1631167},
abstract = {Studying the association between quantitative phenotype (such as height or weight) and single nucleotide polymorphisms (SNPs) is an important problem in biology. To understand underlying mechanisms of complex phenotypes, it is often necessary to consider joint genetic effects across multiple SNPs. ANOVA (analysis of variance) test is routinely used in association study. Important findings from studying gene-gene (SNP-pair) interactions are appearing in the literature. However, the number of SNPs can be up to millions. Evaluating joint effects of SNPs is a challenging task even for SNP-pairs. Moreover, with large number of SNPs correlated, permutation procedure is preferred over simple Bonferroni correction for properly controlling family-wise error rate and retaining mapping power, which dramatically increases the computational cost of association study.In this article, we study the problem of finding SNP-pairs that have significant associations with a given quantitative phenotype. We propose an efficient algorithm, FastANOVA, for performing ANOVA tests on SNP-pairs in a batch mode, which also supports large permutation test. We derive an upper bound of SNP-pair ANOVA test, which can be expressed as the sum of two terms. The first term is based on single-SNP ANOVA test. The second term is based on the SNPs and independent of any phenotype permutation. Furthermore, SNP-pairs can be organized into groups, each of which shares a common upper bound. This allows for maximum reuse of intermediate computation, efficient upper bound estimation, and effective SNP-pair pruning. Consequently, FastANOVA only needs to perform the ANOVA test on a small number of candidate SNP-pairs without the risk of missing any significant ones. Extensive experiments demonstrate that FastANOVA is orders of magnitude faster than the brute-force implementation of ANOVA tests on all SNP pairs. The principles used in FastANOVA can be applied to categorical phenotypes and other statistics such as Chi-square test.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {19},
numpages = {28},
keywords = {permutation test, ANOVA test, Association study}
}

@article{10.1145/1552303.1552304,
author = {Torvik, Vetle I. and Smalheiser, Neil R.},
title = {Author Name Disambiguation in MEDLINE},
year = {2009},
issue_date = {July 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1552303.1552304},
doi = {10.1145/1552303.1552304},
abstract = {Background: We recently described “Author-ity,” a model for estimating the probability that two articles in MEDLINE, sharing the same author name, were written by the same individual. Features include shared title words, journal name, coauthors, medical subject headings, language, affiliations, and author name features (middle initial, suffix, and prevalence in MEDLINE). Here we test the hypothesis that the Author-ity model will suffice to disambiguate author names for the vast majority of articles in MEDLINE. Methods: Enhancements include: (a) incorporating first names and their variants, email addresses, and correlations between specific last names and affiliation words; (b) new methods of generating large unbiased training sets; (c) new methods for estimating the prior probability; (d) a weighted least squares algorithm for correcting transitivity violations; and (e) a maximum likelihood based agglomerative algorithm for computing clusters of articles that represent inferred author-individuals. Results: Pairwise comparisons were computed for all author names on all 15.3 million articles in MEDLINE (2006 baseline), that share last name and first initial, to create Author-ity 2006, a database that has each name on each article assigned to one of 6.7 million inferred author-individual clusters. Recall is estimated at ∼98.8%. Lumping (putting two different individuals into the same cluster) affects ∼0.5% of clusters, whereas splitting (assigning articles written by the same individual to >1 cluster) affects ∼2% of articles. Impact: The Author-ity model can be applied generally to other bibliographic databases. Author name disambiguation allows information retrieval and data integration to become person-centered, not just document-centered, setting the stage for new data mining and social network tools that will facilitate the analysis of scholarly publishing and collaboration behavior. Availability: The Author-ity 2006 database is available for nonprofit academic research, and can be freely queried via http://arrowsmith.psych.uic.edu.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {11},
numpages = {29},
keywords = {bibliographic databases, Name disambiguation}
}

@article{10.1145/1552303.1552307,
author = {Wan, Li and Ng, Wee Keong and Dang, Xuan Hong and Yu, Philip S. and Zhang, Kuan},
title = {Density-Based Clustering of Data Streams at Multiple Resolutions},
year = {2009},
issue_date = {July 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1552303.1552307},
doi = {10.1145/1552303.1552307},
abstract = {In data stream clustering, it is desirable to have algorithms that are able to detect clusters of arbitrary shape, clusters that evolve over time, and clusters with noise. Existing stream data clustering algorithms are generally based on an online-offline approach: The online component captures synopsis information from the data stream (thus, overcoming real-time and memory constraints) and the offline component generates clusters using the stored synopsis. The online-offline approach affects the overall performance of stream data clustering in various ways: the ease of deriving synopsis from streaming data; the complexity of data structure for storing and managing synopsis; and the frequency at which the offline component is used to generate clusters. In this article, we propose an algorithm that (1) computes and updates synopsis information in constant time; (2) allows users to discover clusters at multiple resolutions; (3) determines the right time for users to generate clusters from the synopsis information; (4) generates clusters of higher purity than existing algorithms; and (5) determines the right threshold function for density-based clustering based on the fading model of stream data. To the best of our knowledge, no existing data stream algorithms has all of these features. Experimental results show that our algorithm is able to detect arbitrarily shaped, evolving clusters with high quality.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {14},
numpages = {28},
keywords = {evolving data streams, density based clustering, Data mining algorithms}
}

@article{10.1145/1552303.1552306,
author = {Zhou, Bin and Pei, Jian},
title = {Link Spam Target Detection Using Page Farms},
year = {2009},
issue_date = {July 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1552303.1552306},
doi = {10.1145/1552303.1552306},
abstract = {Currently, most popular Web search engines adopt some link-based ranking methods such as PageRank. Driven by the huge potential benefit of improving rankings of Web pages, many tricks have been attempted to boost page rankings. The most common way, which is known as link spam, is to make up some artificially designed link structures. Detecting link spam effectively is a big challenge. In this article, we develop novel and effective detection methods for link spam target pages using page farms. The essential idea is intuitive: whether a page is the beneficiary of link spam is reflected by how it collects its PageRank score. Technically, how a target page collects its PageRank score is modeled by a page farm, which consists of pages contributing a major portion of the PageRank score of the target page. We propose two spamicity measures based on page farms. They can be used as an effective measure to check whether the pages are link spam target pages. An empirical study using a newly available real dataset strongly suggests that our method is effective. It outperforms the state-of-the-art methods like SpamRank and SpamMass in both precision and recall.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {13},
numpages = {38},
keywords = {PageRank, Page Farm, Link Spam}
}

@article{10.1145/1552303.1552305,
author = {Tu, Li and Chen, Yixin},
title = {Stream Data Clustering Based on Grid Density and Attraction},
year = {2009},
issue_date = {July 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1552303.1552305},
doi = {10.1145/1552303.1552305},
abstract = {Clustering real-time stream data is an important and challenging problem. Existing algorithms such as CluStream are based on the k-means algorithm. These clustering algorithms have difficulties finding clusters of arbitrary shapes and handling outliers. Further, they require the knowledge of k and user-specified time window. To address these issues, this article proposes D-Stream, a framework for clustering stream data using a density-based approach.Our algorithm uses an online component that maps each input data record into a grid and an offline component that computes the grid density and clusters the grids based on the density. The algorithm adopts a density decaying technique to capture the dynamic changes of a data stream and a attraction-based mechanism to accurately generate cluster boundaries.Exploiting the intricate relationships among the decay factor, attraction, data density, and cluster structure, our algorithm can efficiently and effectively generate and adjust the clusters in real time. Further, a theoretically sound technique is developed to detect and remove sporadic grids mapped by outliers in order to dramatically improve the space and time efficiency of the system. The technique makes high-speed data stream clustering feasible without degrading the clustering quality. The experimental results show that our algorithm has superior quality and efficiency, can find clusters of arbitrary shapes, and can accurately recognize the evolving behaviors of real-time data streams.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {12},
numpages = {27},
keywords = {clustering, density-based algorithms, data mining, Stream data}
}

@article{10.1145/1514888.1514890,
author = {Mehler, Andrew and Skiena, Steven},
title = {Expanding Network Communities from Representative Examples},
year = {2009},
issue_date = {April 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1514888.1514890},
doi = {10.1145/1514888.1514890},
abstract = {We present an approach to leverage a small subset of a coherent community within a social network into a much larger, more representative sample. Our problem becomes identifying a small conductance subgraph containing many (but not necessarily all) members of the given seed set. Starting with an initial seed set representing a sample of a community, we seek to discover as much of the full community as possible.We present a general method for network community expansion, demonstrating that our methods work well in expanding communities in real world networks starting from small given seed groups (20 to 400 members). Our approach is marked by incremental expansion from the seeds with retrospective analysis to determine the ultimate boundaries of our community. We demonstrate how to increase the robustness of the general approach through bootstrapping multiple random partitions of the input set into seed and evaluation groups.We go beyond statistical comparisons against gold standards to careful subjective evaluations of our expanded communities. This process explains the causes of most disagreement between our expanded communities and our gold-standards—arguing that our expansion methods provide more reliable communities than can be extracted from reference sources/gazetteers such as Wikipedia.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {7},
numpages = {27},
keywords = {Discrete mathematics, news analysis, social networks, community discovery, graph theory, artificial intelligence}
}

@article{10.1145/1514888.1514892,
author = {Kimura, Masahiro and Saito, Kazumi and Motoda, Hiroshi},
title = {Blocking Links to Minimize Contamination Spread in a Social Network},
year = {2009},
issue_date = {April 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1514888.1514892},
doi = {10.1145/1514888.1514892},
abstract = {We address the problem of minimizing the propagation of undesirable things, such as computer viruses or malicious rumors, by blocking a limited number of links in a network, which is converse to the influence maximization problem in which the most influential nodes for information diffusion is searched in a social network. This minimization problem is more fundamental than the problem of preventing the spread of contamination by removing nodes in a network. We introduce two definitions for the contamination degree of a network, accordingly define two contamination minimization problems, and propose methods for efficiently finding good approximate solutions to these problems on the basis of a naturally greedy strategy. Using large social networks, we experimentally demonstrate that the proposed methods outperform conventional link-removal methods. We also show that unlike the case of blocking a limited number of nodes, the strategy of removing nodes with high out-degrees is not necessarily effective for these problems.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {9},
numpages = {23},
keywords = {Contamination diffusion, link analysis, social networks}
}

@article{10.1145/1514888.1514891,
author = {Lin, Yu-Ru and Chi, Yun and Zhu, Shenghuo and Sundaram, Hari and Tseng, Belle L.},
title = {Analyzing Communities and Their Evolutions in Dynamic Social Networks},
year = {2009},
issue_date = {April 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1514888.1514891},
doi = {10.1145/1514888.1514891},
abstract = {We discover communities from social network data and analyze the community evolution. These communities are inherent characteristics of human interaction in online social networks, as well as paper citation networks. Also, communities may evolve over time, due to changes to individuals' roles and social status in the network as well as changes to individuals' research interests. We present an innovative algorithm that deviates from the traditional two-step approach to analyze community evolutions. In the traditional approach, communities are first detected for each time slice, and then compared to determine correspondences. We argue that this approach is inappropriate in applications with noisy data. In this paper, we propose FacetNet for analyzing communities and their evolutions through a robust unified process. This novel framework will discover communities and capture their evolution with temporal smoothness given by historic community structures. Our approach relies on formulating the problem in terms of maximum a posteriori (MAP) estimation, where the community structure is estimated both by the observed networked data and by the prior distribution given by historic community structures. Then we develop an iterative algorithm, with proven low time complexity, which is guaranteed to converge to an optimal solution. We perform extensive experimental studies, on both synthetic datasets and real datasets, to demonstrate that our method discovers meaningful communities and provides additional insights not directly obtainable from traditional methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {8},
numpages = {31},
keywords = {soft membership, nonnegative matrix factorization, evolution net, evolution, community net, Community}
}

@article{10.1145/1514888.1514893,
author = {Agichtein, Eugene and Liu, Yandong and Bian, Jiang},
title = {Modeling Information-Seeker Satisfaction in Community Question Answering},
year = {2009},
issue_date = {April 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1514888.1514893},
doi = {10.1145/1514888.1514893},
abstract = {Question Answering Communities such as Naver, Baidu Knows, and Yahoo! Answers have emerged as popular, and often effective, means of information seeking on the web. By posting questions for other participants to answer, information seekers can obtain specific answers to their questions. Users of CQA portals have already contributed millions of questions, and received hundreds of millions of answers from other participants. However, CQA is not always effective: in some cases, a user may obtain a perfect answer within minutes, and in others it may require hours—and sometimes days—until a satisfactory answer is contributed. We investigate the problem of predicting information seeker satisfaction in collaborative question answering communities, where we attempt to predict whether a question author will be satisfied with the answers submitted by the community participants. We present a general prediction model, and develop a variety of content, structure, and community-focused features for this task. Our experimental results, obtained from a large-scale evaluation over thousands of real questions and user ratings, demonstrate the feasibility of modeling and predicting asker satisfaction. We complement our results with a thorough investigation of the interactions and information seeking patterns in question answering communities that correlate with information seeker satisfaction. We also explore personalized models of asker satisfaction, and show that when sufficient interaction history exists, personalization can significantly improve prediction accuracy over a “one-size-fits-all” model. Our models and predictions could be useful for a variety of applications, such as user intent inference, answer ranking, interface design, and query suggestion and routing.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {10},
numpages = {27},
keywords = {Community question answering, information seeker satisfaction}
}

@article{10.1145/1514888.1514889,
author = {Liu, Huan and Salerno, John and Young, Michael and Agrawal, Rakesh and Yu, Philip S.},
title = {Introduction to Special Issue on Social Computing, Behavioral Modeling, and Prediction},
year = {2009},
issue_date = {April 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1514888.1514889},
doi = {10.1145/1514888.1514889},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {6},
numpages = {3}
}

@article{10.1145/1497577.1497582,
author = {Chen, Bee-Chung and Ramakrishnan, Raghu and Shavlik, Jude W. and Tamma, Pradeep},
title = {Bellwether Analysis: Searching for Cost-Effective Query-Defined Predictors in Large Databases},
year = {2009},
issue_date = {March 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1497577.1497582},
doi = {10.1145/1497577.1497582},
abstract = {How to mine massive datasets is a challenging problem with great potential value. Motivated by this challenge, much effort has concentrated on developing scalable versions of machine learning algorithms. However, the cost of mining large datasets is not just computational; preparing the datasets into the “right form” so that learning algorithms can be applied is usually costly, due to the human labor that is typically required and a large number of choices in data preparation, which include selecting different subsets of data and aggregating data at different granularities. We make the key observation that, for a number of practically motivated problems, these choices can be defined using database queries and analyzed in an automatic and systematic manner. Specifically, we propose a new class of data-mining problem, called bellwether analysis, in which the goal is to find a few query-defined predictors (e.g., first week sales of Peoria, IL of an item) that can be used to accurately predict the result of a target query (e.g., first year worldwide sales of the item) from a large number of queries that define candidate predictors. To make a prediction for a new item, the data needed to generate such predictors has to be collected (e.g., selling the new item in Peoria, IL for a week and collecting the sales data). A useful predictor is one that has high prediction accuracy and a low data-collection cost. We call such a cost-effective predictor a bellwether.This article introduces bellwether analysis, which integrates database query processing and predictive modeling into a single framework, and provides scalable algorithms for large datasets that cannot fit in main memory. Through a series of extensive experiments, we show that bellwethers do exist in real-world databases, and that our computation techniques achieve good efficiency on large datasets.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {5},
numpages = {49},
keywords = {data cube, predictive models, bellwether, scalable algorithms, Cost-effective prediction, OLAP queries}
}

@article{10.1145/1497577.1497580,
author = {Cerf, Lo\"{\i}c and Besson, J\'{e}r\'{e}my and Robardet, C\'{e}line and Boulicaut, Jean-Fran\c{c}ois},
title = {Closed Patterns Meet <i>n</i>-Ary Relations},
year = {2009},
issue_date = {March 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1497577.1497580},
doi = {10.1145/1497577.1497580},
abstract = {Set pattern discovery from binary relations has been extensively studied during the last decade. In particular, many complete and efficient algorithms for frequent closed set mining are now available. Generalizing such a task to n-ary relations (n ≥ 2) appears as a timely challenge. It may be important for many applications, for example, when adding the time dimension to the popular objects \texttimes{} features binary case. The generality of the task (no assumption being made on the relation arity or on the size of its attribute domains) makes it computationally challenging. We introduce an algorithm called Data-Peeler. From an n-ary relation, it extracts all closed n-sets satisfying given piecewise (anti) monotonic constraints. This new class of constraints generalizes both monotonic and antimonotonic constraints. Considering the special case of ternary relations, Data-Peeler outperforms the state-of-the-art algorithms CubeMiner and Trias by orders of magnitude. These good performances must be granted to a new clever enumeration strategy allowing to efficiently enforce the closeness property. The relevance of the extracted closed n-sets is assessed on real-life 3-and 4-ary relations. Beyond natural 3-or 4-ary relations, expanding a relation with an additional attribute can help in enforcing rather abstract constraints such as the robustness with respect to binarization. Furthermore, a collection of closed n-sets is shown to be an excellent starting point to compute a tiling of the dataset.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {3},
numpages = {36},
keywords = {n-ary relations, Closed patterns, constraint properties, constraint-based mining, tiling}
}

@article{10.1145/1497577.1497579,
author = {Dhurandhar, Amit and Dobra, Alin},
title = {Semi-Analytical Method for Analyzing Models and Model Selection Measures Based on Moment Analysis},
year = {2009},
issue_date = {March 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1497577.1497579},
doi = {10.1145/1497577.1497579},
abstract = {In this article we propose a moment-based method for studying models and model selection measures. By focusing on the probabilistic space of classifiers induced by the classification algorithm rather than on that of datasets, we obtain efficient characterizations for computing the moments, which is followed by visualization of the resulting formulae that are too complicated for direct interpretation. By assuming the data to be drawn independently and identically distributed from the underlying probability distribution, and by going over the space of all possible datasets, we establish general relationships between the generalization error, hold-out-set error, cross-validation error, and leave-one-out error. We later exemplify the method and the results by studying the behavior of the errors for the naive Bayes classifier.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {2},
numpages = {51},
keywords = {classification, generalization error, Model selection}
}

@article{10.1145/1497577.1497581,
author = {Angiulli, Fabrizio and Fassetti, Fabio},
title = {DOLPHIN: An Efficient Algorithm for Mining Distance-Based Outliers in Very Large Datasets},
year = {2009},
issue_date = {March 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1497577.1497581},
doi = {10.1145/1497577.1497581},
abstract = {In this work a novel distance-based outlier detection algorithm, named DOLPHIN, working on disk-resident datasets and whose I/O cost corresponds to the cost of sequentially reading the input dataset file twice, is presented.It is both theoretically and empirically shown that the main memory usage of DOLPHIN amounts to a small fraction of the dataset and that DOLPHIN has linear time performance with respect to the dataset size. DOLPHIN gains efficiency by naturally merging together in a unified schema three strategies, namely the selection policy of objects to be maintained in main memory, usage of pruning rules, and similarity search techniques. Importantly, similarity search is accomplished by the algorithm without the need of preliminarily indexing the whole dataset, as other methods do.The algorithm is simple to implement and it can be used with any type of data, belonging to either metric or nonmetric spaces. Moreover, a modification to the basic method allows DOLPHIN to deal with the scenario in which the available buffer of main memory is smaller than its standard requirements. DOLPHIN has been compared with state-of-the-art distance-based outlier detection algorithms, showing that it is much more efficient.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {4},
numpages = {57},
keywords = {distance-based outliers, outlier detection, Data mining}
}

@article{10.1145/1497577.1497578,
author = {Kriegel, Hans-Peter and Kr\"{o}ger, Peer and Zimek, Arthur},
title = {Clustering High-Dimensional Data: A Survey on Subspace Clustering, Pattern-Based Clustering, and Correlation Clustering},
year = {2009},
issue_date = {March 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {3},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1497577.1497578},
doi = {10.1145/1497577.1497578},
abstract = {As a prolific research area in data mining, subspace clustering and related problems induced a vast quantity of proposed solutions. However, many publications compare a new proposition—if at all—with one or two competitors, or even with a so-called “na\"{\i}ve” ad hoc solution, but fail to clarify the exact problem definition. As a consequence, even if two solutions are thoroughly compared experimentally, it will often remain unclear whether both solutions tackle the same problem or, if they do, whether they agree in certain tacit assumptions and how such assumptions may influence the outcome of an algorithm. In this survey, we try to clarify: (i) the different problem definitions related to subspace clustering in general; (ii) the specific difficulties encountered in this field of research; (iii) the varying assumptions, heuristics, and intuitions forming the basis of different approaches; and (iv) how several prominent solutions tackle different problems.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
articleno = {1},
numpages = {58},
keywords = {high-dimensional data, clustering, Survey}
}

@article{10.1145/1460797.1460801,
author = {Zhang, Zhenjie and Lakshmanan, Laks V. S. and Tung, Anthony K. H.},
title = {On Domination Game Analysis for Microeconomic Data Mining},
year = {2009},
issue_date = {January 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1460797.1460801},
doi = {10.1145/1460797.1460801},
abstract = {Game theory is a powerful tool for analyzing the competitions among manufacturers in a market. In this article, we present a study on combining game theory and data mining by introducing the concept of domination game analysis. We present a multidimensional market model, where every dimension represents one attribute of a commodity. Every product or customer is represented by a point in the multidimensional space, and a product is said to “dominate” a customer if all of its attributes can satisfy the requirements of the customer. The expected market share of a product is measured by the expected number of the buyers in the customers, all of which are equally likely to buy any product dominating him. A Nash equilibrium is a configuration of the products achieving stable expected market shares for all products. We prove that Nash equilibrium in such a model can be computed in polynomial time if every manufacturer tries to modify its product in a round robin manner. To further improve the efficiency of the computation, we also design two algorithms for the manufacturers to efficiently find their best response to other products in the market.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {18},
numpages = {27},
keywords = {game theory, data mining, Domination game}
}

@article{10.1145/1460797.1460799,
author = {Jiang, Daxin and Pei, Jian},
title = {Mining Frequent Cross-Graph Quasi-Cliques},
year = {2009},
issue_date = {January 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1460797.1460799},
doi = {10.1145/1460797.1460799},
abstract = {Joint mining of multiple datasets can often discover interesting, novel, and reliable patterns which cannot be obtained solely from any single source. For example, in bioinformatics, jointly mining multiple gene expression datasets obtained by different labs or during various biological processes may overcome the heavy noise in the data. Moreover, by joint mining of gene expression data and protein-protein interaction data, we may discover clusters of genes which show coherent expression patterns and also produce interacting proteins. Such clusters may be potential pathways.In this article, we investigate a novel data mining problem, mining frequent cross-graph quasi-cliques, which is generalized from several interesting applications in bioinformatics, cross-market customer segmentation, social network analysis, and Web mining. In a graph, a set of vertices S is a γ-quasi-clique (0 < γ ≤ 1) if each vertex v in S directly connects to at least γ ⋅ (|S| − 1) other vertices in S. Given a set of graphs G1, …, Gn and parameter min_sup (0 < min_sup ≤ 1), a set of vertices S is a frequent cross-graph quasi-clique if S is a γ-quasi-clique in at least min_sup ⋅ n graphs, and there does not exist a proper superset of S having the property.We build a general model, show why the complete set of frequent cross-graph quasi-cliques cannot be found by previous data mining methods, and study the complexity of the problem. While the problem is difficult, we develop practical algorithms which exploit several interesting and effective techniques and heuristics to efficaciously mine frequent cross-graph quasi-cliques. A systematic performance study is reported on both synthetic and real data sets. We demonstrate some interesting and meaningful frequent cross-graph quasi-cliques in bioinformatics. The experimental results also show that our algorithms are efficient and scalable.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {16},
numpages = {42},
keywords = {clique, joint mining, Graph mining, bioinformatics}
}

@article{10.1145/1460797.1460798,
author = {Chuang, Kun-Ta and Chen, Hung-Leng and Chen, Ming-Syan},
title = {Feature-Preserved Sampling over Streaming Data},
year = {2009},
issue_date = {January 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1460797.1460798},
doi = {10.1145/1460797.1460798},
abstract = {In this article, we explore a novel sampling model, called feature preserved sampling (FPS) that sequentially generates a high-quality sample over sliding windows. The sampling quality we consider refers to the degree of consistency between the sample proportion and the population proportion of each attribute value in a window. Due to the time-variant nature of real-world datasets, users are more likely to be interested in the most recent data. However, previous works have not been able to generate a high-quality sample over sliding windows that precisely preserves up-to-date population characteristics. Motivated by this shortcoming, we have developed the FPS algorithm, which has several advantages: (1) it sequentially generates a sample from a time-variant data source over sliding windows; (2) the execution time of FPS is linear with respect to the database size; (3) the relative proportional differences between the sample proportions and population proportions of most distinct attribute values are guaranteed to be below a specified error threshold, ε, while the relative proportion differences of the remaining attribute values are as close to ε as possible, which ensures that the generated sample is of high quality; (4) the sample rate is close to the user specified rate so that a high quality sampling result can be obtained without increasing the sample size; (5) by a thorough analytical and empirical study, we prove that FPS has acceptable space overheads, especially when the attribute values have Zipfian distributions, and FPS can also excellently preserve the population proportion of multivariate features in the sample; and (6) FPS can be applied to infinite streams and finite datasets equally, and the generated samples can be used for various applications. Our experiments on both real and synthetic data validate that FPS can effectively obtain a high quality sample of the desired size. In addition, while using the sample generated by FPS in various mining applications, a significant improvement in efficiency can be achieved without compromising the model's precision.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {15},
numpages = {45},
keywords = {sampling, Streaming mining}
}

@article{10.1145/1460797.1460800,
author = {Domeniconi, Carlotta and Al-Razgan, Muna},
title = {Weighted Cluster Ensembles: Methods and Analysis},
year = {2009},
issue_date = {January 2009},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1460797.1460800},
doi = {10.1145/1460797.1460800},
abstract = {Cluster ensembles offer a solution to challenges inherent to clustering arising from its ill-posed nature. Cluster ensembles can provide robust and stable solutions by leveraging the consensus across multiple clustering results, while averaging out emergent spurious structures that arise due to the various biases to which each participating algorithm is tuned. In this article, we address the problem of combining multiple weighted clusters that belong to different subspaces of the input space. We leverage the diversity of the input clusterings in order to generate a consensus partition that is superior to the participating ones. Since we are dealing with weighted clusters, our consensus functions make use of the weight vectors associated with the clusters. We demonstrate the effectiveness of our techniques by running experiments with several real datasets, including high-dimensional text data. Furthermore, we investigate in depth the issue of diversity and accuracy for our ensemble methods. Our analysis and experimental results show that the proposed techniques are capable of producing a partition that is as good as or better than the best individual clustering.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jan,
articleno = {17},
numpages = {40},
keywords = {subspace clustering, Cluster ensembles, data mining, consensus functions, accuracy and diversity measures, text data}
}

@article{10.1145/1409620.1409624,
author = {Vaidya, Jaideep and Clifton, Chris and Kantarcioglu, Murat and Patterson, A. Scott},
title = {Privacy-Preserving Decision Trees over Vertically Partitioned Data},
year = {2008},
issue_date = {October 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1409620.1409624},
doi = {10.1145/1409620.1409624},
abstract = {Privacy and security concerns can prevent sharing of data, derailing data-mining projects. Distributed knowledge discovery, if done correctly, can alleviate this problem. We introduce a generalized privacy-preserving variant of the ID3 algorithm for vertically partitioned data distributed over two or more parties. Along with a proof of security, we discuss what would be necessary to make the protocols completely secure. We also provide experimental results, giving a first demonstration of the practical complexity of secure multiparty computation-based data mining.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {14},
numpages = {27},
keywords = {Decision tree classification, privacy}
}

@article{10.1145/1409620.1409622,
author = {Mangasarian, Olvi L. and Wild, Edward W. and Fung, Glenn M.},
title = {Privacy-Preserving Classification of Vertically Partitioned Data via Random Kernels},
year = {2008},
issue_date = {October 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1409620.1409622},
doi = {10.1145/1409620.1409622},
abstract = {We propose a novel privacy-preserving support vector machine (SVM) classifier for a data matrix A whose input feature columns are divided into groups belonging to different entities. Each entity is unwilling to share its group of columns or make it public. Our classifier is based on the concept of a reduced kernel K(A, B′), where B′ is the transpose of a random matrix B. The column blocks of B corresponding to the different entities are privately generated by each entity and never made public. The proposed linear or nonlinear SVM classifier, which is public but does not reveal any of the privately held data, has accuracy comparable to that of an ordinary SVM classifier that uses the entire set of input features directly.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {12},
numpages = {16},
keywords = {vertically partitioned data, Privacy preserving classification, support vector machines}
}

@article{10.1145/1409620.1409621,
author = {Sun, Jimeng and Tao, Dacheng and Papadimitriou, Spiros and Yu, Philip S. and Faloutsos, Christos},
title = {Incremental Tensor Analysis: Theory and Applications},
year = {2008},
issue_date = {October 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1409620.1409621},
doi = {10.1145/1409620.1409621},
abstract = {How do we find patterns in author-keyword associations, evolving over time? Or in data cubes (tensors), with product-branchcustomer sales information? And more generally, how to summarize high-order data cubes (tensors)? How to incrementally update these patterns over time? Matrix decompositions, like principal component analysis (PCA) and variants, are invaluable tools for mining, dimensionality reduction, feature selection, rule identification in numerous settings like streaming data, text, graphs, social networks, and many more settings. However, they have only two orders (i.e., matrices, like author and keyword in the previous example).We propose to envision such higher-order data as tensors, and tap the vast literature on the topic. However, these methods do not necessarily scale up, let alone operate on semi-infinite streams. Thus, we introduce a general framework, incremental tensor analysis (ITA), which efficiently computes a compact summary for high-order and high-dimensional data, and also reveals the hidden correlations. Three variants of ITA are presented: (1) dynamic tensor analysis (DTA); (2) streaming tensor analysis (STA); and (3) window-based tensor analysis (WTA). In paricular, we explore several fundamental design trade-offs such as space efficiency, computational cost, approximation accuracy, time dependency, and model complexity.We implement all our methods and apply them in several real settings, such as network anomaly detection, multiway latent semantic indexing on citation networks, and correlation study on sensor measurements. Our empirical studies show that the proposed methods are fast and accurate and that they find interesting patterns and outliers on the real datasets.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {11},
numpages = {37},
keywords = {stream mining, Tensor, multilinear algebra}
}

@article{10.1145/1409620.1409623,
author = {Lakshmanan, LAKS V. S. and Ng, Raymond T. and Ramesh, Ganesh},
title = {On Disclosure Risk Analysis of Anonymized Itemsets in the Presence of Prior Knowledge},
year = {2008},
issue_date = {October 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1409620.1409623},
doi = {10.1145/1409620.1409623},
abstract = {Decision makers of companies often face the dilemma of whether to release data for knowledge discovery, vis-a-vis the risk of disclosing proprietary or sensitive information. Among the various methods employed for “sanitizing” the data prior to disclosure, we focus in this article on anonymization, given its widespread use in practice. We do due diligence to the question “just how safe is the anonymized data?” We consider both those scenarios when the hacker has no information and, more realistically, when the hacker may have partial information about items in the domain. We conduct our analyses in the context of frequent set mining and address the safety question at two different levels: (i) how likely of being cracked (i.e., re-identified by a hacker), are the identities of individual items and (ii) how likely are sets of items cracked? For capturing the prior knowledge of the hacker, we propose a belief function, which amounts to an educated guess of the frequency of each item. For various classes of belief functions which correspond to different degrees of prior knowledge, we derive formulas for computing the expected number of cracks of single items and for itemsets, the probability of cracking the itemsets. While obtaining, exact values for more general situations is computationally hard, we propose a series of heuristics called the O-estimates. They are easy to compute and are shown fairly accurate, justified by empirical results on real benchmark datasets. Based on the O-estimates, we propose a recipe for the decision makers to resolve their dilemma. Our recipe operates at two different levels, depending on whether the data owner wants to reason in terms of single items or sets of items (or both). Finally, we present techniques for ascertaining a hacker's knowledge of correlation in terms of co-occurrence of items likely. This information regarding the hacker's knowledge can be incorporated into our framework of disclosure risk analysis and we present experimental results demonstrating how this knowledge affects the heuristic estimates we have developed.},
journal = {ACM Trans. Knowl. Discov. Data},
month = oct,
articleno = {13},
numpages = {44},
keywords = {frequent itemsets, matching, Disclosure risk, belief function, sampling, anonymization, correlation, hacker, bipartite graphs, prior knowledge}
}

@article{10.1145/1376815.1376818,
author = {Tan, Henry and Hadzic, Fedja and Dillon, Tharam S. and Chang, Elizabeth and Feng, Ling},
title = {Tree Model Guided Candidate Generation for Mining Frequent Subtrees from XML Documents},
year = {2008},
issue_date = {July 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1376815.1376818},
doi = {10.1145/1376815.1376818},
abstract = {Due to the inherent flexibilities in both structure and semantics, XML association rules mining faces few challenges, such as: a more complicated hierarchical data structure and ordered data context. Mining frequent patterns from XML documents can be recast as mining frequent tree structures from a database of XML documents. In this study, we model a database of XML documents as a database of rooted labeled ordered subtrees. In particular, we are mainly concerned with mining frequent induced and embedded ordered subtrees. Our main contributions are as follows. We describe our unique embedding list representation of the tree structure, which enables efficient implementation of our Tree Model Guided (TMG) candidate generation. TMG is an optimal, nonredundant enumeration strategy that enumerates all the valid candidates that conform to the structural aspects of the data. We show through a mathematical model and experiments that TMG has better complexity compared to the commonly used join approach. In this article, we propose two algorithms, MB3-Miner and iMB3-Miner. MB3-Miner mines embedded subtrees. iMB3-Miner mines induced and/or embedded subtrees by using the maximum level of embedding constraint. Our experiments with both synthetic and real datasets against two well-known algorithms for mining induced and embedded subtrees, demonstrate the effectiveness and the efficiency of the proposed techniques.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {9},
numpages = {43},
keywords = {Tree mining, TMG, TreeMiner, tree model guided, FREQT}
}

@article{10.1145/1376815.1376816,
author = {Ge, Rong and Ester, Martin and Gao, Byron J. and Hu, Zengjian and Bhattacharya, Binay and Ben-Moshe, Boaz},
title = {Joint Cluster Analysis of Attribute Data and Relationship Data: The Connected <i>k</i>-Center Problem, Algorithms and Applications},
year = {2008},
issue_date = {July 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1376815.1376816},
doi = {10.1145/1376815.1376816},
abstract = {Attribute data and relationship data are two principal types of data, representing the intrinsic and extrinsic properties of entities. While attribute data have been the main source of data for cluster analysis, relationship data such as social networks or metabolic networks are becoming increasingly available. It is also common to observe both data types carry complementary information such as in market segmentation and community identification, which calls for a joint cluster analysis of both data types so as to achieve better results. In this article, we introduce the novel Connected k-Center (CkC) problem, a clustering model taking into account attribute data as well as relationship data. We analyze the complexity of the problem and prove its NP-hardness. Therefore, we analyze the approximability of the problem and also present a constant factor approximation algorithm. For the special case of the CkC problem where the relationship data form a tree structure, we propose a dynamic programming method giving an optimal solution in polynomial time. We further present NetScan, a heuristic algorithm that is efficient and effective for large real databases. Our extensive experimental evaluation on real datasets demonstrates the meaningfulness and accuracy of the NetScan results.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {7},
numpages = {35},
keywords = {market segmentation, document clustering, NP-hardness, approximation algorithms, joint cluster analysis, relationship data, community identification, Attribute data}
}

@article{10.1145/1376815.1376817,
author = {Gupta, Gunjan and Ghosh, Joydeep},
title = {Bregman Bubble Clustering: A Robust Framework for Mining Dense Clusters},
year = {2008},
issue_date = {July 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1376815.1376817},
doi = {10.1145/1376815.1376817},
abstract = {In classical clustering, each data point is assigned to at least one cluster. However, in many applications only a small subset of the available data is relevant for the problem and the rest needs to be ignored in order to obtain good clusters. Certain nonparametric density-based clustering methods find the most relevant data as multiple dense regions, but such methods are generally limited to low-dimensional data and do not scale well to large, high-dimensional datasets. Also, they use a specific notion of “distance”, typically Euclidean or Mahalanobis distance, which further limits their applicability. On the other hand, the recent One Class Information Bottleneck (OC-IB) method is fast and works on a large class of distortion measures known as Bregman Divergences, but can only find a single dense region. This article presents a broad framework for finding k dense clusters while ignoring the rest of the data. It includes a seeding algorithm that can automatically determine a suitable value for k. When k is forced to 1, our method gives rise to an improved version of OC-IB with optimality guarantees. We provide a generative model that yields the proposed iterative algorithm for finding k dense regions as a special case. Our analysis reveals an interesting and novel connection between the problem of finding dense regions and exponential mixture models; a hard model corresponding to k exponential mixtures with a uniform background results in a set of k dense clusters. The proposed method describes a highly scalable algorithm for finding multiple dense regions that works with any Bregman Divergence, thus extending density based clustering to a variety of non-Euclidean problems not addressable by earlier methods. We present empirical results on three artificial, two microarray and one text dataset to show the relevance and effectiveness of our methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {8},
numpages = {49},
keywords = {exponential family, Density-based clustering, expectation maximization, Bregman divergences, One Class classification}
}

@article{10.1145/1376815.1376819,
author = {Islam, Aminul and Inkpen, Diana},
title = {Semantic Text Similarity Using Corpus-Based Word Similarity and String Similarity},
year = {2008},
issue_date = {July 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1376815.1376819},
doi = {10.1145/1376815.1376819},
abstract = {We present a method for measuring the semantic similarity of texts using a corpus-based measure of semantic word similarity and a normalized and modified version of the Longest Common Subsequence (LCS) string matching algorithm. Existing methods for computing text similarity have focused mainly on either large documents or individual words. We focus on computing the similarity between two sentences or two short paragraphs. The proposed method can be exploited in a variety of applications involving textual knowledge representation and knowledge discovery. Evaluation results on two different data sets show that our method outperforms several competing methods.},
journal = {ACM Trans. Knowl. Discov. Data},
month = jul,
articleno = {10},
numpages = {25},
keywords = {Semantic similarity of words, corpus-based measures, similarity of short texts}
}

@article{10.1145/1342320.1342326,
author = {Hashimoto, Kosuke and Aoki-Kinoshita, Kiyoko Flora and Ueda, Nobuhisa and Kanehisa, Minoru and Mamitsuka, Hiroshi},
title = {A New Efficient Probabilistic Model for Mining Labeled Ordered Trees Applied to Glycobiology},
year = {2008},
issue_date = {March 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1342320.1342326},
doi = {10.1145/1342320.1342326},
abstract = {Mining frequent patterns from large datasets is an important issue in data mining. Recently, complex and unstructured (or semi-structured) datasets have appeared as targets for major data mining applications, including text mining, web mining and bioinformatics. Our work focuses on labeled ordered trees, which are typically semi-structured datasets. In bioinformatics, carbohydrate sugar chains, or glycans, can be modeled as labeled ordered trees. Glycans are the third major class of biomolecules, having important roles in signaling and recognition. For mining labeled ordered trees, we propose a new probabilistic model and its efficient learning scheme which significantly improves the time and space complexity of an existing probabilistic model for labeled ordered trees. We evaluated the performance of the proposed model, comparing it with those of other probabilistic models, using synthetic as well as real datasets from glycobiology. Experimental results showed that the proposed model drastically reduced the computation time of the competing model, keeping the predictive power and avoiding overfitting to the training data. Finally, we assessed our results on real data from a variety of biological viewpoints, verifying known facts in glycobiology.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {6},
numpages = {30},
keywords = {maximum likelihood, Expectation-maximization, probabilistic models, labeled ordered trees}
}

@article{10.1145/1342320.1342323,
author = {Sahay, Saurav and Mukherjea, Sougata and Agichtein, Eugene and Garcia, Ernest V. and Navathe, Shamkant B. and Ram, Ashwin},
title = {Discovering Semantic Biomedical Relations Utilizing the Web},
year = {2008},
issue_date = {March 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1342320.1342323},
doi = {10.1145/1342320.1342323},
abstract = {To realize the vision of a Semantic Web for Life Sciences, discovering relations between resources is essential. It is very difficult to automatically extract relations from Web pages expressed in natural language formats. On the other hand, because of the explosive growth of information, it is difficult to manually extract the relations. In this paper we present techniques to automatically discover relations between biomedical resources from the Web. For this purpose we retrieve relevant information from Web Search engines and Pubmed database using various lexico-syntactic patterns as queries over SOAP web services. The patterns are initially handcrafted but can be progressively learnt. The extracted relations can be used to construct and augment ontologies and knowledge bases. Experiments are presented for general biomedical relation discovery and domain specific search to show the usefulness of our technique.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {3},
numpages = {15},
keywords = {Ontology construction, relation identification}
}

@article{10.1145/1342320.1342322,
author = {Jin, Ying and Murali, T. M. and Ramakrishnan, Naren},
title = {Compositional Mining of Multirelational Biological Datasets},
year = {2008},
issue_date = {March 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1342320.1342322},
doi = {10.1145/1342320.1342322},
abstract = {High-throughput biological screens are yielding ever-growing streams of information about multiple aspects of cellular activity. As more and more categories of datasets come online, there is a corresponding multitude of ways in which inferences can be chained across them, motivating the need for compositional data mining algorithms. In this article, we argue that such compositional data mining can be effectively realized by functionally cascading redescription mining and biclustering algorithms as primitives. Both these primitives mirror shifts of vocabulary that can be composed in arbitrary ways to create rich chains of inferences. Given a relational database and its schema, we show how the schema can be automatically compiled into a compositional data mining program, and how different domains in the schema can be related through logical sequences of biclustering and redescription invocations. This feature allows us to rapidly prototype new data mining applications, yielding greater understanding of scientific datasets. We describe two applications of compositional data mining: (i) matching terms across categories of the Gene Ontology and (ii) understanding the molecular mechanisms underlying stress response in human cells.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {2},
numpages = {35},
keywords = {redescription mining, bioinformatics, Biclustering, inductive logic programming, compositional data mining}
}

@article{10.1145/1342320.1342321,
author = {Zaki, Mohammed J. and Karypis, George and Yang, Jiong and Wang, Wei},
title = {Introduction to Special Issue on Bioinformatics},
year = {2008},
issue_date = {March 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1342320.1342321},
doi = {10.1145/1342320.1342321},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {1},
numpages = {1}
}

@article{10.1145/1342320.1342325,
author = {Lu, Yijuan and Tian, Qi and Neary, Jennifer and Liu, Feng and Wang, Yufeng},
title = {Adaptive Discriminant Analysis for Microarray-Based Classification},
year = {2008},
issue_date = {March 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1342320.1342325},
doi = {10.1145/1342320.1342325},
abstract = {Microarray technology has generated enormous amounts of high-dimensional gene expression data, providing a unique platform for exploring gene regulatory networks. However, the curse of dimensionality plagues effort to analyze these high throughput data. Linear Discriminant Analysis (LDA) and Biased Discriminant Analysis (BDA) are two popular techniques for dimension reduction, which pay attention to different roles of the positive and negative samples in finding discriminating subspace. However, the drawbacks of these two methods are obvious: LDA has limited efficiency in classifying sample data from subclasses with different distributions, and BDA does not account for the underlying distribution of negative samples.In this paper, we propose a novel dimension reduction technique for microarray analysis: Adaptive Discriminant Analysis (ADA), which effectively exploits favorable attributes of both BDA and LDA and avoids their unfavorable ones. ADA can find a good discriminative subspace with adaptation to different sample distributions. It not only alleviates the problem of high dimensionality, but also enhances the classification performance in the subspace with na\"{\i}ve Bayes classifier. To learn the best model fitting the real scenario, boosted Adaptive Discriminant Analysis is further proposed. Extensive experiments on the yeast cell cycle regulation data set, and the expression data of the red blood cell cycle in malaria parasite Plasmodium falciparum demonstrate the superior performance of ADA and boosted ADA. We also present some putative genes of specific functional classes predicted by boosted ADA. Their potential functionality is confirmed by independent predictions based on Gene Ontology, demonstrating that ADA and boosted ADA are effective dimension reduction methods for microarray-based classification.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {5},
numpages = {20},
keywords = {BDA, boosted ADA, microarray, ADA, LDA, dimension reduction}
}

@article{10.1145/1342320.1342324,
author = {Ye, Jieping and Chen, Jianhui and Janardan, Ravi and Kumar, Sudhir},
title = {Developmental Stage Annotation of Drosophila Gene Expression Pattern Images via an Entire Solution Path for LDA},
year = {2008},
issue_date = {March 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {2},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1342320.1342324},
doi = {10.1145/1342320.1342324},
abstract = {Gene expression in a developing embryo occurs in particular cells (spatial patterns) in a time-specific manner (temporal patterns), which leads to the differentiation of cell fates. Images of a Drosophila melanogaster embryo at a given developmental stage, showing a particular gene expression pattern revealed by a gene-specific probe, can be compared for spatial overlaps. The comparison is fundamentally important to formulating and testing gene interaction hypotheses. Expression pattern comparison is most biologically meaningful when images from a similar time point (developmental stage) are compared. In this paper, we present LdaPath, a novel formulation of Linear Discriminant Analysis (LDA) for automatic developmental stage range classification. It employs multivariate linear regression with the L1-norm penalty controlled by a regularization parameter for feature extraction and visualization. LdaPath computes an entire solution path for all values of regularization parameter with essentially the same computational cost as fitting one LDA model. Thus, it facilitates efficient model selection. It is based on the equivalence relationship between LDA and the least squares method for multiclass classifications. This equivalence relationship is established under a mild condition, which we show empirically to hold for many high-dimensional datasets, such as expression pattern images. Our experiments on a collection of 2705 expression pattern images show the effectiveness of the proposed algorithm. Results also show that the LDA model resulting from LdaPath is sparse, and irrelevant features may be removed. Thus, LdaPath provides a general framework for simultaneous feature selection and feature extraction.},
journal = {ACM Trans. Knowl. Discov. Data},
month = apr,
articleno = {4},
numpages = {21},
keywords = {linear regression, Gene expression pattern image, linear discriminant analysis, dimensionality reduction}
}

@article{10.1145/1324172.1324174,
author = {Cormode, Graham and Korn, Flip and Muthukrishnan, S. and Srivastava, Divesh},
title = {Finding Hierarchical Heavy Hitters in Streaming Data},
year = {2008},
issue_date = {January 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1324172.1324174},
doi = {10.1145/1324172.1324174},
abstract = {Data items that arrive online as streams typically have attributes which take values from one or more hierarchies (time and geographic location, source and destination IP addresses, etc.). Providing an aggregate view of such data is important for summarization, visualization, and analysis. We develop an aggregate view based on certain organized sets of large-valued regions (“heavy hitters”) corresponding to hierarchically discounted frequency counts. We formally define the notion of hierarchical heavy hitters (HHHs). We first consider computing (approximate) HHHs over a data stream drawn from a single hierarchical attribute. We formalize the problem and give deterministic algorithms to find them in a single pass over the input.In order to analyze a wider range of realistic data streams (e.g., from IP traffic-monitoring applications), we generalize this problem to multiple dimensions. Here, the semantics of HHHs are more complex, since a “child” node can have multiple “parent” nodes. We present online algorithms that find approximate HHHs in one pass, with provable accuracy guarantees. The product of hierarchical dimensions forms a mathematical lattice structure. Our algorithms exploit this structure, and so are able to track approximate HHHs using only a small, fixed number of statistics per stored item, regardless of the number of dimensions.We show experimentally, using real data, that our proposed algorithms yields outputs which are very similar (virtually identical, in many cases) to offline computations of the exact solutions, whereas straightforward heavy-hitters-based approaches give significantly inferior answer quality. Furthermore, the proposed algorithms result in an order of magnitude savings in data structure size while performing competitively.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {2},
numpages = {48},
keywords = {approximation algorithms, Data mining, network data analysis}
}

@article{10.1145/1324172.1324176,
author = {Halkidi, M. and Gunopulos, D. and Vazirgiannis, M. and Kumar, N. and Domeniconi, C.},
title = {A Clustering Framework Based on Subjective and Objective Validity Criteria},
year = {2008},
issue_date = {January 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1324172.1324176},
doi = {10.1145/1324172.1324176},
abstract = {Clustering, as an unsupervised learning process is a challenging problem, especially in cases of high-dimensional datasets. Clustering result quality can benefit from user constraints and objective validity assessment. In this article, we propose a semisupervised framework for learning the weighted Euclidean subspace, where the best clustering can be achieved. Our approach capitalizes on: (i) user constraints; and (ii) the quality of intermediate clustering results in terms of their structural properties. The proposed framework uses the clustering algorithm and the validity measure as its parameters. We develop and discuss algorithms for learning and tuning the weights of contributing dimensions and defining the “best” clustering obtained by satisfying user constraints. Experimental results on benchmark datasets demonstrate the superiority of the proposed approach in terms of improved clustering accuracy.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {4},
numpages = {25},
keywords = {similarity measure learning, space learning, Semisupervised learning, cluster validity, data mining}
}

@article{10.1145/1324172.1324175,
author = {Somaiya, Manas and Jermaine, Christopher and Ranka, Sanjay},
title = {Learning Correlations Using the Mixture-of-Subsets Model},
year = {2008},
issue_date = {January 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1324172.1324175},
doi = {10.1145/1324172.1324175},
abstract = {Using a mixture of random variables to model data is a tried-and-tested method common in data mining, machine learning, and statistics. By using mixture modeling it is often possible to accurately model even complex, multimodal data via very simple components. However, the classical mixture model assumes that a data point is generated by a single component in the model. A lot of datasets can be modeled closer to the underlying reality if we drop this restriction. We propose a probabilistic framework, the mixture-of-subsets (MOS) model, by making two fundamental changes to the classical mixture model. First, we allow a data point to be generated by a set of components, rather than just a single component. Next, we limit the number of data attributes that each component can influence. We also propose an EM framework to learn the MOS model from a dataset, and experimentally evaluate it on real, high-dimensional datasets. Our results show that the MOS model learned from the data represents the underlying nature of the data accurately.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {3},
numpages = {42},
keywords = {EM algorithm, high-dimensional data, Mixture modeling}
}

@article{10.1145/1324172.1324173,
author = {Tang, Lei and Liu, Huan and Zhang, Jianping and Agarwal, Nitin and Salerno, John J.},
title = {Topic Taxonomy Adaptation for Group Profiling},
year = {2008},
issue_date = {January 2008},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {4},
issn = {1556-4681},
url = {https://doi.org/10.1145/1324172.1324173},
doi = {10.1145/1324172.1324173},
abstract = {A topic taxonomy is an effective representation that describes salient features of virtual groups or online communities. A topic taxonomy consists of topic nodes. Each internal node is defined by its vertical path (i.e., ancestor and child nodes) and its horizonal list of attributes (or terms). In a text-dominant environment, a topic taxonomy can be used to flexibly describe a group's interests with varying granularity. However, the stagnant nature of a taxonomy may fail to timely capture the dynamic change of a group's interest. This article addresses the problem of how to adapt a topic taxonomy to the accumulated data that reflects the change of a group's interest to achieve dynamic group profiling. We first discuss the issues related to topic taxonomy. We next formulate taxonomy adaptation as an optimization problem to find the taxonomy that best fits the data. We then present a viable algorithm that can efficiently accomplish taxonomy adaptation. We conduct extensive experiments to evaluate our approach's efficacy for group profiling, compare the approach with some alternatives, and study its performance for dynamic group profiling. While pointing out various applications of taxonomy adaption, we suggest some future work that can take advantage of burgeoning Web 2.0 services for online targeted marketing, counterterrorism in connecting dots, and community tracking.},
journal = {ACM Trans. Knowl. Discov. Data},
month = feb,
articleno = {1},
numpages = {28},
keywords = {Topic taxonomy, text hierarchical classification, taxonomy adjustment, group interest, dynamic profiling}
}

@article{10.1145/1297332.1297333,
author = {Bayardop, Roberto and Bennett, Kristin P. and Das, Gautam and Gunopulos, Dimitrios and Gehrke, Johannes},
title = {Introduction to Special Issue ACM SIGKDD 2006},
year = {2007},
issue_date = {December 2007},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1297332.1297333},
doi = {10.1145/1297332.1297333},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
pages = {9–es},
numpages = {1}
}

@article{10.1145/1297332.1297336,
author = {Koren, Yehuda and North, Stephen C. and Volinsky, Chris},
title = {Measuring and Extracting Proximity Graphs in Networks},
year = {2007},
issue_date = {December 2007},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1297332.1297336},
doi = {10.1145/1297332.1297336},
abstract = {Measuring distance or some other form of proximity between objects is a standard data mining tool. Connection subgraphs were recently proposed as a way to demonstrate proximity between nodes in networks. We propose a new way of measuring and extracting proximity in networks called “cycle-free effective conductance” (CFEC). Importantly, the measured proximity is accompanied with a proximity subgraph which allows assessing and understanding measured values. Our proximity calculation can handle more than two endpoints, directed edges, is statistically well behaved, and produces an effectiveness score for the computed subgraphs. We provide an efficient algorithm to measure and extract proximity. Also, we report experimental results and show examples for four large network datasets: a telecommunications calling graph, the IMDB actors graph, an academic coauthorship network, and a movie recommendation system.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
pages = {12–es},
numpages = {30},
keywords = {proximity, escape probability, Connection subgraph, graph mining, proximity subgraph, cycle-free escape probability, random walk}
}

@article{10.1145/1297332.1297338,
author = {Gionis, Aristides and Mannila, Heikki and Mielik\"{a}inen, Taneli and Tsaparas, Panayiotis},
title = {Assessing Data Mining Results via Swap Randomization},
year = {2007},
issue_date = {December 2007},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1297332.1297338},
doi = {10.1145/1297332.1297338},
abstract = {The problem of assessing the significance of data mining results on high-dimensional 0--1 datasets has been studied extensively in the literature. For problems such as mining frequent sets and finding correlations, significance testing can be done by standard statistical tests such as chi-square, or other methods. However, the results of such tests depend only on the specific attributes and not on the dataset as a whole. Moreover, the tests are difficult to apply to sets of patterns or other complex results of data mining algorithms. In this article, we consider a simple randomization technique that deals with this shortcoming. The approach consists of producing random datasets that have the same row and column margins as the given dataset, computing the results of interest on the randomized instances and comparing them to the results on the actual data. This randomization technique can be used to assess the results of many different types of data mining algorithms, such as frequent sets, clustering, and spectral analysis. To generate random datasets with given margins, we use variations of a Markov chain approach which is based on a simple swap operation. We give theoretical results on the efficiency of different randomization methods, and apply the swap randomization method to several well-known datasets. Our results indicate that for some datasets the structure discovered by the data mining algorithms is expected, given the row and column margins of the datasets, while for other datasets the discovered structure conveys information that is not captured by the margin counts.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
pages = {14–es},
numpages = {32},
keywords = {swaps, 0--1 data, Significance testing, randomization tests}
}

@article{10.1145/1297332.1297337,
author = {Ihler, Alexander and Hutchins, Jon and Smyth, Padhraic},
title = {Learning to Detect Events with Markov-Modulated Poisson Processes},
year = {2007},
issue_date = {December 2007},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1297332.1297337},
doi = {10.1145/1297332.1297337},
abstract = {Time-series of count data occur in many different contexts, including Internet navigation logs, freeway traffic monitoring, and security logs associated with buildings. In this article we describe a framework for detecting anomalous events in such data using an unsupervised learning approach. Normal periodic behavior is modeled via a time-varying Poisson process model, which in turn is modulated by a hidden Markov process that accounts for bursty events. We outline a Bayesian framework for learning the parameters of this model from count time-series. Two large real-world datasets of time-series counts are used as testbeds to validate the approach, consisting of freeway traffic data and logs of people entering and exiting a building. We show that the proposed model is significantly more accurate at detecting known events than a more traditional threshold-based technique. We also describe how the model can be used to investigate different degrees of periodicity in the data, including systematic day-of-week and time-of-day effects, and to make inferences about different aspects of events such as number of vehicles or people involved. The results indicate that the Markov-modulated Poisson framework provides a robust and accurate framework for adaptively and autonomously learning how to separate unusual bursty events from traces of normal human activity.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
pages = {13–es},
numpages = {23},
keywords = {Event detection, Markov modulated, Poisson}
}

@article{10.1145/1297332.1297335,
author = {Mei, Qiaozhu and Xin, Dong and Cheng, Hong and Han, Jiawei and Zhai, Chengxiang},
title = {Semantic Annotation of Frequent Patterns},
year = {2007},
issue_date = {December 2007},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1297332.1297335},
doi = {10.1145/1297332.1297335},
abstract = {Using frequent patterns to analyze data has been one of the fundamental approaches in many data mining applications. Research in frequent pattern mining has so far mostly focused on developing efficient algorithms to discover various kinds of frequent patterns, but little attention has been paid to the important next step—interpreting the discovered frequent patterns. Although the compression and summarization of frequent patterns has been studied in some recent work, the proposed techniques there can only annotate a frequent pattern with nonsemantical information (e.g., support), which provides only limited help for a user to understand the patterns.In this article, we study the novel problem of generating semantic annotations for frequent patterns. The goal is to discover the hidden meanings of a frequent pattern by annotating it with in-depth, concise, and structured information. We propose a general approach to generate such an annotation for a frequent pattern by constructing its context model, selecting informative context indicators, and extracting representative transactions and semantically similar patterns. This general approach can well incorporate the user's prior knowledge, and has potentially many applications, such as generating a dictionary-like description for a pattern, finding synonym patterns, discovering semantic relations, and summarizing semantic classes of a set of frequent patterns. Experiments on different datasets show that our approach is effective in generating semantic pattern annotations.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
pages = {11–es},
numpages = {30},
keywords = {pattern context, pattern semantic analysis, pattern annotation, Frequent pattern}
}

@article{10.1145/1297332.1297334,
author = {B\"{o}hm, Christian and Faloutsos, Christos and Pan, Jia-Yu and Plant, Claudia},
title = {RIC: Parameter-Free Noise-Robust Clustering},
year = {2007},
issue_date = {December 2007},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {3},
issn = {1556-4681},
url = {https://doi.org/10.1145/1297332.1297334},
doi = {10.1145/1297332.1297334},
abstract = {How do we find a natural clustering of a real-world point set which contains an unknown number of clusters with different shapes, and which may be contaminated by noise? As most clustering algorithms were designed with certain assumptions (Gaussianity), they often require the user to give input parameters, and are sensitive to noise. In this article, we propose a robust framework for determining a natural clustering of a given dataset, based on the minimum description length (MDL) principle. The proposed framework, robust information-theoretic clustering (RIC), is orthogonal to any known clustering algorithm: Given a preliminary clustering, RIC purifies these clusters from noise, and adjusts the clusterings such that it simultaneously determines the most natural amount and shape (subspace) of the clusters. Our RIC method can be combined with any clustering technique ranging from K-means and K-medoids to advanced methods such as spectral clustering. In fact, RIC is even able to purify and improve an initial coarse clustering, even if we start with very simple methods. In an extension, we propose a fully automatic stand-alone clustering method and efficiency improvements. RIC scales well with the dataset size. Extensive experiments on synthetic and real-world datasets validate the proposed RIC framework.},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
pages = {10–es},
numpages = {29},
keywords = {noise robustness, Clustering, data summarization, parameter-free data mining}
}

@article{10.1145/1267066.1267069,
author = {Huang, Jen-Wei and Dai, Bi-Ru and Chen, Ming-Syan},
title = {Twain: Two-End Association Miner with Precise Frequent Exhibition Periods},
year = {2007},
issue_date = {August 2007},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1267066.1267069},
doi = {10.1145/1267066.1267069},
abstract = {We investigate the general model of mining associations in a temporal database, where the exhibition periods of items are allowed to be different from one to another. The database is divided into partitions according to the time granularity imposed. Such temporal association rules allow us to observe short-term but interesting patterns that are absent when the whole range of the database is evaluated altogether. Prior work may omit some temporal association rules and thus have limited practicability. To remedy this and to give more precise frequent exhibition periods of frequent temporal itemsets, we devise an efficient algorithm Twain (standing for TWo end AssocIation miNer.) Twain not only generates frequent patterns with more precise frequent exhibition periods, but also discovers more interesting frequent patterns. Twain employs Start time and End time of each item to provide precise frequent exhibition period while progressively handling itemsets from one partition to another. Along with one scan of the database, Twain can generate frequent 2-itemsets directly according to the cumulative filtering threshold. Then, Twain adopts the scan reduction technique to generate all frequent k-itemsets (k > 2) from the generated frequent 2-itemsets. Theoretical properties of Twain are derived as well in this article. The experimental results show that Twain outperforms the prior works in the quality of frequent patterns, execution time, I/O cost, CPU overhead and scalability.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
pages = {8–es},
numpages = {33},
keywords = {temporal, Association}
}

@article{10.1145/1267066.1267068,
author = {Zhang, Minghua and Kao, Ben and Cheung, David W. and Yip, Kevin Y.},
title = {Mining Periodic Patterns with Gap Requirement from Sequences},
year = {2007},
issue_date = {August 2007},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1267066.1267068},
doi = {10.1145/1267066.1267068},
abstract = {We study a problem of mining frequently occurring periodic patterns with a gap requirement from sequences. Given a character sequence S of length L and a pattern P of length l, we consider P a frequently occurring pattern in S if the probability of observing P given a randomly picked length-l subsequence of S exceeds a certain threshold. In many applications, particularly those related to bioinformatics, interesting patterns are periodic with a gap requirement. That is to say, the characters in P should match subsequences of S in such a way that the matching characters in S are separated by gaps of more or less the same size. We show the complexity of the mining problem and discuss why traditional mining algorithms are computationally infeasible. We propose practical algorithms for solving the problem and study their characteristics. We also present a case study in which we apply our algorithms on some DNA sequences. We discuss some interesting patterns obtained from the case study.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
pages = {7–es},
numpages = {39},
keywords = {periodic pattern, gap requirement, Sequence mining}
}

@article{10.1145/1267066.1267067,
author = {Loh, Wei-Yin and Chen, Chien-Wei and Zheng, Wei},
title = {Extrapolation Errors in Linear Model Trees},
year = {2007},
issue_date = {August 2007},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {2},
issn = {1556-4681},
url = {https://doi.org/10.1145/1267066.1267067},
doi = {10.1145/1267066.1267067},
abstract = {Prediction errors from a linear model tend to be larger when extrapolation is involved, particularly when the model is wrong. This article considers the problem of extrapolation and interpolation errors when a linear model tree is used for prediction. It proposes several ways to curtail the size of the errors, and uses a large collection of real datasets to demonstrate that the solutions are effective in reducing the average mean squared prediction error. The article also provides a proof that, if a linear model is correct, the proposed solutions have no undesirable effects as the training sample size tends to infinity.},
journal = {ACM Trans. Knowl. Discov. Data},
month = aug,
pages = {6–es},
numpages = {17},
keywords = {Decision tree, regression, statistics, prediction}
}

@article{10.1145/1217299.1217300,
author = {Han, Jiawei},
title = {Introduction},
year = {2007},
issue_date = {March 2007},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1217299.1217300},
doi = {10.1145/1217299.1217300},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
pages = {1–es},
numpages = {2}
}

@article{10.1145/1217299.1217301,
author = {Leskovec, Jure and Kleinberg, Jon and Faloutsos, Christos},
title = {Graph Evolution: Densification and Shrinking Diameters},
year = {2007},
issue_date = {March 2007},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1217299.1217301},
doi = {10.1145/1217299.1217301},
abstract = {How do real graphs evolve over time? What are normal growth patterns in social, technological, and information networks? Many studies have discovered patterns in static graphs, identifying properties in a single snapshot of a large network or in a very small number of snapshots; these include heavy tails for in- and out-degree distributions, communities, small-world phenomena, and others. However, given the lack of information about network evolution over long periods, it has been hard to convert these findings into statements about trends over time.Here we study a wide range of real graphs, and we observe some surprising phenomena. First, most of these graphs densify over time with the number of edges growing superlinearly in the number of nodes. Second, the average distance between nodes often shrinks over time in contrast to the conventional wisdom that such distance parameters should increase slowly as a function of the number of nodes (like O(log n) or O(log(log n)).Existing graph generation models do not exhibit these types of behavior even at a qualitative level. We provide a new graph generator, based on a forest fire spreading process that has a simple, intuitive justification, requires very few parameters (like the flammability of nodes), and produces graphs exhibiting the full range of properties observed both in prior work and in the present study.We also notice that the forest fire model exhibits a sharp transition between sparse graphs and graphs that are densifying. Graphs with decreasing distance between the nodes are generated around this transition point.Last, we analyze the connection between the temporal evolution of the degree distribution and densification of a graph. We find that the two are fundamentally related. We also observe that real networks exhibit this type of relation between densification and the degree distribution.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
pages = {2–es},
numpages = {41},
keywords = {small-world phenomena, Densification power laws, heavy-tailed distributions, graph mining, graph generators}
}

@article{10.1145/1217299.1217302,
author = {Machanavajjhala, Ashwin and Kifer, Daniel and Gehrke, Johannes and Venkitasubramaniam, Muthuramakrishnan},
title = {<i>L</i>-Diversity: Privacy beyond <i>k</i>-Anonymity},
year = {2007},
issue_date = {March 2007},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1217299.1217302},
doi = {10.1145/1217299.1217302},
abstract = {Publishing data about individuals without revealing sensitive information about them is an important problem. In recent years, a new definition of privacy called k-anonymity has gained popularity. In a k-anonymized dataset, each record is indistinguishable from at least k − 1 other records with respect to certain identifying attributes.In this article, we show using two simple attacks that a k-anonymized dataset has some subtle but severe privacy problems. First, an attacker can discover the values of sensitive attributes when there is little diversity in those sensitive attributes. This is a known problem. Second, attackers often have background knowledge, and we show that k-anonymity does not guarantee privacy against attackers using background knowledge. We give a detailed analysis of these two attacks, and we propose a novel and powerful privacy criterion called ℓ-diversity that can defend against such attacks. In addition to building a formal foundation for ℓ-diversity, we show in an experimental evaluation that ℓ-diversity is practical and can be implemented efficiently.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
pages = {3–es},
numpages = {52},
keywords = {Data privacy, ℓ-diversity, privacy-preserving data publishing, k-anonymity}
}

@article{10.1145/1217299.1217304,
author = {Bhattacharya, Indrajit and Getoor, Lise},
title = {Collective Entity Resolution in Relational Data},
year = {2007},
issue_date = {March 2007},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1217299.1217304},
doi = {10.1145/1217299.1217304},
abstract = {Many databases contain uncertain and imprecise references to real-world entities. The absence of identifiers for the underlying entities often results in a database which contains multiple references to the same entity. This can lead not only to data redundancy, but also inaccuracies in query processing and knowledge extraction. These problems can be alleviated through the use of entity resolution. Entity resolution involves discovering the underlying entities and mapping each database reference to these entities. Traditionally, entities are resolved using pairwise similarity over the attributes of references. However, there is often additional relational information in the data. Specifically, references to different entities may cooccur. In these cases, collective entity resolution, in which entities for cooccurring references are determined jointly rather than independently, can improve entity resolution accuracy. We propose a novel relational clustering algorithm that uses both attribute and relational information for determining the underlying domain entities, and we give an efficient implementation. We investigate the impact that different relational similarity measures have on entity resolution quality. We evaluate our collective entity resolution algorithm on multiple real-world databases. We show that it improves entity resolution performance over both attribute-based baselines and over algorithms that consider relational information but do not resolve entities collectively. In addition, we perform detailed experiments on synthetically generated data to identify data characteristics that favor collective relational resolution over purely attribute-based algorithms.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
pages = {5–es},
numpages = {36},
keywords = {data cleaning, graph clustering, record linkage, Entity resolution}
}

@article{10.1145/1217299.1217303,
author = {Gionis, Aristides and Mannila, Heikki and Tsaparas, Panayiotis},
title = {Clustering Aggregation},
year = {2007},
issue_date = {March 2007},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {1},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/1217299.1217303},
doi = {10.1145/1217299.1217303},
abstract = {We consider the following problem: given a set of clusterings, find a single clustering that agrees as much as possible with the input clusterings. This problem, clustering aggregation, appears naturally in various contexts. For example, clustering categorical data is an instance of the clustering aggregation problem; each categorical attribute can be viewed as a clustering of the input rows where rows are grouped together if they take the same value on that attribute. Clustering aggregation can also be used as a metaclustering method to improve the robustness of clustering by combining the output of multiple algorithms. Furthermore, the problem formulation does not require a priori information about the number of clusters; it is naturally determined by the optimization function.In this article, we give a formal statement of the clustering aggregation problem, and we propose a number of algorithms. Our algorithms make use of the connection between clustering aggregation and the problem of correlation clustering. Although the problems we consider are NP-hard, for several of our methods, we provide theoretical guarantees on the quality of the solutions. Our work provides the best deterministic approximation algorithm for the variation of the correlation clustering problem we consider. We also show how sampling can be used to scale the algorithms for large datasets. We give an extensive empirical evaluation demonstrating the usefulness of the problem and of the solutions.},
journal = {ACM Trans. Knowl. Discov. Data},
month = mar,
pages = {4–es},
numpages = {30},
keywords = {clustering categorical data, Data clustering, correlation clustering, clustering aggregation}
}

license_type: permissive

extension: bib