Search

In this paper, we first study an important but unsolved dilemma in the literature of subspace clustering, which is referred to as "information overlapping-data coverage" challenge. Current solutions of subspace clustering usually invoke a grid-based Apriori-like procedure to identify dense regions and construct subspace clusters afterward. Due to the nature of monotonicity property in Apriori- like procedures, it is inherent that if a region is identified as dense, all its projected regions are also identified as dense, causing overlapping/redundant clustering information to be inevitably reported to users when generating clusters from such highly correlated regions. However, naive methods to filter redundant clusters will incur a challenging problem in the other side of the dilemma, called the "data coverage" issue. Note that two clusters may have highly correlated dense regions but their data members could be highly different to each other. Arbitrarily removing one of them may lose the coverage of data with clustering information, thus likely reporting an incomplete and biased clustering result. In this paper, therefore, we further propose an innovative algorithm, called "NOnRedundant Subspace Cluster mining" (NORSC), to efficiently discover a succinct collection of subspace clusters while also maintaining the required degree of data coverage. NORSC not only avoids generating the redundant clusters with most of the contained data covered by higher dimensional clusters to resolve the information overlapping problem but also limits the information loss to cope with the data coverage problem. As shown by our experimental results, NORSC is very effective in identifying a concise and small set of subspace clusters, while incurring time complexity in orders of magnitude better than that of previous works. [ABSTRACT FROM AUTHOR]

Sampling has been recognized as an important technique to improve the efficiency of clustering. However, with sampling applied, those points that are not sampled will not have their labels after the normal process. Although there is a straightforward approach in the numerical domain, the problem of how to allocate those unlabeled data points into proper clusters remains as a challenging issue in the categorical domain. In this paper, a mechanism named MAximal Resemblance Data Labeling (abbreviated as MARDL) is proposed to allocate each unlabeled data point into the corresponding appropriate cluster based on the novel categorical clustering representative, namely, N-Nodeset Importance Representative(abbreviated as NNIR), which represents clusters by the importance of the combinations of attribute values. MARDL has two advantages: 1) MARDL exhibits high execution efficiency, and 2) MARDL can achieve high intracluster similarity and low intercluster similarity, which are regarded as the most important properties of clusters, thus benefiting the analysis of cluster behaviors. MARDL is empirically validated on real and synthetic data sets and is shown to be significantly more efficient than prior works while attaining results of high quality. [ABSTRACT FROM AUTHOR]

In recent years, data broadcasting has become a promising technique in designing a mobile information system with power conservation, high scalability, and high bandwidth utilization. However, prior research topics in data broadcasting are mainly based on the assumption that the disseminated data items are of the same size. Motivated by the fact that various kinds of data objects may be disseminated in advanced information systems, we explore in this paper the problem of generating broadcast programs in a heterogeneous data broadcasting environment, in which disseminated data items can be of different sizes. Given the broadcast database and the number of channels, we first derive the analytical model of the heterogeneous data broadcasting to obtain the average waiting time of mobile users and prove the allocation problem as an NP-complete problem. In order to solve such problem, we propose a two-phase architecture to perform channel allocation. Algorithm Dimension Reduction Partitioning (DRP) is employed to perform rough allocation to derive the satisfactory solutions, whereas mechanism Cost-Diminishing Movement Selection (CDMS) is used for fine allocation to achieve local optimum solutions. In addition to the two-phase architecture, we also propose algorithm GA-CDMS according to the concept of hybrid genetic algorithm for comparison purposes. GA-CDMS can perform global search more accurately and efficiently than the conventional genetic algorithm GA, and the suboptimum that GA-CDMS achieves will be very close to the optimal solution. In order to validate the two-phase allocation algorithm DRP-CDMS, several experiments are conducted. In these experiments, we consider the important issues such as accuracy, scalability, diversity and efficiency. From the experimental results, we show that the proposed two-phase channel allocation is very practical in performing an effective channel allocation with high efficiency in a heterogeneous broadcasting environment. [ABSTRACT FROM AUTHOR]

When an event occurs, it attracts attention of information sources to publish related documents along its lifespan. The task of event detection is to automatically identify events and their related documents from a document stream, which is a set of chronologically ordered documents collected from various information sources. Generally, each event has a distinct activeness development so that its status changes continuously during its lifespan. When an event is active, there are a lot of related documents from various information sources. In contrast when it is inactive, there are very few documents, but they are focused. Previous works on event detection did not consider the characteristics of the event's activeness, and used rigid thresholds for event detection. We propose a concept called life profile, modeled by a hidden Markov model, to model the activeness trends of events. In addition, a general event detection framework, LIPED, which utilizes the learned life profiles and the burst-and-diverse characteristic to adjust the event detection thresholds adaptively, can be incorporated into existing event detection methods. Based on the official TDT corpus and contest rules, the evaluation results show that existing detection methods that incorporate LIPED achieve better performance in the cost and F1 metrics, than without. [ABSTRACT FROM AUTHOR]

The scalability of data broadcasting has been manifested by prior studies on the base of the traditional data management systems where data objects, mapped to a pair of state and value in the database, are independent, persistent, and static against simple queries. However, many modern information applications spread dynamic data objects and process complex queries for retrieving multiple data objects. Particularly, the information servers dynamically generate data objects that are dependent and can be associated into a complete response against complex queries. Accordingly, the study in this paper considers the problem of scheduling dynamic broadcast data objects in a clients-providers-servers system from the standpoint of data association, dependency, and dynamics. Since the data broadcast problem is NP-hard, we derive the lower and the upper bounds of the mean service access time. In light of the theoretical analyses, we further devise a deterministic algorithm with several gain measure functions for the approximation of schedule optimization. The experimental results show that the proposed algorithm is able to generate a dynamic broadcast schedule and also minimize the mean service access time to the extent of being very close to the theoretical optimum. [ABSTRACT FROM AUTHOR]

In this article, we explore a novel sampling model, called feature preserved sampling (FPS) that sequentially generates a high-quality sample over sliding windows. The sampling quality we consider refers to the degree of consistency between the sample proportion and the population proportion of each attribute value in a window. Due to the time-variant nature of real-world datasets, users are more likely to be interested in the most recent data. However, previous works have not been able to generate a high-quality sample over sliding windows that precisely preserves upto- date population characteristics. Motivated by this shortcoming, we have developed the FPS algorithm, which has several advantages: (1) it sequentially generates a sample from a timevariant data source over sliding windows; (2) the execution time of FPS is linear with respect to the database size; (3) the relative proportional differences between the sample proportions and population proportions of most distinct attribute values are guaranteed to be below a specified error threshold, ϵ, while the relative proportion differences of the remaining attribute values are as close to ϵ as possible, which ensures that the generated sample is of high quality; (4) the sample rate is close to the user specified rate so that a high quality sampling result can be obtained without increasing the sample size; (5) by a thorough analytical and empirical study, we prove that FPS has acceptable space overheads, especially when the attribute values have Zipfian distributions, and FPS can also excellently preserve the population proportion of multivariate features in the sample; and (6) FPS can be applied to infinite streams and finite datasets equally, and the generated samples can be used for various applications. Our experiments on both real and synthetic data validate that FPS can effectively obtain a high quality sample of the desired size. In addition, while using the sample generated by FPS in various mining applications, a significant improvement in efficiency can be achieved without compromising the model's precision. [ABSTRACT FROM AUTHOR]

Although there have been many recent studies on the mining of sequential patterns in a static database and in a database with increasing data, these works, in general, do not fully explore the effect of deleting old data from the sequences in the database. When sequential patterns are generated; the newly arriving patterns may not be identified as frequent sequential patterns due to the existence of old data and sequences. Even worse, the obsolete sequential patterns that are not frequent recently may stay in the reported results. In practice, users are usually more interested in the recent data than the old ones. To capture the dynamic nature of data addition and deletion, we propose a general model of sequential pattern mining with a progressive database while the data in the database may be static, inserted, or deleted. In addition, we present a progressive algorithm Pisa, which stands for Progressive mining of Sequential pAtterns, to progressively discover sequential patterns in defined time period of interest (POI). The POI is a sliding window continuously advancing as the time goes by. Pisa utilizes a progressive sequential tree to efficiently maintain the latest data sequences, discover the complete set of up-to-date sequential patterns, and delete obsolete data and patterns accordingly. The height of the sequential pattern tree proposed is bounded by the length of POI, thereby effectively limiting the memory space required by Pisa that is significantly smaller than the memory needed by the alternative method, Direct Appending (DirApp). Note that the sequential pattern mining with a static database and with an incremental database are special cases of the progressive sequential pattern mining. By changing Start time and End time of the POI, Pisa can easily deal with a static database or an incremental database as well. Complexity of algorithms proposed is analyzed. The experimental results show that Pisa not only significantly outperforms the prior methods in execution time by orders of magnitude but also possesses graceful scalability. [ABSTRACT FROM AUTHOR]

In this paper, we propose a bandwidth-efficient multicast mechanism for heterogeneous wireless networks. We reduce the bandwidth cost of an Internet Protocol (IP) multicast tree by adaptively selecting the cell and the wireless technology for each mobile host to join the multicast group. Our mechanism enables more mobile hosts to cluster together and leads to the use of fewer cells to save the scarce wireless bandwidth. Besides, the paths in the multicast tree connecting to the selected cells share more common links to save the wireline bandwidth. Our mechanism supports the dynamic group membership and offers mobility of group members. Moreover, our mechanism requires no modification to the current IP multicast routing protocols. We formulate the selection of the cell and the wireless technology for each mobile host in the heterogeneous wireless networks as an optimization problem. We use Integer Linear Programming to model the problem and show that the problem is NP-hard. To solve the problem, we propose a distributed algorithm based on Lagrangean relaxation and a network protocol based on the algorithm. The simulation results show that our mechanism can effectively save the wireless and wireline bandwidth as compared to the traditional IP multicast. [ABSTRACT FROM AUTHOR]

Due to the resource limitation in the data stream environments, it has been reported that answering user queries according to the wavelet synopsis of a stream is an essential ability of a Data Stream Management System (DSMS). In the literature, recent research has been elaborated upon minimizing the local error metric of an individual stream. However, many emergent applications such as stock marketing and sensor detection also call for the need of recording multiple streams in a commercial DSMS. As shown in our thorough analysis and experimental studies, minimizing global error in multiple-stream environments leads to good reliability for DSMS to answer the queries. In contrast, only minimizing local error may lead to a significant loss of query accuracy. As such, we first study in this paper the problem of maintaining the wavelet coefficients of multiple streams within collective memory so that the predetermined global error metric is minimized. Moreover, we also examine a promising application in the multistream environment, that is, the queries for top-κ range sum. We resolve the problem of efficient top-κ query processing with minimized global error by developing a general framework. For the purposes of maintaining the wavelet coefficients and processing top-κ queries, several well- designed algorithms are utilized to optimize the performance of each primary component of this general framework. We also evaluate the proposed algorithms empirically on real and simulated data streams and show that our framework can process top-κ queries accurately and efficiently. [ABSTRACT FROM AUTHOR]

We investigate the general model of mining associations in a temporal database, where the exhibition periods of items are allowed to be different from one to another. The database is divided into partitions according to the time granularity imposed. Such temporal association rules allow us to observe short-term but interesting patterns that are absent when the whole range of the database is evaluated altogether. Prior work may omit some temporal association rules and thus have limited practicability. To remedy this and to give more precise frequent exhibition periods of frequent temporal itemsets, we devise an efficient algorithm Twain (standing for TWo end AssocIation miNer.) Twain not only generates frequent patterns with more precise frequent exhibition periods, but also discovers more interesting frequent patterns. Twain employs Start time and End time of each item to provide precise frequent exhibition period while progressively handling itemsets from one partition to another. Along with one scan of the database, Twain can generate frequent 2-itemsets directly according to the cumulative filtering threshold. Then, Twain adopts the scan reduction technique to generate all frequent k-itemsets (k > 2) from the generated frequent 2-itemsets. Theoretical properties of Twain are derived as well in this article. The experimental results show that Twain outperforms the prior works in the quality of frequent patterns, execution time, I/O cost, CPU overhead and scalability. [ABSTRACT FROM AUTHOR]

Abstract  Grouping photos of the same event together is extremely useful for the management of personal photo collections. However, most methods cannot be applied to the problem of online event detection in embedded devices because they do not consider hardware constraints or a user’s photo-taking behavior. In this paper, we propose an efficient and effective event detection algorithm for managing personal photo collections in camera phones or digital cameras. The proposed algorithm fuses time and location information, which is deemed the most important information for personal photo management, and works in real time in embedded devices. We model event occurrences in a user’s photo-taking behavior as a Poisson process by imposing certain constraints on calculating the elapsed time. Location information is incorporated into event detection when confidence in a decision based on the Poisson process is not high enough. The algorithm is user-centric because it provides the unique capabilities of accepting and adjusting to user feedback. Our experiment results show that the proposed event detection method has the potential to support emerging multimedia applications in embedded devices. [ABSTRACT FROM AUTHOR]

We explore in this paper a novel sampling algorithm, referred to as algorithm PAS (standing for Proportion Approximation Sampling), to generate a high-quality online sample with the desired sample rate. The sampling quality refers to the consistency between the population proportion and the sample proportion of each categorical value in the database. Note that the state-of-the-art sampling algorithm to preserve the sampling quality has to examine the population proportion of each categorical value in a pilot sample a priori and is thus not applicable to incremental mining applications. To remedy this, algorithm PAS adaptively determines the inclusion probability of each incoming tuple in such a way that the sampling quality can be sequentially preserved while also guaranteeing the sample rate close to the user specified one. Importantly, PAS not only guarantees the proportion consistency of each categorical value but also excellently preserves the proportion consistency of multivariate statistics, which will be significantly beneficial to various data mining applications. For better execution efficiency, we further devise an algorithm, called algorithm EQAS (standing for Efficient Quality-Aware Sampling), which integrates PAS and random sampling to provide the flexibility of striking a compromise between the sampling quality and the sampling efficiency. As validated in experimental results on real and synthetic data, algorithm PAS can stably provide high-quality samples with corresponding computational overhead, whereas algorithm EQAS can flexibly generate samples with the desired balance between sampling quality and sampling efficiency. In addition, while applying the sample generated by algorithms PAS and EQAS to incremental mining applications, a significant efficiency improvement can be obtained without compromising the resulting precision, showing the prominent advantage of both proposed algorithms to be the quality-aware sampling means for incremental mining applications. [ABSTRACT FROM AUTHOR]

The article presents a study which explores new data mining capability for mobile commerce environment. It uses three algorithms namely, algorithm TJLS, algorithm TJPT, and algorithm TJPF to determine mining mobile sequential patterns from mobile transaction sequences. The study shows that a better model for mobile commerce system can be acquired by taking both moving and purchase patterns into consideration.

Web caching and Web prefetching are two important techniques used to reduce the noticeable response time perceived by users. Note that by integrating Web caching and Web prefetching, these two techniques can complement each other since the Web caching technique exploits the temporal locality, whereas Web prefetching technique utilizes the spatial locality of Web objects. However, without circumspect design, the integration of these two techniques might cause significant performance degradation to each other. In view of this, we propose in this paper an innovative cache replacement algorithm, which not only considers the caching effect in the Web environment, but also evaluates the prefetching rules provided by various prefetching schemes. Specifically, we formulate a normalized profit function to evaluate the profit from caching an object (i.e., either a nonimplied object or an implied object according to some prefetching rule). Based on the normalized profit function devised, we devise an innovative Web cache replacement algorithm, referred to as Algorithm IWCP (standing for the Integration of Web Caching and Pre fetching). Using an event-driven simulation, we evaluate the performance of Algorithm IWCP under several circumstances. The experimental results show that Algorithm IWCP consistently outperforms the companion schemes in various performance metrics. [ABSTRACT FROM AUTHOR]

Spatial clustering has attracted a lot of research attention due to its various applications. In most conventional clustering problems, the similarity measurement mainly takes the geometric attributes into consideration. However, in many real applications, the nongeometric attributes are what users are concerned about. In the conventional spatial clustering, the input data set is partitioned into several compact regions and data points which are similar to one another in their nongeometric attributes may be scattered over different regions, thus making the corresponding objective difficult to achieve. To remedy this, we propose and explore in this paper a new clustering problem on two domains, called dual clustering, where one domain refers to the optimization domain and the other refers to the constraint domain. Attributes on the optimization domain are those involved in the optimization of the objective function, while those on the constraint domain specify the application dependent constraints. Our goal is to optimize the objective function in the optimization domain while satisfying the constraint specified in the constraint domain. We devise an efficient and effective algorithm, named Interlaced Clustering-Classification, abbreviated as ICC, to solve this problem. The proposed ICC algorithm combines the information in both domains and iteratively performs a clustering algorithm on the optimization domain and also a classifications algorithm on the constraint domain to reach the target clustering effectively. The time and space complexities of the ICC algorithm are formally analyzed. Several experiments are conducted to provide the insights into the dual clustering problem and the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we devise data allocation algorithms that can utilize the knowledge of user moving patterns for proper allocation of shared data in a mobile computing system. By employing the data allocation algorithms devised, the occurrences of costly remote accesses can be minimized and the performance of a mobile computing system is thus improved. The data allocation: algorithms for shared data, which are able to achieve local optimization and global optimization, are developed. Local optimization refers to the optimization that the likelihood of local data access by an individual mobile user is maximized whereas global optimization refers to the optimization that the likelihood of local data access by all mobile users is maximized. Specifically, by exploring the features of local optimization and global optimization, we devise algorithm SD-local and algorithm SD-global to achieve local optimization and global optimization, respectively. In general, the mobile users are divided into two types, namely, frequently moving users and infrequently moving users. A measurement, called closeness measure which corresponds to the amount of the intersection between the set of frequently moving user patterns and that of infrequently moving user patterns, is derived to assess the quality of solutions provided by SD-local and SD-global. Performance of these data allocation algorithms is comparatively analyzed. From the analysis of SD-local and SD-global, it is shown that SD-local favors infrequently moving users whereas SD-global is good for frequently moving users. The simulation results show that the knowledge obtained from the user moving patterns is very important in devising effective data allocation algorithms which can lead to prominent performance improvement in a mobile computing system. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of mining the informative structure of a news Web site that consists of thousands of hyperlinked documents. We define the informative structure of a news Web site as a set of index pages (or referred to as TOC, i.e., table of contents, pages) and a set of article pages linked by these TOC pages. Based on the Hyperlink Induced Topics Search (HITS) algorithm, we propose an entropy-based analysis (LAMIS) mechanism for analyzing the entropy of anchor texts and links to eliminate the redundancy of the hyperlinked structure so that the complex structure of a Web site can be distilled. However, to increase the value and the accessibility of pages, most of the content sites tend to publish their pages with intrasite redundant information, such as navigation panels, advertisements, copy announcements, etc. To further eliminate such redundancy, we propose another mechanism, called Info-Discoverer, which applies the distilled structure to identify sets of article pages. Info-Discoverer also employs the entropy information to analyze the information measures of article sets and to extract informative content blocks from these sets. Our result is useful for search engines, information agents, and crawlers to index, extract, and navigate significant information from a Web site. Experiments on several real news Web sites show that the precision and the recall of our approaches are much superior to those obtained by conventional methods in mining the informative structures of news Web sites. On the average, the augmented LAMIS leads to prominent performance improvement and increases the precision by a factor ranging from 122 to 257 percent when the desired recall falls between 0.5 and 1. In comparison with manual heuristics, the precision and the recall of Info-Discoverer are greater than 0.956. [ABSTRACT FROM AUTHOR]

In this paper, we explore a new problem of mining general temporal association rules in publication databases. In essence, a publication database is a set of transactions where each transaction T is a set of items of which each item contains an individual exhibition period. The current model of association rule mining is not able to handle the publication database due to the following fundamental problems, i.e., 1) lack of consideration of the exhibition period of each individual item and 2) lack of an equitable support counting basis for each item. To remedy this, we propose an innovative algorithm Progressive-Partition-Miner (abbreviated as PPM) to discover general temporal association rules in a publication database. The basic idea of PPM is to first partition the publication database in light of exhibition periods of items and then progressively accumulate the occurrence count of each candidate 2-itemset; based on the intrinsic partitioning characteristics. Algorithm PPM is also designed to employ a filtering threshold in each partition to early prune out those cumulatively infrequent 2-itemsets. The feature that the number of candidate 2-itemsets generated by PPM is very close to the number of frequent 2-itemsets allows us to employ the scan reduction technique to effectively reduce the number of database scans. Explicitly, the execution time of PPM is, in orders of magnitude, smaller than those required by other competitive schemes that are directly extended from existing methods. The correctness of PPM is proven and some of its theoretical properties are derived. Sensitivity analysis of various parameters is conducted to provide many insights into Algorithm PPM. [ABSTRACT FROM AUTHOR]

The research issue of broadcasting has attracted a considerable amount of attention in a mobile computing system. By utilizing broadcast channels, a server continuously and repeatedly broadcasts data to mobile users. These broadcast channels are also known as “broadcast disks” from which mobile users can retrieve data. Using broadcasting, mobile users can obtain the data of interest efficiently and only need to wait for the required data to present on the broadcast channel. The issue of designing proper data allocation in the broadcast disks is to reduce the average expected delay of all data items. We explore in this paper the problem of generating hierarchical broadcast programs with the data access frequencies and the number of broadcast disks in a broadcast disk array given. Specifically, we first transform the problem of generating hierarchical broadcast programs into the one of constructing a channel allocation tree with variant-fanout. By exploiting the feature of tree generation with variant-fanout, we develop a heuristic algorithm VFK to minimize the expected delay of data items in the broadcast program. In order to evaluate the solution quality obtained by algorithm VFK and compare its resulting broadcast program with the optimal one, we devise an algorithm OPT based on a guided search to obtain the optimal solution. Performance of these algorithms is comparatively analyzed. Sensitivity analysis on several parameters, including the number of data items and the number of broadcast disks, is conducted. It is shown by our simulation results that by exploiting the feature of variant-fanout in constructing the channel allocation tree, the solution obtained by algorithm VFK is of very high quality and is in fact very close to the optimal one resulted by algorithm OPT. Moreover, algorithm VFK is of very good scalability which is important for algorithm VFK to be of practical use to generate hierarchical broadcast programs dynamically in a mobile computing environment. [ABSTRACT FROM AUTHOR]