12596805
FMC: An Approach for Privacy Preserving OLAP
To preserve private information while providing thorough analysis is one of the significant issues in OLAP systems. One of the challenges in it is to prevent inferring the sensitive value through the more aggregated non-sensitive data. This paper presents a novel algorithm FMC to eliminate the inference problem by hiding additional data besides the sensitive information itself, and proves that this additional information is both necessary and sufficient. Thus, this approach could provide as much information as possible for users, as well as preserve the security. The strategy does not impact on the online performance of the OLAP system. Systematic analysis and experimental comparison are provided to show the effectiveness and feasibility of FMC.
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.
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.
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.
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.
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.
17409738
Flexible Querying of Personal Information
The amount of personal data that users store and access in personal information systems has grown massively. Simple flexible search tools are a necessity for users to be able to access the data they need. In addition, the file organization that is typical in file systems is not a practical logical view anymore as applications may store information across files, or combine different objects into a single file. Users cannot be expected to know or remember the exact location and specific details about the data they are looking for; search techniques should allow for some approximation during query processing in order to return useful results while accounting for possible errors in the query. We present a scoring framework that takes into account approximation in both the content and structural dimensions of the data. Our query model extends the search to consider information across file boundaries. We implemented a prototype of our search techniques over a real data set and report on our experimental results.
42723008
Worst and Best Information Exposure Paths in Wireless Sensor Networks
This paper proposes the concept of information exposure for a point and for a path based on estimation theory. The information exposure of a point is defined as the probability that the absolute value of estimation error is less than some threshold; and the information exposure for a path is the average information exposure of all points along the path. The higher the information exposure, the higher the confidence level that some information of a target is exposed and the better the target is monitored. An approximation algorithm is proposed to solve the problem of finding the worst (best) information exposure path in wireless sensor networks, and its performance is evaluated via simulations. Furthermore, a heuristic for adaptive sensor deployment is proposed to increase the information exposure of the worst information exposure path.
2768791
Finding representative set from massive data
In the information age, data is pervasive. In some applications, data explosion is a significant phenomenon. The massive data volume poses challenges to both human users and computers. In this project, we propose a new model for identifying representative set from a large database. A representative set is a special subset of the original dataset, which has three main characteristics: It is significantly smaller in size compared to the original dataset. It captures the most information from the original dataset compared to other subsets of the same size. It has low redundancy among the representatives it contains. We use information-theoretic measures such as mutual information and relative entropy to measure the representativeness of the representative set. We first design a greedy algorithm and then present a heuristic algorithm that delivers much better performance. We run experiments on two real datasets and evaluate the effectiveness of our representative set in terms of coverage and accuracy. The experiments show that our representative set attains expected characteristics and captures information more efficiently.
30440322
A Quantitative Study of Mobility Impact for Real-Time Services on a Wi-Fi Multi-hop Network
In this paper, we analyze the performance of mobile real time services in a large-scale IEEE 802.11 multi-hop network. We present our field measurements with discussion of performance bottlenecks for VoIP services under mobile scenarios. We utilized our test bed which is located in Nebraska and supported by the University of Nebraska-Lincoln (UNL), US Federal Railroads Administrations (FRA), and major US railroad companies. Our UNL-FRA test bed consists of 8 outdoor access point towers, which are deployed along 3.5 mile of BNSF railroad. Passive measurement approaches are taken to ensure the integrity of collected data and multi-layer stream based packet analyzer has been implemented to provide a global view of the entire performance of the monitored network from the physical layer to the application layer. Based on our analysis of collected data, we conclude that in a typical outdoor 802.11 environment similar to our UNL-FRA test bed, uncertain handoff latencies and lack of Quality of Service guarantee are main performance bottlenecks for real-time applications. Furthermore, we discuss the enhancement strategies to support mobility in high-speed railway networks. We believe our work is one of the initial efforts in wireless mobile network field measurement in terms of scale, methodology, and analysis.
36057715
Guest Editors' Introduction: Special Issue on Mining Biological Data
MINING biological data is an emerging area of intersection between data mining and bioinformatics. Bioinformaticians have been working on the research and development of computational methodologies and tools for expanding the use of biological, medical, behavioral, or health-related data. Data mining researchers have been making substantial contribution to the development of models and algorithms to meet challenges posed by the bioinformatics research. Some successful examples are frequent pattern discovery on biological molecules, text mining in biomedical literature, information integration, probabilistic modeling of genome sequences, etc. This special issue of the IEEE Transactions on Knowledge and Data Engineering features a collection of 11 papers, selected from 54 submissions, representing recent advances at the frontier of mining biological data. Mining frequent trees is very useful in bioinformatics applications. The first paper, “Efficiently Mining Frequent Trees in a Forest: Algorithms and Applications” by Mohammed J. Zaki, formulates the problem of mining (embedded) subtrees in a forest of rooted, labeled, and ordered trees. The author presents TreeMiner, a novel algorithm to discover all frequent subtrees in a forest, using a new data structure called scope-list. TreeMiner has been proven to be superior to previous methods such as PatternMatcher and has shown promising results in analyzing RNA structure and phylogenetics data sets. In the second paper, “Frequent Substructure-Based Approaches for Classifying Chemical Compounds” by Mukund Deshpande, Michihiro Kuramochi, Nikil Wale, and George Karypis, the authors devise a substructurebased classification algorithm that decouples the substructure discovery process from the classification model construction and uses frequent subgraph discovery algorithms to find all topological and geometric substructures present in the data set. The advantage of this approach is that, during classification model construction, all relevant substructures are available and thus allow the classifier to intelligently select the most discriminating ones. This approach is employed to build models to correctly assign chemical compounds to various classes of interests, which have many applications in pharmaceutical research and are used extensively at various phases during the drug development process. Glycans, or carbohydrate sugar chains, are regarded as the third class of biological molecules, subsequent to DNA and proteins, and the recent advent of glycome informatics has generated an increasing number of glycan structures and annotation data. Glycans play important roles in the development and functioning of multicellular organisms and their structures can be represented by labeled ordered trees. The third paper, “A Probabilistic Model for Mining Labeled Ordered Trees: Capturing Patterns in Carbohydrate Sugar Chains” byNobuhisaUeda, Kiyoko F. Aoki-Kinoshita, Atsuko Yamaguchi, Tatsuya Akustu, and Hiroshi Mamitsuka, proposes a probabilistic model for mining labeled ordered trees and an EM algorithm for efficient learning. Proteins are the machinery of life. A number of techniques have been developed to classify proteins according to important features in their sequences, secondary structures, or three-dimensional structures. The fourth paper, “Finding Patterns on Protein Surfaces: Algorithms and Applications to Protein Classification” by Xiong Wang, introduces a novel approach to protein classification based on significant geometric patterns on the surface of a protein. The binding in protein-protein interactions exhibits a kind of biochemical stability in cells, which can be described by the mathematical notion of the fixed points. In the fifth paper, “Using Fixed Point Theorems to Model the Binding in Protein-Protein Interactions” by Jinyan Li and Haiquan Li, the authors define a point as a protein motif pair consisting of two traditional protein motifs. They propose a method to discover stable motif pairs of a given function from a large protein interaction sequence data set. With the rapid growth of articles on genomics research, it has become a challenge for biomedical researchers to access this ever-increasing quantity of information to understand the newest discovery of functions of proteins they are studying. To facilitate functional annotation of proteins by utilizing the huge amounts of biomedical literature and transforming the knowledge into easily accessible database formats, the text mining technique thus becomes essential. The sixth paper, “Literature Extraction of Protein Functions Using Sentence Pattern Mining” by Jung-Hsien Chiang and Hsu-Chun Yu, proposes the method of sentence pattern mining to extract protein functions from biomedical literature. Identifying concepts that have already been patented is essential for undertaking new biomedical research. Traditional keyword-based search on patent databases may not be sufficient enough to retrieve all the relevant information, especially for the biomedical domain. The seventh paper, “Information Retrieval and Knowledge Discovery Utilizing a BioMedical Patent Semantic Web” by Sougata Mukherjea, Bhuvan Bamba, and Pankaj Kankar, presents BioPatentMiner, a system that facilitates information retrieval and knowledge discovery from biomedical patents. BioPatentMiner first identifies biological terms IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 17, NO. 8, AUGUST 2005 1019