k-Regret Querying is a well studied problem to query a dataset$D$for a small subset$S$of size$k$with the minimal regret ratio for unknown utility functions. In this paper, we point out some issues in$k$-Regret Querying, including the assumption of non-negative dataset and the lack of shift invariance. Known algorithms for$k$-Regret Querying are limited in scope and result quality, and are based on the assumption of non-negative data. We introduce a new problem definition called$k$-pleased querying for dealing with the shift variance issue, and propose a strategy of random sampling of the utility functions. This strategy is based on a study of the theoretical guarantee of the sampling approach. We also introduce a dimensionality reduction strategy, an improved greedy algorithm, and a study of other utility function sampling methods. All of our solutions can handle negative data. Theoretically, we derive a guarantee on the approximation attained by our sampling algorithm. Experimental results on numerous real datasets show that our proposed method is effective even with a small number of samples and small values of$k$.

$k$-Regret Querying is a well studied problem to query a dataset$D$for a small subset$S$of size$k$with the minimal regret ratio for unknown utility functions. In this paper, we point out some issues in$k$- Regret Querying, including the assumption of non-negative dataset and the lack of shift invariance. Known algorithms for$k$- Regret Querying are limited in scope and result quality, and are based on the assumption of non-negative data. We introduce a new problem definition called k-pleased querying for dealing with the shift variance issue, and propose a strategy of random sampling of the utility functions. This strategy is based on a study of the theoretical guarantee of the sampling approach. We also introduce a dimensionality reduction strategy, an improved greedy algorithm, and a study of other utility function sampling methods. All of our solutions can handle negative data. Theoretically, we derive a guarantee on the approximation attained by our sampling algorithm. Experimental results on numerous real datasets show that our proposed method is effective even with a small number of samples and small values of$k$.

Searchable symmetric encryption enables a cloud server to answer queries directly over encrypted data. Two key requirements are a strong security guarantee and a sub-linear search performance. The bucketization approach in the literature addresses these requirements at the expense of downloading false positives and requiring the local search at the client side. In this article, we propose a novel approach to meet these requirements while minimizing the clients work and communication cost. First, a relaxed notion of ciphertext indistinguishability on partitioned data is formalized, called class indistinguishability, which provides a level of ciphertext indistinguishability similar to that of bucketization but allows the server to perform search of relevant data and filter false positives. We present a construction for achieving these goals through a two-phase search algorithm. The first phase finds a candidate set through a sub-linear search. The second phase finds the exact query result using a linear search applied to the candidate set. The experiment results on large real-world data-sets show that our approach outperforms the state-of-the-art. This article focuses on the class of equality conjunction search, but it applies to the general class of Boolean queries of equalities because the latter can be reduced to several equality conjunction queries.

The most efficient known approach for shortest distance querying on road networks is via a tree decomposition based 2-hop labeling index. A major challenge here is how to reduce the query time by reducing the label size. To this end, we propose P2H with the novel ideas of projected vertex separators and optimized selection of vertex separators. We also introduce mechanisms for index maintenance for edge weight updating. Our experiments on multiple real road networks show that P2H can greatly reduce the effective label sizes and query time over existing algorithms. For larger datasets, P2H is around twice as efficient as the best known algorithm.

We consider the following secure data retrieval problem: a client outsources encrypted data blocks to a semi-trusted cloud server and later retrieves blocks without disclosing access patterns. Existing PIR and ORAM solutions suffer from serious performance bottlenecks in terms of communication or computation costs. To help eliminate this void, we introduce "access pattern unlinkability'' that separates access pattern privacy into short-term privacy at individual query level and long-term privacy at query distribution level. This new security definition provides tunable trade-offs between privacy and query performance. We present an efficient construction, called SBR protocol, using PIR and Oblivious Shuffling to enable secure data retrieval while satisfying access pattern unlinkability. Both analytical and empirical analysis show that SBR exhibits flexibility and usability in practice.

As data outsourcing becomes popular, oblivious algorithms have raised extensive attentions. Their control flow and data access pattern appear to be independent of the input data they compute on. Oblivious algorithms, therefore, are especially suitable for secure processing in outsourced environments. In this work, we focus on oblivious shuffling algorithms that aim to shuffle encrypted data blocks outsourced to a cloud server without disclosing the actual permutation of blocks to the server. Existing oblivious shuffling algorithms suffer from issues of heavy communication cost and client computation cost for shuffling large-sized blocks because all outsourced blocks must be downloaded to the client for shuffling or peeling off extra encryption layers. To help eliminate this void, we introduce the "repeatable oblivious shuffling" notation that avoids moving blocks to the client and thus restricts the communication and client computation costs to be independent of the block size. For the first time, we present a concrete construction of repeatable oblivious shuffling using additively homomorphic encryption. The comprehensive evaluation of our construction shows its effective usability in practice for shuffling large-sized blocks.

Optimal location querying (OLQ) in road networks is important for various applications. Existing work assumes no labels for servers and that a client only visits the nearest server. These assumptions are not realistic and it renders the existing work not useful in many cases. In this paper, we introduce the KOLQ problem which considers the k nearest servers of clients and labeled servers. We also proposed algorithms for the problem. Extensive experiments on the real road networks illustrate the efficiency of our proposed solutions.

Online social network (OSN) analysis has attracted much attention in recent years. One important distinguishing feature of OSNs is that every user provides his/her personal profile online, which can be regarded as the labels or attributes of this user. Knowing the number of nodes or edge with a particular label will give us deeper insight of the OSNs and can provide valuable information in many real-world applications such as web marketing and advertising. For many OSNs, one can only access parts of the network using the application programming interfaces (APIs). In such cases, conventional algorithms become infeasible. In this paper, we introduce efficient algorithms for estimating the number of edges with target labels in OSNs based on random walk. We also derive theoretical bounds on the sample size and the number of APIs calls needed in our algorithms for a probabilistic accuracy guarantee. We ran experiments on several publicly available real-world networks and the results demonstrate the effectiveness of our algorithms.

Similarity among entities in graphs plays a key role in data analysis and mining. SimRank is a widely used and popular measurement to evaluate the similarity among the vertices. In real-life applications, graphs do not only grow in size, requiring fast and precise SimRank computation for large graphs, but also change and evolve continuously over time, demanding an efficient maintenance process to handle dynamic updates. In this paper, we propose a random walk based indexing scheme to compute SimRank efficiently and accurately over large dynamic graphs. We show that our algorithm outperforms the state-of-the-art static and dynamic SimRank algorithms.

We study the problem of optimal location querying for location-based services in road networks, which aims to find locations for new servers or facilities. The existing optimal solutions on this problem consider only the cases with one new server. When two or more new servers are to be set up, the problem with minmax cost criteria, MinMax, becomes NP-hard. In this work we identify some useful properties about the potential locations for the new servers, from which we derive a novel algorithm for MinMax, and show that it is efficient when the number of new servers is small. When the number of new servers is large, we propose an efficient 3-approximate algorithm. We verify with experiments on real road networks that our solutions are effective and attain significantly better result quality compared to the existing greedy algorithms.

Subgraph querying in a large data graph is interesting for different applications. A recent study shows that top-k diversified results are useful since the number of matching subgraphs can be very large. In this work, we study the problem of top-k diversified subgraph querying that asks for a set of up to k subgraphs isomorphic to a given query graph, and that covers the largest number of vertices. We propose a novel level-based algorithm for this problem which supports early termination and has a theoretical approximation guarantee. From experiments, most of our results on real datasets used in previous works are near optimal with a query time within 10ms on a commodity machine.

Maximal cliques are elementary substructures in a graph and instrumental in graph analysis such as the structural analysis of many complex networks, graph clustering and community detection, network hierarchy detection, emerging pattern mining, vertex importance measures, etc. However, the number of maximal cliques is also notoriously large even for many small real world graphs. This size problem gives rise to challenges in both computing and managing the set of maximal cliques. Many algorithms for computing maximal cliques have been proposed in the literature; however, most of them are sequential algorithms that cannot scale due to the high complexity of the problem, while existing parallel algorithms for computing maximal cliques are mostly immature and especially suffer from skewed workload. As for managing the set of maximal cliques, which is essential due to its large size, there is barely any efficient method for querying or updating the set of maximal cliques. In this paper, we first propose a distributed algorithm built on a share-nothing architecture for computing the set of maximal cliques. We effectively address the problem of skewed workload distribution due to high-degree vertices, which also leads to drastically reduced worst-case time complexity for computing maximal cliques in common real-world graphs. Then, we propose a set of fundamental query operations and efficient algorithms to process the queries, to aid more efficient and effective analysis of the set of maximal cliques. Finally, we also devise algorithms to support efficient update maintenance of the set of maximal cliques when the underlying graph is updated. We verify the efficiency of our algorithms for computing, querying, and updating the set of maximal cliques with a range of real-world graphs from different application domains.

Graph keyword search is the process of extracting small subgraphs that contain a set of query keywords from a graph. This problem is challenging because there are many constraints, including distance constraint, keyword constraint, search time constraint, index size constraint, and memory constraint, while the size of data is inflating at a very high speed nowadays. Existing greedy algorithms guarantee good performance by sacrificing the accuracy to generate approximate answers, and exact algorithms promise exact answers but require a high memory consumption for loading indices and advanced knowledge about the maximum distance constraint. For big data applications, existing techniques are inefficient and impractical due to huge memory consumption and varied distance constraint. We propose a new keyword search algorithm that finds exact answers with low memory consumption and without advanced knowledge of maximum distance constraint. This algorithm builds a compact index structure offline based on a recent labeling index for shortest path queries. At the query time, it finds the answer efficiently by examining a small portion of the index related to a query.

Non-independent reasoning (NIR) allows the information about one record in the data to be learnt from the information of other records in the data. Most posterior/prior based privacy criteria consider NIR as a privacy violation and require to smooth the distribution of published data to avoid sensitive NIR. The drawback of this approach is that it limits the utility of learning statistical relationships. The differential privacy criterion considers NIR as a non-privacy violation, therefore, enables learning statistical relationships, but at the cost of potential disclosures through NIR. A question is whether it is possible to (1) allow learning statistical relationships, yet (2) prevent sensitive NIR about an individual. We present a data perturbation and sampling method to achieve both (1) and (2). The enabling mechanism is a new privacy criterion that distinguishes the two types of NIR in (1) and (2) with the help of the law of large numbers. In particular, the record sampling effectively prevents the sensitive disclosure in (2) while having less effect on the statistical learning in (1).

The computation of Minimum Spanning Trees (MSTs) is a fundamental graph problem with important applications. However, there has been little study of MSTs for temporal graphs, which is becoming common as time information is collected for many existing networks. We define two types of MSTs for temporal graphs, MSTa and MSTw, based on the optimization of time and cost, respectively. We propose efficient linear time algorithms for computing MSTa. We show that computing MSTw is much harder. We design efficient approximation algorithms based on a transformation to the Directed Steiner Tree problem (DST). Our solution also solves the classical DST problem with a better time complexity and the same approximation factor compared to the state-of-the-art algorithm. Our experiments on real temporal networks further verify the effectiveness of our algorithms. For MSTw, our solution is capable of shortening the runtime from 10 hours to 3 seconds.

Top-k nearest keyword search has been of interest because of applications ranging from road network location search by keyword to search of information on an RDF repository. We consider the evaluation of a query with a given vertex and a keyword, and the problem is to find a set of $k$ nearest vertices that contain the keyword. The known algorithms for handling this problem only give approximate answers. In this paper, we propose algorithms for top-k nearest keyword search that provide exact solutions and which handle networks of very large sizes. We have also verified the performance of our solutions compared with the best-known approximation algorithms with experiments on real datasets.

We consider algorithms for sorting and skew equi-join operations for computer clusters. The proposed algorithms achieve the best known theoretical workload balancing guarantee, and exhibit close to optimal balancing in our experiments. Our empirical studies also show that the proposed sorting algorithm is up to 30% faster than the state-of-the-art algorithm.

We study the problem of point-to-point distance querying for massive scale-free graphs, which is important for numerous applications. Given a directed or undirected graph, we propose to build an index for answering such queries based on a novel hop-doubling labeling technique. We derive bounds on the index size, the computation costs and I/O costs based on the properties of unweighted scale-free graphs. We show that our method is much more efficient and effective compared to the state-of-the-art techniques, in terms of both querying time and indexing costs. Our empirical study shows that our method can handle graphs that are orders of magnitude larger than existing methods.

Recent research efforts have made notable progress in improving the performance of (exhaustive) maximal clique enumeration (MCE). However, existing algorithms still suffer from exploring the huge search space of MCE. Furthermore, their results are often undesirable as many of the returned maximal cliques have large overlapping parts. This redundancy leads to problems in both computational efficiency and usefulness of MCE.

Reachability querying is a basic graph operation with numerous important applications in databases, network analysis, computational biology, software engineering, etc. Although many indexes have been proposed to answer reachability queries, most of them are only efficient for handling relatively small graphs. We propose TF-label, an efficient and scalable labeling scheme for processing reachability queries. TF-label is constructed based on a novel topological folding (TF) that recursively folds an input graph into half so as to reduce the label size, thus improving query efficiency. We show that TF-label is efficient to construct and propose efficient algorithms and optimization schemes. Our experiments verify that TF-label is significantly more scalable and efficient than the state-of-the-art methods in both index construction and query processing.

Recently, spatial keyword queries become a hot topic in the literature. One example of these queries is the collective spatial keyword query (CoSKQ) which is to find a set of objects in the database such that it covers a set of given keywords collectively and has the smallest cost. Unfortunately, existing exact algorithms have severe scalability problems and existing approximate algorithms, though scalable, cannot guarantee near-to-optimal solutions. In this paper, we study the CoSKQ problem and address the above issues.

We study the problem of computing shortest path or distance between two query vertices in a graph, which has numerous important applications. Quite a number of indexes have been proposed to answer such distance queries. However, all of these indexes can only process graphs of size barely up to 1 million vertices, which is rather small in view of many of the fast-growing real-world graphs today such as social networks and Web graphs. We propose an efficient index, which is a novel labeling scheme based on the independent set of a graph. We show that our method can handle graphs of size orders of magnitude larger than existing indexes.

Group based anonymization is the most widely studied approach for privacy-preserving data publishing. Privacy models/definitions using group based anonymization includes k -anonymity, l -diversity, and t -closeness, to name a few. The goal of this article is to raise a fundamental issue regarding the privacy exposure of the approaches using group based anonymization. This has been overlooked in the past. The group based anonymization approach by bucketization basically hides each individual record behind a group to preserve data privacy. If not properly anonymized, patterns can actually be derived from the published data and be used by an adversary to breach individual privacy. For example, from the medical records released, if patterns such as that people from certain countries rarely suffer from some disease can be derived, then the information can be used to imply linkage of other people in an anonymized group with this disease with higher likelihood. We call the derived patterns from the published data the foreground knowledge. This is in contrast to the background knowledge that the adversary may obtain from other channels, as studied in some previous work. Finally, our experimental results show such an attack is realistic in the privacy benchmark dataset under the traditional group based anonymization approach.

Maximal clique enumeration is a fundamental problem in graph theory and has important applications in many areas such as social network analysis and bioinformatics. The problem is extensively studied; however, the best existing algorithms require memory space linear in the size of the input graph. This has become a serious concern in view of the massive volume of today's fast-growing networks. We propose a general framework for designing external-memory algorithms for maximal clique enumeration in large graphs. The general framework enables maximal clique enumeration to be processed recursively in small subgraphs of the input graph, thus allowing in-memory computation of maximal cliques without the costly random disk access. We prove that the set of cliques obtained by the recursive local computation is both correct (i.e., globally maximal) and complete. The subgraph to be processed each time is defined based on a set of base vertices that can be flexibly chosen to achieve different purposes. We discuss the selection of the base vertices to fully utilize the available memory in order to minimize I/O cost in static graphs, and for update maintenance in dynamic graphs. We also apply our framework to design an external-memory algorithm for maximum clique computation in a large graph.

Abstract — While previous works on privacy-preserving serial data publishing consider the scenario where sensitive values may persist over multiple data releases, we find that no previous work has sufficient protection provided for sensitive values that can change over time, which should be the more common case. In this work, we propose to study the privacy guarantee for such transient sensitive values, which we call the global guarantee. We formally define the problem for achieving this guarantee. We show that the data satisfying the global guarantee also satisfies a privacy guarantee commonly adopted in the privacy literature called the local guarantee. I.

Temporal data are time-critical in that the snapshot at each timestamp must be made available to researchers in a timely fashion. However, due to the limited data, each snapshot likely has a skewed distribution on sensitive values, which renders classical anonymization methods not possible. In this work, we propose the “reposition model” to allow a record to be published within a close proximity of original timestamp. We show that reposition over a small proximity of timestamp is sufficient for reducing the skewness of a snapshot, therefore, minimizing the impact on window queries. We formalize the optimal reposition problem and present a linear-time solution. The contribution of this work is that it enables classical methods on temporal data.

Background knowledge is an important factor in privacy preserving data publishing. Probabilistic distribution-based background knowledge is a powerful kind of background knowledge which is easily accessible to adversaries. However, to the best of our knowledge, there is no existing work that can provide a privacy guarantee under adversary attack with such background knowledge. The difficulty of the problem lies in the high complexity of the probability computation and the non-monotone nature of the privacy condition. The only solution known to us relies on approximate algorithms with no known error bound. In this paper, we propose a new bounding condition that overcomes the difficulties of the problem and gives a privacy guarantee. This condition is based on probability deviations in the anonymized data groups, which is much easier to compute and which is a monotone function on the grouping sizes.

A highly skewed microdata contains some sensitive attribute values that occur far more frequently than others. Such data violates the “eligibility condition” assumed by existing works for limiting the probability of linking an individual to a specific sensitive attribute value. Specifically, if the frequency of some sensitive attribute value is too high, publishing the sensitive attribute alone would lead to linking attacks. In many practical scenarios, however, this eligibility condition is violated. In this paper, we consider how to publish microdata under this case. A natural solution is “minimally” suppressing “dominating” records to restore the eligibility condition. We show that the minimality of suppression may lead to linking attacks. To limit the inference probability, we propose a randomized suppression solution. We show that this approach has the least expected suppression in a large family of randomized solutions, for a given privacy requirement. Experiments show that this solution approaches the lower bound on the suppression required for this problem.

Serious concerns on privacy protection in social networks have been raised in recent years; however, research in this area is still in its infancy. The problem is challenging due to the diversity and complexity of graph data, on which an adversary can use many types of background knowledge to conduct an attack. One popular type of attacks as studied by pioneer work [2] is the use of embedding subgraphs. We follow this line of work and identify two realistic targets of attacks, namely, NodeInfo and LinkInfo. Our investigations show that k-isomorphism, or anonymization by forming k pairwise isomorphic subgraphs, is both sufficient and necessary for the protection. The problem is shown to be NP-hard. We devise a number of techniques to enhance the anonymization efficiency while retaining the data utility. A compound vertex ID mechanism is also introduced for privacy preservation over multiple data releases. The satisfactory performance on a number of real datasets, including HEP-Th, EUemail and LiveJournal, illustrates that the high symmetry of social networks is very helpful in mitigating the difficulty of the problem.

Maximal clique enumeration (MCE) is a fundamental problem in graph theory and has important applications in many areas such as social network analysis and bioinformatics. The problem is extensively studied; however, the best existing algorithms require memory space linear in the size of the input graph. This has become a serious concern in view of the massive volume of today's fast-growing network graphs. Since MCE requires random access to different parts of a large graph, it is difficult to divide the graph into smaller parts and process one part at a time, because either the result may be incorrect and incomplete, or it incurs huge cost on merging the results from different parts. We propose a novel notion, H*-graph, which defines the core of a network and extends to encompass the neighborhood of the core for MCE computation. We propose the first external-memory algorithm for MCE (ExtMCE) that uses the H*-graph to bound the memory usage. We prove both the correctness and completeness of the result computed by ExtMCE. Extensive experiments verify that ExtMCE efficiently processes large networks that cannot be fit in the memory. We also show that the H*-graph captures important properties of the network; thus, updating the maximal cliques in the H*-graph retains the most essential information, with a low update cost, when it is infeasible to perform update on the entire network.

Utilizing the skewed popularity distribution in P2P systems, common in Gnutella and KazaA like P2P applications, we propose an optimal resource (replica or link) placement strategy, which can optimally trade off the performance gain and paid cost. The proposed resource placement strategy, with better results than existing works, can be generally applied in randomized P2P systems (Symphony) and deterministic P2P systems (e.g., Chord, Pastry, Tapestry, etc.). We apply the proposed resource placement strategy, respectively, to two novel applications: PCache (a P2P-based caching scheme) and PRing (a P2P ring structure). The simulation results as well as a real deployment on Planetlab demonstrate the effectiveness of the proposed resource placement strategy in reducing the average search cost of the whole system.

To receive personalized web services, the user has to provide personal information and preferences, in addition to the query itself, to the web service. However, detailed personal information could identify the sender of sensitive queries, thus compromise user privacy. We propose the notion of online anonymity to enable users to issue personalized queries to an untrusted web service while with their anonymity preserved. The challenge for providing online anonymity is dealing with unknown and dynamic web users who can get online and offline at any time. We define this problem, discuss its implications and differences from the problems in the literature, and propose a solution.

Nowadays contents in Internet like weblogs, wikipedia and news sites become "live". How to notify and provide users with the relevant contents becomes a challenge. Unlike conventional Web search technology or the RSS feed, this paper envisions a personalized full-text content filtering and dissemination system in a highly distributed environment such as a Distributed Hash Table (DHT). Users can subscribe to their interested contents by specifying some terms and threshold values for filtering. Then, published contents will be disseminated to the associated subscribers. We propose a novel and simple framework of filter registration and content publication, STAIRS. By the new framework, we propose three algorithms (default forwarding, dynamic forwarding and adaptive forwarding) to reduce the forwarding cost and false dismissal rate; meanwhile, the subscriber can receive the desired contents with no duplicates. In particular, the adaptive forwarding utilizes the filter information to significantly reduce the forwarding cost. Experiments based on two real query logs and two real datasets show the effectiveness of our proposed framework.

Existing approaches on privacy-preserving data publishing rely on the assumption that data can be divided into quasi-identifier attributes (QI) and sensitive attribute (SA). This assumption does not hold when an attribute has both sensitive values and identifying values, which is typically the case. In this paper, we study how such attributes would impact the privacy model and data anonymization. We identify a new form of attacks, called "freeform attacks", that occur on such data without explicit QI attributes and SA attributes. We present a framework for modeling identifying/sensitive information at the value level, define a problem to eliminate freeform attacks, and outline an efficient solution.

The efficiency of matching structures is the key issue for content publish/subscribe systems. In this paper, we propose an efficient matching tree structure, named CobasTree, for a distributed environment. Particularly, we model a predicate in each subscription filter as an interval and published content value as a data point. The CobasTree is designed to index all subscription intervals and a matching algorithm is proposed to match the data points to these indexed intervals. Through a set of techniques including selective multicast by bounding intervals, cost model-based interval division, and CobasTree merging, CobasTree can match the published contents against subscription filters with a high efficiency. We call the whole framework including CobasTree and the associated techniques as COBAS. The performance evaluation in simulation environment and PlanetLab environment shows COBAS significantly outperforms two counterparts with low cost and fast forwarding.

Lately there exist increasing demands for online abnormality monitoring over trajectory streams, which are obtained from moving object tracking devices. This problem is challenging due to the requirement of high speed data processing within limited space cost. In this paper, we present a novel framework for monitoring anomalies over continuous trajectory streams. First, we illustrate the importance of distance-based anomaly monitoring over moving object trajectories. Then, we utilize the local continuity characteristics of trajectories to build local clusters upon trajectory streams and monitor anomalies via efficient pruning strategies. Finally, we propose a piecewise metric index structure to reschedule the joining order of local clusters to further reduce the time cost. Our extensive experiments demonstrate the effectiveness and efficiency of our methods.

Bichromatic reverse nearest neighbor (BRNN) has been extensively studied in spatial database literature. In this paper, we study a related problem called MaxBRNN: find an optimal region that maximizes the size of BRNNs. Such a problem has many real life applications, including the problem of finding a new server point that attracts as many customers as possible by proximity. A straightforward approach is to determine the BRNNs for all possible points that are not feasible since there are a large (or infinite) number of possible points. To the best of our knowledge, the fastest known method has exponential time complexity on the data size. Based on some interesting properties of the problem, we come up with an efficient algorithm called MaxOverlap. Extensive experiments are conducted to show that our algorithm is many times faster than the best-known technique.

The importance of skyline analysis has been well recognized in multi-criteria decision making applications. All of the previous studies assume a fixed order on the attributes in question. However, in some applications, users may be interested in skylines with respect to various total or partial orders on nominal attributes. In this paper, we identify and tackle the problem of online skyline analysis with dynamic preferences on nominal attributes. We investigate how changes of orders in attributes lead to changes of skylines. We address two novel types of interesting queries: a viewpoint query returns with respect to which orders a point is (or is not) in the skylines and an order-based skyline query retrieves the skyline with respect to a specific order. We develop two methods systematically and report an extensive performance study using both synthetic and real data sets to verify their effectiveness and efficiency.

Data publishing generates much concern over the protection of individual privacy. Recent studies consider cases where the adversary may possess different kinds of knowledge about the data. In this article, we show that knowledge of the mechanism or algorithm of anonymization for data publication can also lead to extra information that assists the adversary and jeopardizes individual privacy. In particular, all known mechanisms try to minimize information loss and such an attempt provides a loophole for attacks. We call such an attack a minimality attack. In this article, we introduce a model called m -confidentiality which deals with minimality attacks, and propose a feasible solution. Our experiments show that minimality attacks are practical concerns on real datasets and that our algorithm can prevent such attacks with very little overhead and information loss.

k-anonymization is an important privacy protection mechanism in data publishing. While there has been a great deal of work in recent years, almost all considered a single static release. Such mechanisms only protect the data up to the first release or first recipient. In practical applications, data is published continuously as new data arrive; the same data may be anonymized differently for a different purpose or a different recipient. In such scenarios, even when all releases are properly k-anonymized, the anonymity of an individual may be unintentionally compromised if recipient cross-examines all the releases received or colludes with other recipients. Preventing such attacks, called correspondence attacks, faces major challenges. In this paper, we systematically characterize the correspondence attacks and propose an efficient anonymization algorithm to thwart the attacks in the model of continuous data publishing. 1.

We consider the problem of publishing sensitive transaction data with privacy preservation. High dimensionality of transaction data poses unique challenges on data privacy and data utility. On one hand, re-identification attacks tend to use a subset of items that infrequently occur in transactions, called moles. On the other hand, data mining applications typically depend on subsets of items that frequently occur in transactions, called nuggets. Thus the problem is how to eliminate all moles while retaining nuggets as much as possible. A challenge is that moles and nuggets are multi-dimensional with exponential growth and are tangled together by shared items. We present a novel and scalable solution to this problem. The novelty lies in a compact border data structure that eliminates the need of generating all moles and nuggets.

This paper considers the problem of publishing "transaction data" for research purposes. Each transaction is an arbitrary set of items chosen from a large universe. Detailed transaction data provides an electronic image of one's life. This has two implications. One, transaction data are excellent candidates for data mining research. Two, use of transaction data would raise serious concerns over individual privacy. Therefore, before transaction data is released for data mining, it must be made anonymous so that data subjects cannot be re-identified. The challenge is that transaction data has no structure and can be extremely high dimensional. Traditional anonymization methods lose too much information on such data. To date, there has been no satisfactory privacy notion and solution proposed for anonymizing transaction data. This paper proposes one way to address this issue.

Previous works about privacy preserving serial data publishing on dynamic databases have relied on unrealistic assumptions of the nature of dynamic databases. In many applications, some sensitive values changes freely while others never change. For example, in medical applications, the disease attribute changes with time when patients recover from one disease and develop another disease. However, patients do not recover from some diseases such as HIV. We call such diseases permanent sensitive values. To the best of our knowledge, none of the existing solutions handle these realistic issues. We propose a novel anonymization approach called HD-composition to solve the above problems. Extensive experiments with real data confirm our theoretical results.

Current skyline evaluation techniques assume a fixed ordering on the attributes. However, dynamic preferences on nominal attributes are more realistic in known applications. In order to generate online response for any such preference issued by a user, one obvious solution is to enumerate all possible preferences and materialize all results of these preferences. However, the pre-processing and storage requirements of a full materialization are typically prohibitive. Instead, we propose a semi-materialization method called the IPO-tree Search which stores partial useful results only. With these partial results, the result of each possible preference can be returned efficiently. We have also conducted experiments to show the efficiency of our proposed algorithm.

Individual privacy will be at risk if a published data set is not properly deidentified. k-anonymity is a major technique to de-identify a data set. Among a number of k-anonymization schemes, local recoding methods are promising for minimizing the distortion of a k-anonymity view. This paper addresses two major issues in local recoding k-anonymization in attribute hierarchical taxonomies. First, we define a proper distance metric to achieve local recoding generalization with small distortion. Second, we propose a means to control the inconsistency of attribute domains in a generalized view by local recoding. We show experimentally that our proposed local recoding method based on the proposed distance metric produces higher quality k-anonymity tables in three quality measures than a global recoding anonymization method, Incognito, and a multidimensional recoding anonymization method, Multi. The proposed inconsistency handling method is able to balance distortion and consistency of a generalized view.

With increasing amount of data being stored in XML format, OLAP queries over these data become important. OLAP queries have been well studied in the relational database systems. However, the evaluation of OLAP queries over XML data is not a trivial extension of the relational solutions, especially when a schema is not available. In this paper, we introduce the IX-cube (Iceberg XML cube) over XML data to tackle the problem. We extend OLAP operations to XML data. We also develop efficient approaches to IX-Cube computation and OLAP query evaluation using IX-cubes.

As a promising new technology with the unique properties like high efficiency, scalability and fault tolerance, Peer-to-Peer (P2P) technology is used as the underlying network to build new Internet-scale applications. However, one of the well known issues in such an application (for example WWW) is that the distribution of data popularities is heavily tailed with a Zipf-like distribution. With consideration of the skewed popularity we adopt a proactive caching approach to handle the challenge, and focus on two key problems: where (i.e. the placement strategy: where to place the replicas) and how (i.e. the degree problem: how many replicas are assigned to one specific content)? For the where problem, we propose a novel approach which can be generally applied to structured P2P networks. Next, we solve two optimization objectives related to the how problem: MAX_PERF and MIN_COST. Our solution is called PoPCache, and we discover two interesting properties: (1) the number of replicas assigned to each content is proportional to its popularity; (2) the derived optimal solutions are related to the entropy of popularity. To our knowledge, none of the previous works has mentioned such results. Finally, we apply the results of PoPCache to propose a P2P base web caching, called as Web-PoPCache. By means of web cache trace driven simulation, our extensive evaluation results demonstrate the advantages of PoPCache and Web-PoPCache.

Recently, the skyline computation and analysis have been extended from one single full space to multidimensional subspaces, which can lead to valuable insights in some applications. Particularly, compressed skyline cubes in the form of skyline groups and their decisive subspaces provide a succinct summarization and compression of multidimensional subspace skylines. However, computing skyline cubes remains a challenging task since the existing methods have to search an exponential number of nonempty subspaces for subspace skylines. In this paper, we propose a novel and efficient method, Stellar, which exploits an interesting skyline group lattice on a small subset of objects which are in the skyline of the full space. We show that this skyline group lattice is easy to compute and can be extended to the skyline group lattice on all objects. After computing the skyline in the full space, Stellar only needs to enumerate skyline groups and their decisive subspaces using the full space skyline objects. Avoiding searching for skylines in an exponential number of subspaces improves the efficiency and the scalability of subspace skyline computation substantially in practice. An extensive performance study verifies the merits of our new method.

The importance of dominance and skyline analysis has been well recognized in multi-criteria decision making applications. Most previous studies assume a fixed order on the attributes. In practice, different customers may have different preferences on nominal attributes. In this paper, we identify an interesting data mining problem, finding favorable facets, which has not been studied before. Given a set of points in a multidimensional space, for a specific target point p we want to discover with respect to which combinations of orders (e.g., customer preferences) on the nominal attributes p is not dominated by any other points. Such combinations are called the favorable facets of p.

Finding discords in time series database is an important problem in a great variety of applications, such as space shuttle telemetry, mechanical industry, biomedicine, and financial data analysis.However, most previous methods for this problem suffer from too many parameter settings which are difficult for users.The best known approach to our knowledge that has comparatively fewer parameters still requires users to choose a word size for the compression of subsequences.In this paper, we propose a Haar wavelet and augmented trie based algorithm to mine the top-K discords from a time series database, which can dynamically determine the word size for compression.Due to the characteristics of Haar wavelet transform, our algorithm has greater pruning power than previous approaches.Through experiments with some annotated datasets, the effectiveness and efficiency of our algorithm are both attested.

In many applications, classifiers need to be built based on multiple related data streams. For example, stock streams and news streams are related, where the classification patterns may involve features from both streams. Thus instead of mining on a single isolated stream, we need to examine multiple related data streams in order to find such patterns and build an accurate classifier. Other examples of related streams include traffic reports and car accidents, sensor readings of different types or at different locations, etc. In this paper, we consider the classification problem defined over sliding-window join of several input data streams. As the data streams arrive in fast pace and the many-to-many join relationship blows up the data arrival rate even more, it is impractical to compute the join and then build the classifier each time the window slides forward. We present an efficient algorithm to build a Naïve Bayesian classifier in such context. Our method does not need to perform the join operations but is still able to build exactly the same classifier as if built on the joined result. It only examines each input tuple twice, independent of the number of tuples it joins in other streams, therefore, is able to keep pace with the fast arriving data streams in the presence of many-to-many join relationships. The experiments confirmed that our classification algorithm is more efficient than conventional methods while maintaining good classification accuracy.

Individual privacy will be at risk if a published data set is not properly de-identified. k -anonymity is a major technique to de-identify a data set. A more general view of k -anonymity is clustering with a constraint of the minimum number of objects in every cluster. Most existing approaches to achieving k -anonymity by clustering are for numerical (or ordinal) attributes. In this paper, we study achieving k -anonymity by clustering in attribute hierarchical structures. We define generalisation distances between tuples to characterise distortions by generalisations and discuss the properties of the distances. We conclude that the generalisation distance is a metric distance. We propose an efficient clustering-based algorithm for k -anonymisation. We experimentally show that the proposed method is more scalable and causes significantly less distortions than an optimal global recoding k -anonymity method. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Privacy preservation is an important issue in the release of data for mining purposes. The k-anonymity model has been introduced for protecting individual identification. Recent studies show that a more sophisticated model is necessary to protect the association of individuals to sensitive information. In this paper, we propose an (α, k)-anonymity model to protect both identifications and relationships to sensitive information in data. We discuss the properties of (α, k)-anonymity model. We prove that the optimal (α, k)-anonymity problem is NP-hard. We first presentan optimal global-recoding method for the (α, k)-anonymity problem. Next we propose a local-recoding algorithm which is more scalable and result in less data distortion. The effectiveness and efficiency are shown by experiments. We also describe how the model can be extended to more general case.

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 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.

In this work, we introduce the new problem of finding time series discords. Time series discords are subsequences of longer time series that are maximally different to all the rest of the time series subsequences. They thus capture the sense of the most unusual subsequence within a time series. While discords have many uses for data mining, they are particularly attractive as anomaly detectors because they only require one intuitive parameter (the length of the subsequence), unlike most anomaly detection algorithms that typically require many parameters. While the brute force algorithm to discover time series discords is quadratic in the length of the time series, we show a simple algorithm that is three to four orders of magnitude faster than brute force, while guaranteed to produce identical results. We evaluate our work with a comprehensive set of experiments on electrocardiograms and other medical datasets.

In this work we introduce the new problem of finding time series discords. Time series discords are subsequences of longer time series that are maximally different to all the rest of the time series subsequences. They thus capture the sense of the most unusual subsequence within a time series. While the brute force algorithm to discover time series discords is quadratic in the length of the time series, we show a simple algorithm that is 3 to 4 orders of magnitude faster than brute force, while guaranteed to produce identical results.

Privacy consideration has much significance in the application of data mining. It is very important that the privacy of individual parties will not be exposed when data mining techniques are applied to a large collection of data about the parties. In many scenarios such as data warehousing or data integration, data from the different parties form a many-to-many schema. This paper addresses the problem of privacy-preserving frequent pattern mining in such a schema across two dimension sites. We assume that sites are not trusted and they are semi-honest. Our method is based on the concept of semi-join and does not involve data encryption which is used in most previous work. Experiments are conducted to study the efficiency of the proposed models. 1

Data mining focuses on patterns that summarize the data. In this paper, we focus on mining patterns that could change the state by responding to opportunities of actions.

In this work, we introduce the new problem of finding time series discords. Time series discords are subsequences of a longer time series that are maximally different to all the rest of the time series subsequences. They thus capture the sense of the most unusual subsequence within a time series. Time series discords have many uses for data mining, including improving the quality of clustering, data cleaning, summarization, and anomaly detection. Discords are particularly attractive as anomaly detectors because they only require one intuitive parameter (the length of the subsequence) unlike most anomaly detection algorithms that typically require many parameters. We evaluate our work with a comprehensive set of experiments. In particular, we demonstrate the utility of discords with objective experiments on domains as diverse as Space Shuttle telemetry monitoring, medicine, surveillance, and industry, and we demonstrate the effectiveness of our discord discovery algorithm with more than one million experiments, on 82 different datasets from diverse domains.

Since their introduction in the seventies by Gibbs and McIntyre, dot plots have proved to be a powerful and intuitive technique for visual sequence analysis and mining. Their main domain of application is the field of bioinformatics where they are frequently used by researchers in order to elucidate genomic sequence similarities and alignment. However, this useful technique has remained comparatively constrained to domains where the data has an inherent discrete structure (i.e., text). In this paper we demonstrate how dot plots can be used for the analysis and mining of real-valued time series. We design a tool that creates highly descriptive dot plots which allow one to easily detect similarities, anomalies, reverse similarities, and periodicities well as changes in the frequencies of repetitions. As the underlying algorithm scales we with the input size, we also show the feasibility of the plots for on-line data monitoring

In this paper, we discuss a problem of finding risk patterns in medical data. We define risk patterns by a statistical metric, relative risk, which has been widely used in epidemiological research. We characterise the problem of mining risk patterns as an optimal rule discovery problem. We study an anti-monotone property for mining optimal risk pattern sets and present an algorithm to make use of the property in risk pattern discovery. The method has been applied to a real world data set to find patterns associated with an allergic event for ACE inhibitors. The algorithm has generated some useful results for medical researchers.

Frequent pattern discovery in data streams can be very useful in different applications. In time critical applications, a sliding window model is needed to discount stale data. In this paper, we adopt this model to mine the K most interesting itemsets, or to estimate the K most frequent itemsets of different sizes in a data stream. In our method, the sliding window is partitioned into buckets. We maintain the statistics of the frequency counts of the itemsets for the transactions in each bucket. We prove that our algorithm guarantees no false negatives for any data distributions. We also show that the number of false positives returned is typically small according to Zipfian Distribution. Our experiments on synthetic data show that the memory used by our method is tens of times smaller than that of a naive approach, and the false positives are negligible.

XML is emerging as a useful platform-independent data representation language. As more and more XML data is shared across data sources, it becomes important to consider the issue of XML access control. One promising approach to store the accessibility information is based on the CAM (compressed accessibility map). We make two advancements in this direction: 1) Previous work suggests that for each user group and each operation type, a different CAM is built. We observe that the performance and storage requirements can be further improved by combining multiple CAMs into an ICAM (integrated CAM). We explore this possibility and propose an integration mechanism. 2) If the change in structure of the XML data is not frequent, we suggest an efficient lookup method, which can be applied to CAMs or ICAMs, with a much lower time complexity compared to the previous approach. We show by experiments the effectiveness of our approach.

Recent research suggests that clustering for high-dimensional data should involve searching for "hidden" subspaces with lower dimensionalities, in which patterns can be observed when data objects are projected onto the subspaces. Discovering such interattribute correlations and location of the corresponding clusters is known as the projective clustering problem. We propose an efficient projective clustering technique by histogram construction (EPCH). The histograms help to generate "signatures", where a signature corresponds to some region in some subspace, and signatures with a large number of data objects are identified as the regions for subspace clusters. Hence, projected clusters and their corresponding subspaces can be uncovered. Compared to the best previous methods to our knowledge, this approach is more flexible in that less prior knowledge on the data set is required, and it is also much more efficient. Our experiments compare behaviors and performances of this approach and other projective clustering algorithms with different data characteristics. The results show that our technique is scalable to very large databases, and it is able to return accurate clustering results.

In classical association rules mining, a minimum support threshold is assumed to be available for mining frequent itemsets. However, setting such a threshold is typically hard. We handle a more practical problem; roughly speaking, it is to mine N k-itemsets with the highest supports for k up to a certain k/sub max/ value. We call the results the N-most interesting itemsets. Generally, it is more straightforward for users to determine N and k/sub max/. We propose two new algorithms, LOOPBACK and BOMO. Experiments show that our methods outperform the previously proposed Itemset-Loop algorithm, and the performance of BOMO can be an order of magnitude better than the original FP-tree algorithm, even with the assumption of an optimally chosen support threshold. We also propose the mining of "N-most interesting k-itemsets with item constraints." This allows user to specify different degrees of interestingness for different itemsets. Experiments show that our proposed Double FP-trees algorithm, which is based on BOMO, is highly efficient in solving this problem.

In the literature of data mining, many different algorithms for association rule mining have been proposed. However, there is relatively little study on how association rules can aid in more specific targets. One of the applications for association rules - maximal-profit item selection with cross-selling effect (MPIS) problem - is investigated. The problem is about selecting a subset of items, which can give the maximal profit with the consideration of cross-selling. We prove that a simple version of this problem is NP-hard. We propose a new approach to the problem with the consideration of the loss rule - a kind of association rule to model the cross-selling effect. We show that the problem can be transformed to a quadratic programming problem. In case quadratic programming is not applicable, we also propose a heuristic approach. Experiments are conducted to show that both of the proposed methods are highly effective and efficient.

This paper aims for designing algorithms for the problem of mining frequent traversal path patterns from very large Web logs with best possible efficiency. We devise two algorithms for this problem with the help of fast construction of "shallow" generalized suffix trees over a very large alphabet. These two algorithms have respectively provable linear time and sublinear complexity, and their performance is analyzed in comparison with the two a priori-like algorithms in (Chen et al., 1998) and the well-known Ukkonen algorithm for online suffix tree construction (1995). It is shown that these two algorithms are substantially efficient than the two apriori-like algorithms and the Ukkonen algorithm. The linear time algorithm has optimal performance in theory, while the sublinear time algorithm has better empirical performance.

In this paper, we study in a general setting the notion of outliered patterns as intentional knowledge of outliers and algorithms to mine those patterns. Our contributions consist of a model for defining outliered patterns with the help of categorical and behavioral similarities of outliers, and efficient algorithms for mining knowledge sets of distance-based outliers and outliered patterns. Our algorithms require only very limited domain knowledge, and no classified information. We also present an empirical study to show the feasibility of our algorithms.

Outliers, commonly referred to as exceptional cases, exist in many real-world databases. Detection of such outliers is important for many applications. In this paper, we focus on the density-based notion that discovers local outliers by means of the local outlier factor (LOF) formulation. Three enhancement schemes over LOF are introduced, namely LOF' and LOF" and GridLOF. Thorough explanation and analysis is given to demonstrate the abilities of LOF' in providing simpler and more intuitive meaning of local outlier-ness; LOF" in handling cases where LOF fails to work appropriately; and GridLOF in improving the efficiency and accuracy.

We study the problem of mining changes of classification characteristics as the data changes. Available are an old classifier, representing previous knowledge about classification characteristics, and a new data. We want to find the changes of classification characteristics in the new data. An example of such changes is “members with a large family no longer shop frequently, but they used to”. Finding this kind of changes holds the key for the organization to adopt to the changed environment and stay ahead of competitors. The challenge is that it is difficult to see what has really changed from comparing the old and new classifiers that could be very large and different. In this paper, we propose a technique to identify such changes. The idea is tracing the characteristics, in the old and new classifiers, that correspond to each other by classifying the same examples. We describe several ways to present changes so that the user can focus on a small number of important ones. We evaluate the proposed method on real life data sets.

We address the handling of time series search based on two important distance definitions: Euclidean distance and time warping distance. The conventional method reduces the dimensionality by means of a discrete Fourier transform. We apply the Haar wavelet transform technique and propose the use of a proper normalization so that the method can guarantee no false dismissal for Euclidean distance. We found that this method has competitive performance from our experiments. Euclidean distance measurement cannot handle the time shifts of patterns. It fails to match the same rise and fall patterns of sequences with different scales. A distance measure that handles this problem is the time warping distance. However, the complexity of computing the time warping distance function is high. Also, as time warping distance is not a metric, most indexing techniques would not guarantee any false dismissal. We propose efficient strategies to mitigate the problems of time warping. We suggest a Haar wavelet-based approximation function for time warping distance, called Low Resolution Time Warping, which results in less computation by trading off a small amount of accuracy. We apply our approximation function to similarity search in time series databases, and show by experiment that it is highly effective in suppressing the number of false alarms in similarity search.

With high-dimensional data, natural clusters are expected to exist in different subspaces. We propose the EPC (efficient projected clustering) algorithm to discover the sets of correlated dimensions and the location of the clusters. This algorithm is quite different from previous approaches and has the following advantages: (1) there is no requirement on the input regarding the number of natural clusters and the average cardinality of the subspaces; (2) it can handle clusters of irregular shapes; (3) it produces better clustering results compared to the best previous method; (4) it has high scalability. From experiments, it is several times faster than the previous method, while producing more accurate results.

Association rule mining is an important data mining problem. It is found to be useful for conventional relational data. However, previous work has mostly targeted on mining a single table. In real life, a database is typically made up of multiple tables and one important case is where some of the tables form a star schema. The tables typically correspond to entity sets and joining the tables in a star schema gives relationships among entity sets which can be very interesting information. Hence mining on the join result is an important problem. Based on characteristics of the star schema we propose an efficient algorithm for mining association rules on the join result but without actually performing the join operation. We show that this approach can significantly out-perform the join-then-mine approach even when the latter adopts a fastest known mining algorithm.

INTRODUCTION While extracting functional dependencies has received considerable attention [6, 3, 4, 5], relatively less research effort has been put in finding multivalued dependencies. Based on the previously proposed techniques of discovering functional dependencies [3], we propose a new algorithm for finding multivalued dependencies from a large database. We assume the usual interpretation of a relation (or table) in the relational database model where no duplicate tuples are allowed. The definition of multivalued dependency is given as below: Let R be a relation schema and let X = X1 ; X2 ; :::; Xn be a subset of R , let Y = Y1 ; Y2 ; :::; Yn be a subset of R and let Z = R \\Gamma Y \\Gamma X. The multivalued dependency<

A new layout method, Prime-groups, is proposed to evenly distribute parity groups for declustered RAID. Prime-groups satisfies most of the layout goals for a good declustered RAID layout. For the goals that are not satisfied, it is near optimal. A new layout goal maximal write and reconstruction parallelism is also proposed. If a layout satisfies the new goal, all the surviving disks can be read in parallel and can be rewritten in parallel during reconstruction and reconfiguration. Prime-groups satisfies the new goal when the write request begins in the first disk of the array. It is also near optimal in term of declustering ratio when p is a prime. Prime-groups can compliment the layouts proposed by G.A. Alvarez et. al. (1996), as the criteria to obtain a good layout is quite different between Prime-groups and those proposed by Alvarez et. al.

Clustering has typically been a problem related to numerical data. However, in databases, oftentimes the data values are categorical and cannot be assigned meaningful numerical substitutes. With the recent interest in data mining, we begin to question the possibility of clustering numerical data. Following some recent work in this area, we propose an algorithm based on dynamical systems. To our knowledge, this is the first such algorithm that can guarantee the convergence of the dynamical system, which is a very important property for successful application. We demonstrated the effectiveness of the proposed method on both real data and synthetic data. We also propose a second method based on a graph partitioning approach, for which a new definition of similarity between two nodes is tailored for categorical data. 1 Introduction Mining numerical data has received much attention in recent research in data mining. One important form of knowledge that can be derived from such da...

We propose a new n-dimensional fault-tolerant hypercube architecture. We use (n-1) switching networks to connect the N=2/sup n/ active processors and k spare processors to form an n-dimensional fault-tolerant hypercube. The k spare processors can be used to back-up any k processor failures in the fault-tolerant hypercube. We call such a method global sparing and it is optimal in terms of the number of processor failures that can be back-up by k spare processors. The new architecture can achieve a higher level of reliability using less hardware compared to previously proposed schemes.

Time series stored as feature vectors can be indexed by multidimensional index trees like R-Trees for fast retrieval. Due to the dimensionality curse problem, transformations are applied to time series to reduce the number of dimensions of the feature vectors. Different transformations like Discrete Fourier Transform (DFT) Discrete Wavelet Transform (DWT), Karhunen-Loeve (KL) transform or Singular Value Decomposition (SVD) can be applied. While the use of DFT and K-L transform or SVD have been studied on the literature, to our knowledge, there is no in-depth study on the application of DWT. In this paper we propose to use Haar Wavelet Transform for time series indexing. The major contributions are: (1) we show that Euclidean distance is preserved in the Haar transformed domain and no false dismissal will occur, (2) we show that Haar transform can outperform DFT through experiments, (3) a new similarity model is suggested to accommodate vertical shift of time series, and (4) a two-phase method is proposed for efficient n-nearest neighbor query in time series databases.

Mining numerical data is a relatively difficult problem in data mining. Clustering is one of the techniques. We consider a database with numerical attributes, in which each transaction is viewed as a multi-dimensional vector. By studying the clusters formed by these vectors, we can discover certain behaviors hidden in the data. Traditional clustering algorithms find clusters in the full space of the data sets. This results in high dimensional clusters, which are poorly comprehensible to human. One important task in this setting is the ability to discover clusters embedded in the subspaces of a high-dimensional data set. This problem is known as subspace clustering. We follow the basic assumptions of previous work CLIQUE. It is found that the number of subspaces with clustering is very large, and a criterion called the coverage is proposed in CLIQUE for the pruning. In addition to coverage, we identify new useful criteria for this problem and propose an entropybased algorithm called ENC...

Estimate of exponential convergence rate and exponential stability are studied for a class of neural networks which includes the Hopfield neural networks and the cellular neural networks. Both local and global exponential convergence is discussed. Theorems for estimate of exponential convergence rate are established and the bounds on the rate of convergence are given. The domains of attraction in the case of local exponential convergence are obtained. Simple conditions are presented for checking exponential stability of the neural networks.

An indexing structure called triple-node hierarchy is proposed for enhancing query processing in object-oriented database systems. The proposed structure provides efficient support for object references along an aggregation hierarchy by maintaining direct mapping between objects of interested pairs of classes. The intermediate classes along the object path are maintained separately for update purpose. We show that the proposed structure can achieve better performance compared to the previously known methods. The superior performance is also demonstrated by a set of simulations based on a cost model that we have developed. With some modification, the proposed structure can also provide fast support for object navigation in an integration of aggregation and inheritance hierarchies. Our results show that the extended triple-node hierarchy performs better than the best previous method known to us. keywords: object-oriented databases, indexing, aggregation, inheritance, performance analysis...

Discovery of association rules has been found useful in many applications. In previous work, all items in a basket database are treated uniformly. We generalize this to the case where items are given weights to reflect their importance to the user. The weights may correspond to special promotions on some products, or the profitability of different items. We can mine the weighted association rules with weights. The downward closure property of the support measure in the unweighted case no longer exists and previous algorithms cannot be applied. In this paper, two new algorithms are introduced to handle this problem. In these algorithms we make use of a metric called the k-support bound in the mining process. Experimental results show the efficiency of the algorithms for large databases.

We introduce a new family of interconnection networks that are Cayley graphs with fixed degrees of any even number greater than or equal to four. We call the proposed graphs cyclic-cubes because contracting some cycles in such a graph results in a generalized hypercube. These Cayley graphs have optimal fault tolerance and logarithmic diameters. For comparable number of nodes, a cyclic-cube can have a diameter smaller than previously known fixed-degree networks. The proposed graphs can adopt an optimum routing algorithm known for one of its subfamilies of Cayley graphs. We also show that a graph in the new family has a Hamiltonian cycle and, hence, there is an embedding of a ring. Embedding of meshes and hypercubes are also discussed.

Given a set of nodes S, a coterie is a set of pairwise intersecting subsets of S. Each element in a coterie is called a quorum. Mutual exclusion in a distributed system can be achieved if each request is required to gel consensus from a quorum of nodes. This technique of quorum consensus is also used for replicated distributed database systems, and bicoteries and wr-coteries have been defined to capture the requirements of read and write operations in user transactions. The author is interested in finding coteries, bicoteries, and wr-coteries with optimal communication delay. The protocols take into account the network topology. They design delay-optimal quorum consensus protocols for network topologies of trees, rings, and clustered networks.

When a data file is replicated at more than one site, we are interested in detecting corruption by comparing the multiple copies. In order to reduce the amount of messaging for large files, techniques based on page signatures and combined signatures have been explored. However, for 3 or more sites, the known methods assume that the number of corrupted page copies to be at most [M/2]-1, where M is the number of sites. We point out that this assumption is unrealistic and the corresponding methods are unnecessarily pessimistic. In this paper, we replace this assumption by another assumption which we show to be reasonable. Based on this assumption, we derived a distributed algorithm which in general achieves better performance than previously known results. Our system model is also more refined than previous work.

Many sequential algorithms have been proposed for the mining of association rules. However, very little work has been done in mining association rules in distributed databases. A direct application of sequential algorithms to distributed databases is not effective, because it requires a large amount of communication overhead. In this study, an efficient algorithm called DMA (Distributed Mining of Association rules), is proposed. It generates a small number of candidate sets and requires only O(n) messages for support-count exchange for each candidate set, where n is the number of sites in a distributed database. The algorithm has been implemented on an experimental testbed, and its performance is studied. The results show that DMA has superior performance, when compared with the direct application of a popular sequential algorithm, in distributed databases.

This paper presents a concurrency control algorithm for nested transactions accessing B-trees. It combines the idea of B-link tree with that of resilient 2-phase locking [Mos85b]. The I/O automaton model is used in the specification and proofs of correctness of the system. We define “strongly-serially correct” schedules and use this property as our correctness criterion.