waashk/dblp huggingface dataset:
characterizing individual communication patterns. the increasing availability of electronic communication data, such as that arising from e-mail exchange, presents social and information scientists with new possibilities for characterizing individual behavior and, by extension, identifying latent structure in human populations. here, we propose a model of individual e-mail communication that is sufficiently rich to capture meaningful variability across individuals, while remaining simple enough to be interpretable. we show that the model, a cascading non-homogeneous poisson process, can be formulated as a double-chain hidden markov model, allowing us to use an efficient inference algorithm to estimate the model parameters from observed data. we then apply this model to two e-mail data sets consisting of 404 and 6,164 users, respectively, that were collected from two universities in different countries and years. we find that the resulting best-estimate parameter distributions for both data sets are surprisingly similar, indicating that at least some features of communication dynamics generalize beyond specific contexts. we also find that variability of individual behavior over time is significantly less than variability across the population, suggesting that individuals can be classified into persistent "types". we conclude that communication patterns may prove useful as an additional class of attribute data, complementing demographic and network data, for user classification and outlier detection-a point that we illustrate with an interpretable clustering of users based on their inferred model parameters.
improving clustering stability with combinatorial mrfs. as clustering methods are often sensitive to parameter tuning, obtaining stability in clustering results is an important task. in this work, we aim at improving clustering stability by attempting to diminish the influence of algorithmic inconsistencies and enhance the signal that comes from the data. we propose a mechanism that takes m clusterings as input and outputs m clusterings of comparable quality, which are in higher agreement with each other. we call our method the clustering agreement process (cap). to preserve the clustering quality, cap uses the same optimization procedure as used in clustering. in particular, we study the stability problem of randomized clustering methods (which usually produce different results at each run). we focus on methods that are based on inference in a combinatorial markov random field (or comraf, for short) of a simple topology. we instantiate cap as inference within a more complex, bipartite comraf. we test the resulting system on four datasets, three of which are medium-sized text collections, while the fourth is a large-scale user/movie dataset. first, in all the four cases, our system significantly improves the clustering stability measured in terms of the macro-averaged jaccard index. second, in all the four cases our system managed to significantly improve clustering quality as well, achieving the state-of-the-art results. third, our system significantly improves stability of consensus clustering built on top of the randomized clustering solutions.
cp-summary: a concise representation for browsing frequent itemsets. this paper tackles the problem of summarizing frequent itemsets. we observe that previous notions of summaries cannot be directly used for analyzing frequent itemsets. in order to be used for analysis, one requirement is that the analysts should be able to browse all frequent itemsets by only having the summary. for this purpose, we propose to build the summary based upon a novel formulation, conditional profile (or c-profile). several features of our proposed summary are: (1) each profile in the summary can be analyzed independently, (2) it provides error guarantee (ε-adequate), and (3) it produces no false positives or false negatives. having the formulation, the next challenge is to produce the most concise summary which satisfies the requirement. in this paper, we also designed an algorithm which is both effective and efficient for this task. the quality of our approach is justified by extensive experiments. the implementations for the algorithms are available from www.cais.ntu.edu.sg/~vivek/pubs/cprofile09.
anonymizing healthcare data: a case study on the blood transfusion service. sharing healthcare data has become a vital requirement in healthcare system management; however, inappropriate sharing and usage of healthcare data could threaten patients' privacy. in this paper, we study the privacy concerns of the blood transfusion information-sharing system between the hong kong red cross blood transfusion service (bts) and public hospitals, and identify the major challenges that make traditional data anonymization methods not applicable. furthermore, we propose a new privacy model called lkc-privacy, together with an anonymization algorithm, to meet the privacy and information requirements in this bts case. experiments on the real-life data demonstrate that our anonymization algorithm can effectively retain the essential information in anonymous data for data analysis and is scalable for anonymizing large datasets.
relational learning via latent social dimensions. social media such as blogs, facebook, flickr, etc., presents data in a network format rather than classical iid distribution. to address the interdependency among data instances, relational learning has been proposed, and collective inference based on network connectivity is adopted for prediction. however, connections in social media are often multi-dimensional. an actor can connect to another actor for different reasons, e.g., alumni, colleagues, living in the same city, sharing similar interests, etc. collective inference normally does not differentiate these connections. in this work, we propose to extract latent social dimensions based on network information, and then utilize them as features for discriminative learning. these social dimensions describe diverse affiliations of actors hidden in the network, and the discriminative learning can automatically determine which affiliations are better aligned with the class labels. such a scheme is preferred when multiple diverse relations are associated with the same network. we conduct extensive experiments on social media data (one from a real-world blog site and the other from a popular content sharing site). our model outperforms representative relational learning methods based on collective inference, especially when few labeled data are available. the sensitivity of this model and its connection to existing methods are also examined.
pervasive parallelism in data mining: dataflow solution to co-clustering large and sparse netflix data. all netflix prize algorithms proposed so far are prohibitively costly for large-scale production systems. in this paper, we describe an efficient dataflow implementation of a collaborative filtering (cf) solution to the netflix prize problem [1] based on weighted coclustering [5]. the dataflow library we use facilitates the development of sophisticated parallel programs designed to fully utilize commodity multicore hardware, while hiding traditional difficulties such as queuing, threading, memory management, and deadlocks. the dataflow cf implementation first compresses the large, sparse training dataset into co-clusters. then it generates recommendations by combining the average ratings of the co-clusters with the biases of the users and movies. when configured to identify 20x20 co-clusters in the netflix training dataset, the implementation predicted over 100 million ratings in 16.31 minutes and achieved an rmse of 0.88846 without any fine-tuning or domain knowledge. this is an effective real-time prediction runtime of 9.7 us per rating which is far superior to previously reported results. moreover, the implemented co-clustering framework supports a wide variety of other large-scale data mining applications and forms the basis for predictive modeling on large, dyadic datasets [4, 7].
learning patterns in the dynamics of biological networks. our dynamic graph-based relational mining approach has been developed to learn structural patterns in biological networks as they change over time. the analysis of dynamic networks is important not only to understand life at the system-level, but also to discover novel patterns in other structural data. most current graph-based data mining approaches overlook dynamic features of biological networks, because they are focused on only static graphs. our approach analyzes a sequence of graphs and discovers rules that capture the changes that occur between pairs of graphs in the sequence. these rules represent the graph rewrite rules that the first graph must go through to be isomorphic to the second graph. then, our approach feeds the graph rewrite rules into a machine learning system that learns general transformation rules describing the types of changes that occur for a class of dynamic biological networks. the discovered graph-rewriting rules show how biological networks change over time, and the transformation rules show the repeated patterns in the structural changes. in this paper, we apply our approach to biological networks to evaluate our approach and to understand how the biosystems change over time. we evaluate our results using coverage and prediction metrics, and compare to biological literature.
olap on search logs: an infrastructure supporting data-driven applications in search engines. search logs, which contain rich and up-to-date information about users' needs and preferences, have become a critical data source for search engines. recently, more and more data-driven applications are being developed in search engines based on search logs, such as query suggestion, keyword bidding, and dissatisfactory query analysis. in this paper, by observing that many data-driven applications in search engines highly rely on online mining of search logs, we develop an olap system on search logs which serves as an infrastructure supporting various data-driven applications. an empirical study using real data of over two billion query sessions demonstrates the usefulness and feasibility of our design.
an integrated proof language for imperative programs. we present an integrated proof language for guiding the actions of multiple reasoning systems as they work together to prove complex correctness properties of imperative programs. the language operates in the context of a program verification system that uses multiple reasoning systems to discharge generated proof obligations. it is designed to 1) enable developers to resolve key choice points in complex program correctness proofs, thereby enabling automated reasoning systems to successfully prove the desired correctness properties; 2) allow developers to identify key lemmas for the reasoning systems to prove, thereby guiding the reasoning systems to find an effective proof decomposition; 3) enable multiple reasoning systems to work together productively to prove a single correctness property by providing a mechanism that developers can use to divide the property into lemmas, each of which is suitable for a different reasoning system; and 4) enable developers to identify specific lemmas that the reasoning systems should use when attempting to prove other lemmas or correctness properties, thereby appropriately confining the search space so that the reasoning systems can find a proof in an acceptable amount of time. the language includes a rich set of declarative proof constructs that enables developers to direct the reasoning systems as little or as much as they desire. because the declarative proof statements are embedded into the program as specialized comments, they also serve as verified documentation and are a natural extension of the assertion mechanism found in most program verification systems. we have implemented our integrated proof language in the context of a program verification system for java and used the resulting system to verify a collection of linked data structure implementations. our experience indicates that our proof language makes it possible to successfully prove complex program correctness properties that are otherwise beyond the reach of automated reasoning systems.
parallelizing sequential applications on commodity hardware using a low-cost software transactional memory. multicore designs have emerged as the mainstream design paradigm for the microprocessor industry. unfortunately, providing multiple cores does not directly translate into performance for most applications. the industry has already fallen short of the decades-old performance trend of doubling performance every 18 months. an attractive approach for exploiting multiple cores is to rely on tools, both compilers and runtime optimizers, to automatically extract threads from sequential applications. however, despite decades of research on automatic parallelization, most techniques are only effective in the scientific and data parallel domains where array dominated codes can be precisely analyzed by the compiler. thread-level speculation offers the opportunity to expand parallelization to general-purpose programs, but at the cost of expensive hardware support. in this paper, we focus on providing low-overhead software support for exploiting speculative parallelism. we propose stmlite, a light-weight software transactional memory model that is customized to facilitate profile-guided automatic loop parallelization. stmlite eliminates a considerable amount of checking and locking overhead in conventional software transactional memory models by decoupling the commit phase from main transaction execution. further, strong atomicity requirements for generic transactional memories are unnecessary within a stylized automatic parallelization framework. stmlite enables sequential applications to extract meaningful performance gains on commodity multicore hardware.
a decision procedure for subset constraints over regular languages. reasoning about string variables, in particular program inputs, is an important aspect of many program analyses and testing frameworks. program inputs invariably arrive as strings, and are often manipulated using high-level string operations such as equality checks, regular expression matching, and string concatenation. it is difficult to reason about these operations because they are not well-integrated into current constraint solvers. we present a decision procedure that solves systems of equations over regular language variables. given such a system of constraints, our algorithm finds satisfying assignments for the variables in the system. we define this problem formally and render a mechanized correctness proof of the core of the algorithm. we evaluate its scalability and practical utility by applying it to the problem of automatically finding inputs that cause sql injection vulnerabilities.
automatic generation of library bindings using static analysis. high-level languages are growing in popularity. however, decades of c software development have produced large libraries of fast, time-tested, meritorious code that are impractical to recreate from scratch. cross-language bindings can expose low-level c code to high-level languages. unfortunately, writing bindings by hand is tedious and error-prone, while mainstream binding generators require extensive manual annotation or fail to offer the language features that users of modern languages have come to expect. we present an improved binding-generation strategy based on static analysis of unannotated library source code. we characterize three high-level idioms that are not uniquely expressible in c's low-level type system: array parameters, resource managers, and multiple return values. we describe a suite of interprocedural analyses that recover this high-level information, and we show how the results can be used in a binding generator for the python programming language. in experiments with four large c libraries, we find that our approach avoids the mistakes characteristic of hand-written bindings while offering a level of python integration unmatched by prior automated approaches. among the thousands of functions in the public interfaces of these libraries, roughly 40% exhibit the behaviors detected by our static analyses.
chameleon: adaptive selection of collections. languages such as java and c#, as well as scripting languages like python, and ruby, make extensive use of collection classes. a collection implementation represents a fixed choice in the dimensions of operation time, space utilization, and synchronization. using the collection in a manner not consistent with this fixed choice can cause significant performance degradation. in this paper, we present chameleon, a low-overhead automatic tool that assists the programmer in choosing the appropriate collection implementation for her application. during program execution, chameleon computes elaborate trace and heap-based metrics on collection behavior. these metrics are consumed on-thefly by a rules engine which outputs a list of suggested collection adaptation strategies. the tool can apply these corrective strategies automatically or present them to the programmer. we have implemented chameleon on top of a ibm's j9 production jvm, and evaluated it over a small set of benchmarks. we show that for some applications, using chameleon leads to a significant improvement of the memory footprint of the application.
program verification using templates over predicate abstraction. we address the problem of automatically generating invariants with quantified and boolean structure for proving the validity of given assertions or generating pre-conditions under which the assertions are valid. we present three novel algorithms, having different strengths, that combine template and predicate abstraction based formalisms to discover required sophisticated program invariants using smt solvers. two of these algorithms use an iterative approach to compute fixed-points (one computes a least fixed-point and the other computes a greatest fixed-point), while the third algorithm uses a constraint based approach to encode the fixed-point. the key idea in all these algorithms is to reduce the problem of invariant discovery to that of finding optimal solutions for unknowns (over conjunctions of some predicates from a given set) in a template formula such that the formula is valid. preliminary experiments using our implementation of these algorithms show encouraging results over a benchmark of small but complicated programs. our algorithms can verify program properties that, to our knowledge, have not been automatically verified before. in particular, our algorithms can generate full correctness proofs for sorting algorithms (which requires nested universally-existentially quantified invariants) and can also generate preconditions required to establish worst-case upper bounds of sorting algorithms. furthermore, for the case of previously considered properties, in particular sortedness in sorting algorithms, our algorithms take less time than reported by previous techniques.
sharing classes between families. class sharing is a new language mechanism for building extensible software systems. recent work has separately explored two different kinds of extensibility: first, family inheritance, in which an entire family of related classes can be inherited, and second, adaptation, in which existing objects are extended in place with new behavior and state. class sharing integrates these two kinds of extensibility mechanisms. with little programmer effort, objects of one family can be used as members of another, while preserving relationships among objects. therefore, a family of classes can be adapted in place with new functionality spanning multiple classes. object graphs can evolve from one family to another, adding or removing functionality even at run time. several new mechanisms support this flexibility while ensuring type safety. class sharing has been implemented as an extension to java, and its utility for evolving and extending software is demonstrated with realistic systems.
softbound: highly compatible and complete spatial memory safety for c. the serious bugs and security vulnerabilities facilitated by c/c++'s lack of bounds checking are well known, yet c and c++ remain in widespread use. unfortunately, c's arbitrary pointer arithmetic, conflation of pointers and arrays, and programmer-visible memory layout make retrofitting c/c++ with spatial safety guarantees extremely challenging. existing approaches suffer from incompleteness, have high runtime overhead, or require non-trivial changes to the c source code. thus far, these deficiencies have prevented widespread adoption of such techniques. this paper proposes softbound, a compile-time transformation for enforcing spatial safety of c. inspired by hardbound, a previously proposed hardware-assisted approach, softbound similarly records base and bound information for every pointer as disjoint metadata. this decoupling enables softbound to provide spatial safety without requiring changes to c source code. unlike hardbound, softbound is a software-only approach and performs metadata manipulation only when loading or storing pointer values. a formal proof shows that this is sufficient to provide spatial safety even in the presence of arbitrary casts. softbound's full checking mode provides complete spatial violation detection with 67% runtime overhead on average. to further reduce overheads, softbound has a store-only checking mode that successfully detects all the security vulnerabilities in a test suite at the cost of only 22% runtime overhead on average.
semantics-aware trace analysis. as computer systems continue to become more powerful and complex, so do programs. high-level abstractions introduced to deal with complexity in large programs, while simplifying human reasoning, can often obfuscate salient program properties gleaned from automated source-level analysis through subtle (often non-local) interactions. consequently, understanding the effects of program changes and whether these changes violate intended protocols become difficult to infer. refactorings, and feature additions, modifications, or removals can introduce hard-to-catch bugs that often go undetected until many revisions later. to address these issues, this paper presents a novel dynamic program analysis that builds a semantic view of program executions. these views reflect program abstractions and aspects; however, views are not simply projections of execution traces, but are linked to each other to capture semantic interactions among abstractions at different levels of granularity in a scalable manner. we describe our approach in the context of java and demonstrate its utility to improve regression analysis. we first formalize a subset of java and a grammar for traces generated at program execution. we then introduce several types of views used to analyze regression bugs along with a novel, scalable technique for semantic differencing of traces from different versions of the same program. benchmark results on large open-source java programs demonstrate that semantic-aware trace differencing can identify precise and useful details about the underlying cause for a regression, even in programs that use reflection, multithreading, or dynamic code generation, features that typically confound other analysis techniques.