207162632
Utility-based anonymization for privacy preservation with less information loss
Privacy becomes a more and more serious concern in applications involving microdata. Recently, efficient anonymization has attracted much research work. Most of the previous methods use global recoding, which maps the domains of the quasi-identifier attributes to generalized or changed values. However, global recoding may not always achieve effective anonymization in terms of discernability and query answering accuracy using the anonymized data. Moreover, anonymized data is often used for analysis. As well accepted in many analytical applications, different attributes in a data set may have different utility in the analysis. The utility of attributes has not been considered in the previous methods.
 In this paper, we study the problem of utility-based anonymization. First, we propose a simple framework to specify utility of attributes. The framework covers both numeric and categorical data. Second, we develop two simple yet efficient heuristic local recoding methods for utility-based anonymization. Our extensive performance study using both real data sets and synthetic data sets shows that our methods outperform the state-of-the-art multidimensional global recoding methods in both discernability and query answering accuracy. Furthermore, our utility-based method can boost the quality of analysis using the anonymized data.
139968
Efficient Pattern-Growth Methods for Frequent Tree Pattern Mining
Mining frequent tree patterns is an important research problems with broad applications in bioinformatics, digital library, e-commerce, and so on. Previous studies highly suggested that pattern-growth methods are efficient in frequent pattern mining. In this paper, we systematically develop the pattern growth methods for mining frequent tree patterns. Two algorithms, Chopper and XSpanner, are devised. An extensive performance study shows that the two newly developed algorithms outperform TreeMinerV [13], one of the fastest methods proposed before, in mining large databases. Furthermore, algorithm XSpanner is substantially faster than Chopper in many cases.
18683414
Extending Tree Automata to Obtain Consistent Query Answer from Inconsistent XML Document
Data may contain inconsistencies that violate integrity constraints, the consistent query answering problem attempts to find answers common for every possible repair. In this paper, we study how to handle the inconsistent XML document, which conforms to the DTD, while violates constraints. We consider three types of constraints, including functional dependencies, keys and foreign keys. We provide a repair framework for inconsistent XML document with three basic update operations: node insertion, node deletion and value modification. Following this approach, we introduce the concept of labelled XML document, which is an extension to the traditional tree model of XML with a function to indicate the unreliable nodes. We then give the definition of minimal labelled XML document, a representation of all possible repairs and can be used for consistent query answering. We provide a method for building an extended bottom-up tree automaton. The automaton can, in only one pass, not only check the validity of an XML document w.r.t DTD and integrity constraints, but also generate the corresponding minimal labelled XML document
24206437
Chopper: Efficient algorithm for tree mining
With the development of Internet, frequent pattern mining has been extended to more complex patterns like tree mining and graph mining. Such applications arise in complex domains like bioinformatics, web mining, etc. In this paper, we present a novel algorithm, namedChopper, to discover frequent subtrees from ordered labeled trees. An extensive performance study shows that the newly developed algorithm outperformsTreeMiner V, one of the fastest methods proposed previously, in mining large databases. At the end of this paper, the potential improvement ofChopper is mentioned.
14792668
Personalization as a service: the architecture and a case study
Cloud computing has become a hot topic in the IT industry. Great efforts have been made to establish cloud computing platforms for enterprise users, mostly small businesses. However, there are few researches about the impact of cloud computing over individual users. In this paper we focus on how to provide personalized services for individual users in the cloud environment. We argue that a personalized cloud service shall compose of two parts. The client side program records user activities on personal de-vices such as PC. Besides that, the user model is also computed on the client side to avoid server overhead. The cloud side program fetches the user model periodically and adjusts its results accordingly. We build a personalized cloud data search engine prototype to prove our idea.
30881426
Constraint-Based Graph Mining in Large Database
Currently, constraints are increasingly considered as a kind of means of user- or expert-control for filtering those unsatisfied and redundant patterns rapidly during the web mining process. Recent work has highlighted the importance of constraint-based mining paradigm in the context of frequent itemsets, sequences, and many other interesting patterns in large database. However, it is still not clear how to push various constraints systematically into graph mining process. In this paper, we categorize various graph-based constraints into several major classes and develop a framework CabGin (i.e. C onstr a int- b ased G raph M in ing) to push them into mining process by their categories. Non-monotonic aggregates like average also can be pushed into CabGin with minor revision. Experimental results show that CabGin can prunes a large search space effectively by pushing graph-based constraints into mining process.
16657065
Collaborative Web caching based on proxy affinities
With the exponential growth of hosts and traffic workloads on the Internet, collaborative web caching has been recognized as an efficient solution to alleviate web page server bottlenecks and reduce traffic. However, cache discovery, i.e., locating where a page is cached, is a challenging problem, especially in the fast growing World Wide Web environment, where the number of participating proxies can be very large. In this paper, we propose a new scheme which employs proxy affinities to maintain a dynamic distributed collaborative caching infrastructure. Web pages are partitioned into clusters according to proxy reference patterns. All proxies which frequently access some page(s) in the same web page cluster form an “information group”. When web pages belonging to a web page cluster are deleted from or added into a proxy's cache, only proxies in the associated information group are notified. This scheme can be shown to greatly reduce the number of messages and other overhead on individual proxies while maintaining a high cache hit rate. Finally, we employ trace driven simulation to evaluate our web caching scheme using three web access trace logs to verify that our caching structure can provide significant benefits on real workloads.
14374205
Understanding Social Welfare Service Patterns Using Sequential Analysis
Classical exploratory data analysis methods in statistics and many of the earlier KDD methods tend to focus only on basic data types, (interval or categorical data) as the unit of analysis. However, some information cannot be interpreted unless the data is treated as a unit. For example, viewing the data as sequences of sets can reveal useful information that could not be extracted in any other way. Analyzing suitable databases from such a perspective can assist many social scientists in their work.
29637234
A new architecture of RRNS error-correcting QC encoder/decoder and its FPGA implementation
In this paper, a new architecture of a redundant residue number system (RRNS) quasi-chaotic (QC) encoder/decoder with an error-correcting ability is proposed for secure communication and is tailored to FPGA implementation. In the proposed architecture, binary subencoders and subdecoders are used so that a number of modulo operations required in the existing design of D. R. Frey (IEEE Trans. Circuits Syst. II, vol. 40, pp. 660-666, Oct. 2000) are replaced by a simple truncation. Furthermore, a size-reduced design of the R/B (residue-to-binary) converter with error-correcting function, which is the crucial part of the system, is proposed. As a case study, the proposed architecture is implemented in FPGA for the case of the 16-bit input and some simulation results obtained.
12810933
Incremental Subspace Clustering over Multiple Data Streams
Data streams are often locally correlated, with a subset of streams exhibiting coherent patterns over a subset of time points. Subspace clustering can discover clusters of objects in different subspaces. However, traditional sub- space clustering algorithms for static data sets are not readily used for incremental clustering, and is very expensive for frequent re-clustering over dynamically changing stream data. In this paper, we present an efficient incremental sub- space clustering algorithm for multiple streams over sliding windows. Our algorithm detects all the delta-CC-Clusters, which capture the coherent changing patterns among a set of streams over a set of time points. delta-CC'-Cluster s are incrementally generated by traversing a directed acyclic graph pDAG. We propose efficient insertion and deletion operations to update the pDAG dynamically. In addition, effective pruning techniques are applied to reduce the search space. Experiments on real data sets demonstrate the performance of our algorithm.
62615149
Mining Asynchronous Periodic Patterns in Time Series Data
Periodicy detection in time series data is a challenging problem of great importance in many applications. Most previous work focused on mining synchronous periodic patterns and did not recognize the misaligned presence of a pattern due to the intervention of random noise. In this paper, we propose a more flexible model of asynchronous periodic pattern that may be present only within a subsequence and whose occurrences may be shifted due to disturbance. Two parameters min/spl I.bar/rep and max/spl I.bar/dis are employed to specify the minimum number of repetitions that is required within each segment of nondisrupted pattern occurrences and the maximum allowed disturbance between any two successive valid segments. Upon satisfying these two requirements, the longest valid subsequence of a pattern is returned. A two-phase algorithm is devised to first generate potential periods by distance-based pruning followed by an iterative procedure to derive and validate candidate patterns and locate the longest valid subsequence. We also show that this algorithm cannot only provide linear time complexity with respect to the length of the sequence but also achieve space efficiency.