Incremental View Maintenance for Mobile Databases

In a mobile environment, querying a database at a stationary server from a mobile client is expensive due to the limited bandwidth of a wireless channel and the instability of the wireless network. We address this problem by maintaining a materialized view in a mobile client's local storage. Such a materialized view can be considered as a data warehouse. The materialized view contains results of common queries in which the mobile client is interested. In this paper, we address the view update problem for maintaining the consistency between a materialized view at a mobile client and the database server. The content of a materialized view could become incoherent with that at the database server when the content of the database server and/or when the location of the client is changed. Existing view update mechanisms are ‘push-based’. The server is responsible for notifying all clients whose views might be affected by the changes in database or the mobility of the client. This is not appropriate in a mobile environment due to the frequent wireless channel disconnection. Furthermore, it is not easy for a server to keep track of client movements to update individual client location-dependent views. We propose a ‘pull-based’ approach that allows a materialized view to be updated at a client in an incremental manner, requiring a client to request changes to its view from the server. We demonstrate the feasibility of our approach with experimental results. Received 27 January 1999 / Revised 26 November 1999 / Accepted 17 April 2000     

P(VDF-TrFE) copolymer acoustic emission sensors

Acoustic emission (AE) sensors have been fabricated using polarized polyvinylidene fluoride/trifluoroethylene (P(VDF-TrFE)) piezoelectric copolymer films. The acoustic and electromechanical properties of the copolymers have been determined using the ultrasonic immersion technique and the resonance technique, respectively. The P(VDF-TrFE) AE sensors have been calibrated according to the ASTM standard and evaluated for potential application in the detection of AE in glass fiber reinforced polypropylene (GFPP). A ceramic AE sensor also has been fabricated using lead zirconate titanate (PZT) 7A piezoelectric ceramic and its sensitivity and performance are reported as well. The copolymer sensors do not show resonance peaks of the ceramic sensor and have adequate sensitivity. They can reproduce AE signals accurately without giving artifacts and have potential use in commercial AE systems.     

Interaction of ISPs: Distributed Resource Allocation and Revenue Maximization

The Internet is a hierarchical architecture comprising heterogeneous entities of privately owned infrastructures, where higher level Internet service providers (ISPs) supply connectivity to the local ISPs and charge the local ISPs for the transit services. One of the challenging problems facing service providers today is how the profitability can be increased while maintaining good service qualities as the network scales up. In this work, we seek to understand the fundamental issues on the "interplay" (or interaction) between ISPs at different tiers. Although the local ISPs (which we term peers) can communicate with each other by purchasing the connectivity from transit ISPs, there stands an opportunity for them to set up private peering relationships. Under this competitive framework, we explore the issues on 1) the impact of peering relationship; 2) resource distribution; 3) revenue maximization; and 4) condition for network upgrade. First, a generalized model is presented to characterize the behaviors of peers and the transit ISP, in which their economic interests are reflected. We study how a peer can distributively determine its optimal peering strategy. Furthermore, we show how a transit ISP is able to utilize the available information to infer its optimal pricing strategy, under which a revenue maximization is achieved. Two distributed algorithms are proposed to help ISPs to provide a fair and efficient bandwidth allocation to peers, avoiding a resource monopolization of the market. Last, we investigate the above issues in a "many-peers region," that is, when we scale up the network. We provide insightful evidence to show that the ISPs can still gain profits as they upgrade the network infrastructures. Extensive simulations are carried out to support our theoretical claims.     

Efficient Phrase-Based Document Similarity for Clustering

In this paper, we propose a phrase-based document similarity to compute the pair-wise similarities of documents based on the Suffix Tree Document (STD) model. By mapping each node in the suffix tree of STD model into a unique feature term in the Vector Space Document (VSD) model, the phrase-based document similarity naturally inherits the term tf-idf weighting scheme in computing the document similarity with phrases. We apply the phrase-based document similarity to the group-average Hierarchical Agglomerative Clustering (HAC) algorithm and develop a new document clustering approach. Our evaluation experiments indicate that, the new clustering approach is very effective on clustering the documents of two standard document benchmark corpora OHSUMED and RCV1. The quality of the clustering results significantly surpass the results of traditional single-word textit{tf-idf} similarity measure in the same HAC algorithm, especially in large document data sets. Furthermore, by studying the property of STD model, we conclude that the feature vector of phrase terms in the STD model can be considered as an expanded feature vector of the traditional single-word terms in the VSD model. This conclusion sufficiently explains why the phrase-based document similarity works much better than the single-word tf-idf similarity measure.     

The <Emphasis Type="Italic">B</Emphasis><Superscript><Emphasis Type="Italic">dual</Emphasis></Superscript>-Tree: indexing moving objects by space filling curves in the dual space

Existing spatiotemporal indexes suffer from either large update cost or poor query performance, except for the B ^x -tree (the state-of-the-art), which consists of multiple B ⁺-trees indexing the 1D values transformed from the (multi-dimensional) moving objects based on a space filling curve (Hilbert, in particular). This curve, however, does not consider object velocities, and as a result, query processing with a B ^x -tree retrieves a large number of false hits, which seriously compromises its efficiency. It is natural to wonder “can we obtain better performance by capturing also the velocity information, using a Hilbert curve of a higher dimensionality?”. This paper provides a positive answer by developing the B ^dual -tree, a novel spatiotemporal access method leveraging pure relational methodology. We show, with theoretical evidence, that the B ^dual -tree indeed outperforms the B ^x -tree in most circum- stances. Furthermore, our technique can effectively answer progressive spatiotemporal queries, which are poorly supported by B ^x -trees.     

A data mining proxy approach for efficient frequent itemset mining

Data mining has attracted a lot of research efforts during the past decade. However, little work has been reported on the efficiency of supporting a large number of users who issue different data mining queries periodically when there are new needs and when data is updated. Our work is motivated by the fact that the pattern-growth method is one of the most efficient methods for frequent pattern mining which constructs an initial tree and mines frequent patterns on top of the tree. In this paper, we present a data mining proxy approach that can reduce the I/O costs to construct an initial tree by utilizing the trees that have already been resident in memory. The tree we construct is the smallest for a given data mining query. In addition, our proxy approach can also reduce CPU cost in mining patterns, because the cost of mining relies on the sizes of trees. The focus of the work is to construct an initial tree efficiently. We propose three tree operations to construct a tree. With a unique coding scheme, we can efficiently project subtrees from on-disk trees or in-memory trees. Our performance study indicated that the data mining proxy significantly reduces the I/O cost to construct trees and CPU cost to mine patterns over the trees constructed.     

Type-2 Fuzzy Markov Random Fields and Their Application to Handwritten Chinese Character Recognition

In this paper, we integrate type-2 (T2) fuzzy sets with Markov random fields (MRFs) referred to as T2 FMRFs, which may handle both fuzziness and randomness in the structural pattern representation. On the one hand, the T2 membership function (MF) has a 3-D structure in which the primary MF describes randomness and the secondary MF evaluates the fuzziness of the primary MF. On the other hand, MRFs can represent patterns statistical-structurally in terms of neighborhood system and clique potentials and, thus, have been widely applied to image analysis and computer vision. In the proposed T2 FMRFs, we define the same neighborhood system as that in classical MRFs. To describe uncertain structural information in patterns, we derive the fuzzy likelihood clique potentials from T2 fuzzy Gaussian mixture models. The fuzzy prior clique potentials are penalties for the mismatched structures based on prior knowledge. Because Chinese characters have hierarchical structures, we use T2 FMRFs to model character structures in the handwritten Chinese character recognition system. The overall recognition rate is 99.07%, which confirms the effectiveness of the proposed method.     

Primal or dual: which promises faster spatiotemporal search?

The existing predictive spatiotemporal indexes can be classified into two categories, depending on whether they are based on the primal or dual methodology. Although we have gained considerable empirical knowledge about various access methods, currently there is only limited understanding on the theoretical characteristics of the two methodologies. In fact, the experimental results in different papers even contradict each other, regarding the relative superiority of the primal and dual techniques. This paper presents a careful study on the query performance of general primal and dual indexes, and reveals important insight into the behavior of each technique. In particular, we mathematically establish the conditions that determine the superiority of each methodology, and provide rigorous justification for well-known observations that have not been properly explained in the literature. Our analytical findings also resolve the contradiction in the experiments of previous work.     

Empirical evaluation of distributed pair programming

Pair programming, in which two individuals share a single computer to collaboratively develop software, has been shown to have many benefits in industry and in education. One drawback of pair programming is its collocation requirement, which limits its use to situations where the partners can physically meet. A tool that supported distributed pair programming, in which the partners could pair from separate locations, would remove this impediment.This paper discusses the development and empirical evaluation of such a tool. A significant feature of this tool is the presence of a second cursor that supports gesturing. Students who used the tool in their introductory programming course performed as well as collocated students on their programming assignments and final exam. These students also spent less time working by themselves. They also felt that the gesturing feature was useful and used it regularly.