Adherence clustering: an efficient method for mining market-basket clusters

We explore in this paper the efficient clustering of market-basket data. Different from those of the traditional data, the features of market-basket data are known to be of high dimensionality and sparsity. Without explicitly considering the presence of the taxonomy, most prior efforts on clustering market-basket data can be viewed as dealing with items in the leaf level of the taxonomy tree. Clustering transactions across different levels of the taxonomy is of great importance for marketing strategies as well as for the result representation of the clustering techniques for market-basket data. In view of the features of market-basket data, we devise in this paper a novel measurement, called the category-based adherence, and utilize this measurement to perform the clustering. With this category-based adherence measurement, we develop an efficient clustering algorithm, called algorithm k-todes, for market-basket data with the objective to minimize the category-based adherence. The distance of an item to a given cluster is defined as the number of links between this item and its nearest tode. The category-based adherence of a transaction to a cluster is then defined as the average distance of the items in this transaction to that cluster. A validation model based on information gain is also devised to assess the quality of clustering for market-basket data. As validated by both real and synthetic datasets, it is shown by our experimental results, with the taxonomy information, algorithm k-todes devised in this paper significantly outperforms the prior works in both the execution efficiency and the clustering quality as measured by information gain, indicating the usefulness of category-based adherence in market-basket data clustering.     

Online Scheduling Sequential Objects with Periodicity for Dynamic Information Dissemination

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.     

Stabilization and extraction of 2D barcodes for camera phones

With the ubiquity of cellular phones, mobile applications with 2D barcodes have drawn a lot of attentions in recent years. When a user takes a barcode image with the camera in a mobile device, the captured image tends to be blurred due to camera shaking when the user presses the shutter. In addition, the captured image includes part of the complex background of the page with the barcode. In this paper, we point out that the above two issues, which have not been identified in previous works, deteriorate the accuracy of barcode recognition in the mobile computing. We then propose an efficient and effective algorithm to restore and extract 2D barcode from a complex background in a camera-shaken image. Compared with previous approaches, our algorithm outperforms in not only smaller running time but also higher accuracy of the barcode recognition in the mobile computing.     

On Bandwidth-Efficient Data Broadcast

In this paper, we leverage network coding to reduce the bandwidth consumption for data broadcast. We use the concept of mixing in a different way from the traditional network coding. Traditional network coding mixes all data items together. However, we mix each data item from only some data items according to the queried and stored data of receivers. Therefore, each receiver in our approach is required to receive fewer coded data to decode the required information, and the sender thereby is able to broadcast fewer data items. We formulate an optimization problem with integer-linear programming to minimize the bandwidth consumption in data broadcast. We prove that the problem is NP-hard and design an approximation algorithm that can be implemented in the data server. In addition, we show that different mixings of data items lead to different decoding costs for receivers. We design an algorithm to optimally code the data items with the minimum decoding cost.     

Optimal design of multiple hash tables for concurrency control

In this paper, we propose the approach of using multiple hash tables for lock requests with different data access patterns to minimize the number of false contentions in a data sharing environment. We first derive some theoretical results on using multiple hash tables. Then, in light of these derivations, a two-step procedure to design multiple hash tables is developed. In the first step, data items are partitioned into a given number of groups. Each group of data items is associated with the use of a hash table in such a way that lock requests to data items in the same group will be hashed into the same hash table. In the second step, given an aggregate hash table size, the hash table size for each individual data group is optimally determined so as to minimize the number of false contentions. Some design examples and remarks on the proposed method are given. It is observed from real database systems that different data sets usually have their distinct data access patterns, thus resulting in an environment where this approach can offer significant performance improvement     

Mining Web informative structures and contents based on entropy analysis

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 InfoDiscoverer, which applies the distilled structure to identify sets of article pages. InfoDiscoverer 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 InfoDiscoverer are greater than 0.956.     

Combining partitional and hierarchical algorithms for robust and efficient data clustering with cohesion self-merging

Data clustering has attracted a lot of research attention in the field of computational statistics and data mining. In most related studies, the dissimilarity between two clusters is defined as the distance between their centroids or the distance between two closest (or farthest) data points However, all of these measures are vulnerable to outliers and removing the outliers precisely is yet another difficult task. In view of this, we propose a new similarity measure, referred to as cohesion, to measure the intercluster distances. By using this new measure of cohesion, we have designed a two-phase clustering algorithm, called cohesion-based self-merging (abbreviated as CSM), which runs in time linear to the size of input data set. Combining the features of partitional and hierarchical clustering methods, algorithm CSM partitions the input data set into several small subclusters in the first phase and then continuously merges the subclusters based on cohesion in a hierarchical manner in the second phase. The time and the space complexities of algorithm CSM are analyzed. As shown by our performance studies, the cohesion-based clustering is very robust and possesses excellent tolerance to outliers in various workloads. More importantly, algorithm CSM is shown to be able to cluster the data sets of arbitrary shapes very efficiently and provide better clustering results than those by prior methods.     

Efficient Resource Allocation for Wireless Multicast

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.