Search

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

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., L²-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 overtime. As demonstrated by our experimental results, our proposed framework can outperform current techniques in both real and synthetic data. [ABSTRACT FROM AUTHOR]

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

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

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 k 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. [ABSTRACT FROM AUTHOR]

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

Generally speaking, to implement Apriori-based association rule mining in hardware, one has to load candidate iten~sets and a database into the hardware. Since the capacity of the hardware architecture is fixed, if the number of candidate itemsets dr 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 PiPellned (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 simultaneou~ly. When the database is fed into the hardware, candidate itemsets are ~ompared 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. [ABSTRACT FROM AUTHOR]

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

In a mobile computing system, as users move to a new service area, the new server is usually considered to take over the execution of running programs for mobile users from the previous server so as to reduce the communication overhead of a mobile system. This procedure is referred to as service handoff. Note that when service handoff occurs, the new server will lose its advantage for cache access. To remedy this, we explore in this paper several cache retrieval schemes to improve the efficiency of cache retrieval. In particular, we analyze the impact of using a coordinator buffer to improve the overall performance of cache retrieval. Moreover, in light of the properties of transactions (i.e., temporal locality of data access among transactions), we devise a Dynamic and Adaptive cache Retrieval scheme (DAR) that can utilize proper cache methods according to some specific criteria to deal with the service handoff situation in a mobile computing environment. Performance of these cache retrieval schemes is analyzed and a system simulator is developed to validate our results. We devise a systematic procedure for determining the optimal operating points of DAR. Our experimental results show that by adaptively adopting the advantages of different cache retrieval methods, DAR significantly outperforms other schemes and is particularly effective for a mobile computing environment. [ABSTRACT FROM AUTHOR]

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 in this paper 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. [ABSTRACT FROM AUTHOR]

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