9041413
Structure-based graph distance measures of high degree of precision
In recent years, evaluating graph distance has become more and more important in a variety of real applications and many graph distance measures have been proposed. Among all of those measures, structure-based graph distance measures have become the research focus due to their independence of the definition of cost functions. However, existing structure-based graph distance measures have low degree of precision because only node and edge information of graphs are employed in these measures. To improve the precision of graph distance measures, we define substructure abundance vector (SAV) to capture more substructure information of a graph. Furthermore, based on SAV, we propose unified graph distance measures which are generalization of the existing structure-based graph distance measures. In general, the unified graph distance measures can evaluate graph distance in much finer grain. We also show that unified graph distance measures based on occurrence mapping and some of their variants are metrics. Finally, we apply the unified graph distance metric and its variants to the population evolution analysis and construct distance graphs of marker networks in three populations, which reflect the single nucleotide polymorphism (SNP) linkage disequilibrium (LD) differences among these populations.
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.
10409272
Repairing Inconsistent XML Documents
XML document may contain inconsistencies that violate predefined integrity constraints, and there are two basic concepts for this problem: Repair is the data consistent with the integrity constraints, and also minimally differs from the original one. Consistent data is the data common for every possible repair. In this paper, first we give a general constraint model for XML, which can express functional dependencies, keys and multivalued dependencies. Next 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 repair for inconsistent XML document, discuss the chase process to generate repairs, and prove some important properties of the chase process. Finally we give a method to obtain the greatest lower bound of all possible repairs, which is sufficient for consistent data.
8249361
SUDEPHIC: Self-Tuning Density-Based Partitioning and Hierarchical Clustering
Clustering is one of the primary techniques in data mining, for which to find the user expecting result is a major issue. However, to dynamically specify the parameters for clustering algorithms presents an obstacle for users. This paper firstly introduces a novel density-based partitioning and hierarchical algorithm, which makes it easy to employ synthetic feedback mechanism in clustering. Additionally, by investigating into the relation between parameters and the clustering result, we propose a self-tuning technique for the setting of parameters. Meanwhile, the density distribution within a cluster can be expressed in the result for the user to specify the cluster’s feature. The algorithm is both evaluated in theory and practice. It outperforms many existing algorithms both in efficiency and quality.
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.
15012785
An area-reduced scheme for modulo 2/sup n/-1 addition/subtraction
In this paper, we present a versatile area-reduced scheme for modulo 2/sup n/-1 adders and subtracters using a MUX-based increment/decrement algorithm. A FPGA-based comparison of the proposed modulo adder and the conventional modulo adder designs is carried out. The implementation results show that the proposed adder reduces the area close to 30% compared with the modulo adder of Bayoumi et al. The delay and the power are also reduced around 10%. In addition, it is also shown that the proposed design requires less hardware resources than the parallel-prefix modulo adder of Kalampoukas et al. while providing a comparable operation speed.
1519174
Split-Order Distance for Clustering and Classification Hierarchies
Clustering and classification hierarchies are organizational structures of a set of objects. Multiple hierarchies may be derived over the same set of objects, which makes distance computation between hierarchies an important task. In this paper, we model the classification and clustering hierarchies as rooted, leaf-labeled, unordered trees. We propose a novel distance metric Split-Order distance to evaluate the organizational structure difference between two hierarchies over the same set of leaf objects. Split-Order distance reflects the order in which subsets of the tree leaves are differentiated from each other and can be used to explain the relationships between the leaf objects. We also propose an efficient algorithm for computing Split-Order distance between two trees in O (n 2 d 4) time, where n is the number of leaves, and d is the maximum number of children of any node. Our experiments on both real and synthetic data demonstrate the efficiency and effectiveness of our algorithm.
28996873
Distance Measures for Anomaly Intrusion Detection
Heat treatment of shaped articles, larger than films or fibers, formed from anisotropic-melt-forming polymers provides an increase of at least 25% in energy to break in flexure. In at least one direction of measurement the heat treated articles are characterized by a flexural break strength of at least 10,000 psi, maximum strain to break in flexure of at least 2% and a flexural modulus of at least 500,000 psi. In many instances the heat treated articles can be further characterized by a notched Izod impact strength of at least 2 foot-pounds per inch. Since the heat-treated shaped articles have high levels of strength, stiffness and toughness, they are useful as replacements for some metals, e.g., brass.
3845821
Performance Analysis of Three Text-Join Algorithms
When a multidatabase system contains textual database systems (i.e., information retrieval systems), queries against the global schema of the multidatabase system may contain a new type of joins-joins between attributes of textual type. Three algorithms for processing such a type of joins are presented and their I/O costs are analyzed in this paper. Since such a type of joins often involves document collections of very large size, it is very important to find efficient algorithms to process them. The three algorithms differ on whether the documents themselves or the inverted files on the documents are used to process the join. Our analysis and the simulation results indicate that the relative performance of these algorithms depends on the input document collections, system characteristics, and the input query. For each algorithm, the type of input document collections with which the algorithm is likely to perform well is identified. An integrated algorithm that automatically selects the best algorithm to use is also proposed.
6717365
Efficient approximate entity extraction with edit distance constraints
Named entity recognition aims at extracting named entities from unstructured text. A recent trend of named entity recognition is finding approximate matches in the text with respect to a large dictionary of known entities, as the domain knowledge encoded in the dictionary helps to improve the extraction performance.
 In this paper, we study the problem of approximate dictionary matching with edit distance constraints. Compared to existing studies using token-based similarity constraints, our problem definition enables us to capture typographical or orthographical errors, both of which are common in entity extraction tasks yet may be missed by token-based similarity constraints. Our problem is technically challenging as existing approaches based on q-gram filtering have poor performance due to the existence of many short entities in the dictionary. Our proposed solution is based on an improved neighborhood generation method employing novel partitioning and prefix pruning techniques. We also propose an efficient document processing algorithm that minimizes unnecessary comparisons and enumerations and hence achieves good scalability. We have conducted extensive experiments on several publicly available named entity recognition datasets. The proposed algorithm outperforms alternative approaches by up to an order of magnitude.