Recently, Non-Fungible Tokens (NFTs) have attracted attention as valuable digital assets. However, NFT marketplaces face complex challenges in simultaneously recommending optimal pricing to sellers and desirable NFTs to buyers. Unlike conventional marketplaces that focus only on balancing demand and supply between sellers and buyers, these tasks are complicated by intricate value interdependencies arising from diverse buyer preferences, budgets, trait rarities, and the unprecedented breeding mechanisms. This paper formulates the NFT Project Pricing/Purchasing Recommendation (NP3R) problem, aiming to achieve a competitive equilibrium that concurrently optimizes seller revenue and buyer utility. We introduce BANTER, an iterative algorithm that jointly determines (1) optimal NFT purchases for buyers (via NFT-REC), considering breeding utility and current prices; and (2) optimal pricing for sellers (via PRICEREC), based on aggregated demand from NFT-REC. To efficiently manage the combinatorial complexity of breeding, we devise Optimal Parent Pair Selection (OPPS) and Heterogeneous Parent Set Selection (HPSS) schemes. Theoretical analysis guarantees BANTER to converge to a competitive equilibrium. Experiments on five real-world NFT datasets demonstrate its effectiveness in enhancing both seller revenue and average buyer utility. Source code: https://github.com/jimmy-academia/BANTER

Non-fungible tokens (NFTs) have emerged as a transformative innovation in art and technology, relying heavily on social networks for promotion and revenue generation. The value of NFTs is profoundly influenced by their scarcity, rarity, and unique breeding mechanisms, which present novel challenges for viral marketing strategies. In this paper, we introduce a new research problem of NFT Revenue Maximization (NRM), which focuses on maximizing revenue from the perspective of NFT marketplaces by optimally selecting users for viral marketing campaigns (NFT airdrops) and determining the ideal quantities of NFTs to release. We prove the hardness of NRM and propose an approximation algorithm named Quantity and Offspring-Oriented Airdrops (QOOA). Our algorithm leverages the concepts of Scarcity-Conscious Revenue and Valuation-based Quantity Inequality to prune suboptimal airdrops and quantities at an early stage. To further enhance revenue through NFT breeding, QOOA identifies and incentivizes Rare Trait Collectors to acquire multiple NFTs with rare traits, facilitating the breeding of high-value offspring. Experimental results demonstrate that QOOA significantly outperforms baselines, achieving up to 3.8 times higher revenue in large-scale social networks.

Community detection is a cornerstone problem in social network analysis (SNA), aimed at identifying cohesive communities with minimal external links. However, the rise of generative AI and Metaverse introduce complexities by creating hybrid human-AI social networks (denoted by HASNs), where traditional methods fall short, especially in human-centric settings. This paper introduces a novel community detection problem in HASNs (denoted by MetaCD), which seeks to enhance human connectivity within communities while reducing the presence of AI nodes. Effective processing of MetaCD poses challenges due to the delicate trade-off between excluding certain AI nodes and maintaining community structure. To address this, we propose CUSA, an innovative framework incorporating AI-aware clustering techniques that navigate this trade-off by selectively retaining AI nodes that contribute to community integrity. Furthermore, given the scarcity of real-world HASNs, we devise four strategies for synthesizing these networks under various hypothetical scenarios. Empirical evaluations on real social networks, reconfigured as HASNs, demonstrate the effectiveness and practicality of our approach compared to traditional non-deep learning and graph neural network (GNN)-based methods.

In this paper, we address the problem of revenue maximization (RM) for multi-grade products in social networks by considering pricing, seed selection, and coupon distribution. Previous works on RM often focus on a single product and neglect the use of coupons for promotion. We propose a new optimization problem,Revenue Maximization of Multi-Grade Product(RMMGP), to simultaneously determine pricing, seed selection, and coupon distribution for multi-grade products with both promotional and competitive relationships between grades in order to maximize revenue through viral marketing. We prove the hardness and inapproximability of RMMGP and show that the revenue function is not monotone or submodular. To solve RMMGP, we design an approximation algorithm, namelyData-Dependent Revenue Maximization (DDRM), and propose thePricing-Seeding-Coupon allocation (PriSCa)algorithm, which uses the concepts of Worth Receiving Probability, Pricing-Promotion Alternating Framework, and Independent/Holistic Customer-Grade Determinant sets. Our experiments on real social networks, using valuation distributions from Amazon.com, demonstrate that PriSCa and DDRM achieve on average 1.5 times higher revenue than state-of-the-art approaches. Additionally, PriSCa is efficient and scalable on large datasets.

Data poisoning attacks against recommender systems (RecSys) often assume a single seller as the adversary. However, in reality, there are usually multiple sellers attempting to promote their items through RecSys manipulation. To obtain the best data poisoning plan, it is important for an attacker to anticipate and withstand the actions of his opponents. This work studies the problem of Multiplayer Comprehensive Attack (MCA) from the perspective of the attacker, considering the subsequent attacks by his opponents. In MCA, we target the Heterogeneous RecSys, where user-item interaction records, user social network, and item correlation graph are used for recommendations. To tackle MCA, we present the Multilevel Stackelberg Optimization over Progressive Differentiable Surrogate (MSOPDS). The Multilevel Stackelberg Optimization (MSO) method is used to form the optimum strategies by solving the Stackelberg game equilibrium between the attacker and his opponents, while the Progressive Differentiable Surrogate (PDS) addresses technical challenges in deriving gradients for candidate poisoning actions. Experiments on Heterogeneous RecSys trained with public datasets show that MSOPDS outperforms all examined prior works by up to 10.6% in average predicted ratings and up to 11.4% in HitRate@3 for an item targeted by an attacker facing one opponent. Source code provided in https://github.com/jimmy-academia/MSOPDS.

The phenomena of influence diffusion on social networks have received tremendous research interests in the past decade. While most prior works mainly focus on predicting the total influence spread on a single network, a marketing campaign that exploits influence diffusion often involves multiple channels with various information disseminated on different media. In this paper, we introduce a new influence estimation problem, namely Content-aware Multi-channel Influence Diffusion (CMID), and accordingly propose CMINet to predict newly influenced users, given a set of seed users with different multimedia contents. In CMINet, we first introduce DiffGNN to encode the influencing power of users (nodes) and Influence-aware Optimal Transport (IOT) to align the embeddings to address the distribution shift across different diffusion channels. Then, we transform CMID into a node classification problem and propose Social-based Multimedia Feature Extractor (SMFE) and Content-aware Multi-channel Influence Propagation (CMIP) to jointly learn the user preferences on multimedia contents and predict the susceptibility of users. Furthermore, we prove that CMINet preserves monotonicity and submodularity, thus enabling (1 − 1/e)-approximate solutions for influence maximization. Experimental results manifest that CMINet outperforms eleven baselines on three public datasets.

The potential impact of epidemics, e.g., COVID-19, H1N1, and SARS, is severe on public health, the economy, education, and society. Before effective treatments are available and vaccines are fully deployed, combining Non-Pharmaceutical Interventions (NPIs) and vaccination strategies is the main approaches to contain the epidemic or live with the virus. Therefore, research for deciding the best containment operations to contain the epidemic based on various objectives and concerns is much needed. In this paper, we formulate the problem of Containment Operation Optimization Design (COOD) that optimizes the epidemic containment by carefully analyzing contacts between individuals. We prove the hardness of COOD and propose an approximation algorithm, named Multi-Type Action Scheduling (MTAS), with the ideas of Infected Ratio, Contact Risk, and Severity Score to select and schedule appropriate actions that implement NPIs and allocate vaccines for different groups of people. We evaluate MTAS on real epidemic data of a population with real contacts and compare it against existing approaches in epidemic and misinformation containment. Experimental results demonstrate that MTAS improves at least 200% over the baselines in the test case of sustaining public health and the economy. Moreover, the applicability of MTAS to various epidemics of different dynamics is demonstrated, i.e., MTAS can effectively slow down the peak and reduce the number of infected individuals at the peak.

Existing research on finding social groups mostly focuses on dense subgraphs in social networks. However, finding socially tenuous groups also has many important applications. In this paper, we introduce the notion of k-triangles to measure the tenuity of a group. We then formulate a new research problem, Minimum k-Triangle Disconnected Group with No-Pair Constraint (MkTG), to find a socially tenuous group from the online social network. We prove that MkTG is NP-hard and inapproximable within any ratio. Two algorithms, namely TERA and TERA-ADV, are designed for solving MkTG effectively and efficiently. Further, we examine the MkTG problem on tree-based social networks, due to their structural resemblance with corporate social networks built upon the supervision relation. Accordingly, we devise an efficient algorithm, namely Tenuity Maximization for Trees (TMT), to obtain the optimal solution in polynomial time. In addition, we study a more general version of MkTG, named Generalized Minimum k-Triangle Disconnected Group without No-Pair Constraint (MkTG-G). We formulate MkTG-G, analyze its inapproximability, and propose a randomized approximation algorithm, named Randomized Ranking with Limited Neighborhood Participation (RLNP). Experimental results on real datasets manifest that the proposed algorithms outperform the baselines in terms of both efficiency and solution quality.

The social presence theory in social psychology suggests that computer-mediated online interactions are inferior to face-to-face, in-person interactions. Thus, it's important to organize social activities for online social network users to meet in person. In this paper, we consider the scenarios of organizing in person friend-making social activities via online social networks (OSNs) and formulate a new research problem, namely,Hop-bounded Maximum Group Friending (HMGF), that takes into consideration both existing friendships and the likelihood of new friend making in organization of the targeted in person friend-making social activities. To find a set of attendees for such social activities, HMGF is unique and challenging due to the interplay of the group size, the constraint on existing friendships, and the objective of maximizing the likelihood of friend making. We prove that HMGF is NP-Hard, and there exists no approximation algorithm for it unless$P=NP$. We also provide an Integer Linear Programming (ILP) formulation for the HMGF problem. The ILP formulation, which can be solved efficiently by a commercial solver to obtain the optimal solution for small HMGF instances, acts as a baseline approach for comparison in the evaluation of the proposed algorithm. We further propose an error-bounded approximation algorithm,MaxGF, to efficiently obtain the solutions very close to the optimal solutions. To boost the performance, we devise two graph-theoretical pruning strategies, namelyNeighbor PruningandCore Pruning, which can effectively avoid redundant graph explorations to improve the performance of HMGF. We also study HMGF on a class of special graphs,threshold graphs, which have properties very similar to many online social networks. We prove that MaxGF can obtain the optimal solution to HMGF on threshold graphs in polynomial time. We conduct a user study to validate our problem formulation and perform extensive experiments on real datasets to demonstrate the efficiency and effectiveness of our proposed algorithm. The experimental results manifest that our proposed algorithms outperform the baselines, including the ILP formulation.

With the maturity and popularity of Internet of Things (IoT), the notion of Social Internet of Things (SIoT) has been proposed to support novel applications and networking services for the IoT in more effective and efficient ways. Although there are many works for SIoT, they focus on designing the architectures and protocols for SIoT under the specific schemes. How to efficiently utilize the collaboration capability of SIoT to complete complex tasks remains unexplored. Therefore, we propose a new problem family, namely,Task-Optimized SIoT Selection (TOSS), to find the best group of IoT objects for a given set of tasks in the task pool. TOSS aims to select the target SIoT group such that the target SIoT group is able to easily communicate with each other while maximizing the accuracy of performing the given tasks. We propose two problem formulations, namedBounded Communication-loss TOSS (BC-TOSS)andRobustness Guaranteed TOSS (RG-TOSS), for different scenarios and prove that they are both NP-hard and inapproximable. We propose a polynomial-time algorithm with a performance guarantee for BC-TOSS, and an efficient polynomial-time algorithm to obtain good solutions for RG-TOSS. Moreover, as RG-TOSS is NP-hard and inapproximable within any factor, we further proposeStructure-Aware Reinforcement Learning (SARL)to leverage the Graph Convolutional Networks (GCN) and Deep Reinforcement Learning (DRL) to effectively solve RG-TOSS. Further, since we use graph models to simulate the problem instance for DRL, which is different from the real ones, we proposeStructure-Aware Meta Reinforcement Learning (SAMRL)for fast adapting to new domains. Experimental results on multiple real datasets indicate that our proposed algorithms outperform the other deterministic and learning-based baseline approaches.

Owing to a wide range of important applications, such as team formation, dense subgraph discovery, and activity attendee suggestions on online social networks, Group Query attracts a lot of attention from the research community. However, most existing works are constrained by a unified social tightness k (e.g., for k-core, or k-plex), without considering the diverse preferences of social cohesiveness in individuals. In this paper, we introduce a new group query, namely Parameter-free Group Query (PGQ), and propose a learning-based model, called PGQN, to find a group that accommodates personalized requirements on social contexts and activity topics. First, PGQN extracts node features by a GNN-based method on Heterogeneous Activity Information Network (HAIN). Then, we transform the PGQ into a graph-to-set (Graph2Set) problem to learn the diverse user preference on topics and members, and find new attendees to the group. Experimental results manifest that our proposed model outperforms nine state-of-the-art methods by at least 51% in terms of F1-score on three public datasets.

Viral marketing on social networks, also known as Influence Maximization (IM), aims to select k users for the promotion of a target item by maximizing the total spread of their influence. However, most previous works on IM do not explore the dynamic user perception of promoted items in the process. In this paper, by exploiting the knowledge graph (KG) to capture dynamic user perception, we formulate the problem of Influence Maximization based on Dynamic Personal Perception (IMDPP) that considers user preferences and social influence reflecting the impact of relevant item adoptions. We prove the hardness of IMDPP and design an approximation algorithm, named Dynamic perception for seeding in target markets (Dysim), by exploring the concepts of dynamic reachability, target markets, and substantial influence to select and promote a sequence of relevant items. We evaluate the performance of Dysim in comparison with the state-of-the-art approaches using real social networks with real KGs. The experimental results show that Dysim effectively achieves at least 6 times of influence spread in large datasets over the state-of-the-art approaches.

Matrix factorization (MF) has earned great success on recommender systems. However, the common-used regression-based MF not only is sensitive to outliers but also unable to guarantee that the predicted values are in line with the user preference orders, which is the basis of common measures of recommender systems, e.g., nDCG. To overcome the aforementioned drawbacks, we propose a framework for personalized ranking of Poisson factorization that utilizes learning-to-rank based posteriori instead of the classical regression-based ones. Owing to the combination, the proposed framework not only preserves user preference but also performs well on a sparse matrix. Since the posteriori that combines learning to rank and Poisson factorization does not follow the conjugate prior relationship, we estimate variational parameters approximately and propose two optimization approaches based on variational inference. As long as the used learning-to-rank model has the 1st and 2nd order partial derivatives, by exploiting our framework, the proposed optimizing algorithm can maximize the posteriori whichever the used learning-to-rank model is. In the experiment, we show that the proposed framework outperforms the state-of-the-art methods and achieves promising results on consuming log and rating datasets for multiple recommendation tasks.

In this article, we pursue a better solution for the promising problem, i.e., the bidding strategy design, in the real-time bidding (RTB) advertising (AD) environment. Under the budget constraint, the design of an optimal strategy for bidding on each incoming impression opportunity targets at acquiring as many clicks as possible during an AD campaign. State-of-the-art bidding algorithms rely on a single predictor, the clickthrough rate predictor, to calculate the bidding value for each impression. This provides reasonable performance if the predictor has appropriate accuracy in predicting the probability of user clicking. However, the classical methods usually fail to capture optimal results since the predictor accuracy is limited. We improve the situation by accomplishing an additional winning price predictor in the bidding process. In this article, an algorithm combining powers of multiple prediction models is developed. It emerges from an analogy to the online stochastic knapsack problem, and the efficiency of the algorithm is also theoretically analyzed. Experiments conducted on real world RTB datasets show that the proposed solution performs better with regard to both number of clicks achieved and effective cost per click in many different settings of budget constraints.

Three essential criteria are important for social activity planning: (1) finding attendees familiar with the initiator, (2) ensuring most attendees have tight social relations with each other, and (3) selecting an activity period available to all. In this paper, we propose the Social-Temporal Group Query (STGQ) to find suitable time and attendees with minimum total social distance. We first prove that the problem is NP-hard and inapproximable within any ratio. Next, we design two algorithms, SGSelect and STGSelect, which include effective pruning techniques to substantially reduce running time. Moreover, as users may iteratively adjust query parameters to fine tune the results, we study the problem of Subsequent Social Group Query (SSGQ). We propose the Accumulative Search Tree and Social Boundary, to cache and index intermediate results of previous queries in order to accelerate subsequent query processing. Experimental results indicate that SGSelect and STGSelect are significantly more efficient than baseline approaches. With the caching mechanisms, processing time of subsequent queries can be further reduced by 50-75 percent. We conduct a user study to compare the proposed approach with manual activity coordination. The results show that our approach obtains higher quality solutions with lower coordination effort, thereby increasing the users' willingness to organize activities.

Sequential pattern mining can be applied to various fields such as disease prediction and stock analysis. Many algorithms have been proposed for sequential pattern mining, together with acceleration methods. In this paper, we show that a heterogeneous platform with CPU and GPU is more suitable for sequential pattern mining than traditional CPU-based approaches since the support counting process is inherently succinct and repetitive. Therefore, we propose the PArallel SequenTial pAttern mining algorithm, referred to as PASTA, to accelerate sequential pattern mining by combining the merits of CPU and GPU computing. Explicitly, PASTA adopts the vertical bitmap representation of database to exploits the GPU parallelism. In addition, a pipeline strategy is proposed to ensure that both CPU and GPU on the heterogeneous platform operate concurrently to fully utilize the computing power of the platform. Furthermore, we develop a swapping scheme to mitigate the limited memory problem of the GPU hardware without decreasing the performance. Finally, comprehensive experiments are conducted to analyze PASTA with different baselines. The experiments show that PASTA outperforms the state-of-the-art algorithms by orders of magnitude on both real and synthetic datasets.

We generalize the winning price model to incorporate the deep learning models with different distributions and propose an algorithm to learn from the historical bidding information, where the winning price are either observed or partially observed. We study if the successful deep learning models of the click-through rate can enhance the prediction of the winning price or not. We also study how different distributions of winning price can affect the learning results. Experiment results show that the deep learning models indeed boost the prediction quality when they are learned on the historical observed data. In addition, the deep learning models on the unobserved data are improved after learning from the censored data. The main advantage of the proposed generalized deep learning model is to provide more flexibility to model the winning price and improve the performance in consideration of the possibly various winning price distributions and various model structures in practice.

In many applications the classification model needs to utilize limited resources properly while predicting an instance, e.g. the limited response time for a real-time search engine. In order to satisfy the resource constraint, many researchers try to simplify the model structure or shrink the feature subset size. Because the informative features may take too much cost for the model, a common way is to build a model by considering the trade-off between performance and cost. However, most previous works assume that the cost of a feature is independent of the cost of another feature, which is not practical in reality. In the paper, we consider two categories of the feature cost, individual cost and group cost. The former is independent of the cost of any other feature whereas the latter regards the cost dependency between the other features in the corresponding group. We propose a two-stage framework that integrates the cost-sensitive feature selection and learning a model with a cost budget constraint. First, we propose the group-cost-sensitive random forest (GOAT) model to consider these two costs to select a proper feature subset. Second, we propose a salient ensemble of trees each of which uses cascaded linear classifiers (ETIC) with the satisfaction of the featurecost constraints using the derived features from the GOAT model. We conduct experiments on real-world datasets, including mobile-user preference data and object detection data. When the group cost dominates, GOAT-ETIC can gain a 10–30% improvement over the baselines. Even if the group cost is ignored, GOAT-ETIC can still get better performance than the state-of-the-arts.

Matrix factorization (MF) has earned great success on recommender systems. However, the commonly-used regression-based MF is not only sensitive to outliers but also unable to guarantee that the predicted values are in line with the user preference orders, which is the basis of common measures in recommender systems, e.g., nDCG. To overcome this drawback, we propose personalized ranking on Poisson factorization (PRPF), which utilizes the posteriori based on pair-wise learning to rank instead of the classical regression-based ones. Since the posteriori that combines learning to rank and Poisson factorization does not follow the conjugate prior relationship, we estimate variational parameters approximately and propose two optimization approaches based on variational interference. Due to the combination, PRPF not only preserves user preference but also performs well on a sparse matrix. In the experiment, we show that PRPF outperforms the state-of-the-art methods and achieves promising results for recommendation tasks.

The problem of revenue maximization, which aims at earning the highest revenue by properly pricing the product and/or seeding customers, is an important issue about utilizing the social influences. In this paper, we are interested in the marketing of the multi-grade product, where the different grades of a product from a company, such as iPhone 8, iPhone 8 Plus, and iPhone X, have both competitive and promotional relationships. For the study, a new diffusion model named MuG-IC (Multi-Grade IC) is first proposed based on the IC and the concave graph models to describe the phenomena of social influences regarding the multi-grade product. Afterwards, we then study the revenue maximization upon the MuG-IC and solve the problem by designing a novel algorithm named PS (Pricing-Seeding). The PS algorithm can give proper suggestions of pricing each grade of the product and seeding customers by tuning the suggestions in an iterative manner. The experiments conducted on the real network structure with simulated valuation distributions from Amazon.com demonstrate the effectiveness of the proposed algorithm.

Information diffusion is a natural phenomenon occurring in social networks. The adoption behavior of a node toward an information piece in a social network can be affected by different factors, e.g., freshness and hotness. Previously, many diffusion models are proposed to consider one or several fixed factors. In fact, the factors affecting adoption decision of a node are different from one to another and may not be seen before. For a different scenario of diffusion with new factors, previous diffusion models may not model the diffusion well, or are not applicable at all. Moreover, uncertainty of information exposure intrinsically exists between two connected nodes, which causes modeling diffusion more challenge in social networks. In this work, our aim is to design a diffusion model in which factors considered are flexible to be extended and changed and the uncertainly of information exposure is explicitly tackled. Therefore, with different factors, our diffusion model can be adapted to more scenarios of diffusion without requiring the modification of the learning framework. We conduct comprehensive experiments to show that our diffusion model is effective on two important tasks of information diffusion, namely activation prediction and spread estimation.

In this paper, we propose SUbsequence Matching framework with cell MERgence (SUMMER) for online subsequence matching between histogram-based stream synopsis structures under the dynamic time warping distance. Given a query synopsis pattern, SUMMER continuously identifies all the matching subsequences for a stream as the bins are generated. To effectively reduce the computation time, we design a Weighted Dynamic Time Warping (WDTW) algorithm, which computes the warping distance directly between two histogram-based synopses. Furthermore, a Stack-based Overlapping Filter Algorithm (SOFA) is provided to remove the overlapping subsequences to avoid the redundant information. Finally, we design an optional refinement module to relax the subsequence range limit and improve the matching accuracy. Our experiments on real datasets show that the proposed method significantly speeds up the pattern matching without compromising the accuracy required when compared with other approaches.

The explosive growth in popularity of social networking leads to the problematic usage. An increasing number of social network mental disorders (SNMDs), such as Cyber-Relationship Addiction, Information Overload, and Net Compulsion, have been recently noted. Symptoms of these mental disorders are usually observed passively today, resulting in delayed clinical intervention. In this paper, we argue that mining online social behavior provides an opportunity to actively identify SNMDs at an early stage. It is challenging to detect SNMDs because the mental status cannot be directly observed from online social activity logs. Our approach, new and innovative to the practice of SNMD detection, does not rely on self-revealing of those mental factors via questionnaires in Psychology. Instead, we propose a machine learning framework, namely, Social Network Mental Disorder Detection (SNMDD), that exploits features extracted from social network data to accurately identify potential cases of SNMDs. We also exploit multi-source learning in SNMDD and propose a new SNMD-based Tensor Model (STM) to improve the accuracy. To increase the scalability of STM, we further improve the efficiency with performance guarantee. Our framework is evaluated via a user study with 3,126 online social network users. We conduct a feature analysis, and also apply SNMDD on large-scale datasets and analyze the characteristics of the three SNMD types. The results manifest that SNMDD is promising for identifying online social network users with potential SNMDs.

Telecommunication fraud is one of the most prevalent crimes nowadays, and causes most property loss of victims. The criminals of telecommunication fraud are highly organized, concealed and transnational, making investigators difficult to track and capture the suspects. In this paper, we propose a Telecom Fraud Analysis Model (TFAM) which can unveil the underlying structure of fraud groups and identify the roles of the fraudsters. The links between suspects are built using flight information, and co-offending records. Social network analysis techniques are applied to analyze group structures as well as influences of each member. We collect a real telecom fraud dataset with 113 fraudsters whose fraudulent activities spread across four countries and 17 cities. Experimental results demonstrate that our method can successfully identify the key roles and discover the hidden structure of the fraud groups.

Existing research on finding social groups mostly focuses on dense subgraphs in social networks. However, finding socially tenuous groups also has many important applications. In this paper, we introduce the notion of k-triangles to measure the tenuity of a group. We then formulate a new research problem, Minimum k-Triangle Disconnected Group (MkTG), to find a socially tenuous group from online social networks. We prove that MkTG is NP-Hard and inapproximable within any ratio in arbitrary graphs but polynomial-time tractable in threshold graphs. Two algorithms, namely TERA and TERA-ADV, are designed to exploit graph-theoretical approaches for solving MkTG on general graphs effectively and efficiently. Experimental results on seven real datasets manifest that the proposed algorithms outperform existing approaches in both efficiency and solution quality.

In recent years, a large volume of natural signal data has become available for scientists because of the maturity of sensor techniques. However, the sensor data can form huge data streams that are non-linear and non-stationary. Existing methods cannot process such a large volume of data efficiently with a single CPU because of the high complexity of the algorithms. In this paper, we present Massive Parallelism GPU-Optimized Adaptive Data Analysis (MG-ADA), a new parallel signal data analysis algorithm that utilizes General-Purpose Graphics Programming Unit (GPGPU) to improve data scalability and reduce computation time for large non-linear and non-stationary datasets. We propose effective strategies to significantly improve the efficiency and scalability of MG-ADA. Our experimental results show that MG-ADA provides high scalability and significantly reduces the processing time in large datasets compared to other baseline algorithms.

We address the bidding strategy design problem faced by a Demand-Side Platform (DSP) in Real-Time Bidding (RTB) advertising. A RTB campaign consists of various parameters and usually a predefined budget. Under the budget constraint of a campaign, designing an optimal strategy for bidding on each impression to acquire as many clicks as possible is a main job of a DSP. State-of-the-art bidding algorithms rely on a single predictor, namely the clickthrough rate (CTR) predictor, to calculate the bidding value for each impression. This provides reasonable performance if the predictor has appropriate accuracy in predicting the probability of user clicking. However when the predictor gives only moderate accuracy, classical algorithms fail to capture optimal results.

We consider the problem where companies provide different types of products and want to promote their products through viral marketing simultaneously. Most previous works assume products are purely competitive. Different from them, our work considers that each product has a pairwise relationship which can be from strongly competitive to strongly complementary to each other's product. The problem is to maximize the spread size with the presence of different opponents with different relationships on the network. We propose Interacting Influence Maximization (IIM) game to model such problems by extending the model of the Competitive Influence Maximization (CIM) game studied by previous works, which considers purely competitive relationship. As for the theoretical approach, we prove that the Nash equilibrium of highly complementary products of different companies may still be very inefficient due to the selfishness of companies. We do so by introducing a well-known concept in game theory, called Price of Stability (PoS) of the extensive-form game. We prove that in any k selfish players symmetric complementary IIM game, the overall spread of the products can be reduced to as less as 1/k of the optimal spread. Since companies may fail to cooperate with one another, we propose different competitive objective functions that companies may consider and deal with separately. We propose a scalable strategy for maximizing influence differences, called TOPBOSS that is guaranteed to beat the first player in a single-round two-player second-move game. In the experiment, we first propose a learning method to learn the ILT model, which we propose for IIM game, from both synthetic and real data to validate the effectiveness of ILT. We then exhibit that the performance of several heuristic strategies in the traditional influence maximization problem can be improved by acquiring the knowledge of the existence of competitive/complementary products in the network. Finally, we compare the TOPBOSS with different heuristic algorithms in real data and demonstrate the merits of TOPBOSS.

Research issues and data mining techniques for product recommendation and viral marketing have been widely studied. Existing works on seed selection in social networks do not take into account the effect of product recommendations in e-commerce stores. In this paper, we investigate the seed selection problem for viral marketing that considers both effects of social influence and item inference (for product recommendation). We develop a new model, Social Item Graph (SIG), that captures both effects in the form of hyperedges. Accordingly, we formulate a seed selection problem, called Social Item Maximization Problem (SIMP), and prove the hardness of SIMP. We design an efficient algorithm with performance guarantee, called Hyperedge-Aware Greedy (HAG), for SIMP and develop a new index structure, called SIG-index, to accelerate the computation of diffusion process in HAG. Moreover, to construct realistic SIG models for SIMP, we develop a statistical inference based framework to learn the weights of hyperedges from data. Finally, we perform a comprehensive evaluation on our proposals with various baselines. Experimental result validates our ideas and demonstrates the effectiveness and efficiency of the proposed model and algorithms over baselines.

In our daily life, rumors are spread among people but diffusion processes and spreading paths behind rumors are usually hidden. The problem of finding this hidden process is getting more attention since after understanding the process, one can manipulate the diffusion speed of the process. In this work, we observe the pattern of information propagation that most nodes are inclined to share the first-hand information. In other words, the virality of an information piece will generally decay as it becomes rephrased or secondhand. We propose a generative model with the pattern and design the corresponding optimization method to infer both the hidden networks and transmission rates between nodes. Experimental results show that our model outperforms several state-of-the-art models on both synthetic and real datasets for network inference.

An increasing number of social network mental disorders (SNMDs), such as Cyber-Relationship Addiction, Information Overload, and Net Compulsion, have been recently noted. Symptoms of these mental disorders are usually observed passively today, resulting in delayed clinical intervention. In this paper, we argue that mining online social behavior provides an opportunity to actively identify SNMDs at an early stage. It is challenging to detect SNMDs because the mental factors considered in standard diagnostic criteria (questionnaire) cannot be observed from online social activity logs. Our approach, new and innovative to the practice of SNMD detection, does not rely on self-revealing of those mental factors via questionnaires. Instead, we propose a machine learning framework, namely, Social Network Mental Disorder Detection (SNMDD), that exploits features extracted from social network data to accurately identify potential cases of SNMDs. We also exploit multi-source learning in SNMDD and propose a new SNMDbased Tensor Model (STM) to improve the performance. Our framework is evaluated via a user study with 3126 online social network users. We conduct a feature analysis, and also apply SNMDD on large-scale datasets and analyze the characteristics of the three SNMD types. The results show that SNMDD is promising for identifying online social network users with potential SNMDs.

Spatial proximity is one of the most important factors for the quick deployment of the task groups in various time-sensitive missions. This article proposes a new spatial query, Spatio-Social Team Query (SSTQ) , that forms a strong task group by considering (1) the group’s spatial distance (i.e., transportation time), (2) skills of the candidate group members, and (3) social rapport among the candidates. Efficient processing of SSTQ is very challenging, because the aforementioned spatial, skill, and social factors need to be carefully examined. In this article, therefore, we first formulate two subproblems of SSTQ, namely Hop-Constrained Team Problem (HCTP) and Connection-Oriented Team Query (COTQ) . HCTP is a decision problem that considers only social and skill dimensions. We prove that HCTP is NP-Complete. Moreover, based on the hardness of HCTP, we prove that SSTQ is NP-Hard and inapproximable within any factor . On the other hand, COTQ is a special case of SSTQ that relaxes the social constraint. We prove that COTQ is NP-Hard and propose an approximation algorithm for COTQ, namely COTprox . Furthermore, based on the observations on COTprox, we devise an approximation algorithm, SSTprox , with a guaranteed error bound for SSTQ. Finally, to efficiently obtain the optimal solution to SSTQ for small instances, we design two efficient algorithms, SpatialFirst and SkillFirst , with different scenarios in mind. These two algorithms incorporate various effective ordering and pruning techniques to reduce the search space for answering SSTQ. Experimental results on real datasets indicate that the proposed algorithms can efficiently answer SSTQ under various parameter settings.

The development and integration of social networking services and smartphones have made it easy for individuals to organize impromptu social activities anywhere and anytime. Main challenges arising in organizing impromptu activities are mostly due to the requirements of making timely invitations in accordance with the potential activity locations, corresponding to the locations of, and the relationships among the candidate attendees. Various combinations of candidate attendees and activity locations create a large solution space. Thus, in this paper, we propose Multiple Rally-Point Social Spatial Group Query (MRGQ), to select an appropriate activity location for a group of nearby attendees with tight social relationships. We first consider a special case of MRGQ, namely the Socio-Spatial Group Query (SSGQ), to determine a set of socially acquainted attendees while minimizing the total spatial distance to a specific activity location. We prove that SSGQ is NP-hard and formulate an Integer Linear Programming optimization model for SSGQ. We then develop an efficient algorithm, called SSGS, which employs effective pruning techniques to reduce the running time to determine the optimal solution. Moreover, we propose a heuristic algorithm for SSGQ to efficiently produce good solutions. We next consider the more general MRGQ. Although MRGQ is NP-hard, the number of attendees in practice is usually small enough such that an optimal solution can be found efficiently. Therefore, we first propose an Integer Linear Programming optimization model for MRGQ. We then design an efficient algorithm, called MAGS, which employs effective search space exploration and pruning strategies to reduce the running time for finding the optimal solution. We also propose to further optimize efficiency by indexing the potential activity locations. A user study demonstrates the strength of using SSGS and MAGS over manual coordination in terms of both solution quality and efficiency. Experimental results on real datasets show that our algorithms can process SSGQ and MRGQ efficiently and significantly outperform other baseline algorithms, including one based on the commercial parallel optimizer IBM CPLEX.

Studies show that a person is willing to join a social group activity if the activity is interesting, and if some close friends also join the activity as companions. The literature has demonstrated that the interests of a person and the social tightness among friends can be effectively derived and mined from social networking websites. However, even with the above two kinds of information widely available, social group activities still need to be coordinated manually, and the process is tedious and time-consuming for users, especially for a large social group activity, due to complications of social connectivity and the diversity of possible interests among friends. To address the above important need, this paper proposes to automatically select and recommend potential attendees of a social group activity, which could be very useful for social networking websites as a value-added service. We first formulate a new problem, named Willingness mAximization for Social grOup (WASO). This paper points out that the solution obtained by a greedy algorithm is likely to be trapped in a local optimal solution. Thus, we design a new randomized algorithm to effectively and efficiently solve the problem. Given the available computational budgets, the proposed algorithm is able to optimally allocate the resources and find a solution with an approximation ratio. We implement the proposed algorithm in Facebook, and the user study demonstrates that social groups obtained by the proposed algorithm significantly outperform the solutions manually configured by users.

Big-data computing is a new critical challenge for the ICT industry. Engineers and researchers are dealing with data sets of petabyte scale in the cloud computing paradigm. Thus, the demand for building a service stack to distribute, manage, and process massive data sets has risen drastically. In this paper, we investigate the Big Data Broadcasting problem for a single source node to broadcast a big chunk of data to a set of nodes with the objective of minimizing the maximum completion time. These nodes may locate in the same datacenter or across geo-distributed datacenters. This problem is one of the fundamental problems in distributed computing and is known to be NP-hard in heterogeneous environments. We model the Big-data broadcasting problem into a LockStep Broadcast Tree (LSBT) problem. The main idea of the LSBT model is to define a basic unit of upload bandwidth, r, such that a node with capacity c broadcasts data to a set of [c/r] children at the rater. Note that r is a parameter to be optimized as part of the LSBT problem. We further divide the broadcast data into m chunks. These data chunks can then be broadcast down the LSBT in a pipeline manner. In a homogeneous network environment in which each node has the same upload capacity c, we show that the optimal uplink rate r* of LSBT is either c/2 or c/3, whichever gives the smaller maximum completion time. For heterogeneous environments, we present an O(nlog2n) algorithm to select an optimal uplink rater* and to construct an optimal LSBT. Numerical results show that our approach performs well with less maximum completion time and lower computational complexity than other efficient solutions in literature.

As the social networking websites arise, the social network has become an important vehicle for sharing information and exerting influences. For the widespread utilization of social influences, a lot of works such as influence maximization and innovation promotion have been studied on various diffusion models. However, to the best of our knowledge, none of the existing works has incorporated the interplay between the intensity of interest and influence strength, which has been widely observed in social sciences, into the diffusion model. To fulfill this gap, in this paper, we propose the ID model that is able to capture the dynamic influence strength owing to the interplay. Under this ID model, we address the novel utilization of dynamic influence strength for personalized promotion to grow the intensity of a target individual's interest in an issue. In particular, to have the cost of promotion minimized, we introduce a novel Algorithm ISES to search for the least number of individuals as seeds in the promotion strategy. The ISES algorithm is able to identify the cost-effective solution by adopting the backtracking search and employing pruning strategies. On the real dataset of DBLP, the experiments demonstrate the effectiveness of ISES.

Nowadays, companies are usually strongly interested in discovering the latent social influences among their customers since the information is highly valuable to their marketing strategies. In this paper, we study how to model the influence probabilities among the customers of a telecommunication company by analyzing their call records and mobile web browsing histories. We first construct a directed network using the phone call records. We verify whether the statistical properties of our constructed network follow the commonly known social network properties. Next, we propose several heuristics to measure the influence probabilities between users in the constructed network by analyzing both the call records and the mobile web browsing histories. Finally, we evaluate our proposed measurements by two prediction tasks, including predicting the lengths of a call and estimating the number of common website visits between two users. The results show that our proposed measurements are effective with better prediction accuracy.

Viral marketing, a marketing strategy that leverages the influence power in intimate relationship, has become more prevalent due to the popularity of online social networking services in recent years. Consumers are more likely to make a purchase based on social media referrals. Since marketing through social media and traditional channels may target on different audiences, how to maximize the revenue of a telecommunications company by employing different advertising ways and selecting initial users for advertisements is a critical problem. Therefore, in this paper, we formulate a new research problem, namely Cost-Aware Multi-wAy Influence maXimization (CAMAIX) to address the need mentioned above. We design a 1/2-approximation algorithm with various pruning and budget allocation strategies to solve CAMAIX efficiently. We conduct extensive experiments on a large-scale real dataset from a telecommunications company. The results show that our proposed algorithm outperforms the baseline algorithms in both solution quality and efficiency.

While online social networks have become a part of many people's daily lives, Internet and social network addictions (ISNAs) have been noted recently. With increased patients in addictive Internet use, clinicians often form support groups to help patients. This has become a trend because groups organized around therapeutic goals can effectively enrich members with insight and guidance while holding everyone accountable along the way. With the emergence of online social network services, there is a trend to form support groups online with the aid of mental health professionals. Nevertheless, it becomes impractical for a psychiatrist to manually select the group members because she faces an enormous number of candidates, while the selection criteria are also complicated since they span both the social and symptom dimensions. To effectively address the need of mental healthcare professionals, this paper makes the first attempt to study a new problem, namely Member Selection for Online Support Group (MSSG). The problem aims to maximize the similarity of the symptoms of all selected members, while ensuring that any two members are unacquainted to each other. We prove that MSSG is NP-Hard and inapproximable within any ratio, and design a 3-approximation algorithm with a guaranteed error bound. We evaluate MSSG via a user study with 11 mental health professionals, and the results manifest that MSSG can effectively find support group members satisfying the member selection criteria. Experimental results on large-scale real datasets also demonstrate that our proposed algorithm outperforms other baselines in terms of solution quality and efficiency.

Previous research has aimed to lower the cost of handling large networks by reducing the network size via sparsification. However, when many edges are removed from the network, the information that can be used for link prediction becomes rather limited, and the prediction accuracy thereby drops significantly. To address this issue, we propose a framework called Diverse Ensemble of Drastic Sparsification (DEDS), which constructs ensemble classifiers with good accuracy while keeping the prediction time short. DEDS includes various sparsification methods that are designed to preserve different measures of a network. Therefore, DEDS can generate sparsified networks with significant structural differences and increase the diversity of the ensemble classifier, which is key to improving prediction performance. When a network is drastically sparsified to 0.1% of the original one, DEDS effectively relieves the drop in prediction accuracy and raises the AUC value from 0.52 to 0.70. With a larger sparsification ratio, DEDS is even able to outperform the classifier trained from the original network. As for the efficiency, more than 95% prediction cost can be saved when the network is sparsified to 1% of the original one. If the original network is disk-resident but can fit into main memory after being sparsified, as much as 99.94% of the prediction cost can be saved.

Considering nowadays companies providing similar products or services compete with each other for resources and customers, this work proposes a learning-based framework to tackle the multi-round competitive influence maximization problem on a social network. We propose a data-driven model leveraging the concept of meta-learning to maximize the expected influence in the long run. Our model considers not only the network information but also the opponent's strategy while making a decision. It maximizes the total influence in the end of the process instead of myopically pursuing short term gain. We propose solutions for scenarios when the opponent's strategy is known or unknown and available or unavailable for training. We also show how an effective framework can be trained without manually labeled data, and conduct several experiments to verify the effectiveness of the whole process.

Recently the influence maximization problem has received much attention for its applications on viral marketing and product promotions. However, such influence maximization problems have not taken into account the monetary effect on the purchasing decision of individuals. To fulfill this gap, in this paper, we aim for maximizing the revenue by considering the quantity constraint on the promoted commodity. For this problem, we not only identify a proper small group of individuals as seeds for promotion but also determine the pricing of the commodity. To tackle the revenue maximization problem, we first introduce a strategic searching algorithm, referred to as Algorithm PRUB, which is able to derive the optimal solutions. After that, we further modify PRUB to propose a heuristic, Algorithm PRUB+IF, for obtaining feasible solutions more efficiently on larger instances. Experiments on real social networks with different valuation distributions demonstrate the effectiveness of PRUB and PRUB+IF.

In the aspect of a Demand-Side Platform (DSP), which is the agent of advertisers, we study how to predict the winning price such that the DSP can win the bid by placing a proper bidding value in the real-time bidding (RTB) auction. We propose to leverage the machine learning and statistical methods to train the winning price model from the bidding history. A major challenge is that a DSP usually suffers from the censoring of the winning price, especially for those lost bids in the past. To solve it, we utilize the censored regression model, which is widely used in the survival analysis and econometrics, to fit the censored bidding data. Note, however, the assumption of censored regression does not hold on the real RTB data. As a result, we further propose a mixture model, which combines linear regression on bids with observable winning prices and censored regression on bids with the censored winning prices, weighted by the winning rate of the DSP. Experiment results show that the proposed mixture model in general prominently outperforms linear regression in terms of the prediction accuracy.

This paper focuses on the problem of short text summarization on the comment stream of a specific message from social network services (SNS). Due to the high popularity of SNS, the quantity of comments may increase at a high rate right after a social message is published. Motivated by the fact that users may desire to get a brief understanding of a comment stream without reading the whole comment list, we attempt to group comments with similar content together and generate a concise opinion summary for this message. Since distinct users will request the summary at any moment, existing clustering methods cannot be directly applied and cannot meet the real-time need of this application. In this paper, we model a novel incremental clustering problem for comment stream summarization on SNS. Moreover, we propose IncreSTS algorithm that can incrementally update clustering results with latest incoming comments in real time. Furthermore, we design an at-a-glance visualization interface to help users easily and rapidly get an overview summary. From extensive experimental results and a real case demonstration, we verify that IncreSTS possesses the advantages of high efficiency, high scalability, and better handling outliers, which justifies the practicability of IncreSTS on the target problem.

Information diffusion and virus propagation are the fundamental processes often taking place in networks. The problem of devising a strategy to facilitate or block such process has received a considerable amount of attention. A major challenge therein is that the underlying network of diffusion is often hidden. Most researchers dealing with this issue assume only one underlying network over which cascades spread. However, in the real world, whether the transmission pathways of a contagion, a piece of information, emerge or not depends on many factors, such as the topic of the information and the time when the information is first mentioned. In our opinion, it is impractical to model the diffusion processes by using only a single network when information is of all kind and diffuses in different underlying topic-specific networks. In this paper, we formulate a problem of K-network inference, inferring K underlying diffusion networks, based on a proposed probabilistic generative mixture model that models the generation of cascades. We further propose an algorithm that could cluster similar cascades and infer the corresponding underlying network for each cluster in the Expectation-Maximization framework. Finally, in experiments, we show that our algorithm could cluster cascades and infer the underlying networks effectively.

k-truss, a type of cohesive subgraphs of a network, is an important measure for a social network graph. However, with the emergence of large online social networks, the running time of the traditional batch algorithms for k-truss decomposition is usually prohibitively long on such a graph with billions of edges and millions of vertices. Moreover, the size of a graph becomes too large to load into the main memory of a single machine. Currently, cloud computing has become an imperative way to process the big data. Thus, our aim is to design a scalable algorithm of k-truss decomposition in the scenario of cloud computing. In this paper, we first improve the existing distributed k-truss decomposition in the MapReduce framework. We then propose a theoretical basis for k-truss and use it to design an algorithm based on graph-parallel abstractions. Our experiment results show that our method in the graph-parallel abstraction significantly outperforms the methods based on MapReduce in terms of running time and disk usage.

To characterize the relationship between items, graph-based ranking algorithms are widely used in various applications, such as information retrieval, recommender system, and natural language processing. Many ranking approaches tackle the dilemma between relevance and diversity. Diversity is considered as a critical objective of reducing redundancy and retrieving prestige information that has high coverage. However, the traditional evaluation of diversification is found to be deficient. In this paper, we address the coverage problem from a viewpoint of influence diffusion. Firstly, we transform the coverage problem into the diffusion problem and propose a novel measure called essential influence that combines relevance and diversity into a single function. Next, we propose a reinforced random walk, InfRank, of which the heuristic function is based on the essential influence. We applied InfRank on two applications, ranking in networks and tag recommendation. Our approach outperforms existing network-based ranking methods.

Social networks model the social activities between individuals, which change as time goes by. In light of useful information from such dynamic networks, there is a continuous demand for privacy-preserving data sharing with analyzers, collaborators or customers. In this paper, we address the privacy risks of identity disclosures in sequential releases of a dynamic network. To prevent privacy breaches, we proposed novel kw-structural diversity anonymity, where k is an appreciated privacy level and w is a time period that an adversary can monitor a victim to collect the attack knowledge. We also present a heuristic algorithm for generating releases satisfying kw-structural diversity anonymity so that the adversary cannot utilize his knowledge to reidentify the victim and take advantages. The evaluations on both real and synthetic data sets show that the proposed algorithm can retain much of the characteristics of the networks while confirming the privacy protection.

As an increasing number of social networking data is published and shared for commercial and research purposes, privacy issues about the individuals in social networks have become serious concerns. Vertex identification, which identifies a particular user from a network based on background knowledge such as vertex degree, is one of the most important problems that have been addressed. In reality, however, each individual in a social network is inclined to be associated with not only a vertex identity but also a community identity, which can represent the personal privacy information sensitive to the public, such as political party affiliation. This paper first addresses the new privacy issue, referred to as community identification, by showing that the community identity of a victim can still be inferred even though the social network is protected by existing anonymity schemes. For this problem, we then propose the concept of structural diversity to provide the anonymity of the community identities. The k-Structural Diversity Anonymization (k-SDA) is to ensure sufficient vertices with the same vertex degree in at least k communities in a social network. We propose an Integer Programming formulation to find optimal solutions to k-SDA and also devise scalable heuristics to solve large-scale instances of k-SDA from different perspectives. The performance studies on real data sets from various perspectives demonstrate the practical utility of the proposed privacy scheme and our anonymization approaches.

Mining big graph data is an important problem in the graph mining research area. Although cloud computing is effective at solving traditional algorithm problems, mining frequent patterns of a massive graph with cloud computing still faces the three challenges: 1) the graph partition problem, 2) asymmetry of information, and 3) pattern-preservation merging. Therefore, this paper presents a new approach, the cloud-based SpiderMine (c-SpiderMine), which exploits cloud computing to process the mining of large patterns on big graph data. The proposed method addresses the above issues for implementing a big graph data mining algorithm in the cloud. We conduct the experiments with three real data sets, and the experimental results demonstrate that c-SpiderMine can significantly reduce execution time with high scalability in dealing with big data in the cloud.

We in this paper explore a new research paradigm, called query homogeneity, to process KNN queries on road networks for online LBS applications. While previous works in the literature concentrate on the improvement of query processing time, we turn to examine the issue of response time for a user query, which needs to additionally consider the waiting time in the queue. Note that the response time is the more precise value corresponding to the user experience in an online service, and the unacceptable response time is likely to turn away disgruntled users. Surprisingly, we will show in this paper that the response time will be more significantly dominated by the waiting time but it is left unexplored thus far. Since previous works all perform queries in the one-by-one fashion, which will lead to unexpected long waiting time, we thus in this paper propose a novel query framework, called SHI, aiming at diminishing the waiting time by a new group-by-group solution. SHI relies on the natural phenomenon of query homogeneity, which refers to the behavior that queries are usually issued in the sense of spatial and temporal correlation. Motivated by this natural behavior, operations of query processing and queue processing are incorporated in the SHI framework. During the network expansion for a query, a group of homogeneity queries in the waiting queue, which have results identical to the processing query, will be picked up and flushed out together when the query processing is accomplished, achieving the group-by-group query processing and reducing the waiting time significantly.

Real datasets always play an essential role in graph mining and analysis. However, nowadays most available real datasets only support millions of nodes. Therefore, the literature on Big Data analysis utilizes statistical graph generators to generate a massive graph (e.g., billions of nodes) for evaluating the scalability of an algorithm. Nevertheless, current popular statistical graph generators are properly designed to preserve only the statistical metrics, such as the degree distribution, diameter, and clustering coefficient of the original social graphs. Recently, the importance of frequent graph patterns has been recognized in the various works on graph mining, but unfortunately this crucial criterion has not been noticed in the existing graph generators. To address this important need, we make the first attempt to design a Pattern Preserving Graph Generation (PPGG) algorithm to generate a graph including all frequent patterns and three most popular statistical parameters: degree distribution, clustering coefficient, and average vertex degree. The experimental results show that PPGG, which we have released as a free download, is efficient and able to generate a billion-node graph in approximately 10 minutes, much faster than the existing graph generators.

Closeness centrality measures the communication efficiency of a specific vertex within a network while the average path length (APL) measures that of the whole network. Since the nature of these two measurements is based on the computation of all-pair shortest path distances, one can perform the breadth-first search method starting at every vertex and obtain the two measurements. However, as the edge counts in the real-world networks like Facebook increase over time, this naive way is obviously inefficient. In this paper, we proposed CENDY, an efficient approach to updating Closeness centrality and average path length in Dynamic networks when there is an edge insertion or deletion. In CENDY, we derived some theoretical properties to quickly identify a set of vertices whose shortest path changed after an edge update, and then update the closeness centralities of those vertices only as well as the APL of the graph by a few of single-source shortest path computations. We conducted extensive experiments to show that, when compared to the existing methods of computing exact or approximate values, CENDY outperformed others in significantly low update time while providing exact values of the two measurements on various real-world graph datasets.

Place query is one of the most fundamental applications, and traditional use cases include finding the exact spatial location of a place and searching for a specific type of places in a given spatial range. On the other hand, there is another possibility that you may want to recommend a visited place to friends but forget the complete name of it. You have vague impressions on it and only remember the information of the place type, the rough range of the place, and some places near it. To enable the capability of query by impression that has not been fully explored in the literature, we define a new place query problem called Place Query with Adjacency Constraints (abbreviated as PQAC). We propose a naive approach and two enhancement algorithms, distance pre-calculating algorithm and grid indexing algorithm, to achieve greater efficiency that can satisfy the real-time need of this place query service. We implement the Query By Impression (abbreviated as QBI) system with a real metropolitan place dataset consisting of more than 40,000 place records from Google Place API. Several experiments are conducted to validate the efficiency and effectiveness of the proposed QBI system.

Studies show that a person is willing to join a social group activity if the activity is interesting, and if some close friends also join the activity as companions. The literature has demonstrated that the interests of a person and the social tightness among friends can be effectively derived and mined from social networking websites. However, even with the above two kinds of information widely available, social group activities still need to be coordinated manually, and the process is tedious and time-consuming for users, especially for a large social group activity, due to complications of social connectivity and the diversity of possible interests among friends. To address the above important need, this paper proposes to automatically select and recommend potential attendees of a social group activity, which could be very useful for social networking websites as a value-added service. We first formulate a new problem, named Willingness mAximization for Social grOup (WASO). This paper points out that the solution obtained by a greedy algorithm is likely to be trapped in a local optimal solution. Thus, we design a new randomized algorithm to effectively and efficiently solve the problem. Given the available computational budgets, the proposed algorithm is able to optimally allocate the resources and find a solution with an approximation ratio. We implement the proposed algorithm in Facebook, and the user study demonstrates that social groups obtained by the proposed algorithm significantly outperform the solutions manually configured by users.

The Support Vector Machines (SVMs) have been widely used for classification due to its ability to give low generalization error. In many practical applications of classification, however, the wrong prediction of a certain class is much severer than that of the other classes, making the original SVM unsatisfactory. In this paper, we propose the notion of Asymmetric Support Vector Machine (ASVM), an asymmetric extension of the SVM, for these applications. Different from the existing SVM extensions such as thresholding and parameter tuning, ASVM employs a new objective that models the imbalance between the costs of false predictions from different classes in a novel way such that user tolerance on false-positive rate can be explicitly specified. Such a new objective formulation allows us of obtaining a lower false-positive rate without much degradation of the prediction accuracy or increase in training time. Furthermore, we show that the generalization ability is preserved with the new objective. We also study the effects of the parameters in ASVM objective and address some implementation issues related to the Sequential Minimal Optimization (SMO) to cope with large-scale data. An extensive simulation is conducted and shows that ASVM is able to yield either noticeable improvement in performance or reduction in training time as compared to the previous arts.

An object can move with various speeds and arbitrarily changing directions. Given a bounded area where a set of objects moving around, there are some typical moving styles of the objects at different local regions due to the geography nature or other spatiotemporal conditions. Not only the paths that the objects move along, we also want to know how different groups of objects move with various speeds. Therefore, given a set of collected trajectories spreading in a bounded area, we are interested in discovering the typical moving styles in different regions of all the monitored moving objects. These regional typical moving styles are regarded as the profile of the monitored moving objects, which may help reflect the geoinformation of the observed area and the moving behaviors of the observed moving objects. In this paper, we present DivCluST, an approach to finding regional typical moving styles by dividing and clustering the trajectories in consideration of both the spatial and temporal constraints. Different from the existing works that consider only the spatial properties or just the interesting regions of trajectories, DivCluST focuses more on typical movements in local regions of a bounded area and takes the temporal information into account when designing the criteria for trajectory dividing and the distance measurement for adaptive $(k)$-means clustering. Extensive experiments on three types of real data sets with specially designed visualization are presented to show the effectiveness of DivCluST.

Information network analysis has drawn a lot attention in recent years. Among all the aspects of network analysis, similarity measure of nodes has been shown useful in many applications, such as clustering, link prediction and community identification, to name a few. As linkage data in a large network is inherently sparse, it is noted that collecting more data can improve the quality of similarity measure. This gives different parties a motivation to cooperate. In this paper, we address the problem of link-based similarity measure of nodes in an information network distributed over different parties. Concerning the data privacy, we propose a privacy-preserving Sim Rank protocol based on fully-homomorphic encryption to provide cryptographic protection for the links.

In the current social network, a user may have hundreds of friends and find it very time consuming to categorize and tag every friend manually. When a user is going to initiate an activity by issuing a corresponding query, he/she needs to consider the relationship among candidate attendees to find a group of mutually close friends. Meanwhile, he/she also needs to consider the schedule of candidate attendees to find an activity period available for all attendees. It would certainly be desirable if the efficiency of such process is improved. In this talk, information processing in social networks will first be reviewed in three phrases, namely (i) from content to social relationship, (ii) mining on social relationship, and (iii) from social relationship to content organization. In addition, we shall present an effective procedure which helps a user to organize an event with proper attendees with minimum total social distance and commonly available time. Moreover, it is noted that the information retrieved from the social networks is also able to facilitate those user-dependent and human-centric services. In light of this, we shall explore the quality of recommendation through incorporating the notion of social filtering and collaborative filtering. Finally, it is recognized that the cloud computing has offered many new capabilities of storing and processing huge amounts of heterogeneous data in social networks. In view of this, we shall also examine how this paradigm shift will affect the information processing in social networks.

Challenges faced in organizing impromptu activities are the requirements of making timely invitations in accordance with the locations of candidate attendees and the social relationship among them. It is desirable to find a group of attendees close to a rally point and ensure that the selected attendees have a good social relationship to create a good atmosphere in the activity. Therefore, this paper proposes Socio-Spatial Group Query (SSGQ) to select a group of nearby attendees with tight social relation. Efficient processing of SSGQ is very challenging due to the tradeoff in the spatial and social domains. We show that the problem is NP-hard via a proof and design an efficient algorithm SSGSelect, which includes effective pruning techniques to reduce the running time for finding the optimal solution. We also propose a new index structure, Social R-Tree to further improve the efficiency. User study and experimental results demonstrate that SSGSelect significantly outperforms manual coordination in both solution quality and efficiency.

We explore in this paper a new KNN algorithm, called the SQUARE algorithm, for searching spatial objects on road networks. Recent works in the literature discussed the necessity to support object updates for promising location-based services. Among them, the decoupling spatial search algorithms, which separate the handle of the network traversal and the object lookup, has been recognized as the most effective approach to cut the maintenance overhead from updates. However, the queue-based network traversal needs to be performed from scratch for each KNN query until the KNN objects are exactly identified, indicating that the query complexity is in proportion to the number of visited network nodes. The query efficiency is concerned for online LBS applications since they only allow lightweight operations for minimizing the query latency. To improve the query scalability while supporting data updates, SQUARE constructs the network index similar to the way used in decoupling models, and meanwhile exploit the coupling idea to maintain the KNN information relative to hot regions in the network index. The hot region denotes the area with frequent queries discovered in the query history. Inspired from the prevalently observed 80-20 rule, SQUARE can maximize the query throughput by returning KNN results in the quasi-constant time for 80% queries that are roughly issued within 20% area (hot regions). As validated in our experimental results, SQUARE outperforms previous works and achieves the significant performance improvement without sacrifice on the maintenance overhead for object updates.

The primary objective of privacy preservation is to protect an individual's confidential information in released data sets. In recent years, several simulation-based approaches for privacy preservation have been proposed. The idea is to generate a synthetic data set with the constraint that the probability distribution is as close as possible to that of the original set. In this paper, we propose two frameworks for simulation-based privacy preservation of multivariate numerical data. The first framework, called PRIMP (PRivacy preserving by Independent coMPonents), is based on independent component analysis (ICA). It is shown empirically that PRIMP outperforms other simulation-based approaches in terms of Spearman's rank correlation and Kendall's tau correlation. The second approach proposed is a hybrid method that combines PRIMP and Cholesky's decomposition technique. It is shown empirically that the hybrid method preserves the covariance matrix of the original data exactly. The method also resolves the problem of generating good seeds for the Cholesky-based approach. Although the empirical results show that the hybrid approach is not always better than the PRIMP in terms of Spearman's rank correlation and Kendall's tau correlation, in theory, the risk of information leakage under the hybrid approach is much less than that under PRIMP.

Privacy in social network data publishing is always an important concern. Nowadays most prior privacy protection techniques focus on static social networks. However, there are additional privacy disclosures in dynamic social networks due to the sequential publications. In this paper, we first show that the risks of vertex and community re-identification exist in a dynamic social network, even if the release at each time instance is protected by a static anonymity scheme. To prevent vertex and community re-identification in a dynamic social network, we propose novel dynamic kw-structural diversity anonymity, where w is the time that an adversary can monitor a victim. This scheme extends the k-structural diversity anonymity to a dynamic scenario. We also present a heuristic to anonymize the releases of networks to satisfy the proposed privacy scheme. The evaluations show that our approach can retain much of the characteristics of the networks while confirming the privacy protection.

Due to the rich information in graph data, the technique for privacy protection in published social networks is still in its infancy, as compared to the protection in relational databases. In this paper we identify a new type of attack called a friendship attack. In a friendship attack, an adversary utilizes the degrees of two vertices connected by an edge to re-identify related victims in a published social network data set. To protect against such attacks, we introduce the concept of k2-degree anonymity, which limits the probability of a vertex being re-identified to 1/k. For the k2-degree anonymization problem, we propose an Integer Programming formulation to find optimal solutions in small-scale networks. We also present an efficient heuristic approach for anonymizing large-scale social networks against friendship attacks. The experimental results demonstrate that the proposed approaches can preserve much of the characteristics of social networks.

Training support vector machines (SVMs) with nonlinear kernel functions on large-scale data are usually very time-consuming. In contrast, there exist faster solvers to train the linear SVM. We propose a technique which sufficiently approximates the infinite-dimensional implicit feature mapping of the Gaussian kernel function by a low-dimensional feature mapping. By explicitly mapping data to the low-dimensional features, efficient linear SVM solvers can be applied to train the Gaussian kernel SVM, which leverages the efficiency of linear SVM solvers to train a nonlinear SVM. Experimental results show that the proposed technique is very efficient and achieves comparable classification accuracy to a normal nonlinear SVM solver.

How to protect individual privacy in public data is always a concern. For social networks, the challenge is that, the structure of the social network graph can be utilized to infer the private and sensitive information of users. The existing anonymity schemes mostly focus on the anonymity of vertex identities, such that a malicious attacker cannot associate an user with a specific vertex. In real social networks, however, each vertex is usually associated with not only a vertex identity but also a community identity, which could represent the private information for the corresponding user, such as the political party affiliation or disease information sensitive to the public. In this paper, we first show that the attacker can still infer the community identity of an user even though the graph is protected by previous anonymity schemes. Afterward, we propose the structural diversity, which ensures the existences of at least k communities containing vertices with the same degree for every vertex in the graph, to provide the anonymity of the community identities. Specifically, we formulate a new problem, k-Structural Diversity Anonymization (k-SDA), which protects the community identity of each individual in publishing social networks. We propose an Integer Programming formulation to find the optimal solutions to k-SDA. Moreover, we devise three scalable heuristics to solve the large instances of k-SDA with different perspectives. The experiments on real data sets demonstrate the practical utility of our privacy model and our approaches.

Three essential criteria are important for activity planning, including: (1) finding a group of attendees familiar with the initiator, (2) ensuring each attendee in the group to have tight social relations with most of the members in the group, and (3) selecting an activity period available for all attendees. Therefore, this paper proposes Social-Temporal Group Query to find the activity time and attendees with the minimum total social distance to the initiator. Moreover, this query incorporates an acquaintance constraint to avoid finding a group with mutually unfamiliar attendees. Efficient processing of the social-temporal group query is very challenging. We show that the problem is NP-hard via a proof and formulate the problem with Integer Programming. We then propose two efficient algorithms, SGSelect and STGSelect , which include effective pruning techniques and employ the idea of pivot time slots to substantially reduce the running time, for finding the optimal solutions. Experimental results indicate that the proposed algorithms are much more efficient and scalable. In the comparison of solution quality, we show that STGSelect outperforms the algorithm that represents manual coordination by the initiator.

The support vector machine (SVM) is a widely used tool in classification problems. The SVM trains a classifier by solving an optimization problem to decide which instances of the training data set are support vectors, which are the necessarily informative instances to form the SVM classifier. Since support vectors are intact tuples taken from the training data set, releasing the SVM classifier for public use or shipping the SVM classifier to clients will disclose the private content of support vectors. This violates the privacy-preserving requirements for some legal or commercial reasons. The problem is that the classifier learned by the SVM inherently violates the privacy. This privacy violation problem will restrict the applicability of the SVM. To the best of our knowledge, there has not been work extending the notion of privacy preservation to tackle this inherent privacy violation problem of the SVM classifier. In this paper, we exploit this privacy violation problem, and propose an approach to postprocess the SVM classifier to transform it to a privacy-preserving classifier which does not disclose the private content of support vectors. The postprocessed SVM classifier without exposing the private content of training data is called Privacy-Preserving SVM Classifier (abbreviated as PPSVC). The PPSVC is designed for the commonly used Gaussian kernel function. It precisely approximates the decision function of the Gaussian kernel SVM classifier without exposing the sensitive attribute values possessed by support vectors. By applying the PPSVC, the SVM classifier is able to be publicly released while preserving privacy. We prove that the PPSVC is robust against adversarial attacks. The experiments on real data sets show that the classification accuracy of the PPSVC is comparable to the original SVM classifier.

Natural phenomena show that many creatures form large social groups and move in regular patterns. However, previous works focus on finding the movement patterns of each single object or all objects. In this paper, we first propose an efficient distributed mining algorithm to jointly identify a group of moving objects and discover their movement patterns in wireless sensor networks. Afterward, we propose a compression algorithm, called 2P2D, which exploits the obtained group movement patterns to reduce the amount of delivered data. The compression algorithm includes a sequence merge and an entropy reduction phases. In the sequence merge phase, we propose a Merge algorithm to merge and compress the location data of a group of moving objects. In the entropy reduction phase, we formulate a Hit Item Replacement (HIR) problem and propose a Replace algorithm that obtains the optimal solution. Moreover, we devise three replacement rules and derive the maximum compression ratio. The experimental results show that the proposed compression algorithm leverages the group movement patterns to reduce the amount of delivered data effectively and efficiently.

Existing object tracking applications focus on finding the moving patterns of a single object or all objects. In contrast, we propose a distributed mining algorithm that identifies a group of objects with similar movement patterns. This information is important in some biological research domains, such as the study of animals' social behavior and wildlife migration. The proposed algorithm comprises a local mining phase and a cluster ensembling phase. In the local mining phase, the algorithm finds movement patterns based on local trajectories. Then, based on the derived patterns, we propose a new similarity measure to compute the similarity of moving objects and identify the local group relationships. To address the energy conservation issue in resource-constrained environments, the algorithm only transmits the local grouping results to the sink node for further ensembling. In the cluster ensembling phase, our algorithm combines the local grouping results to derive the group relationships from a global view. We further leverage the mining results to track moving objects efficiently. The results of experiments show that the proposed mining algorithm achieves good grouping quality, and the mining technique helps reduce the energy consumption by reducing the amount of data to be transmitted.

E-mail communication is indispensable nowadays, but the e-mail spam problem continues growing drastically. In recent years, the notion of collaborative spam filtering with near-duplicate similarity matching scheme has been widely discussed. The primary idea of the similarity matching scheme for spam detection is to maintain a known spam database, formed by user feedback, to block subsequent near-duplicate spams. On purpose of achieving efficient similarity matching and reducing storage utilization, prior works mainly represent each e-mail by a succinct abstraction derived from e-mail content text. However, these abstractions of e-mails cannot fully catch the evolving nature of spams, and are thus not effective enough in near-duplicate detection. In this paper, we propose a novel e-mail abstraction scheme, which considers e-mail layout structure to represent e-mails. We present a procedure to generate the e-mail abstraction using HTML content in e-mail, and this newly devised abstraction can more effectively capture the near-duplicate phenomenon of spams. Moreover, we design a complete spam detection system Cosdes (standing for COllaborative Spam DEtection System), which possesses an efficient near-duplicate matching scheme and a progressive update scheme. The progressive update scheme enables system Cosdes to keep the most up-to-date information for near-duplicate detection. We evaluate Cosdes on a live data set collected from a real e-mail server and show that our system outperforms the prior approaches in detection results and is applicable to the real world.

Recently, management of uncertain data draws lots of attention to consider the granularity of devices and noises in collection and delivery of data. Previous works directly model and handle uncertain data to find the required results. However, when data uncertainty is not small or limited, users are not able to obtain useful insights and thereby tend to provide more resources to improve the solution, by reducing the uncertainty of data. In light of this issue, this paper formulates a new problem of choosing a given number of uncertain data objects for acquiring their attribute values to improve the solutions of Probabilistic k-Nearest-Neighbor (k-PNN) query. We prove that solutions must be better after data acquisition, and we devise algorithms to maximize expected improvement. Our experiment results demonstrate that the probability can be significantly improved with only a small number of data acquisitions.

Outsourcing the training of support vector machines (SVM) to external service providers benefits the data owner who is not familiar with the techniques of the SVM or has limited computing resources. In outsourcing, the data privacy is a critical issue for some legal or commercial reasons since there may be sensitive information contained in the data. Existing privacy-preserving SVM works are either not applicable to outsourcing or weak in security. In this paper, we propose a scheme for privacy-preserving outsourcing the training of the SVM without disclosing the actual content of the data to the service provider. In the proposed scheme, the data sent to the service provider is perturbed by a random transformation, and the service provider trains the SVM for the data owner from the perturbed data. The proposed scheme is stronger in security than existing techniques, and incurs very little redundant communication and computation cost.

For any outsourcing service, privacy is a major concern. This paper focuses on outsourcing frequent itemset mining and examines the issue on how to protect privacy against the case where the attackers have precise knowledge on the supports of some items. We propose a new approach referred to as k-support anonymity to protect each sensitive item with k-1 other items of similar support. To achieve k-support anonymity, we introduce a pseudo taxonomy tree and have the third party mine the generalized frequent itemsets under the corresponding generalized association rules instead of association rules. The pseudo taxonomy is a construct to facilitate hiding of the original items, where each original item can map to either a leaf node or an internal node in the taxonomy tree. The rationale for this approach is that with a taxonomy tree, the k nodes to satisfy the k-support anonymity may be any k nodes in the taxonomy tree with the appropriate supports. So this approach can provide more candidates for k-support anonymity with limited fake items as only the leaf nodes, not the internal nodes, of the taxonomy tree need to appear in the transactions. Otherwise for the association rule mining, the k nodes to satisfy the k-support anonymity have to correspond to the leaf nodes in the taxonomy tree. This is far more restricted. The challenge is thus on how to generate the pseudo taxonomy tree to facilitate k-support anonymity and to ensure the conservation of original frequent itemsets. The experimental results showed that our methods of k-support anonymity can achieve very good privacy protection with moderate storage overhead.

Data broadcast is an advanced technique to realize large scalability and bandwidth utilization in a mobile computing environment. In this environment, the channel bandwidth of each channel is variant with time in real cases. However, traditional schemes do not consider time-variant bandwidth of each channel to schedule data items. Therefore, the above drawback degrades the performance in generating broadcast programs. In this paper, we address the problem of generating a broadcast program to disseminate data via multiple channels of time-variant bandwidth. In view of the characteristics of time-variant bandwidth, we propose an algorithm using adaptive allocation on time-variant bandwidth to generate the broadcast program to avoid the above drawback to minimize average waiting time. Experimental results show that our approach is able to generate the broadcast programs with high quality and is very efficient in a data broadcasting environment with the time-variant bandwidth.

Instead of finding clusters in the full feature space, subspace clustering is an emergent task which aims at detecting clusters embedded in subspaces. Most of previous works in the literature are density-based approaches, where a cluster is regarded as a high-density region in a subspace. However, the identification of dense regions in previous works lacks of considering a critical problem, called "the density divergence problemrdquo in this paper, which refers to the phenomenon that the region densities vary in different subspace cardinalities. Without considering this problem, previous works utilize a density threshold to discover the dense regions in all subspaces, which incurs the serious loss of clustering accuracy (either recall or precision of the resulting clusters) in different subspace cardinalities. To tackle the density divergence problem, in this paper, we devise a novel subspace clustering model to discover the clusters based on the relative region densities in the subspaces, where the clusters are regarded as regions whose densities are relatively high as compared to the region densities in a subspace. Based on this idea, different density thresholds are adaptively determined to discover the clusters in different subspace cardinalities. Due to the infeasibility of applying previous techniques in this novel clustering model, we also devise an innovative algorithm, referred to as DENCOS (density conscious subspace clustering), to adopt a divide-and-conquer scheme to efficiently discover clusters satisfying different density thresholds in different subspace cardinalities. As validated by our extensive experiments on various data sets, DENCOS can discover the clusters in all subspaces with high quality, and the efficiency of DENCOS outperformes previous works.

Due to the dynamic nature of data streams, a sliding window is used to generate synopses that approximate the most recent data within the retrospective horizon to answer queries or discover patterns. In this paper, we propose a dynamic scheme for wavelet synopses management in sensor networks. We define a data structure sliding dual tree, abbreviated as SDT, to generate dynamic synopses that adapts to the insertions and deletions in the most recent sliding window. By exploiting the properties of Haar wavelet transform, we develop several operations to incrementally maintain SDT over consecutive time windows in a time- and space-efficient manner. These operations directly operate on the transformed time-frequency domain without the need of storing/reconstructing the original data. As shown in our thorough analysis, our SDT-based approach greatly reduces the required resources for synopses generation and maximizes the storage utilization of wavelet synopses in terms of the window length and quality measures. We also show that the approximation error of the dynamic wavelet synopses, i.e., L2-norm error, can be incrementally updated. We also derive the bound of the overestimation of the approximation error due to the incremental thresholding scheme. Furthermore, the synopses can be used to answer various kinds of numerical queries such as point and distance queries. In addition, we show that our SDT can adapt to resource allocation to further enhance the overall storage utilization over time. As demonstrated by our experimental results, our proposed framework can outperform current techniques in both real and synthetic data.

We consider the problem of ranking refinement for image object retrieval, whose goal is to improve an existing ranking function by a small number of labeled instances. To retrieve the relevant image object, one state-of-the-art approach is to use the relevance feedback: it first ranks the images in database based on a given ranking function (i.e., base ranker), and then rerank the initial result by further introducing user's feedback information. The key challenge of combining the information from the base ranker and user's feedback comes from the fact that the base ranker tends to give an imperfect result and the information obtained from user's feedback tends to be very noisy. This paper describes an Intention-Focused Active Reranking, an approach for automatically finding the right information to re-estimate the query model. Three novel strategies are proposed to boost the performance of the base ranker: (1) an active selection criterion, which obtains a small number of feedback images that are the most informative to the base ranker for user labeling; (2) the user intention verification, which captures the user's intention in object level to alleviate the query drift problem; (3) a discriminative query model re-estimation, which augments the generative approach with a model of the discriminative information conveyed by positive and negative feedback information. Experiments on a real world data set demonstrate the effectiveness of the proposed approach and furthermore it significantly outperforms the baseline visual bag-of-words retrieval.

We present PROUD -- A PRObabilistic approach to processing similarity queries over Uncertain Data streams, where the data streams here are mainly time series streams. In contrast to data with certainty, an uncertain series is an ordered sequence of random variables. The distance between two uncertain series is also a random variable. We use a general uncertain data model, where only the mean and the deviation of each random variable at each timestamp are available. We derive mathematical conditions for progressively pruning candidates to reduce the computation cost. We then apply PROUD to a streaming environment where only sketches of streams, like wavelet synopses, are available. Extensive experiments are conducted to evaluate the effectiveness of PROUD and compare it with Det, a deterministic approach that directly processes data without considering uncertainty. The results show that, compared with Det, PROUD offers a flexible trade-off between false positives and false negatives by controlling a threshold, while maintaining a similar computation cost. In contrast, Det does not provide such flexibility. This trade-off is important as in some applications false negatives are more costly, while in others, it is more critical to keep the false positives low.

Data broadcast is an advanced technique to realize large scalability and bandwidth utilization in a mobile computing environment. In the heterogeneous data broadcast, the data size is variant with time in multiple broadcast channels. However, traditional indexing schemes do not consider variant data size to design indexing techniques in the multiple channels. Therefore, the above drawback leads to large power consumption in the heterogeneous data broadcast. In this paper, we remedy the problem of devising an indexing technique to index the data of variant size via the multiple channels. In view of the characteristics of variant data size in the multiple channels, we propose an indexing technique using an index tree to minimize average waiting time and average tuning time. Experimental results show that our approach is able to generate broadcast programs including data indices with high quality and is very efficient in the heterogeneous data broadcast.

In this article, we explore a novel sampling model, calledfeature 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 up-to-date population characteristics. Motivated by this shortcoming, we have developed theFPSalgorithm, which has several advantages: (1) it sequentially generates a sample from a time-variant data source over sliding windows; (2) the execution time ofFPSis linear with respect to the database size; (3) therelativeproportional differences between the sample proportions and population proportions of most distinct attribute values are guaranteed to be below a specified error threshold, ε, while therelativeproportion 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 thatFPShas acceptable space overheads, especially when the attribute values have Zipfian distributions, andFPScan also excellently preserve the population proportion of multivariate features in the sample; and (6)FPScan 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 thatFPScan effectively obtain a high quality sample of the desired size. In addition, while using the sample generated byFPSin various mining applications, a significant improvement in efficiency can be achieved without compromising the model's precision.

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.

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.

Effective distance functions in high dimensional data space are very important in solutions for many data mining problems. Recent research has shown that if the Pearson variation of the distance distribution converges to zero with increasing dimensionality, the distance function will become unstable (or meaningless) in high dimensional space, even with the commonly used Lpmetric in the Euclidean space. This result has spawned many studies the along the same lines. However, the necessary condition for unstability of a distance function, which is required for function design, remains unknown. In this paper, we shall prove that several important conditions are in fact equivalent to unstability. Based on these theoretical results, we employ some effective and valid indices for testing the stability of a distance function. In addition, this theoretical analysis inspires us that unstable phenomena are rooted in variation of the distance distribution. To demonstrate the theoretical results, we design a meaningful distance function, called the shrinkage-divergence proximity (SDP), based on a given distance function. It is shown empirically that the SDP significantly outperforms other measures in terms of stability in high dimensional data space, and is thus more suitable for distance-based clustering applications.

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.

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.

PageRank is one of the most important ranking techniques used in search engines nowadays. Since billions of pages already existed in Web, many PageRank acceleration techniques were explored by many researchers. However, in the real Web, just like the existence of pages without out-links, there are many pages without in-links. (In this paper, a Web page without in-links is called a reverse-dangling page.) Given the state of the art, we propose a new reordered PageRank algorithm, called two-way reordered PageRank algorithm, which exploits both dangling nodes and reverse-dangling nodes to reduce the computational complexity of the PageRank vector.

Prior studies on collaborative spam filtering with near-duplicate similarity matching scheme mainly represent each email by a succinct abstraction derived from email content text. Since these abstractions of emails cannot fully catch the evolving nature of spams, we propose in this paper a novel email abstraction scheme, which considers email layout structure to represent emails. With the proposed abstraction, we design a near-duplicate matching scheme to efficiently match each incoming email with a huge spam database.

One leading framework for image object mining is the bag-of-words (BOW) approach. The idea is to encode an image as a collection of visual words of the quantized local patches. Objects in the image can then be retrieved through inferring the semantic topics associated with the set of visual words. However, the visual BOW mining framework is apt to suffer from the so-called term-mismatch problem (a.k.a. vocabulary problem). This is caused by the poverty of query information, and consequently becomes an obstacle to deal with synonymy (i.e., different visual words for describing the same object). In this paper, we propose a novel language-model-based approach with pseudo-relevance feedback for addressing the vocabulary problem in visual BOW mining. We employ the pseudo positive images produced in response to the original query as a set of "cues" to gradually refine the query language model. Unlike traditional approaches that only ruggedly append feedback information into the original query, the proposed approach reconstructs the query language model with finer granularities so that the query concepts can be captured more accurately. The proposed approach is experimentally evaluated using two different types of image object databases. Our algorithms are shown to bring significant improvement in the retrieval accuracy over a non-feedback baseline, and achieve better performance than conventional feedback approaches.

Support vector machine (SVM) is a widely used tool in classification problem. SVM solves a quadratic optimization problem to decide which instances of training dataset are support vectors, i.e., the necessarily informative instances to form the classifier. The support vectors are intact tuples taken from the training dataset. Releasing the SVM classifier to public use or shipping the SVM classifier to clients will disclose the private content of support vectors, violating the privacy-preservation requirement in some legal or commercial reasons. To the best of our knowledge, there has not been work extending the notion of privacy-preservation to releasing the SVM classifier. In this paper, we propose an approximation approach which post-processes the SVM classifier to protect the private content of support vectors. This approach is designed for the commonly used Gaussian radial basis function kernel. By applying this post-processor on the SVM classifier, the resulted privacy-preserving SVM classifier can be publicly released without exposing the private content of support vectors and is able to provide comparable classification accuracy to the original SVM classifier.

Many practical applications of classification require the classifier to produce a very low false-positive rate. Although the Support Vector Machine (SVM) has been widely applied to these applications due to its superiority in handling high dimensional data, there are relatively little effort other than setting a threshold or changing the costs of slacks to ensure the low false-positive rate. In this paper, we propose the notion of Asymmetric Support VectorMachine (ASVM) that takes into account the false-positives and the user tolerance in its objective. Such a new objective formulation allows us to raise the confidence in predicting the positives, and therefore obtain a lower chance of false-positives. We study the effects of the parameters in ASVM objective and address some implementation issues related to the Sequential Minimal Optimization (SMO) to cope with large-scale data. An extensive simulation is conducted and shows that ASVM is able to yield either noticeable improvement in performance or reduction in training time as compared to the previous arts.

On-demand data broadcast is widely deployed to achieve high scalability in a mobile computing environment. However, traditional on-demand data broadcasting assumes that each time slot includes only one data item. Therefore, the above constraint requires the mobile users to wait until the next broadcast cycle to retrieve a data item if they miss the item in this cycle. The above constraint also limits the number of users that can be served in each time slot. In this paper, we propose a new on-demand data broadcast model with modified network coding. Our approach enables a server to encode multiple data items in each time slot, while each mobile user retrieves the data items by decoding the encoded data items with the locally stored data items. Our approach is different from the traditional network coding because each time slot encodes only a subset of data items, which are decided according to identities of the requested and stored data items of users. The simulation results show that our algorithm can reduce the access time by 66% as compared to the traditional schemes.

We present LeeWave --- a bandwidth-efficient approach to searching range-specified k -nearest neighbors among distributed streams by LEvEl-wise distribution of WAVElet coefficients. To find the k most similar streams to a range-specified reference one, the relevant wavelet coefficients of the reference stream can be sent to the peer sites to compute the similarities. However, bandwidth can be unnecessarily wasted if the entire relevant coefficients are sent simultaneously. Instead, we present a level-wise approach by leveraging the multi-resolution property of the wavelet coefficients. Starting from the top and moving down one level at a time, the query initiator sends only the single-level coefficients to a progressively shrinking set of candidates. However, there is one difficult challenge in LeeWave: how does the query initiator prune the candidates without knowing all the relevant coefficients? To overcome this challenge, we derive and maintain a similarity range for each candidate and gradually tighten the bounds of this range as we move from one level to the next. The increasingly tightened similarity ranges enable the query initiator to effectively prune the candidates without causing any false dismissal. Extensive experiments with real and synthetic data show that, when compared with prior approaches, LeeWave uses significantly less bandwidth under a wide range of conditions.

Sampling has been recognized as an important technique to improve the efficiency of clustering. However, with sampling applied, those points which 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; (2) MARDL can achieve high intra-cluster similarity and low inter-cluster 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 not only more efficient than prior methods but also attaining results of better quality.

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.

Generally speaking, to implement Apriori-based association rule mining in hardware, one has to load candidate itemsets and a database into the hardware. Since the capacity of the hardware architecture is fixed, if the number of candidate itemsets or the number of items in the database is larger than the hardware capacity, the items are loaded into the hardware separately. The time complexity of those steps that need to load candidate itemsets or database items into the hardware is in proportion to the number of candidate itemsets multiplied by the number of items in the database. Too many candidate itemsets and a large database would create a performance bottleneck. In this paper, we propose a HAsh-based and Pipelined (abbreviated as HAPPI) architecture for hardware- enhanced association rule mining. We apply the pipeline methodology in the HAPPI architecture to compare itemsets with the database and collect useful information for reducing the number of candidate itemsets and items in the database simultaneously. When the database is fed into the hardware, candidate itemsets are compared with the items in the database to find frequent itemsets. At the same time, trimming information is collected from each transaction. In addition, itemsets are generated from transactions and hashed into a hash table. The useful trimming information and the hash table enable us to reduce the number of items in the database and the number of candidate itemsets. Therefore, we can effectively reduce the frequency of loading the database into the hardware. As such, HAPPI solves the bottleneck problem in a priori-based hardware schemes. We also derive some properties to investigate the performance of this hardware implementation. As shown by the experiment results, HAPPI significantly outperforms the previous hardware approach and the software algorithm in terms of execution time.

The K-nearest neighbors (KNN) query has been of significant interest in many studies and has become one of the most important spatial queries in mobile sensor networks. Applications of KNN queries may include vehicle navigation, wildlife social discovery, and squad/platoon searching on the battlefields. Current approaches to KNN search in mobile sensor networks require a certain kind of indexing support. This index could be either a centralized spatial index or an in-network data structure that is distributed over the sensor nodes. Creation and maintenance of these index structures, to reflect the network dynamics due to sensor node mobility, may result in long query response time and low battery efficiency, thus limiting their practical use. In this paper, we propose a maintenance-free itinerary-based approach called density-aware itinerary KNN query processing (DIKNN). The DIKNN divides the search area into multiple cone-shape areas centered at the query point. It then performs a query dissemination and response collection itinerary in each of the cone-shape areas in parallel. The design of the DIKNN scheme takes into account several challenging issues such as the trade-off between degree of parallelism and network interference on query response time, and the dynamic adjustment of the search radius (in terms of number of hops) according to spatial irregularity or mobility of sensor nodes. To optimize the performance of DIKNN, a detailed analytical model is derived that automatically determines the most suitable degree of parallelism under various network conditions. This model is validated by extensive simulations. The simulation results show that DIKNN yields substantially better performance and scalability over previous work, both as kappa increases and as the sensor node mobility increases. It outperforms the second runner with up to a 50 percent saving in energy consumption and up to a 40 percent reduction in query response time, while rendering the same level of query result accuracy.

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.

Current approaches to k nearest neighbor (KNN) search in mobile sensor networks require certain kind of indexing support. This index could be either a centralized spatial index or an in-network data structure that is distributed over the sensor nodes. Creation and maintenance of these index structures, to reflect the network dynamics due to sensor node mobility, may result in long query response time and low battery efficiency, thus limiting their practical use. In this paper, we propose a maintenance-free, itinerary-based approach called density-aware itinerary KNN query processing (DIKNN). The DIKNN divides the search area into multiple cone-shape areas centered at the query point. It then performs a query dissemination and response collection itinerary in each of the cone-shape areas in parallel. The design of the DIKNN scheme also takes into account challenging issues such as the the dynamic adjustment of the search radius (in terms of number of hops) according to spatial irregularity or mobility of sensor nodes. The simulation results show that DIKNN yields substantially better performance and scalability over previous work, both as k increases and as the sensor node mobility increases. It outperforms the second runner with up to 50% saving in energy consumption and up to 40% reduction in query response time, while rendering the same level of query result accuracy.

Data broadcast is a technique to realize energy saving and bandwidth utilization in a mobile computing environment. However, traditional schemes schedule data items without considering channel bandwidth. Therefore, the above drawback leads to the unfair broadcasting rate of each item of the different access frequency. In this paper, we address the problem of generating a broadcast program to disseminate data via multiple channels with variant bandwidth. In view of the characteristics of variant bandwidth, we propose an algorithm using adaptive partition on bandwidth to generate broadcast program to avoid the above drawback so as to minimize the average waiting time. The empirical results show that our approach is able to produce broadcast programs of high quality and is very efficient in a data broadcasting environment with variant bandwidth.

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.

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 sequential/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

Data cubes have become important components in most data warehouse systems and decision support systems. In such systems, users usually pose very complex queries to the online analytical processing (OLAP) system, and systems usually have to deal with a huge amount of data because of the large dimensionality of the sets; thus, approximating query processing has emerged as a viable solution. Specifically, the applications of cube streams handle multidimensional data sets in a continuous manner in contrast to the traditional cube approximation. Such an application collects data events for cube streams online, generates snapshots with limited resources, and keeps the approximated information in a synopsis memory for further analysis. Compared to the OLAP applications, applications of cube streams are subject to many more resource constraints on both the processing time and the memory and cannot be dealt with by existing methods due to the limited resources. In this paper, we propose the DAWA algorithm, which is a hybrid algorithm of discrete cosine transform (DCT) for data and the discrete wavelet transform (DWT), to approximate cube streams. Our algorithm combines the advantages of the high compression rate of DWT and the low memory cost of DCT. Consequently, DAWA requires much smaller working buffer and outperforms both DWT-based and DCT-based methods in execution efficiency. Also, it is shown that DAWA provides a good solution for an approximate query processing of cube streams with a small working buffer and a short execution time. The optimality of the DAWA algorithm is theoretically proved and empirically demonstrated by our experiments.

In recent years, data broadcasting becomes a promising technique to design a mobile information system with power conservation, high scalability and high bandwidth utilization. In many applications, the query issued by a mobile client corresponds to multiple items which should be accessed in a sequential order. In this paper, we study the scheduling approach in such a sequential data broadcasting environment. Explicitly, we propose a general framework referred to as MULS (standing for MUlti-Level Service) for an information system. There are two primary stages in MULS: on-line scheduling and optimization procedure. In the first stage, we propose an On- Line Scheduling algorithm (denoted by OLS) to allocate the data items into multiple channels. As for the second stage, we devise an optimization procedure SCI, standing for Sampling with Controlled Iteration, to enhance the quality of broadcast programs generated by algorithm OLS. Procedure SCI is able to strike a compromise between effectiveness and efficiency by tuning the control parameters. According to the experimental results, we show that algorithm OLS with procedure SCI outperforms the approaches in prior works prominently in both effectiveness (i.e., the average access time of mobile users) and efficiency (i.e., the complexity of the scheduling algorithm). Therefore, by cooperating algorithm OLS with procedure SCI, the proposed MULS framework is able to generate broadcast programs with flexibility of providing different service qualities under different requirements of effectiveness and efficiency: in the dynamic environment in which the access patterns and information contents change rapidly, the parameters used in SCI will perform online scheduling with satisfactory service quality. As for the static environment in which the query profile and the database are updated infrequently, larger values of parameters are helpful to generate an optimized broadcast program, indicating the advantageous feature of MULS.

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 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, i.e., the queries for top-k range sum. We resolve the problem of efficient top-k query processing with minimized global error by developing a general framework. For the purposes of maintaining the wavelet coefficients and processing top-k 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-k queries accurately and efficiently.

In applications of multiple data streams such as stock market trading and sensor network data analysis, the clusters of streams change at different time because of the data evolution. The information of evolving cluster is valuable to support corresponding online decisions. In this paper, we present a framework for Clustering Over Multiple Evolving sTreams by CORrelations and Events, which, abbreviated as COMETCORE, monitors the distribution of clusters over multiple data streams based on their correlation. Instead of directly clustering the multiple data streams periodically, COMET-CORE applies efficient cluster split and merge processes only when significant cluster evolution happens. Accordingly, we devise an event detection mechanism to signal the cluster adjustments. The coming streams are smoothed as sequences of end points by employing piecewise linear approximation. At the time when end points are generated, weighted correlations between streams are updated. End points are good indicators of significant change in streams, and this is a main cause of cluster evolution event. When an event occurs, through split and merge operations we can report the latest clustering results. As shown in our experimental studies, COMET-CORE can be performed effectively with good clustering quality.

In this paper, a problem, called "the density divergence problem" is explored. This problem is related to the phenomenon that the densities of the clusters vary in different subspace cardinalities. We take the densities into consideration in subspace clustering and explore an algorithm to adaptively determine different density thresholds to discover clusters in different subspace cardinalities.

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. 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. In addition, we present a progressive concept to progressively discover sequential patterns in recent time period of interest.

Due to the resource limitation in the data stream environment, 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 this paper, motivated by the fact that a user may be interested in an arbitrary range of the data streams, we investigate two important types of range-constrained queries in time series streaming environments: the distance queries (which aim at obtaining the Euclidean distance between two streams) and the kNN queries (which aim at discovering k nearest neighbors to a reference stream). To achieve high efficiency in processing these two types of queries, we propose procedure RED (standing for Range-constrained Euclidean Distance) and algorithm EKS (standing for Enhanced KNN Search). Compared to the existing methods in the prior research, the advantageous features of our approaches are in two folds. First, our approaches are capable of processing the queries directly from the wavelet synopses retained in the main memory without using IDWT to reconstruct the data cells. This feature allows us to save the complexity in both memory and time. Moreover, our approaches enable the users to query the DSMS within their range of interest. Unlike the conventional methods which only support the full-range query processing, this feature will enhance the flexibility at the client side. We evaluate procedure RED and algorithm EKS on live and synthetic datasets empirically and show that the proposed approaches are efficient in similarity search and kNN discovery within arbitrary ranges in the time series streaming environments.

The use of effective distance functions has been explored for many data mining problems including clustering, nearest neighbor search, and indexing. Recent research results show that if the Pearson variation of the distance distribution converges to zero with increasing dimensionality, the distance function will become unstable (or meaningless) in high dimensional space even with the commonly used Lp metric on the Euclidean space. This result has spawned many subsequent studies. We first comment that although the prior work provided the sufficient condition for the unstability of a distance function, the corresponding proof has some defects. Also, the necessary condition for unstability (i.e., the negation of the sufficient condition for the stability) of a distance function, which is required for function design, remains unknown. Consequently, we first provide in this paper a general proof for the sufficient condition of unstability. More importantly, we go further to prove that the rapid degradation of Pearson variation for a distance distribution is in fact a necessary condition of the resulting unstability. With the result, we will then have the necessary and the sufficient conditions for unstability, which in turn imply the sufficient and necessary conditions for stability. This theoretical result derived leads to a powerful means to design a meaningful distance function. Explicitly, in light of our results, we design in this paper a meaningful distance function, called Shrinkage-Divergence Proximity (abbreviated as SDP), based on a given distance function. It is empirically shown that the SDP significantly outperforms prior measures for its being stable in high dimensional data space and robust to noise, and is thus deemed more suitable for distance-based clustering applications than the priorly used metric.

In the data stream environment, the patterns generated at different time instances are different due to data evolution. As time progresses, the behavior and members of clusters usually change. Hence, clustering continuous data streams allows us to observe the changes of group behavior. In order to support flexible clustering requirements, we devise in this paper a Clustering on Demand framework, abbreviated as COD framework, to dynamically cluster multiple data streams. While providing a general framework of clustering on multiple data streams, the COD framework has two advantageous features, namely, one data scan for online statistics collection and compact multiresolution approximations, which are designed to address, respectively, the time and the space constraints in a data stream environment. The COD framework consists of two phases, i.e., the online maintenance phase and the offline clustering phase. The online maintenance phase provides an efficient mechanism to maintain summary hierarchies of data streams with multiple resolutions in time linear in both the number of streams and the number of data points in each stream. On the other hand, an adaptive clustering algorithm is devised for the offline phase to retrieve approximations of desired substreams from summary hierarchies according to clustering queries. We propose two summarization techniques, based on wavelet and regression analyses, to construct the summary hierarchies. The regression-based summary hierarchy approximates the data stream more precisely and provides better clustering results, at the cost of slightly longer time than and twice the storage space as the wavelet-based one. An adaptive version of COD framework is designed to make a selection between a wavelet-based model and a regression-based model for building the summary hierarchy. By the adaptive COD, we can obtain clustering results with almost the same quality as the regression-based COD while using much less storage space for the summary hierarchy. As shown in the complexity analyses and also validated by our empirical studies, the COD framework performs very efficiently in the data stream environment while producing clustering results of very high quality.

We explore in this paper a practicably interesting mining task to retrieve frequent itemsets with memory constraint. As opposed to most previous works that concentrate on improving the mining efficiency or on reducing the memory size by best effort, we first attempt to constrain the upper memory size that can be utilized by mining frequent itemsets in this paper.

For time-relevant multi-dimensional data sets (MDS), users usually pose a huge amount of data due to the large dimensionality, and approximating query processing has emerged as a viable solution. Specifically, the cube streams handle MDSs in a continuous manner. Traditional cube approximation focuses on generating single snapshots rather than continuous ones. To address this issue, the application of generating snapshots for cube streams, called SCS, is investigated in this paper. Such an application collects data events for cube streams on-line and generates snapshots with limited resources in order to keep the approximated information in synopsis memory for further analysis. As compared to OLAP applications, the SCS ones are subject to much more resource constraints for both processing time and memory and cannot be dealt with by existing methods due to the limited resources. In this paper, the DAWA algorithm, standing for a hybrid algorithm of Dct for Data and discrete WAvelet transform, is proposed to approximate the cube streams. The DAWA algorithm combines the advantage of high compression rate from DWT and that of low memory cost from DCT. Consequently, DAWA costs much smaller working buffer and outperforms both DWT-based and DCT-based methods in execution efficiency. Also, it is shown that DAWA provides answers of good quality for SCS applications with a small working buffer and short execution time. The optimality of algorithm DAWA is theoretically proved and also empirically demonstrated by our experiments.

Sampling has been recognized as an important technique to improve the efficiency of clustering. However, with sampling applied, those points which are not sampled will not have their labels. 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, Node Importance Representative (abbreviated as NIR), which represents clusters by the importance of attribute values. MARDL has two advantages: (1) MARDL exhibits high execution efficiency; (2) after each unlabeled data is allocated into the proper cluster, MARDL preserves clustering characteristics, i.e., high intra-cluster similarity and low inter-cluster similarity. MARDL is empirically validated via real and synthetic data sets, and is shown to be not only more efficient than prior methods but also attaining results of better quality.

We address the issue of providing highly informative and comprehensive annotations using information revealed by the structured vocabularies of gene ontology (GO). For a target, a set of candidate terms for inferring target properties is collected and form a unique distribution on the GO directed acyclic graph (DAG). We propose a novel ontology-based clustering algorithm $CLUGO, which considers GO hierarchical characteristics and the clustering of term distributions. By identifying significant groups in the distributions, CLUGO assigns comprehensive and correct annotations for a target. According to the results of experiments with automated sequence functional annotations, CLUGO represents a considerable improvement over our previous work - GOMIT in terms of recall while maintaining a similar level of precision. We conclude that given a GO candidate term distribution, CLUGO is an efficient ontology-based clustering algorithm for selecting comprehensive and correct annotations.

In this paper, the proposed LIPED (LIfe Profile based Event Detection) employs the concept of life profiles to predict the activeness of event for effective event detection. A group of events with similar activeness patterns shares a life profile, modeled by a hidden Markov model. Considering the burst-and-diverse property of events, LIPED identifies the activeness status of event. As a result, LIPED balances the clustering precision and recall to achieve better F1 scores than other well known approaches evaluated on the official TDT1 corpus.

Hybrid data dissemination, which combines the push-based (i.e., broadcast) and pull-based (i.e., on-demand) data delivery, is the most common technique to deliver information in a mobile computing system. Most of the prior works in hibrid dissemination are based on the assumption that each delivered data item is of the same size. However, in the modern communication environment in which various information is delivered, the conventional dissemination schemes suffer from the efficiency issues. In this paper, we consider a general model of hybrid data dissemination, in which each data item is allowed to have an arbitrary size. The analytical model MGBC (Model of General Broadcast Channels) and MGOD (Model of General On-demand Channels) are first proposed to describe the broadcast and on-demand channels, respectively. In addition, the scheme GDS (General Dissemination Scheme) is adopted to perform the channel allocation and the data classification. Experimental results show that the proposed approach gives a near-optimal solution in achieving the minimun access time in the general dissemination environment.

To increase the commercial value and accessibility of pages, most content sites tend to publish their pages with intrasite redundant information, such as navigation panels, advertisements, and copyright announcements. Such redundant information increases the index size of general search engines and causes page topics to drift. In this paper, we study the problem of mining intrapage informative structure in news Web sites in order to find and eliminate redundant information. Note that intrapage informative structure is a subset of the original Web page and is composed of a set of fine-grained and informative blocks. The intrapage informative structures of pages in a news Web site contain only anchors linking to news pages or bodies of news articles. We propose an intrapage informative structure mining system called WISDOM (Web intrapage informative structure mining based on the document object model) which applies Information Theory to DOM tree knowledge in order to build the structure. WISDOM splits a DOM tree into many small subtrees and applies a top-down informative block searching algorithm to select a set of candidate informative blocks. The structure is built by expanding the set using proposed merging methods. Experiments on several real news Web sites show high precision and recall rates which validates WISDOM'S practical applicability.

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.

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

With the cutting edge technology advance in wireless and mobile computers, the query processing in a mobile environment involves join processing among different sites, which include static servers and mobile computers. Because of the need for energy saving and also the presence of asymmetric features in a mobile computing environment, the conventional query processing for a distributed database cannot be directly applied to a mobile computing system. In this paper, we first explore three asymmetric features of a mobile environment. Then, in light of these features, we devise query processing methods for both join and query processing. Intuitively, employing semijoin operations in a mobile computing environment is able to further reduce both the amount of data transmission and energy consumption. A semijoin which is initiated by a mobile computer (respectively, the server) and is beneficial to reduce the cost of a join operation is termed a mobile-initiated or MI (respectively, server-initiated or SI) profitable semijoin. According to those asymmetric features of a mobile computing system, we examine three different join methods and devise some specific criteria to identify MI/SI profitable semijoins. For query processing, which refers to the processing of multijoin queries, we develop three query processing schemes. In particular, we formulate the query processing in a mobile computing system as a two-phase query processing procedure that can determine a join sequence and interleave that join sequence with SI profitable semijoins to reduce both the amount of data transmission and energy consumption. Performance of these join and query methods is comparatively analyzed and sensitivity analysis on several parameters: is conducted. Furthermore, we develop a systematic procedure to derive the characteristic functions of MI and SI profitable semijoins. It is noted that, given some system parameters, those characteristic functions are very important in determining which join method is the most appropriate one to employ in that configuration. It is shown by our simulation results that, by exploiting the three asymmetric features, these characteristic functions are very powerful in reducing both the amounts of energy consumption and data transmission incurred and can lead to the design of an efficient and effective query processing procedure for a mobile computing environment.

In the data stream environment, the patterns generated by the mining techniques are usually distinct at different time because of the evolution of data. In order to deal with various types of multiple data streams and to support flexible mining requirements, we devise in this paper a clustering on demand framework, abbreviated as COD framework, to dynamically cluster multiple data streams. While providing a general framework of clustering on multiple data streams, the COD framework has two major features, namely one data scan for online statistics collection and compact multiresolution approximations, which are designed to address, respectively, the time and the space constraints in a data stream environment. Furthermore, with the multiresolution approximations of data streams, flexible clustering demands can be supported.

We explore in this paper a novel clustering algorithm, named CORE (standing for CORrelated-Force Ensemble), for categorical data. In general, it is more difficult to perform clustering on categorical data than on numerical data due to the absence of the ordered property in the former. Though several clustering algorithms which concentrate on categorical date were proposed, acquiring the desirable quality remains a challenging issue. Note that there is significance hidden in the correlation between attribute values that can be explored to aid clustering, especially extracting clusters in the high dimensional data. Therefore by employing the concept of correlated-force ensemble, clusters which consist of the highly correlated set of nominal attribute values, can be acquired by the proposed algorithm, CORE. As validated by variant real datasets, it is shown in our experimental results that algorithm CORE significantly outperforms the prior works.

Due to the growth of dynamic page generation techniques, the amount and the complexity of Web pages has been increasing explosively, as has the information contained within Web pages. Redundant and irrelevant information is distributed and mixed throughout a page, making it difficult to automatically identify the useful information in that page. Consequently, we propose an information hierarchy in this paper, and, from that hierarchy, we can extract the significance and the relationship value of information contained within a Web page. We can then use this hierarchical structure to create a new browsing process. Our DOM-based Information Space Adsorption (DOMISA) system applies information theory to map information in a page into an information space, and our gradient tree adsorption (GTA) process uses the document object model (DOM) trees of pages to build information hierarchies. Experiments on several commercial news Web sites show high precision and recall rates achieved by DOMISA in determining information clusters of pages which validates its practical applicability to Web sites.

For data stream applications, both approximation and adaptability are important issues for effective mining. We explore in this paper a fundamental problem that how the limited resources, e.g., memory space and computation power, can be well utilized to produce accurate estimates. Two important features for tracking mined patterns with properly utilized resources are examined. The first issue is temporal granularity which refers to the phenomenon that as time advances, people are more interested in recent events, meaning that more resources can be utilized to explore more recent data with finer granularities. Second, with the mining task of discovering frequent temporal patterns, more resources are expected to be allocated to the processing of those borderline patterns whose statistics, e.g., occurrence frequencies, are close to the specified threshold so as to have proper frequent itemset identification. This feature is called mining with support count granularity. Consequently, algorithm RAM-DS (Resource-Aware Mining for Data Streams) is designed to not only reduce the memory required for data storage but also retain good approximation of target time series. Experimental results have shown that the memory required for storing significant wavelet coefficients is very small and the quality of approximation is stable when performing incremental data updates, indicating that algorithm RAM-DS is feasible and suitable for adaptive mining in data streams.

Data broadcast is a promising technique to improve the bandwidth utilization and conserve the power consumption in a mobile computing environment. In many applications, the data items broadcast are dependent upon one another. However, most prior studies on broadcasting dependent data are restricted to a single broadcast channel environment, and as a consequence, the results are of limited applicability to the upcoming mobile environments. In view of this, we relax this restriction and explore the problem of broadcasting dependent data in multiple broadcast channels. By analyzing the model of dependent data broadcasting, we derive several theoretical properties for the average access time in a multiple channel environment. In light of the theoretical results, we develop a genetic algorithm to generate broadcast programs. Our experimental results show that the theoretical results derived are able to guide the search of the genetic algorithm very effectively, thus leading to broadcast programs of very high quality.

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.

The growth in wireless communication technologies attracts a considerable amount of attention in mobile ad-hoc networks. Since mobile hosts in an ad-hoc network usually move freely, the topology of the network changes dynamically and disconnection occurs frequently. These characteristics make a mobile ad-hoc network be likely to be separated into several disconnected partitions, and the data accessibility is hence reduced. Several schemes are proposed to alleviate the reduction of data accessibility by replicating data items. However, little research effort was elaborated upon exploiting the group mobility where the group mobility refers to the phenomenon that several mobile nodes tend to move together. In this paper, we address the problem of replica allocation in a mobile ad-hoc network by exploring group mobility. We first analyze the group mobility model and derive several theoretical results. In light of these results, we propose a replica allocation scheme to improve the data accessibility. Several experiments are conducted to evaluate the performance of the proposed scheme. The experimental results show that the proposed scheme is able to not only obtain higher data accessibility but also produce lower network traffic than prior schemes.

In several mobile applications, the data items broadcast are dependent upon one another. However, most prior studies on broadcasting dependent data mainly consider single broadcast channel environments. In view of this, we explore the problem of broadcasting dependent data in multiple broadcast channels. By analyzing the model of dependent data broadcasting, we derive several theoretical properties for the average access time in a multiple channel environment. In light of the theoretical results, we develop a genetic algorithm to generate broadcast programs.

We explore here the efficient clustering of item data. Different from those of the traditional data, the features of item data are known to be of high dimensionality and sparsity. In view of the features of item data, we devise here a novel measurement, called the association-taxonomy similarity, and utilize this measurement to perform the clustering. With this association-taxonomy similarity measurement, we develop an efficient clustering algorithm, called algorithm AT (standing for association-taxonomy), for item data. Two validation indexes based on association and taxonomy properties are also devised to assess the quality of clustering for item data. As validated by the real dataset, it is shown by our experimental results that algorithm AT devised here significantly outperforms the prior works in the clustering quality as measured by the validation indexes, indicating the usefulness of association-taxonomy similarity in item data clustering.

In this paper, the attributes employed to model the constraints are called constraint attributes and those attributes involved in the objective function to be optimized are called cost-optimal attributes. The constrained clustering considered is conducted in such a way that the objective function of cost-optimal attributes is optimized subject to the condition that the imposed constraint is satisfied. Explicitly, we address the problem of constrained clustering with numerical constraints, in which the constraint attribute values of any two data items in the same cluster are required to be within the corresponding constraint range. We devise an effective and efficient algorithm with complete-link to solve this clustering problem. It is noted that due to the intrinsic nature of the numerical constrained clustering, there is an order dependency on the process of attaining the clustering, which in many cases degrades the clustering results. In view of this, we devise a progressive constraint relaxation technique to remedy this drawback and improve the overall performance of clustering results. Explicitly, by using a smaller (tighter) constraint range in earlier iterations of merge, we will have more room to relax the constraint and seek for better solutions in subsequent iterations. It is empirically shown that the progressive constraint relaxation technique is able to improve not only the execution efficiency but also the clustering quality.

Benefiting from the growth of techniques of dynamic page generation, the amount and the complexity of Web pages increase explosively. The structures of Web pages which are dynamically generated by the same templates are thus similar to one another and are usually assembled by a set of fundamental information clusters These neighboring information clusters usually represent the similar semantics and form a larger cluster with the more generalized information. The hierarchical structure generated by information clusters in a bottom-up manner is called the information hierarchy of a page. We study the problem of mining the information hierarchies of pages in Web sites to recognize the information distribution of pages within the multilevel, multigranularity configurations. Explicitly, we propose an information clustering system that applies a top-down information centroid searching algorithm and a multigranularity centroid converging process on the document object model (DOM) trees of pages to build the information hierarchies of pages. Experiments on several real news Web sites show the high precision and recall rates of the proposed method on determining information clusters of pages and also validate its practical applicability to real Web sites.

Energy saving is one of the most important issues in wireless mobile computing. Among others, one viable approach to achieving energy saving is to use an indexed data organization to broadcast data over wireless channels to mobile units. Using indexed broadcasting, mobile units can be guided to the data of interest efficiently and only need to be actively listening to the broadcasting channel when the relevant information is present. We explore the issue of indexing data with skewed access for sequential broadcasting in wireless mobile computing. We first propose methods to build index trees based on access frequencies of data records. To minimize the average cost of index probes, we consider two cases: one for fixed index fanouts and the other for variant index fanouts, and devise algorithms to construct index trees for both cases. We show that the cost of index probes can be minimized not only by employing an imbalanced index tree that is designed in accordance with data access skew, but also by exploiting variant fanouts for index nodes. Note that, even for the same index tree, different broadcasting orders of data records will lead to different average data access times. To address this issue, we develop an algorithm to determine the optimal order for sequential data broadcasting to minimize the average data access time. Performance evaluation on the algorithms proposed is conducted. Examples and remarks are given to illustrate our results.

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.

In this paper, we present a new data mining algorithm which involves incremental mining for user moving patterns in a mobile computing environment and exploit the mining results to develop data allocation schemes so as to improve the overall performance of a mobile system. First, we propose an algorithm to capture the frequent user moving patterns from a set of log data in a mobile environment. The algorithm proposed is enhanced with the incremental mining capability and is able to discover new moving patterns efficiently without compromising the quality of results obtained. Then, in light of mining results of user moving patterns and the properties of data objects, we develop data allocation schemes that can utilize the knowledge of user moving patterns for proper allocation of both personal and shared data. By employing the data allocation schemes, the occurrences of costly remote accesses can be minimized and the performance of a mobile computing system is thus improved. For personal data allocation, two schemes are devised: one utilizes the set level of moving patterns and the other utilizes their path level. Schemes for shared data are also developed. Performance of these schemes is comparatively analyzed.

Web caching and Web prefetching are two important techniques 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 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 non-implied 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 Prefetching). 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.

In this paper, we study the problem of mining the informative structure of a news Web site which 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 TOC pages through informative links. It is noted that the Hyperlink Induced Topics Search (HITS) algorithm has been employed to provide a solution to analyzing authorities and hubs of pages. However, most of the content sites tend to contain some extra hyperlinks, such as navigation panels, advertisements and banners, so as to increase the add-on values of their Web pages. Therefore, due to the structure induced by these extra hyperlinks, HITS is found to be insufficient to provide a good precision in solving the problem. To remedy this, we develop an algorithm to utilize entropy-based Link Analysis on Mining Web Informative Structures. This algorithm is referred to as LAMIS. The key idea of LAMIS is to utilize information entropy for representing the knowledge that corresponds to the amount of information in a link or a page in the link analysis. Experiments on several real news Web sites show that the precision and the recall of LAMIS are much superior to those obtained by heuristic methods and conventional ink analysis methods.

This paper explores the aggregate effect when caching multiple versions of the same Web object in the transcoding proxy. Explicitly, the aggregate profit from caching multiple versions of an object is not simply the sum of the profits from caching individual versions, but rather, depends on the transcoding relationships among them. Hence, to evaluate the profit from caching each version of an object efficiently, we devise the notion of a weighted transcoding graph and formulate a generalized profit function which explicitly considers the aggregate effect and several new emerging factors in the transcoding proxy. Based on the weighted transcoding graph and the generalized profit function, an innovative cache replacement algorithm for transcoding proxies is proposed in this paper. Experimental results show that the algorithm proposed consistently outperforms companion schemes in terms of the delay saving ratios and cache hit ratios.

In this paper we explore a new model of mining general temporal association rules from large databases where the exhibition periods of the items are allowed to be different from one to another. Note that in this new model, the downward closure property which all prior Apriori-based algorithms relied upon to attain good efficiency is no longer valid. As a result, how to efficiently generate candidate itemsets form large databases has become the major challenge. To address this issue, we develop an efficient algorithm, referred to as algorithm SPF (standing for Segmented Progressive Filter) in this paper The basic idea behind SPF is to first segment the database into sub-databases in such a way that items in each sub-database will have either the common starting time or the common ending time. Then, for each sub-database, SPF progressively filters candidate 2-itemsets with cumulative filtering thresholds either forward or backward in time. This feature allows SPF of adopting the scan reduction technique by generating all candidate k-itemsets (k>2) from candidate 2-itemsets directly. The experimental results show that algorithm SPF significantly outperforms other schemes which are extended from prior methods in terms of the execution time and scalability.

In this paper a new mining capability, called mining of substitution rules, is explored. A substitution refers to the choice made by a customer to replace the purchase of items with that of others. The process of mining substitution rules can be decomposed into two procedures. The first identifies concrete itemsets among a large number of frequent itemsets, where a concrete itemset is a frequent itemset whose items are statistically dependent. The second is substitution rule generation. Two concrete itemsets X and Y form a substitution rule, denoted by X /spl utri/ Y to mean that X is a substitute for Y if and only if X and Y are negatively correlated and the negative association rule X /spl rarr/ Y~ exists. We derive theoretical properties for the model of substitution rule mining. Then, in light of these properties, the SRM algorithm (substitution rule mining) is designed and implemented to discover substitution rules efficiently while attaining good statistical significance. Empirical studies are performed to evaluate the performance of the SRM algorithm. It is shown that SRM produces substitution rules of very high quality.

We devise an efficient algorithm for clustering market-basket data. Different from those of the traditional data, the features of market-basket data are known to be of high dimensionality, sparsity, and with massive outliers. 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 a measurement, called the category-based adherence, and utilize this measurement to perform the clustering. The distance of an item to a given cluster is defined as the number of links between this item and its nearest large node in the taxonomy tree where a large node is an item or a category node whose occurrence count exceeds a given threshold. 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 With this category-based adherence measurement, we develop an efficient clustering algorithm, called algorithm CBA, for market-basket data with the objective to minimize the category-based adherence. 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 CBA significantly outperforms the prior works in both the execution efficiency and the clustering quality for market-basket data.

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 dis-tance between two closest (or farthest) data points. How-ever, all of these measurements are vulnerable to outliers, and removing the outliers precisely is yet another difficult task. In view of this, we propose a new similarity measure-ment, referred to as cohesion, to measure the inter-cluster distances. By using this new measurement of cohesion, we design a two-phase clustering algorithm, called cohesion-based self-merging (abbreviated as CSM), which runs in lin-ear time 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 subclus-ters in the first phase, and then continuously merges the sub-clusters based on cohesion in a hierarchical manner in the second phase. As shown by our performance studies, the cohesion-based clustering is very robust and possesses the 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.

In this paper, we broaden the horizon of traditional rule mining by introducing a new framework of causality rule mining in a distributed chain store database. Specifically, the causality rule explored in this paper consists of a sequence of triggering events and a set of consequential events, and is designed with the capability of mining non-sequential, inter-transaction information. Hence, the causality rule mining provides a very general framework for rule derivation. Note, however, that the procedure of causality rule mining is very costly particularly in the presence of a huge number of candidate sets and a distributed database, and in our opinion, cannot be dealt with by direct extensions from existing rule mining methods. Consequently, we devise in this paper a series of level matching algorithms, including Level Matching (abbreviatedly as LM), Level Matching with Selective Scan (abbreviatedly as LMS), and Distributed Level Matching (abbreviatedly as Distibuted LM), to minimize the computing cost needed for the distributed data mining of causality rules. In addition, the phenomena of time window constraints are also taken into consideration for the development of our algorithms. As a result of properly employing the technologies of level matching and selective scan, the proposed algorithms present good efficiency and scalability in the mining of local and global causality rules. Scale-up experiments show that the proposed algorithms scale well with the number of sites and the number of customer transactions.Index Terms: knowledge discovery, distributed data mining causality rules, triggering events, consequential events

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 By exploring the corresponding features, we devise algorithm SD-local and algorithm SD-global to achieve local optimization and global optimization, respectively. 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.

1 Introduction Since the earlier work in [2], a broad variety of data mining capabilities has been developed. These studies cover a broad spectrum of topics including: (1) association rule mining [1, 3, 11, 17]; (2) incremental updating [7, 14]; (3) mining of generalized [20], multi-level [8], multi-dimensional rules [22, 23]; (4) constraint-based rule mining [9, 18]; (5) temporal association rule [6, 13, 21]; (6) frequent episodes discovery [15, 16]; and (7) sequential patterns mining [4, 19].

Data clustering has attracted a lot of attention in the field of computational statistics and data mining. Notice, however, that in many applications not only the attributes but also the sequence of the objects has to be considered for clustering. Specifically, in some applications, a set of sequential data has to be partitioned into clusters in such a way that all the data points in each cluster form a continous region. This clustering capability, termed sequential clustering in this paper, can be applied to analyze the moving pattern of an object or the status log of a running machine. Due to its continuous constraint, prior results on data clustering cannot be applied to solve this problem, thus calling for the design of new algorithms. To remedy this, we shall explore the problem of optimal sequential clustering in this paper. Specifically, we first prove that this optimal sequential clustering problem addressed in this paper possesses the optimal substructure property which means that an optimal solution to this problem is composed of the optimal solutions to its subproblems. In light of this property, we devise algorithm SCOPT to obtain the optimal solution of the problem. The time complexity of algorithm SCOPT is O (kn2), where n is the size of the dataset and k is the number of clusters. To further reduce its complexity, we devise a greedy algorithm, SCGD, which solves the problem in linear time. Extensive experimental studies are conducted to evaluate the performance and the effectiveness of these two algorithms. It is shown that algorithm SCGD is able to obtain the solution clustering of very high quality which is in fact very close to that obtained by algorithm SCOPT.

We explore in this paper the problem of dynamic data and channel allocations with the number of communication channels and the number of data items given. It is noted that the combined use of broadcast and on-demand channels can utilize the bandwidth effectively for data dissemination in a mobile computing environment. We first derive the an-alytical models of the expected delays when the data are requested through the broadcast and on-demand channels. Then, we transform this problem into to a guided search problem. In light of the theoretical properties derived, we devise an algorithm based on binary interpolation search, referred to as algorithm BIS, to obtain solutions of high quality efficiently. In essence, algorithm BIS is guided to explore the solution space with higher likelihood to be the optimal first, thereby leading to an efficient and effective search. It is shown by our simulation results that the solution obtained by algorithm BIS is of very high quality and is in fact very close to the optimal one. Sensitivity analysis on several parameters, including the number of data items and the number of communication channels, is conducted.

We explore in this paper an effective sliding-window filtering (abbreviatedly as SWF) algorithm for incremental mining of association rules. In essence, by partitioning a transaction database into several partitions, algorithm SWF employs a filtering threshold in each partition to deal with the candidate itemset generation. Under SWF, the cumulative information of mining previous partitions is selectively carried over toward the generation of candidate itemsets for the subsequent partitions. Algorithm SWF not only significantly reduces I/O and CPU cost by the concepts of cumulative filtering and scan reduction techniques but also effectively controls memory utilization by the technique of sliding-window partition. Algorithm SWF is particularly powerful for efficient incremental mining for an ongoing time-variant transaction database. By utilizing proper scan reduction techniques, only one scan of the incremented dataset is needed by algorithm SWF. The I/O cost of SWF is, in orders of magnitude, smaller than those required by prior methods, thus resolving the performance bottleneck. Experimental studies are performed to evaluate performance of algorithm SWF. It is noted that the improvement achieved by algorithm SWF is even more prominent as the incremented portion of the dataset increases and also as the size of the database increases.

The query processing in a mobile computing environment involves join processing among different sites which include static servers and mobile computers. In this paper, we first present some unique features of a mobile environment, and then, in light of these features, devise query processing methods for both join and query processing. Remote mobile joins are said to be effectual if they are, when interleaved into a join sequence, able to reduce the data transmission cost required for distributed mobile query processing. It can be verified that the total data transmission cost of the processing in a distributed mobile query can be reduced by algorithms designed by using effectual remote joins. A simulator is developed to evaluate the performance of the devised algorithms. Our results show that the approach of interleaving the processing of distributed mobile queries with effectual remote mobile joins is not only efficient but also effective in reducing the total data transmission cost required to process distributed mobile queries.

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, each containing an individual exhibition period. The current model of association rule mining is not able to handle a publication database due to the following fundamental problems: (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 (PPM), to discover general temporal association rules in a publication database. The basic idea of PPM is to first partition the publication database into exhibition periods of items and then progressively accumulate the occurrence count of each candidate 2-itemset based on the intrinsic partitioning characteristics. PPM is also designed to employ a filtering threshold in each partition to prune out those cumulatively infrequent 2-itemsets at an early stage. Explicitly, the execution time of PPM is, in orders of magnitude, smaller than those required by schemes which are directly extended from existing methods.

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 variantfanout, we develop a heuristic algorithm VF K to minimize the expected delay of data items in the broadcast program.Performance of these algorithms is analyzed.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 VF K is of very high quality and is in fact very close to the optimal one.

The authors explore a new data mining capability that involves mining path traversal patterns in a distributed information-providing environment where documents or objects are linked together to facilitate interactive access. The solution procedure consists of two steps. First, they derive an algorithm to convert the original sequence of log data into a set of maximal forward references. By doing so, one can filter out the effect of some backward references, which are mainly made for ease of traveling and concentrate on mining meaningful user access sequences. Second, they derive algorithms to determine the frequent traversal patterns-i.e., large reference sequences-from the maximal forward references obtained. Two algorithms are devised for determining large reference sequences; one is based on some hashing and pruning techniques, and the other is further improved with the option of determining large reference sequences in batch so as to reduce the number of database scans required. Performance of these two methods is comparatively analyzed. It is shown that the option of selective scan is very advantageous and can lead to prominent performance improvement. Sensitivity analysis on various parameters is conducted.

Article Mining association rules with adjustable accuracy Share on Authors: Jong Soo Park Dept of Comput. Sci., Sungshin Women's Univ., Seoul, Korea Dept of Comput. Sci., Sungshin Women's Univ., Seoul, KoreaView Profile , Philip S. Yu IBM T.J. Watson Res. Ctr., P.O. Box 704, Yorktown, NY IBM T.J. Watson Res. Ctr., P.O. Box 704, Yorktown, NYView Profile , Ming-Syan Chen Elect. Eng. Department, National Taiwan Univ., Taipei, Taiwan, ROC Elect. Eng. Department, National Taiwan Univ., Taipei, Taiwan, ROCView Profile Authors Info & Claims CIKM '97: Proceedings of the sixth international conference on Information and knowledge managementJanuary 1997 Pages 151–160https://doi.org/10.1145/266714.266886Online:01 January 1997Publication History 20citation444DownloadsMetricsTotal Citations20Total Downloads444Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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.

We examine the issue of mining association rules among items in a large database of sales transactions. Mining association rules means that, given a database of sales transactions, to discover all associations among items such that the presence of some items in a transaction will imply the presence of other items in the same transaction. The mining of association rules can be mapped into the problem of discovering large itemsets where a large itemset is a group of items that appear in a sufficient number of transactions. The problem of discovering large itemsets can be solved by constructing a candidate set of itemsets first, and then, identifying, within this candidate set, these itemsets that meet the large itemset requirement. Generally, this is done iteratively for each large k-itemset in increasing order of k, where a large k-itemset is a large itemset with k items. To determine large itemsets from a huge number of candidate sets in early iterations is usually the dominating factor for the overall data mining performance. To address this issue, we develop an effective algorithm for the candidate set generation. It is a hash-based algorithm and is especially effective for the generation of a candidate set for large 2-itemsets. Explicitly, the number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck. Note that the generation of smaller candidate sets enables us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly. The advantage of the proposed algorithm also provides us the opportunity of reducing the amount of disk I/O required. An extensive simulation study is conducted to evaluate performance of the proposed algorithm.

Caching can reduce the bandwidth requirement in a mobile computing environment. However, due to battery power limitations, a wireless mobile computer may often be forced to operate in a doze (or even totally disconnected) mode. As a result, the mobile computer may miss some cache invalidation reports broadcast by a server, forcing it to discard the entire cache contents after waking up. In this paper, we present an energy-efficient cache invalidation method, called GCORE (Grouping with COld update-set REtention), that allows a mobile computer to operate in a disconnected mode to save the battery while still retaining most of the caching benefits after a reconnection. We present an efficient implementation of GCORE and conduct simulations to evaluate its caching effectiveness. The results show that GCORE can substantially improve mobile caching by reducing the communication bandwidth (or energy consumption) for query processing.

Mining information and knowledge from large databases has been recognized by many researchers as a key research topic in database systems and machine learning, and by many industrial companies as an important area with an opportunity of major revenues. Researchers in many different fields have shown great interest in data mining. Several emerging applications in information-providing services, such as data warehousing and online services over the Internet, also call for various data mining techniques to better understand user behavior, to improve the service provided and to increase business opportunities. In response to such a demand, this article provides a survey, from a database researcher's point of view, on the data mining techniques developed recently. A classification of the available data mining techniques is provided and a comparative study of such techniques is presented.

We study the subject of exploiting interoperator parallelism to optimize the execution of multi-join queries. Specifically, we focus on two major issues: (1) scheduling the execution sequence of multiple joins within a query, and (2) determining the number of processors to be allocated for the execution of each join operation obtained in (1). For the first issue, we propose and evaluate by simulation several methods to determine the general join sequences, or bushy trees. Despite their simplicity, the heuristics proposed can lead to the general join sequences that significantly outperform the optimal sequential join sequence. The quality of the join sequences obtained by the proposed heuristics is shown to be fairly close to that of the optimal one. For the second issue, it is shown that the processor allocation for exploiting interoperator parallelism is subject to more constraints-such as execution dependency and system fragmentation-than those in the study of intraoperator parallelism for a single join. The concept of synchronous execution time is proposed to alleviate these constraints. Several heuristics to deal with the processor allocation, categorized by bottom-up and top-down approaches, are derived and are evaluated by simulation. The relationship between issues (1) and (2) is explored. Among all the schemes evaluated, the two-step approach proposed, which first applies the join sequence heuristic to build a bushy tree as if under a single processor system, and then, in light of the concept of synchronous execution time, allocates processors to execute each join in the bushy tree in a top-down manner, emerges as the best solution to minimize the query execution time.

We conduct a performance study of coupling multiple systems with a global buffer, and present several results obtained from a multiple-system simulator. This simulator has been run against three workloads, and the coupled system behavior with these three different inputs is studied. Several statistics, including those on local and global buffer hits, page writes to the global buffer, cross-invalidations, and castouts are reported. Their relationship to the degree of data skew is explored. Moreover, in addition to the update-caching approach, a design alternative for the use of a global buffer, namely read-caching, is explored. In read-caching, not only updated pages but also pages read by each node are kept in the global buffer, thereby facilitating other nodes access to the same pages at the cost of a higher global buffer usage. Also investigated is the case of no-caching, i.e., without using a global buffer. Several simulation results are presented and analyzed.

Dynamic finite versioning (DFV) schemes are an effective approach to concurrent transaction and query processing, where a finite number of consistent, but maybe slightly out-of-date, logical snapshots of the database can be dynamically derived for query access. In DFV, the storage overhead for keeping additional versions of changed data to support the logical snapshots and the amount of obsolescence faced by queries are two major performance issues. We analyze the performance of DFV, with emphasis on the trade-offs between the storage cost and obsolescence. We develop analytical models based on a renewal process approximation to evaluate the performance of DFV using M/spl ges/2 snapshots. Asymptotic closed form results for high query arrival rates are given for the case of two snapshots. Simulation is used to validate the analytical models and to evaluate the tradeoffs between various strategies for advancing snapshots when M>2. The results show that (1) the analytical models match closely with simulation; (2) storage cost and obsolescence are sensitive to the snapshot advancing strategies, and (3) usually, increasing the number of snapshots demonstrates a trade-off between storage overhead and query obsolescence. For cases with skewed accessor low update rates, a small increase in the number of snapshots beyond two can substantially reduce the obsolescence. Such a reduction in obsolescence is more significant as the coefficient of variation of the query length distribution becomes larger. Moreover, for very low update rates, a large number of snapshots can be used to reduce the obsolescence to almost zero without increasing the storage overhead.

While a significant amount of research efforts has been reported on developing algorithms, based on joins and semijoins, to tackle distributed query processing, there is relatively little progress made toward exploring the complexity of the problems studied. As a result, proving NP-hardness of or devising polynomial-time algorithms for certain distributed query optimization problems has been elaborated upon by many researchers. However, due to its inherent difficulty, the complexity of the majority of problems on distributed query optimization remains unknown. In this paper we generally characterize the distributed query optimization problems and provide a frame work to explore their complexity. As it will be shown, most distributed query optimization problems can be transformed into an optimization problem comprising a set of binary decisions, termed Sum Product Optimization (SPO) problem. We first prove SPO is NP-hard in light of the NP-completeness of a well-known problem, Knapsack (KNAP). Then, using this result as a basis, we prove that five classes of distributed query optimization problems, which cover the majority of distributed query optimization problems previously studied in the literature, are NP-hard by polynomially reducing SPO to each of them. The detail for each problem transformation is derived. We not only prove the conjecture that many prior studies relied upon, but also provide a frame work for future related studies.

In this paper, we develop an algorithm, called PDM, to conduct parallel data mining for association rules.Consider

In this paper, we examine the issue of mining association rules among items in a large database of sales transactions. The mining of association rules can be mapped into the problem of discovering large itemsets where a large itemset is a group of items which appear in a sufficient number of transactions. The problem of discovering large itemsets can be solved by constructing a candidate set of itemsets first and then, identifying, within this candidate set, those itemsets that meet the large itemset requirement. Generally this is done iteratively for each large k-itemset in increasing order of k where a large k-itemset is a large itemset with k items. To determine large itemsets from a huge number of candidate large itemsets in early iterations is usually the dominating factor for the overall data mining performance. To address this issue, we propose an effective hash-based algorithm for the candidate set generation. Explicitly, the number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck. Note that the generation of smaller candidate sets enables us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly. Extensive simulation study is conducted to evaluate performance of the proposed algorithm.

The pipelined execution of multijoin queries in a multiprocessor-based database system is explored in this paper. Using hash-based joins, multiple joins can be pipelined so that the early results from a join, before the whole join is completed, are sent to the next join for processing. The execution of a query is usually denoted by a query execution tree. To improve the execution of pipelined hash joins, an innovative approach to query execution tree selection is proposed to exploit segmented right-deep trees, which are bushy trees of right-deep subtrees. We first derive an analytical model for the execution of a pipeline segment, and then, in the light of the model, we develop heuristic schemes to determine the query execution plan based on a segmented right-deep tree so that the query can be efficiently executed. As shown by our simulation, the proposed approach, without incurring additional overhead on plan execution, possesses more flexibility in query plan generation, and can lead to query plans of better performance than those achievable by the previous schemes using right-deep trees.>

In this paper we study parallel execution of multiple pipelined hash joins. Specifically, we deal with two issues, processor allocation and the use of hash filters, to improve parallel execution of hash joins. We first present a scheme to transform a bushy execution tree to an allocation tree, where each node denotes a pipeline. Then, processors are allocated to the nodes in the allocation tree based on the concept of synchronous execution time such that inner relations (i.e., hash tables) in a pipeline can be made available approximately the same time. In addition, the approach of hash filtering is investigated to further improve the overall performance. Performance studies are conducted via simulation to demonstrate the importance of processor allocation and to evaluate various schemes using hash filters. Simulation results indicate that processor allocation based on the allocation tree significantly outperforms that based on the original bushy tree, and that the effect of hash filtering becomes prominent as the number of relations in a query increases.

Semijoin has traditionally been relied upon to reduce the cost of data transmission for distributed query processing. However, judiciously applying join operations as reducers can lead to further reduction in the amount of data transmission required. In view of this fact, we explore the approach of using join operations as reducers in distributed query processing. We first show that the problem of determining a sequence of join operations for a query can be transformed to that of finding a specific type of set of cuts to the corresponding query graph, where a cut to a graph is a partition of nodes in that graph. Then, in light of this concept, we prove that the problem of determining the optimal sequence of join operations for a given query graph is of exponential complexity, thus justifying the necessity of applying heuristic approaches to solve this problem. By mapping the problem of determining a sequence of join reducers into the one of finding a set of cuts, we develop (for tree and general query graphs, respectively) efficient heuristic algorithms to determine a join reducer sequence for distributed query processing. The algorithms developed are based on the concept of divide and conquer and are of polynomial time complexity. Simulation is performed to evaluate these algorithms.>

Dynamic finite versioning (DFV) schemes that effectively support concurrent processing of transaction and queries are presented. Without acquiring locks, queries read from a small, fixed number of dynamically derived, transaction-consistent, possibly slightly obsolete, logical snapshots of the database. On the other hand, transactions access the most up-to-date data in the database without data contention from queries. Intermediate versions created between snapshots are automatically discarded. Dirty pages updated by active transactions are allowed to be written back into the database before commitment and, at the same time, consistent logical snapshots can be advanced automatically without quiescing the ongoing transactions or queries.>

In this paper, we develop algorithms to achieve optimal processor allocation for pipelined hash joins in a multiprocessor-based database system. A pipeline of hash joins is composed of several stages, each of which is associated with one join operation. The whole pipeline is executed in two phases: (1) the table-building phase, and (2) the tuple-probing phase. We focus on the problem of allocating processors to the stages of a pipeline to minimize the query execution time. We formulate the processor allocation problem as a two-phase mini-max optimization problem, and develop three optimal allocation schemes under three different constraints. The effectiveness of our problem formulation and solution is verified through a detailed tuple-by-tuple simulation of pipelined hash joins. Our solution scheme is general and applicable to any optimal resource allocation problem formulated as a two-phase mini-max problem.

The application of a combination of join and semi-join operations to minimize the amount of data transmission required for distributed query processing is discussed. Specifically, two important concepts that occur with the use of join operations as reducers in query processing, namely, gainful semi-joins and pure joint attributes, are used. Some semi-joint, though not profitable themselves, may benefit the execution of subsequent join operations as reducers. Such a semi-join is termed a gainful semi-join. In addition, join attributes that are not part of the output attributes are referred to as pure join attributes. They exploit the usefulness of gainful semi-joins and use the removability of pure join attributes to reduce the amount of data transmission required for query processing. Heuristic searches are developed to determine a sequence of join and semi-join reducers for query processing. Results indicate the importance of the approach to combining joins and semi-joins for distributed query processing.>

The authors deal with two major issues to exploit inter-operator parallelism within a multijoin query: join sequence scheduling and processor allocation. For the first issue, they propose and evaluate by simulation several methods to determine the general join sequences, or the bush execution trees. Despite their simplicity, the proposed heuristics can lead to the general join sequences which significantly outperform the optimal sequential join sequence. In addition, several heuristics to determine the processor allocation, categorized by bottom-up and top-down approaches, were derived and evaluated by simulation. As confirmed by the simulation, by first using the join sequence heuristics to build a busy tree and then applying the concept of synchronous execution time to the busy tree for processor allocation, an efficient two-step approach to schedule and execute multijoin queries in a multiprocessor system can be obtained.>

The problem of combining join and semijoin reducers for distributed query processing is studied. An approach, of interleaving a join sequence with beneficial semijoins is proposed. A join sequence is mapped into a join sequence tree that provides an efficient way to identify for each semijoin its correlated semijoins as well as its reducible relations under the join sequence. In light of these properties, an algorithm is developed to determine an effective sequence of join reducers. Examples are also given to illustrate the results, which show that the approach of interleaving a join sequence with beneficial semijoins is effective in reducing the amount of data transmission to process distributed queries.>