Early detection of patient deterioration is crucial for reducing mortality rates. Heart rate data has shown promise in assessing patient health, and wearable devices offer a cost-effective solution for real-time monitoring. However, extracting meaningful insights from diverse heart rate data and handling missing values in wearable device data remain key challenges. To address these challenges, we propose TARL, an innovative approach that models the structural relationships of representative subsequences, known as shapelets, in heart rate time series. TARL creates a shapelet-transition knowledge graph to model shapelet dynamics in heart rate time series, indicating illness progression and potential future changes. We further introduce a transition-aware knowledge embedding to reinforce relationships among shapelets and quantify the impact of missing values, enabling the formulation of comprehensive heart rate representations. These representations capture explanatory structures and predict future heart rate trends, aiding early illness detection. We collaborate with physicians and nurses to gather ICU patient heart rate data from wearables and diagnostic metrics to assess illness severity and evaluate deterioration. Experiments on real-world ICU data demonstrate that TARL achieves both high reliability and early detection. A case study further showcases TARL's explainable detection process, highlighting its potential as an AI-driven tool to assist clinicians in recognizing early signs of patient deterioration.

In the semiconductor industry, integrated circuit (IC) processes play a vital role, as the rising complexity and market expectations necessitate improvements in yield. Identifying IC defects and assigning IC testing tasks to the right engineers improves efficiency and reduces losses. While current studies emphasize fault localization or defect classification, they overlook the integration of defect characteristics, historical failures, and the insights from engineer expertise, which restrains their effectiveness in improving IC handling. To leverage AI for these challenges, we propose DeCo, an innovative approach for optimizing task assignment in IC testing. DeCo constructs a novel defect-aware graph from IC testing reports, capturing co-failure relationships to enhance defect differentiation, even with scarce defect data. Additionally, it formulates defect-aware representations for engineers and tasks, reinforced by local and global structure modeling on the defect-aware graph. Finally, a contrasting-based assignment mechanism pairs testing tasks with QA engineers by considering their skill level and current workload, thus promoting an equitable and efficient job dispatch. Experiments on a real-world dataset demonstrate that DeCo achieves the highest task-handling success rates in different scenarios, exceeding 80%, while also maintaining balanced workloads on both scarce or expanded defect data. Moreover, case studies reveal that DeCo can assign tasks to potentially capable engineers, even for their unfamiliar defects, highlighting its potential as an AI-driven solution for the real-world IC failure analysis and task handling.

Consumer wearable devices like smartwatches enable real-time tracking of vital signs with various sensors. Accordingly, experts may leverage smart home techniques for treating sleep disorders by targeting specific sleep stages. To facilitate this scenario, this paper focuses on sleep stage classification based on body movement and heart rate signals detected by wearables in real time. Due to their limited battery capacity, it is crucial to balance the trade-off between power efficiency and classification accuracy. To address the problem, inspired by multi-tasking, we propose COPS, an innovative framework that includes a power-efficient shallow classifier for simple cases and a deep classifier for complex instances. COPS introduces an intelligent switch, CESwitch, to determine a confidence score that directs input to either the shallow or deep classifier. By selectively activating the shallow classifier, the overall expected power consumption could be lower. Two strategies of CESwitch, namely Confidence Delegation and Agreement Verification, are proposed and examined. Notably, both COPS and CESwitch can be seamlessly integrated with existing deep sleep stage classifiers. Comprehensive experimental results on two real datasets manifest that COPS outperforms state-of-the-art lightweight and deep sleep stage classifiers by reducing 77.8% computational cost in terms of FLOPs with only 1.9% accuracy drop. Moreover, adapting to an existing deep model saves up to 32.7% in FLOPs compared to its original architecture.

With the rise of Internet-of-Things devices, the analysis of sensor-generated energy time series data has become increasingly important. This is especially crucial for detecting rare events like unusual electricity usage or water leakages in residential and commercial buildings, which is essential for optimizing energy efficiency and reducing costs. However, existing detection methods on large-scale data may fail to correctly detect rare events when they do not behave significantly differently from standard events or when their attributes are non-stationary. Additionally, the capacity of computational resources to analyze all time series data generated by an increasing number of sensors becomes a challenge. This situation creates an emergent demand for a workload-bounded strategy. To ensure both effectiveness and efficiency in detecting rare events in massive energy time series, we propose a heuristic-based framework called HALE . This framework utilizes an explore–exploit selection process that is specifically designed to recognize potential features of rare events in energy time series. HALE involves constructing an attribute-aware graph to preserve the attribute information of rare events. A heuristic-based random walk is then derived based on partial labels received at each time period to discover the non-stationarity of rare events. Potential rare event data are selected from the attribute-aware graph, and existing detection models are applied for final confirmation. Our study, which was conducted on three actual energy datasets, demonstrates that the HALE framework is both effective and efficient in its detection capabilities. This underscores its practicality in delivering cost-effective energy monitoring services.

The growing adoption of electric vehicles (EVs) has resulted in an increased demand for public EV charging infrastructure. Currently, the collaboration between these stations has become vital for efficient charging scheduling and cost reduction. However, most existing scheduling methods primarily focus on recommending charging stations without considering users’ charging preferences. Adopting these strategies may require considerable modifications to how people charge their EVs, which could lead to a reluctance to follow the scheduling plan from charging services in real-world situations. To address these challenges, we propose the POSKID framework in this article. It focuses on spatial-temporal charging scheduling, aiming to recommend a feasible charging arrangement, including a charging station and a charging time slot, to each EV user while minimizing overall operating costs and ensuring users’ charging satisfaction. The framework adopts an online charging mechanism that provides recommendations without prior knowledge of future electricity information or charging requests. To enhance users’ willingness to accept the recommendations, POSKID incorporates an incentive strategy and a novel embedding method combined with Bayesian personalized analysis. These techniques reveal users’ implicit charging preferences, enhancing the success probability of the charging scheduling task. Furthermore, POSKID integrates an online candidate arrangement selection and an explore-exploit strategy to improve the charging arrangement recommendations based on users’ feedback. Experimental results using real-world datasets validate the effectiveness of POSKID in optimizing charging management, surpassing other strategies. The results demonstrate that POSKID benefits each charging station while ensuring user charging satisfaction.

Personality inference has received widespread attention for its potential to infer psychological well being, job satisfaction, romantic relationship success, and professional performance. In this research, we focus on Conscientiousness, one of the well studied Big Five personality traits, which determines if a person is self-disciplined, organized, and hard-working. Research has shown that Conscientiousness is related to a person's academic and workplace success. For an expert to evaluate a person's Conscientiousness, long-term observation of the person's behavior at work place or at home is usually required. To reduce this evaluation effort as well as to cope with the increasing trend of human behavior turning digital, there is a need to conduct the evaluation using digital traces of human behavior. In this paper, we propose a novel framework, called HAPE, to automatically infer an individual's Conscientiousness scores using his/her behavioral data in an E-learning system. We first determine how users learn in the E-learning system, and design a novel Pattern Relational Graph Embedding method to learn the representations of users, their learning actions, and learning situations. The interaction between users, learning actions and situations characterizes the learning style of a user. Through experimental studies on real data, we demonstrate that HAPE framework outperforms the baseline methods in the Conscientiousness inference task.

Accurate network traffic load (TL) prediction is essential in many networking applications. However, the real TLs in practical networks may have high variability and are difficult to be predicted, which may severely affect users’ quality of experience (QoE). To address this problem, we first analyze the real-world network traffic dataset to investigate real TLs properties and find out the distance-correlation between regions in a spatial graph have the potential to improve the prediction result. Hence, we propose a time-series model based method to consider the distance-correlation in an efficient way. Empirically, experimental studies on real data demonstrate that our proposed method can effectively reduce at least 10% error value on regions with high-variability TLs. Finally, we further discuss the impact of the distance-correlation on the TL prediction.

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.

The arise of fast parcel delivery has led to anytime-anywhere online shopping for everyone. However, due to the unknown of household occupancy, traditional parcel delivery is generally not very effective. Delivery drivers have to arrange redelivery every time when the household is not at home, which is time-consuming. Therefore, we address an important issue on the exploration of optimal delivery routes using household occupancy detection, which leads to a novel routing framework, called DROD. In this paper, we develop a novel routing framework by borrowing the strengths of household occupancy detection from electricity consumption. Our experimental studies on real datasets show that the proposed framework can effectively and efficiently discover optimal delivery routes with precise occupancy detection model.

The arise of E-learning systems has led to an anytime-anywhere-learning environment for everyone by providing various online courses and tests. However, due to the lack of teacher-student interaction, such ubiquitous learning is generally not as effective as offline classes. In traditional offline courses, teachers facilitate real-time interaction to teach students in accordance with personal aptitude from students' feedback in classes. Without the interruption of instructors, it is difficult for users to be aware of personal unknowns. In this paper, we address an important issue on the exploration of 'user unknowns' from an interactive question-answering process in E-learning systems. A novel interactive learning system, called CagMab, is devised to interactively recommend questions with a round-by-round strategy, which contributes to applications such as a conversational bot for self-evaluation. The flow enables users to discover their weakness and further helps them to progress. In fact, despite its importance, discovering personal unknowns remains a challenging problem in E-learning systems. Even though formulating the problem with the multi-armed bandit framework provides a solution, it often leads to suboptimal results for interactive unknowns recommendation as it simply relies on the contextual features of answered questions. Note that each question is associated with concepts and similar concepts are likely to be linked manually or systematically, which naturally forms the concept graphs. Mining the rich relationships among users, questions and concepts could be potentially helpful in providing better unknowns recommendation. To this end, in this paper, we develop a novel interactive learning framework by borrowing strengths from concept-aware graph embedding for learning user unknowns. Our experimental studies on real data show that the proposed framework can effectively discover user unknowns in an interactive fashion for the recommendation in E-learning systems.

The effectiveness of monetary promotions has been well reported in the literature to affect shopping decisions for products in real life experience. Nowadays, e-commerce retailers are facing more fierce competition on price promotion in that consumers can easily use a search engine to find another merchant selling an identical product for comparing price.

Spatio-temporal pattern mining attempts to discover unknown, potentially interesting and useful event sequences in which events occur within a specific time interval and spatial region. In the literature, mining of spatio-temporal sequential patterns generally relies on the existence of identity in formation for the accumulation of pattern appearances. For the recent trend of open data, which are mostly released without the specific identity information due to privacy concern, previous work will encounter the challenging difficulty to properly transform such non-identity data into the mining process. In this paper, we propose a practical approach, called Top K Spatio-Temporal Chaining Patterns Discovery (abbreviated as TKSTP), to discover frequent spatio-temporal chaining patterns. The TKSTP framework is applied on two real criminal datasets which are released without the identity information. As shown in our experimental studies, the proposed framework effectively discovers high-quality spatio-temporal patterns. In addition, case studies of crime pattern analysis also demonstrate their applicability and reveal several interestingly hidden phenomenons.

We in this paper explore a novel model of influence minimization for the need to effectively prevent the outbreak of epidemic-prone spread on networks. The current network-blocking models usually report the expected number of infected nodes under the limited number of cutting edges. However, to control the epidemic-prone spread such as dengue fever, epidemiologists tend to deploy a cost-effective intervention with low outbreak risk, but the outbreak risk cannot be estimated based on the expectation of infected count. We in this paper explore the first solution to estimate the probability that can successfully bound the infected count below the out-of-control threshold, which can be logically mapped to the outbreak risk and can facilitate the authority to adaptively adjust the intervention cost for the need of risk control. We elaborate upon the proposed MCP (standing for Maximization of Containment Probability) problem and show that it is a NP-hard challenge without the submodular property. We further devise an effective measurement of sufficient number of Monte Carlo iterations based on the relative error of Monte Carol integration. The experimental results show that our proposed algorithm with small iterations can deliver the qualified guarantee of containment probability, demonstrating its feasibility for real applications.

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.

With the effects of global warming, some epidemic diseases via mosquito (e.g. mosquito-borne diseases) become more serious, such as dengue fever and zika virus. It is reported that the epidemic disease may cause many challenges to the hospital management due to the unexpected burst with uncertain reasons. Furthermore, the imperfect cares during the propagation of epidemic diseases, such as dengue fever (so far the appropriate treatment is not well established), may lead to the increasing mortality rate which should be avoided. In this paper, a novel paradigm for optimizing the placement of medical resource is proposed in pursuit of reducing the overloading cases in hospitals during the epidemic outbreak in the urban area. In this paper we explore the first paper to explore two important issues, including the strategy to evaluate the service quality and the solution to dynamically dispatch the medical resource, along with the spatial variation of epidemic outbreak. As validated in our experimental results in real data of dengue outbreak happening in Tainan (2015), we present the feasibility of our framework to deploy a dynamic placement strategy for medical resource assignment.

In this paper, we explore a novel problem to identify timely new knowledge triples. In the literature, the need of knowledge enrichment has been recognized as the key to the success of semantic search. However, previous work of automatic knowledge extraction, such as Google Knowledge Vault, aim at identifying the unannotated knowledge triples from the full web-scale content in the offline execution. In our study, we show that most people demand the updated knowledge soon after the information is announced. However, the number of queries of such knowledge dramatically declines after a few days, meaning that the most people cannot obtain the precise knowledge from the execution of the offline knowledge enrichment when they inquire the answer of the timely events. To remedy this, we propose the SCKE framework to extract new knowledge triples which can be executed in the online scenario. We model the 'Query-Click' bipartite graph to extract the query correlation and to identify temporally coexistent entity pairs. Our experimental studies show that new triples can also be identified effectively and efficiently.

In this paper, we study a novel problem of influence maximization in social networks: Given a period of promotion time and a set of target users, each of which can be activated by its neighbors multiple times, we aim at maximizing the total acceptance frequency of these target users by initially selecting k most influential seeds. The promising viral marketing paradigm on social network is different from the current research in two main aspects. First, instead of maximizing the message spread over the entire social network, we focus on the target market since the business vendors almost specify the target users before designing its marketing strategy. Second, the status of a user is no longer a binary indicator representing either active or inactive. In the new model the user status turns to be an integer value reflecting the amount of influences delivered to that user. In this paper, we prove the NP-hard nature of this challenging problem.

In this paper, we study an important issue whether the network properties on mobile social networks are still similar to these on traditional web-based social networks. To explore such answers is important since the paradigm shift has already happened from PC-based access to mobile access nowadays. In this paper, we focus on Instagram, which is a remarkable mobile-based photo sharing platform, as the reference network. We comprehensively study its network properties in the quantitative sense, and reveal some interesting results. Surprisingly, some properties in Instagram are highly diverse from these characteristics in traditional social networks such as Facebook and Twitter. We thus state that traditional assumptions on the network properties should be re-verified when developers devise social applications, such as the advertisement strategies, for mobile networks. We also conclude that the new research spectrum is highly demanded on network analysis and social technologies for the next-generation mobile-based social platform.

In this paper, we study a novel paradigm of viral marketing with the goal to sustain the influential effectiveness in the network. We study from real cases such as the Ice Bucket Challenges for the ALS awareness, and figure out the "easy come and easy go" phenomenon in the marketing promotion. Such a natural property is fully unexplored in the literature, but it will violate the need of many marketing applications which attempt to receive the perpetual attention and support. We thus highlight the problem of Influential Sustainability, to pursue the long-term and effective influence on the network. Given the set of initial seeds S and a threshold ρ, the goal of Influential Sustainability is to best decide the timing to activate each seed in S so as to maximize the number of iterations in which each iteration will activate the number of inactive nodes more than ρ. The Influential Sustainability problem is challenging due to its #P-hard nature. In addition to the greedy idea, we further present three strategies to heuristically decide the activating timing for each seed. As demonstrated in the empirical study on real data, instead of only providing the flexibility of striking a compromise between the execution efficiency and the resulting quality, these heuristic algorithms can be executed highly efficiently and meanwhile it is able to sustain the longer period which can continuously activate inactive nodes effectively. The results demonstrate their prominent advantage to be practical algorithms for the promising viral marketing paradigm.

Recently, most background modeling approaches represent distributions of background changes by using parametric models such as Gaussian mixture models. Because of significant illumination changes and dynamic moving backgrounds with time, variations of background changes are hard to be modeled by parametric background models. Moreover, how to efficiently and effectively update parameters of parametric models to reflect background changes remains a problem. In this paper, we propose a novel coarse-to-fine detection theory algorithm to extract foreground objects on the basis of nonparametric background and foreground models represented by binary descriptors. We update background and foreground models by a first-in-first-out strategy to maintain the most recent observed background and foreground instances. As shown in the experiments, our method can achieve better foreground extraction results and fewer false alarms of surveillance videos with lighting changes and dynamic backgrounds in both collected and CDnet 2012 benchmark data sets.

There has been an increasing research interest in classification for data streams. Due to the evolving nature of data streams, it is a highly challenging issue to detect the appearance of concept drifts, which will make the current classification model invalid as time passes. So far most stream classification solutions exploit the so-called incremental learning process to continuously track the deviation of prediction accuracy. Unfortunately, to achieve the prompt concept-drifting detection, such strategies usually rely on an infeasible assumption about the availability of data instances with true labels. We in this paper propose a new framework, called Inference of Concept Evolution (abbreviated as ICE), to minimize the need of real-time acquisition of true labels. Specifically, the ICE framework is devised based on the idea of model reuse. The dictionary learning technique is utilized to determine whether the concept drift appears without the need of label acquisition. When the drift happens, the ICE framework will select the best model maintained in the model pool, decreasing the need of model re-training and its costly label acquisition. As demonstrated in our experimental result, the ICE framework can track the best model correctly and efficiently, showing its feasibility in real cases.

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.

We in this paper explore a new data dissemination framework in Mobile P2P networks. Previous works in the literature usually elaborated upon the reduction of dissemination frequency in the network. However, many important and practical issues remain unresolved. First, the success of the system design usually relies on the support of other hardware components such as GPS, causing the extra power consumption. In addition, the property of the physical media used to make the ad-hoc network is not well discussed in the system. The system which assumes all users can access WiFi or 3G everywhere will limit the grow of the system popularity. Most importantly, the user preference is not considered, and each peer will receive and help to broadcast all messages whether the user is interested in. In this paper, we propose the MobiPAD framework, which the current stage concentrates on applications of data dissemination in student communities. The MobiPAD framework is built based on Bluetooth since Bluetooth is low power consumption and high penetration rate, and is suitable for students without the expensive 3G or WiFi accessibility. We also consider preference-aware disseminations to support various user preferences in the Mobile P2P network. The fairness issue is considered in the model, meaning that users who receive more interesting messages should contribute more message retransmission than users who wonder to receive few messages. The basic MobiPAD platform for student communities is also discussed in the paper, to show its possibility for further use.

The mobile social networking application is aimed to build an application that helps users to check-in places and save the check-in data on cloud. Users can then show their trajectory on a web site. This project is ideal for people who spend a great deal of time traveling. The major benefit is the privacy that it offers and the algorithms that help the user to save the battery life. All the data is store in the Google Cloud SQL.

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.

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.

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

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.

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.

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

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

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.

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

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.

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.

In this paper we devise an efficient algorithm for clustering market-basket data items. In view of the nature of clustering market basket data, we devise in this paper a novel measurement, called the small-large (abbreviated as SL) ratio, and utilize this ratio to perform the clustering. With this SL ratio measurement, we develop an efficient clustering algorithm for data items to minimize the SL ratio in each group. The proposed algorithm not only incurs an execution time that is significantly smaller than that by prior work but also leads to the clustering results of very good quality.