Visual Prompt Tuning (VPT) has become a promising solution for Parameter-Efficient Fine-Tuning (PEFT) approach for Vision Transformer (ViT) models by partially fine-tuning learnable tokens while keeping most model parameters frozen. Recent research has explored modifying the connection structures of the prompts. However, the fundamental correlation and distribution between the prompts and image tokens remain unexplored. In this paper, we leverage metric learning techniques to investigate how the distribution of prompts affects fine-tuning performance. Specifically, we propose a novel framework, Distribution Aware Visual Prompt Tuning (DA-VPT), to guide the distributions of the prompts by learning the distance metric from their class-related semantic data. Our method demonstrates that the prompts can serve as an effective bridge to share semantic information between image patches and the class token. We extensively evaluated our approach on popular benchmarks in both recognition and segmentation tasks. The results demonstrate that our approach enables more effective and efficient fine-tuning of ViT models by leveraging semantic information to guide the learning of the prompts, leading to improved performance on various downstream vision tasks. The code is released on https://github.com/Noahsark/DA-VPT.

Deep Metric Learning (DML) plays an important role in modern computer vision research, where we learn a distance metric for a set of image representations. Recent DML techniques utilize the proxy to interact with the corresponding image samples in the embedding space. However, existing proxy-based DML methods focus on learning individual proxy-to-sample distance, while the overall distribution of samples and proxies lacks attention. In this paper, we present a novel proxy-based DML framework that focuses on aligning the sample and proxy distributions to improve the efficiency of proxy-based DML losses. Specifically, we propose the Data-Augmented Domain Adaptation (DADA) method to adapt the domain gap between the group of samples and proxies. To the best of our knowledge, we are the first to leverage domain adaptation to boost the performance of proxy-based DML. We show that our method can be easily plugged into existing proxy-based DML losses. Our experiments on benchmarks, including the popular CUB-200-2011, CARS196, Stanford Online Products, and In-Shop Clothes Retrieval, show that our learning algorithm significantly improves the existing proxy losses and achieves superior results compared to the existing methods. The code and Appendix are available at: https://github.com/Noahsark/DADA

Deep Metric Learning (DML) has long attracted the attention of the machine learning community as a key objective. Existing solutions concentrate on fine-tuning the pre-trained models on conventional image datasets. As a result of the success of recent pre-trained models derived from larger-scale datasets, it is challenging to adapt the model to the DML tasks in the local data domain while retaining the previously gained knowledge. In this paper, we investigate parameter-efficient methods for fine-tuning the pre-trained model for DML tasks. In particular, we propose a novel and effective framework based on learning Visual Prompts (VPT) in the pre-trained Vision Transformers (ViT). Based on the conventional proxy-based DML paradigm, we augment the proxy by incorporating the semantic information from the input image and the ViT, in which we optimize the visual prompts for each class. We demonstrate that our new approximations with semantic information are superior to representative capabilities, thereby improving metric learning performance. We conduct extensive experiments to demonstrate that our proposed framework is superior and efficient by evaluating popular DML benchmarks. In particular, we demonstrate that our fine-tuning method achieves comparable or even better performance than recent state-of-the-art full fine-tuning works of DML while tuning only a small percentage of total parameters.

The syntactic structure of sentences in a document substantially informs about its authorial writing style. Sentence representation learning has been widely explored in recent years and it has been shown that it improves the generalization of different downstream tasks across many domains. Even though utilizing probing methods in several studies suggests that these learned contextual representations implicitly encode some amount of syntax, explicit syntactic information further improves the performance of deep neural models in the domain of authorship attribution. These observations have motivated us to investigate the explicit representation learning of syntactic structure of sentences. In this article, we propose a self-supervised framework for learning structural representations of sentences. The self-supervised network contains two components; a lexical sub-network and a syntactic sub-network which take the sequence of words and their corresponding structural labels as the input, respectively. Due to the n -to-1 mapping of words to their structural labels, each word will be embedded into a vector representation which mainly carries structural information. We evaluate the learned structural representations of sentences using different probing tasks, and subsequently utilize them in the authorship attribution task. Our experimental results indicate that the structural embeddings significantly improve the classification tasks when concatenated with the existing pre-trained word embeddings.

Effective feature selection can help reduce dimensionality, improve prediction accuracy, and increase result comprehensibility. Classic feature selection methods typically select and test feature subset in multiple iterations, and thus can be regarded as an exploratory process. In recent literature, the multi-armed bandit has become an emerging method to automate exploration for searching optimal solutions in large spaces. In this paper, our research question is: Can the multi-armed bandit formulation help us to automate feature selection? Along this line, we reformulate the feature selection problem with the combinatorial multi-armed bandit (CMAB) framework by regarding each feature as an arm. We propose two novel oracles and investigate how the super arm is formed under different oracles, and how the coordination between various features can be improved by a novel reward scheme. We present extensive experimental results to demonstrate the improved performance of the proposed methods over conventional feature selection approaches.

With recent advances in artificial intelligence, recurrent neural networks have successfully generated pleasing melodies; however, they have struggled to create a full song that has structure, theme, and uniqueness. To overcome this limitation, we introduce Deep Composer, a music generation system based on music retrieval using deep neural hashing to encode the music building blocks. Music generation is performed by using the current music segment to retrieve the next segment from the database until the whole composition is complete. We present performance comparisons with multiple recent state-of-the-art music generation methods to show that the songs generated by Deep Composer are unique, musically pleasing and contain more structure and theme features like that of a professionally composed song.

Music is one of the most appreciated forms of art, and generating songs has become a popular subject in the artificial intelligence community. There are various networks that can produce pleasant sounding music, but no model has been able to produce music that duplicates the style of a specific artist or artists. In this paper, we extend a previous single-instrument model: the Deep Composer-a model we believe to be capable of achieving this. Deep Composer originates from the Deep Segment Hash Learning (DSHL) single instrument model and is designed to learn how a specific artist would place individual segments of music together rather than create music similar to a specific genre. To the best of our knowledge, no other network has been designed to achieve this. For these reasons, we introduce a new field of study, Intelligence Duplication (ID). AI research generally focuses on developing techniques to mimic universal intelligence. Intelligence Duplication (ID) research focuses on techniques to artificially duplicate or clone a specific mind such as Mozart. Additionally, we present a new retrieval algorithm, Segment Barrier Retrieval (SBR), to improve retrieval accuracy within the hash-space as opposed to a more traditionally used feature-space. SBR prevents retrieval branches from entering areas of low-density within the hash-space, a phenomena we identify and label as segment sparsity. To test our Deep Composer and the effectiveness of SBR, we evaluate various models with different SBR threshold values and conduct qualitative surveys for each model. The survey results indicate that our Deep Composer model is capable of learning music generation from multiple composers. Our extended Deep Composer model provides a more suitable platform for Intelligence Duplication. Future work can apply this platform to duplicate great composers such as Mozart or allow them to collaborate in the virtual space.

Matching information across image and text modalities is a fundamental challenge for many applications that involve both vision and natural language processing. The objective is to find efficient similarity metrics to compare the similarity between visual and textual information. Existing approaches mainly match the local visual objects and the sentence words in a shared space with attention mechanisms. The matching performance is still limited because the similarity computation is based on simple comparisons of the matching features, ignoring the characteristics of their distribution in the data. In this paper, we address this limitation with an efficient learning objective that considers the discriminative feature distributions between the visual objects and sentence words. Specifically, we propose a novel Adversarial Discriminative Domain Regularization (ADDR) learning framework, beyond the paradigm metric learning objective, to construct a set of discriminative data domains within each image-text pairs. Our approach can generally improve the learning efficiency and the performance of existing metrics learning frameworks by regulating the distribution of the hidden space between the matching pairs. The experimental results show that this new approach significantly improves the overall performance of several popular cross-modal matching techniques (SCAN [13], VSRN [14], BFAN [15]) on the MS-COCO and Flickr30K benchmarks.

In this paper, we design and evaluate a new substructure-aware Graph Representation Learning (GRL) approach. GRL aims to map graph structure information into low-dimensional representations. While extensive efforts have been made for modeling global and/or local structure information, GRL can be improved by substructure information. Some recent studies exploit adversarial learning to incorporate substructure awareness, but hindered by unstable convergence. This study will address the major research question: is there a better way to integrate substructure awareness into GRL? As subsets of the graph structure, interested substructures (i.e., subgraph) are unique and representative for differentiating graphs, leading to the high correlation between the representation of the graph-level structure and substructures. Since mutual information (MI) is to evaluate the mutual dependence between two variables, we develop a MI inducted substructure-aware GRL method. We decompose the GRL pipeline into two stages: (1) node-level, where we introduce to maximize MI between the original and learned representation by the intuition that the original and learned representation should be highly correlated; (2) graph-level, where we preserve substructures by maximizing MI between the graph-level structure and substructure representation. Finally, we present extensive experimental results to demonstrate the improved performances of our method with real-world data.

With the popularity of mobile sensor technology, smart wearable devices open a unprecedented opportunity to solve the challenging human activity recognition (HAR) problem by learning expressive representations from the multi-dimensional daily sensor signals. This inspires us to develop a new algorithm applicable to both camera-based and wearable sensor-based HAR systems. Although competitive classification accuracy has been reported, existing methods often face the challenge of distinguishing visually similar activities composed of activity patterns in different temporal orders. In this paper, we propose a novel probabilistic algorithm to compactly encode temporal orders of activity patterns for HAR. Specifically, the algorithm learns an optimal set of latent patterns such that their temporal structures really matter in recognizing different human activities. Then, a novel probabilistic First-Take-All (pFTA) approach is introduced to generate compact features from the orders of these latent patterns to encode the entire sequence, and the temporal structural similarity between different sequences can be efficiently measured by the Hamming distance between compact features. Experiments on three public HAR datasets show the proposed pFTA approach can achieve competitive performance in terms of accuracy as well as efficiency.

Software-defined networking introduces opportunities to optimize the Internet Service Provider’s network and to improve client experience for the Video-on-Demand applications. Recent studies on SDN frameworks show that traffic engineering methods allow a fair share of bandwidth between adaptive video streaming clients. Additionally, ISPs can make better estimations of bandwidth and contribute to the bitrate selection for the clients. This study focuses on another aspect of network assistance in video delivery: CDN server selection. In a typical framework where the ISP contributes to the CDN selection, the video provider and the network provider interfaces are merged together. Clients connect to the ISP to get the best CDN server candidate for a given video. This exposes client requests to the ISP. However, video providers have been investing large resources for encrypted video provisioning to preserve their client’s information from third parties, especially network providers. The typical approach is not practical due to privacy concerns. In this study, we present a framework called PPNet to allow CDN-ISP collaboration while preventing the ISP’s access to the video request and availability information. Our framework introduces an isolation between the video provider’s and the ISP’s web interfaces. Clients connect to both of the interfaces and deliver information on a need-to-know basis. As a second contribution, PPNet introduces a practical optimization method for CDN selection. Real-time data collection capabilities of a typical OpenFlow network is used as the input for optimization. Congestion-awareness has been the priority. To adapt for changing network conditions, capability of utilizing multiple servers simultaneously for a single video is introduced. Instead of directing each video client into a CDN node, the proposed system performs request routing per video segment. Finally, we present a system prototype of PPNet and show that our multiple-host adaptive streaming method introduces a significant improvement in quality of experience when compared to the state of the art.

Writing style is a combination of consistent decisions associated with a specific author at different levels of language production, including lexical, syntactic, and structural. In this paper, we introduce a style-aware neural model to encode document information from three stylistic levels and evaluate it in the domain of authorship attribution. First, we propose a simple way to jointly encode syntactic and lexical representations of sentences. Subsequently, we employ an attention-based hierarchical neural network to encode the syntactic and semantic structure of sentences in documents while rewarding the sentences which contribute more to capturing the writing style. Our experimental results, based on four benchmark datasets, reveal the benefits of encoding document information from all three stylistic levels when compared to the baseline methods in the literature.

Learning translation from images to human-readable natural language has become a great challenge in computer vision research in recent years. Existing works explore the semantic correlation between the visual and language domains via encoder-to-decoder learning frameworks based on classifying visual features in the language domain. This approach, however, is criticized for its lacking of naturalness and diversity. In this paper, we demonstrate a novel way to learn a semantic connection between visual information and natural language directly based on a Variational Autoencoder (VAE) that is trained in an adversarial routine. Instead of using the classification based discriminator, our method directly learns to estimate the diversity between a hidden vector embedded from a text encoder and an informative feature that is sampled from a learned distribution of the autoencoders. We show that the sentences learned from this matching contains accurate semantic meaning with high diversity in the image captioning task. Our experiments on the popular MSCOCO dataset indicates that our method learns to generate high-quality natural language with competitive scores on both correctness and diversity.

Due to their special gating schemes, Long Short-Term Memory (LSTM) has shown greater potential to process complex sequential information than the traditional Recurrent Neural Network (RNN). The conventional LSTM, however, fails to take into consideration the impact of salient spatio-temporal dynamics present in the sequential input data. This problem was first addressed by the differential Recurrent Neural Network (dRNN), which uses a differential gating scheme known as Derivative of States (DoS). DoS uses higher orders of internal state derivatives to analyze the change in information gain originated from the salient motions between the successive frames. The weighted combination of several orders of DoS is then used to modulate the gates in dRNN. While each individual order of DoS is good at modeling a certain level of salient spatio-temporal sequences, the sum of all the orders of DoS could distort the detected motion patterns. To address this problem, we propose to control the LSTM gates via individual orders of DoS. To fully utilize the different orders of DoS, we further propose to stack multiple levels of LSTM cells in an increasing order of state derivatives. The proposed model progressively builds up the ability of the LSTM gates to detect salient dynamical patterns in deeper stacked layers modeling higher orders of DoS; thus, the proposed LSTM model is termed deep differential Recurrent Neural Network ( d 2 RNN). The effectiveness of the proposed model is demonstrated on three publicly available human activity datasets: NUS-HGA, Violent-Flows, and UCF101. The proposed model outperforms both LSTM and non-LSTM based state-of-the-art algorithms.

Image description has become a popular topic in multimedia computing and computer vision areas. Recent works have demonstrated that learning the local semantic concepts, in addition to the image features, as the contextual information can help to understand the image scene better. However, current image description methods treating the local features as the bag-of-visual-words that do not capture the interaction and structure of the objects embedded in the image. In this paper, we propose a novel captioning framework that learns to integrate local concepts with their geometry structure as the side information. We design an Object Structure Graph to encode the positions and the distribution of the objects in the image. In order to embed the graph into an efficient representation, we introduce a semantic matching schema that matches our embedded graph with their corresponding sentence. Our experiments based on the public image captioning data sets, the MS-COCO and the Flickr30k, show that our improved solution is significantly better than current state-of-the-art techniques that leverage local semantic concepts; and our best model on the same splitting has competitive results compared to other recent approaches.

Cross-modal hashing has become a popular research topic in recent years due to the efficiency of storing and retrieving high-dimensional multimodal data represented by compact binary codes. While most cross-modal hash functions use binary space partitioning functions (e.g. the sign function), our method uses ranking-based hashing, which is based on numerically stable and scale-invariant rank correlation measures. In this paper, we propose a novel deep learning architecture called Deep De-correlated Subspace Ranking Hashing (DDSRH) that uses feature-ranking methods to determine the hash codes for the image and text modalities in a common hamming space. Specifically, DDSRH learns a set of de-correlated nonlinear subspaces on which to project the original features, so that the hash code can be determined by the relative ordering of projected feature values in a given optimized subspace. The network relies upon a pre-trained deep feature learning network for each modality, and a hashing network responsible for optimizing the hash codes based on the known similarity of the training image-text pairs. Our proposed method includes both architectural and mathematical techniques designed specifically for ranking-based hashing in order to achieve de-correlation between the bits, bit balancing, and quantization. Finally, through extensive experimental studies on two widely-used multimodal datasets, we show that the combination of these techniques can achieve state-of the-art performance on several benchmarks.

Integrating media elements of various medium, multimedia is capable of expressing complex information in a neat and compact way. Early studies have linked different sensory presentation in multimedia with the perception of human-like concepts. Yet, the richness of information in multimedia makes understanding and predicting user perceptions in multimedia content a challenging task both to the machine and the human mind. This paper presents a novel multi-task feature extraction method for accurate prediction of user perceptions in multimedia content. Differentiating from the conventional feature extraction algorithms which focus on perfecting a single task, the proposed model recognizes the commonality between different perceptions (e.g., interestingness and emotional impact), and attempts to jointly optimize the performance of all the tasks through uncovered commonality features. Using both a media interestingness dataset and a media emotion dataset for user perception prediction tasks, the proposed model attempts to simultaneously characterize the individualities of each task and capture the commonalities shared by both tasks, and achieves better accuracy in predictions than other competing algorithms on real-world datasets of two related tasks: MediaEval 2017 Predicting Media Interestingness Task and MediaEval 2017 Emotional Impact of Movies Task.

A user-specific model generally performs better in facial affect recognition. Existing solutions, however, have usability issues since the annotation can be long and tedious for the end users (e.g., consumers). We address this critical issue by presenting a more user-friendly user-adaptive model to make the personalized approach more practical. This paper proposes a novel user-adaptive model, which we have called fast-Personal Affect Detection with Minimal Annotation (Fast-PADMA). Fast-PADMA integrates data from multiple source subjects with a small amount of data from the target subject. Collecting this target subject data is feasible since fast-PADMA requires only one self-reported affect annotation per facial video segment. To alleviate overfitting in this context of limited individual training data, we propose an efficient bootstrapping technique, which strengthens the contribution of multiple similar source subjects. Specifically, we employ an ensemble classifier to construct pretrained weak generic classifiers from data of multiple source subjects, which is weighted according to the available data from the target user. The result is a model that does not require expensive computation, such as distribution dissimilarity calculation or model retraining. We evaluate our method with in-depth experimental evaluations on five publicly available facial datasets, with results that compare favorably with the state-of-the-art performance on classifying pain, arousal, and valence. Our findings show that fast-PADMA is effective at rapidly constructing a user-adaptive model that outperforms both its generic and user-specific counterparts. This efficient technique has the potential to significantly improve user-adaptive facial affect recognition for personal use and, therefore, enable comprehensive affect-aware applications.

Learning-based hashing has been researched extensively in the past few years due to its great potential in fast and accurate similarity search among huge volumes of multimedia data. In this article, we present a novel multimedia hashing framework, called Label Preserving Multimedia Hashing (LPMH) for multimedia similarity search. In LPMH, a general optimization method is used to learn the joint binary codes of multiple media types by explicitly preserving semantic label information. Compared with existing hashing methods which are typically developed under and thus restricted to some specific objective functions, the proposed optimization strategy is not tied to any specific loss function and can easily incorporate bit balance constraints to produce well-balanced binary codes. Specifically, our formulation leads to a set of Binary Integer Programming (BIP) problems that have exact solutions both with and without bit balance constraints. These problems can be solved extremely fast and the solution can easily scale up to large-scale datasets. In the hash function learning stage, the boosted decision trees algorithm is utilized to learn multiple media-specific hash functions that can map heterogeneous data sources into a homogeneous Hamming space for cross-media retrieval. We have comprehensively evaluated the proposed method using a range of large-scale datasets in both single-media and cross-media retrieval tasks. The experimental results demonstrate that LPMH is competitive with state-of-the-art methods in both speed and accuracy.

Human group activity recognition has drawn the attention of researchers worldwide because of the significant role it plays in many applications, including video surveillance and public security. Existing solutions for group activity recognition rely on human detection and tracking. To ensure high detection accuracy, current state-of-the-art tracking techniques require human supervision to identify objects of interest before automatic tracking can take place. This limitation has prevented existing approaches from being used in real-world applications. In scenarios when human supervision is unavailable, tracking algorithms could generate inaccurate trajectories and cause a decrease in performance for the existing group analysis methods. To address the aforementioned drawbacks, we investigate in this paper an end-to-end deep model, Differential Recurrent Convolutional Neural Networks (DRCNN). Our model consists of convolutional neural networks (CNN) and stacked differential long short-term memory (DLSTM) networks. It takes sequential raw video data as input and does not consider each group member as an individual object. Different from traditional non-end-to-end solutions which separate the steps of feature extraction and parameter learning, DRCNN utilizes a unified deep model to optimize the parameters of CNN and LSTM hand in hand. It thus has the potential of generating a more harmonious model. In addition, taking advantage of the semantic representation of CNN and the memory states of DLSTM, DRCNN has strong capabilities in understanding complex scene semantics and group dynamics. Extensive experimental studies indicate that the proposed technique can accomplish the task of fully automatic group activity recognition without sacrificing performance, and even outperforms the human-aided state-of-the- art methods on two benchmark group activity datasets. To the best of our knowledge, this is the first end-to-end group activity recognition technique ever proposed.

In high-dimensional kNN search, both exact and approximate kNN solutions incur considerable time in the candidate refinement phase. In this paper, we investigate a caching solution to reduce the candidate refinement time. Our caching method HC-O is faster than EXACT caching by at least an order of magnitude, on an approximate index (C2LSH). Our work is also applicable to exact indexes (e.g., iDistance, VPtree and VA-file).

With the growth of crowd phenomena in the real world, crowd scene understanding is becoming an important task in anomaly detection and public security. Visual ambiguities and occlusions, high density, low mobility and scene semantics, however, make this problem a great challenge. In this paper, we propose an end-to-end deep architecture, Convolutional DLSTM (ConvDLSTM), for crowd scene understanding. ConvDLSTM consists of GoogleNet Inception V3 convolutional neural networks (CNN) and stacked differential long short-term memory (DLSTM) networks. Different from traditional non-end-to-end solutions which separate the steps of feature extraction and parameter learning, ConvDLSTM utilizes a unified deep model to optimize the parameters of CNN and RNN hand in hand. It thus has the potential of generating a more harmonious model. The proposed architecture takes sequential raw image data as input, and does not rely on tracklet or trajectory detection. It thus has clear advantages over the traditional flow-based and trajectory-based methods, especially in challenging crowd scenarios of high density and low mobility. Taking advantage of the semantic representation of CNN and the memory states of LSTM, ConvDLSTM can effectively analyze both the crowd scene and motion information. Existing LSTM-based crowd scene solutions explore deep temporal information and are claimed to be "deep in time". ConvDLSTM, however, models the spatial and temporal information in a unified architecture and achieves "deep in space and time". Extensive performance studies on the Violent-Flows and CUHK Crowd datasets show that the proposed technique significantly outperforms state-of-the-art methods.

Media interestingness prediction plays an important role in many real-world applications and attracts much research attention recently. In this paper, we aim to investigate this problem from the perspective of supervised feature extraction. Specifically, we design a novel algorithm dubbed Multi-view Manifold Learning (M) to uncover the latent factors that are capable of distinguishing interesting media data from non-interesting ones. By modelling both geometry preserving criterion and discrimination maximization criterion in a unified framework, M2L learns a common subspace for data from multiple views. The analytical solution of M2L is obtained by solving a generalized eigen-decomposition problem. Experiments on the Predicting Media Interestingness Dataset validate the effectiveness of the proposed method.

We present COMMIT (Collaborative MultiMedia Interactive Table), a collaborative multimedia environment for remote group interaction. COMMIT enables collaboration among people at different locations by allowing them to not only share multimedia objects such as images, PDFs and videos, but also co-operate on these cyber objects. COMMIT is also motivated by the emerging Internet of Things (IoT), and provides a team-thing interface which supports the sharing of data streams from physical IoT objects, such as IP cameras. It enables collaborators to more effectively exploit huge volumes of valuable IoT data. COMMIT has been evaluated using real-life scenarios with random users. Feedback from our user study shows that COMMIT is intuitive and can aid group interactions in collaborative tasks requiring the Internet of Things.

Video content makes up more than half of the world's Internet traffic, and this figure is expected to grow rapidly. New techniques that remove traffic redundancy have been shown to significantly improve network performance since many concurrent streams deliver the same video. These techniques employ smart routers that recognize duplicated video streams and merge them to reduce traffic redundancy. Routers deployed over an ISP's network or Internet backbone capture the video traffic and convey it into the overlay. Overlapping streams are merged into each other in link-level by receiving the packet only for the first stream, and re-using it for the subsequent duplicated streams. In this paper, we significantly improve these techniques by introducing a merger-aware routing method. The conventional wisdom is that traffic congestion is bad and routing techniques should be designed to prevent congestion. Video access patterns, however, follow the 80:20 rule; i.e., many video requests are for the same videos. The proposed routing technique leverages this characteristic of streaming traffic. It plans strategic network congestion to increase the opportunity for traffic merging. Although it sounds counter-intuitive to improve network performance by introducing network congestion, we show that creating momentary congestion is indeed an effective solution to reduce network congestion. We introduce a new kind of overlay network, called the Deduplication Overlay Network (DON), to reduce traffic for the underlying network. In DON, redundancy is maximized in link-level by the new routing technique. In order to compute the optimal network path for a new stream, the overall delay of packet transfers in DON is modeled by taking merging streams into consideration. The cost minimization is reduced down to the shortest path problem for efficient computation. The proposed method is implemented on a network simulator and the redundancy elimination performance is compared with an alternative overlay solution based on a recent stream merging technique. Experiments under various workloads and overlay network densities show significantly less traffic over the alternative.

Hashing has attracted a great deal of research in recent years due to its effectiveness for the retrieval and indexing of large-scale high-dimensional multimedia data. In this paper, we propose a novel ranking-based hashing framework that maps data from different modalities into a common Hamming space where the cross-modal similarity can be measured using Hamming distance. Unlike existing cross-modal hashing algorithms where the learned hash functions are binary space partitioning functions, such as the sign and threshold function, the proposed hashing scheme takes advantage of a new class of hash functions closely related to rank correlation measures which are known to be scale-invariant, numerically stable, and highly nonlinear. Specifically, we jointly learn two groups of linear subspaces, one for each modality, so that features' ranking orders in different linear subspaces maximally preserve the cross-modal similarities. We show that the ranking-based hash function has a natural probabilistic approximation which transforms the original highly discontinuous optimization problem into one that can be efficiently solved using simple gradient descent algorithms. The proposed hashing framework is also flexible in the sense that the optimization procedures are not tied up to any specific form of loss function, which is typical for existing cross-modal hashing methods, but rather we can flexibly accommodate different loss functions with minimal changes to the learning steps. We demonstrate through extensive experiments on four widely-used real-world multimodal datasets that the proposed cross-modal hashing method can achieve competitive performance against several state-of-the-arts with only moderate training and testing time.

We study a nearest neighbor search problem on a matrix by its element values. Given a data matrix D and a query matrix q, the sub-window nearest neighbor search problem finds a sub-window of D that is the most similar to q. This problem has a wide range of applications, e.g., geospatial data integration, object detection, and motion estimation. In this paper, we propose an efficient progressive search solution that overcomes the drawbacks of existing solutions. First, we present a generic approach to build level based lower bound functions on top of basic lower bound functions. Second, we develop a novel lower bound function for a group of sub-windows, in order to boost the efficiency of our solution. Furthermore, we extend our solution to support irregular-shaped queries. Experimental results on real data demonstrate the efficiency of our proposed methods.

From wearable devices to depth cameras, researchers have exploited various multimodal data to recognize human actions for applications, such as video gaming, education, and healthcare. Although there many successful techniques have been presented in the literature, most current approaches have focused on statistical or local spatiotemporal features and do not explicitly explore the temporal dynamics of the sensor data. However, human action data contain rich temporal structure information that can characterize the unique underlying patterns of different action categories. From this perspective, we propose a novel temporal order modeling approach to human action recognition. Specifically, we explore subspace projections to extract the latent temporal patterns from different human action sequences. The temporal order between these patterns are compared, and the index of the pattern that appears first is used to encode the entire sequence. This process is repeated multiple times and produces a compact feature vector representing the temporal dynamics of the sequence. Human action recognition can then be efficiently solved by the nearest neighbor search based on the Hamming distance between these compact feature vectors. We further introduce a sequential optimization algorithm to learn the optimized projections that preserve the pairwise label similarity of the action sequences. Experimental results on two public human action datasets demonstrate the superior performance of the proposed technique in both accuracy and efficiency.

Hashing has been widely used for approximate nearest neighbor search of high-dimensional multimedia data. In this paper, we propose a novel hash learning framework that maps high-dimensional multimodal data into a common Hamming space where the cross-modal similarity can be measured using Hamming distance. Unlike existing cross-modal hashing methods that learn hash functions in the form of numeric quantization of linear projections, the proposed hash learning algorithm encodes features' ranking properties and takes advantage of rank correlations which are known to be scale-invariant, numerically stable and highly nonlinear. Specifically, we learn two groups of subspaces jointly, one for each modality, so that the ranking orders in those subspaces maximally preserve the cross-modal similarity. Extensive experiments on realworld datasets demonstrate superiority of the proposed methods compared to state-of-the-arts.

Although Query-by-Example techniques based on Euclidean distance in a multidimensional feature space have proved to be effective for image databases, this approach cannot be effectively applied to video since the number of dimensions would be massive due to the richness and complexity of video data. The above issue has been addressed in two recent solutions, namely Deterministic Quantization (DQ) and Dynamic Temporal Quantization (DTQ). DQ divides the video into equal segments and extracts a visual feature vector for each segment. The bag-of-word feature is then encoded by hashing to facilitate approximate nearest neighbor search using Hamming distance. One weakness of this approach is the deterministic segmentation of video data. DTQ improves on this by using dynamic video segmentation to obtain varied-length video segments. As a result, feature vectors extracted from these video segments can better capture the semantic content of the video. To support very large video databases, it is desirable to minimize the number of segments in order to keep the size of the feature representation as small as possible. We achieve this by using only one video segment (i.e., no video data segmentation is even necessary) with even better retrieval performance. Our scheme models video using differential long short-term memory (DLSTM) recurrent neural networks and obtains a highly compact fixed-size feature representation with the output of hidden states of the DLSTM. Each of these features are further compressed by hashing them into binary bits via quantization. Experimental results based on two public data sets, UCF101 and MSRActionPairs, indicate that the proposed video modeling technique outperforms DTQ by a significant margin.

The era of big data has spawned unprecedented interests in developing hashing algorithms for their storage efficiency and effectiveness in fast nearest neighbor search in large-scale databases. Most of the existing hash learning algorithms focus on learning hash functions which generate binary codes by numeric quantization of some projected feature space. In this work, we propose a novel hash learning framework that encodes features' ranking orders instead of quantizing their numeric values in a number of optimal low-dimensional ranking subspaces. We formulate the ranking-based hash learning problem as the optimization of a continuous probabilistic error function using softmax approximation and present an efficient learning algorithm to solve the problem. We extensively evaluate the proposed algorithm in several datasets and demonstrate superior performance against several state-of-the-arts.

Pictures and videos from social events and gatherings usually contain multiple people. Physiological and behavioral science studies indicate that there are strong emotional connections among group members. These emotional relations among group members are indispensable to better analyzing individual emotions in a group. However, most of the existing affective computing methods focus on estimating the emotion of a single object only. In this work, we concentrate on estimating happiness intensities of group members while considering the reciprocities among them. We propose a novel facial descriptor that effectively captures happiness related facial action units. We also introduce two different structural regression models, Continuous Conditional Random Fields (CCRF) and Continuous Conditional Neural Fields (CCNF), for estimating emotions of group members. Our experimental results on HAPPEI dataset demonstrate the viability of proposed features and the two frameworks.

This paper presents Personalized Affect Detection with Minimal Annotation (PADMA), a user-dependent approach for identifying affective states from spontaneous facial expressions without the need for expert annotation. The conventional approach relies on the use of key frames in recorded affect sequences and requires an expert observer to identify and annotate the frames. It is susceptible to user variability and accommodating individual differences is difficult. The alternative is a user-dependent approach, but it would be prohibitively expensive to collect and annotate data for each user. PADMA uses a novel Association-based Multiple Instance Learning (AMIL) method, which learns a personal facial affect model through expression frequency analysis, and does not need expert input or frame-based annotation. PADMA involves a training/calibration phase in which the user watches short video segments and reports the affect that best describes his/her overall feeling throughout the segment. The most indicative facial gestures are identified and extracted from the facial response video, and the association between gesture and affect labels is determined by the distribution of the gesture over all reported affects. Hence both the geometric deformation and distribution of key facial gestures are specially adapted for each user. We show results that demonstrate the feasibility, effectiveness and extensibility of our approach.

High-dimensional$k$nearest neighbor (kNN) search has a wide range of applications in multimedia information retrieval. Existing disk-based$k$NN search methods incur significant I/O costs in the candidate refinement phase. In this paper, we propose to cache compact approximate representations of data points in main memory in order to reduce the candidate refinement time during$k$NN search. This problem raises two challenging issues: (i) which is the most effective encoding scheme for data points to support$k$NN search? and (ii) what is the optimal number of bits for encoding a data point? For (i), we formulate and solve a novel histogram optimization problem that decides the most effective encoding scheme. For (ii), we develop a cost model for automatically tuning the optimal number of bits for encoding points. In addition, our approach is generic and applicable to exact / approximate$k$NN search methods. Extensive experimental results on real datasets demonstrate that our proposal can accelerate the candidate refinement time of$k$NN search by at least an order of magnitude.

Image recognition with incomplete data is a well-known hard problem in computer vision and machine learning. This article proposes a novel deep learning technique called Field Effect Bilinear Deep Networks (FEBDN) for this problem. To address the difficulties of recognizing incomplete data, we design a novel second-order deep architecture with the Field Effect Restricted Boltzmann Machine, which models the reliability of the delivered information according to the availability of the features. Based on this new architecture, we propose a new three-stage learning procedure with field effect bilinear initialization, field effect abstraction and estimation, and global fine-tuning with missing features adjustment. By integrating the reliability of features into the new learning procedure, the proposed FEBDN can jointly determine the classification boundary and estimate the missing features. FEBDN has demonstrated impressive performance on recognition and estimation tasks in various standard datasets.

Statistics show that 79% of the Internet traffic is video and mostly “redundant”. Video-On-Demand in particular follows a 90/10 access pattern, where 90% of the users access the same 10% of all video content. As a result, redundant data are repeatedly transmitted over the Internet. In this paper, we propose a novel traffic deduplication technique to achieve more efficient network communication between video sources (video servers or proxy servers in a CDN) and clients. The proposed SMART (Small packet Merge-Able RouTers) overlay network employs an opportunistic traffic deduplication approach and allows each SMART router to dynamically merge independent streams of the same video content, forming a video streaming tree (VST). The merged streams are tunneled through the overlay together with TCP sessions information before eventually being de-multiplexed and delivered to the clients fully compatible with the TCP protocol. We present theoretical analysis findings on the merging strategy between the video source and clients, the efficiency of the SMART router to save traffic during a merge process, and the overall performance of implementing a SMART overlay topology between a video source and clients. Finally, we prototyped SMART in the PlanetLab environment. We illustrate that performance evaluation results are consistent with our theoretical analysis and significant bandwidth saving is achieved.

With the prevalence of the commodity depth sensors (e.g. Kinect), multimodal data including RGB stream, depth stream and audio stream have been utilized in various applications such as video games, education and health. Nevertheless, it is still very challenging to effectively fuse the features from multimodal data. In this paper, we propose a WTA (Winner-Take-All) Hash-based feature fusion algorithm and investigate its application in 3D human action recognition. Specifically, the WTA Hashing is performed to encode features from different modalities into the ordinal space. By leveraging the ordinal measures rather than using the absolute value of the original features, such feature embedding can provide a form of resilience to the scale and numerical perturbations. We propose a frame-level feature fusion algorithm and develop a WTA Hash-embedded warping algorithm to measure the similarity between two sequences. Experiments performed on three public 3D human action datasets show that the proposed fusion algorithm has achieved state-of-the-art recognition results even with the nearest neighbor search.

Recent commodity depth cameras have been widely used in the applications of video games, business, surveillance and have dramatically changed the way of human-computer interaction. They provide rich multimodal information that can be used to interpret the human-centric environment. However, it is still of great challenge to model the temporal dynamics of the human actions and great potential can be exploited to further enhance the retrieval accuracy by adequately modeling the patterns of these actions. To address this challenge, we propose a temporal order-preserving dynamic quantization method to extract the most discriminative patterns of the action sequence. We further present a multimodal feature fusion method that can be derived in this dynamic quantization framework to exploit different discriminative capability of features from multiple modalities. Experiments based on three public human action datasets show that the proposed technique has achieved state-of-the-art performance.

Music can convey and evoke powerful emotions. This amazing ability has not only fascinated the general public but also attracted the researchers from different fields to discover the relationship between music and emotion. Psychologists have indicated that some specific characters of rhythm, harmony, and melody can evoke certain kinds of emotions. Those hypotheses are based on real life experience and proved by psychological paradigms on human beings. Aiming at the same target, this paper intends to design a systematic and quantitative framework, and answer three widely interested questions: 1) what are the intrinsic features embedded in music signal that essentially evoke human emotions; 2) to what extent these features influence human emotions; and 3) whether the findings from computational models are consistent with the existing research results from psychology. We formulate these tasks as a multi-label dimensionality reduction problem and propose an algorithm called multi-emotion similarity preserving embedding (ME-SPE). To adapt to the second-order music signals, we extend ME-SPE to its bilinear version. The proposed techniques show good performance in two standard music emotion datasets. Moreover, they demonstrate some interesting results for further research in this interdisciplinary topic.

As computer and interaction technologies mature, a much broader range of media is now used for input and output, each of which has its own rich repertoire of techniques, instruments, and cultural heritage. The combination of multiple media can produce novel multimedia human-computer interaction approaches which are more efficient and interesting than traditional single media methods. This paper presents CalliPaint, a system for cross-modal art generation that links together Chinese ink brush calligraphy writing and Chinese landscape painting. We investigate the mapping between the two modalities based on concepts of metaphoric congruence, and implement our findings into a prototype system. A multi-step evaluation experiment with real users suggests that CalliPaint provides a realistic and intuitive experience that allows even novice users to create attractive landscape paintings from writing. Comparison with a general-purpose digital painting software suggests that CalliPaint provides users with a more enjoyable experience. Finally, exhibiting CalliPaint in an open-access location for use by casual users without any training shows that the system is easy to learn.

In this paper, we investigate techniques to localize the sound source in video made using one microphone. The visual object whose motion generates the sound is located and segmented based on the synchronization analysis of object motion and audio energy. We first apply an effective region tracking algorithm to segment the video into a number of spatial-temporal region tracks, each representing the temporal evolution of an appearance-coherent image structure (i.e., object). We then extract the motion features of each object as its average acceleration in each frame. Meanwhile, Short-term Fourier Transform is applied to the audio signal to extract audio energy feature as the audio descriptor. We further impose a nonlinear transformation on both audio and visual descriptors to obtain the audio and visual codes in a common rank correlation space. Finally, the correlation between an object and the audio signal is simply evaluated by computing the Hamming distance between the audio and visual codes generated in previous steps. We evaluate the proposed method both qualitatively and quantitatively using a number of challenging test videos. In particular, the proposed method is compared with a state-of-the-art audiovisual source localization algorithm. The results demonstrate the superior performance of the proposed algorithm in spatial-temporal localization and segmentation of audio sources in the visual domain.correlation space. Finally, the correlation between an object and the audio signal is simply evaluated by computing the Hamming distance between the audio and visual codes generated in previous steps. We evaluate the proposed method both qualitatively and quantitatively using a number of challenging test videos. In particular, the proposed method is compared with a state-of-the-art audiovisual source localization algorithm. The results demonstrate the superior performance of the proposed algorithm in spatial-temporal localization and segmentation of audio sources in the visual domain.

Music can convey and evoke powerful emotions. This amazing ability has fascinated the general public and also attracted the researchers from different fields to discover the relationship between music and emotion. Psychologists have indicated that some specific characters of rhythm, harmony, melody, and also their combinations can evoke certain kinds of emotions. Their hypotheses are based on real life experience and proved by psychological paradigms on human beings. Aiming at the same target, this paper intends to design a systematic and quantitative framework, and answer three widely interested questions: 1) what are the intrinsic features embedded in music signal that essentially evoke human emotions; 2) to what extent these features influence human emotions; and 3) whether the findings from computational models are consistent with the existing research results from psychological experiments. We formulate the problem as a multi-label dimensionality reduction problem and provide the optimal solution. The proposed multi-emotion similarity preserving embedding technique not only shows better performance in two standard music emotion datasets but also demonstrates some interesting observations for further research in this interdisciplinary topic.

Mobile ad hoc networks (MANETs) are ideal for situations where a fixed infrastructure is unavailable or infeasible. Today's MANETs, however, may suffer from network partitioning. This limitation makes MANETs unsuitable for applications such as crisis management and battlefield communications, in which team members might need to work in groups scattered in the application terrain. In such applications, intergroup communication is crucial to the team collaboration. To address this weakness, we introduce in this paper a new class of ad-hoc network called Autonomous Mobile Mesh Network (AMMNET). Unlike conventional mesh networks, the mobile mesh nodes of an AMMNET are capable of following the mesh clients in the application terrain, and organizing themselves into a suitable network topology to ensure good connectivity for both intra- and intergroup communications. We propose a distributed client tracking solution to deal with the dynamic nature of client mobility, and present techniques for dynamic topology adaptation in accordance with the mobility pattern of the clients. Our simulation results indicate that AMMNET is robust against network partitioning and capable of providing high relay throughput for the mobile clients.

In this brief, we present a novel supervised manifold learning framework dubbed hybrid manifold embedding (HyME). Unlike most of the existing supervised manifold learning algorithms that give linear explicit mapping functions, the HyME aims to provide a more general nonlinear explicit mapping function by performing a two-layer learning procedure. In the first layer, a new clustering strategy called geodesic clustering is proposed to divide the original data set into several subsets with minimum nonlinearity. In the second layer, a supervised dimensionality reduction scheme called locally conjugate discriminant projection is performed on each subset for maximizing the discriminant information and minimizing the dimension redundancy simultaneously in the reduced low-dimensional space. By integrating these two layers in a unified mapping function, a supervised manifold embedding framework is established to describe both global and local manifold structure as well as to preserve the discriminative ability in the learned subspace. Experiments on various data sets validate the effectiveness of the proposed method.

Live video computing (LVC) on distributed smart cameras has many important applications; and a database approach based on a Live Video DataBase Management System (LVDBMS) has shown to be effective for general LVC application development. The performance of such a database system relies on accurate interpretation of spatial relationships among objects in the live video. With the popularity of affordable depth cameras, 3D spatial computation techniques have been applied. However, the 3D object models currently used are expensive to compute, and offer limited scalability. We address this drawback in this article by proposing an octree-based 3D spatial logic and presenting algorithms for computing 3D spatial relationships using depth cameras. To support continuous query processing on live video streams, we also develop a GPU-based implementation of the proposed technique to further enhance scalability for real-time applications. Extensive performance studies based on a public RGB-D dataset as well as the LVDBMS prototype demonstrates the correctness and efficiency of our techniques.

Clustering proves to be an effective approach to reduce energy consumption of micro-sensors and prolong the lifetime of wireless sensor networks. In this paper, we address the sensor clustering problem in the design of an autonomous MANET (aMANET) for energy-efficient data collection in wireless sensor networks. In the aMANET context, we formulate the network energy optimization as a weighted K-means clustering problem, and present a distributed technique called MADSEC (Mobility-Assisted Distributed SEnsor Clustering) for sensor clustering and data collection. MADSEC allows the mobile nodes to dynamically run a distributed clustering algorithm to reposition themselves and organize energy-efficient sensor clusters. Extensive NS-2 simulation results indicate that the proposed distributed clustering strategy is as effective as a theoretical centralized K-means clustering technique. Furthermore, MADSEC can at least double the network lifetime of LEACH, a well-known static clustering method.

Interpretation of spatial relations between objects is essential to many applications such as robotics, video surveillance, spatial reasoning, and scene understanding. Current models for spatial logic are two-dimensional. With the advance in new sensing technology, inexpensive depth sensors become widely available and 3D scene reconstruction can be applied in various application scenarios. In this paper, we propose a 3D spatial logic and algorithms for interpretation of spatial relationships among objects in 3D space. More specifically, these techniques are developed for LVDBMS (Live Video DataBase Management System), a generic platform for live video computing. We extend the original directional relationships into 3D directional relationships, and introduce a simple yet effective way to build 3D object models based on depth sensors. A highly accurate and efficient algorithm is also proposed to compute the spatial relationships between two objects by sampling the entire space from the reference object. Experimental results based on a real indoor scene and an RGB-D dataset are given to demonstrate the effectiveness of our techniques.

Video streaming is the core technology for online video delivery systems. Initial research on this technology faced many challenges. In this article, lessons learned from beginning trials are discussed; some pioneering works that provided early solutions and inspired subsequent research are presented; and new techniques required for emerging applications are examined.

Location-based applications are becoming increasingly popular due to the wide spread of global positioning devices. One major concern in location-based applications is how to protect user privacy. A typical solution consists of three tiers: mobile users, trusted anonymizer, and service provider. The trusted anonymizer first needs to cloak the queries received from mobile users, then sends the cloaked queries to the service provider. The service provider then answers the cloaked query, which is a challenge if the underlying environment is a road network. In this paper, we propose to use Road Network Embedding (RNE) to answer cloaked queries in a road network environment. We first give an algorithm to answer k-nearest neighbor queries, then extend the algorithm to answer range queries and queries over private objects. Extensive simulation studies are preformed to show the effectiveness of the proposed technique.

In recent years, there has been a dramatic increase in the number of users who access online videos from wireless access networks. It is highly desirable that such wireless networks be robust in handling sudden spurts in demand for certain videos due to occurrences like special events. An abrupt increase in network usage should not significantly impact normal access to other regular videos or other day-to-day applications in a well-designed system. In this paper, we tackle this problem in wireless mesh access networks by proposing a distributed video sharing technique called Dynamic Stream Merging for Access Networks (DSMAN). DSMAN improves the robustness of the access network without requiring directives from the video servers. In fact, it optimizes the video transport independent of video server participation/knowledge. We present a wireless mesh network prototype based on DSMAN. Our experimental results, based on the mobile YouTube website as the video source, validate the correctness of DSMAN and demonstrate the feasibility of the proposed technique.

Supporting high mobility is essential to mobile ad hoc networks in a wide range of emerging applications such as vehicular networks. Communication links of an established communication path that extends between source and destination nodes are often broken under a high mobility environment. Although a new communication route can be established when a break in the communication path occurs, repeatedly reestablishing new routes incurs delay and substantial overhead. To address this limitation, we introduce the Communication Path abstraction in this paper. A communication path is a dynamically-created geographical area that connects the source and destination nodes. The routing functionality of a communication path is provided by the physical nodes (i.e., mobile devices) currently within the geographical region served by the path. These physical nodes take turns in forwarding data packets for the path. Since a path can be supported by many alternative nodes, this scheme is much less susceptible to node mobility. Our simulation results show the Communication Path approach can achieve several times better performance than traditional approach based on a fixed sequence of physical links.

Abstract In this work, we study two cross‐layer techniques, the Patching‐based scheme (PS) and the Caching‐based scheme (CS), to provide video‐on‐demand (VoD) in the multi‐hop WiMax mesh networks. PS consists of an efficient and lightweight multicast routing technique as well as the Patching technique in the application layer. Although PS improves the scalability of the system, the server has to launch extra Patching streams for later users in the multicast group. CS caches the video content in the subscribe stations of the mesh network. The cached video data can be used to accommodate later request. Both approaches employ a novel joint solution of admission control and channel scheduling for video streams in the lower layer. This joint solution guarantees the data rate for the admitted video streams, which is crucial for real‐time video streaming application. We used simulation to study the performance of PS and CS under real system settings. Copyright © 2010 John Wiley & Sons, Ltd.

User Relevance feedback techniques based on learning methods such as Artificial Neural Networks and kernel machines have been widely used in content-based image retrieval. However, the traditional relevance feedback framework for existing techniques still suffers from: (1) high learning cost incurs substantial delay in responding to user relevance feedback, (2) the classifiers may be biased when the negative feedback samples out-number the positive feedback samples, and (3) The high feature dimensions compared to the size of the training set causes over fitting. We propose a new relevance feedback approach based on a lazy processing framework. This approach combines random sampling, data clustering, and ensembles of classifiers to address the aforementioned problems. Our experimental studies show that the proposed framework provides a responsive user feedback environment that is capable of outperforming the traditional approach.

Vehicular Ad-Hoc Network (VANET) has been one of the most transforming technologies for Intelligent Transportation Systems (ITS) in recent years. In particular, wireless mesh network is widely used for VANETs due to its scalability, flexibility, and low maintenance cost. When a mesh node fails, one can simply replace it with a new mesh node, and the network automatically reconfigures itself. However, due to the environment or limited resources, it may not be feasible to replace the failed node immediately. In this work, we introduce a resilient VANET that can effectively retain the coverage and capacity of the original network until the failed mesh nodes can be repaired or replaced. We give simulation results to show that this desirable property can be achieved using a virtual router concept with minimal overhead.

Querying in the context of moving objects environments has been largely studied. Extensive research effort has also been dedicated to exploring different techniques of handling uncertainty, an issue intrinsic to the nature of node mobility. Current trends in moving object database-related applications impose the need to consider uncertainty from different perspectives. In this paper, we examine the case in which the exact locations of moving objects are never reported to the central database server. Instead, deductions about the objects positions are based on data gathered from the readings of mobile sensors. With this arrangement in mind, we introduce and study approximate rank queries, where a mobile object is in the answer set of a query with probability p and is assigned a rank with probability P. The rank reflects the objects approximate distance from the query point. Queries are evaluated based on different pruning techniques and ranking heuristics. Our work is backed with an extensive simulation study, which examines the effectiveness of the algorithm with varied numbers of mobile sensors and objects.

We propose a Dynamic Stream Merging (DSM) technique for efficient video-on-demand services to mobile users on wireless mesh networks at the edges. DSM is a new communication paradigm, in which multicast topologies are created incrementally through dynamic merging of server streams at the mesh nodes. This is accomplished without the knowledge of the server. The formation of the multicast group in this manner is fundamentally different from traditional multicast techniques which rely on centralized control at the server. We present a system prototype and give experimental results to demonstrate the feasibility of this new approach. We also give simulation results based on the NS-2 simulator to show the performance efficiency in a larger system setting.

This paper examines major privacy concerns in location-based services. Most user privacy techniques are based on cloaking, which achieves location k-anonymity. The key is to reduce location resolution by ensuring that each cloaking area reported to a service provider contains at least k mobile users. However, maintaining location k-anonymity alone is inadequate when the majority of the k mobile users are interested in the same query subject. In this paper, the authors address this problem by defining a novel concept called query l-diversity, which requires diversified queries submitted from the k users. The authors propose two techniques: Expand Cloak and Hilbert Cloak to achieve query l-diversity. To show the effectiveness of the proposed techniques, they compare the improved Interval Cloak technique through extensive simulation studies. The results show that these techniques better protect user privacy.

Support vector machines (SVMs) have been widely used in multimedia retrieval to learn a concept in order to find the best matches. In such a SVM active learning environment, the system first processes k sampling queries and top-k uncertain queries to select the candidate data items for training. The user's top-k relevant queries are then evaluated to compute the answer. This approach has shown to be effective. However, it suffers from the scalability problem associated with larger database sizes. To address this limitation, we propose an incremental query evaluation technique for these three types of queries. Based on the observation that most queries are not revised dramatically during the iterative evaluation, the proposed technique reuses the results of previous queries to reduce the computation cost. Furthermore, this technique takes advantage of a tuned index structure to efficiently prune irrelevant data. As a result, only a small portion of the data set needs to be accessed for query processing. This index structure also provides an inexpensive means to process the set of candidates to evaluate the final query result. This technique can work with different kernel functions and kernel parameters. Our experimental results indicate that the proposed technique significantly reduces the overall computation cost, and offers a promising solution to the scalability issue.

Video-on-demand service in wireless networks is one important step to achieving the goal of providing video services anywhere anytime. Typically, carrier mobile networks are used to deliver videos wirelessly. Since every video stream comes from the base station, regardless of what bandwidth sharing techniques are being utilized, the media stream system is still limited by the network capacity of the base station. The key to overcome the scalability issue is to exploit resources available to mobile clients in a peer-to-peer setting. We observe that it is common to have a carrier mobile network and a mobile peer-to-peer network co-existing in a wireless environment. A feature of such hybrid environment is that the former offers high availability assurance, while the latter presents an opportunistic use of resources available at mobile clients. Our proposed video-on-demand technique, PatchPeer, leverages this network characteristic to allow the video-on-demand system to scale beyond the bandwidth capacity of the server. Mobile clients in PatchPeer are no longer passive receivers, but also active senders of video streams to other mobile clients. Our extensive performance study shows that PatchPeer can accept more clients than the current state-of-the-art technique, while maintaining the same quality-of-service to clients.

We consider the problem of supporting continuous spatial queries in a new and challenging network environment, namely a Mobile Peer-To-Peer (MP2P) network. Specifically, we propose a distributed technique, called ExtRange, that can efficiently answer continuous moving range queries in a MP2P network. The two key ideas in ExtRange are extended range and safe period. For each query, ExtRange extends the query monitoring region beyond the query range to ensure the accuracy of the query result under the dynamic condition of mobile nodes. Additionally, for each query it monitors, a mobile node computesa safe period, during which the mobile node does not have to update its location with the query node. Through analytical study, we prove that ExtRange guarantees the accuracy for query results when network communication is perfect. Using extensive simulation study, we show that ExtRange delivers high accuracy for query results with low associated costs under realistic simulation settings.

Most existing cloaking techniques only focus on achieving location k-anonymity. However, maintaining location k-anonymity alone is not enough to counter query homogeneity attacks. In this paper, we first define the query l-diversity concept in location-based services, and then propose a technique to achieve query l-diversity. The proposed technique is compared with the improved Interval Cloak technique using simulation; and the extensive results indicate that our technique is better in protecting user privacy.

A Location-based Service has to protect user's location and query information to alleviate privacy concerns. Several location and query privacy preserving approaches, based on the concept of k-anonymity and l-diversity, have been proposed in the literature. These approaches assume a trusted anonymizer. Caching has been used as the trusted anonymizer to save communication and computation cost and to enhance the privacy of snapshot and continuous user queries. Such cache designs only provide privacy up to a certain limit and are not designed for multiple points of interest (POI) type queries. We propose a novel cache design and a cache event model that provides significantly higher levels of privacy. We also propose a novel privacy preserving metric which measures the privacy offered by different components (caching, k-anonymity, l-diversity) of the anonymizer which is to the best of our knowledge the first comprehensive privacy measuring metric. We perform several experiments on real world data to evaluate the effectiveness of our cache design in terms of privacy enhancements, computation and communication costs.

Similarity search is widely used in multimedia retrieval systems to find the most similar ones for a given object. Some similarity measures, however, are not metric, leading to existing metric index structures cannot be directly used. To address this issue, we propose a simulated-annealing-based technique to derive optimized mapping functions that transfer non-metric measures into metric, and still preserve the original similarity orderings. Then existing metric index structures can be used to speed up similarity search by exploiting the triangular inequality property. The experimental study confirms the efficacy of our approach.

Target search in content-based image retrieval (CBIR) systems refers to finding a specific (target) image such as a particular registered logo or a specific historical photograph. Existing techniques, designed around query refinement based on relevance feedback, suffer from slow convergence, and do not guarantee to find intended targets. To address these limitations, we propose several efficient query point movement methods. We prove that our approach is able to reach any given target image with fewer iterations in the worst and average cases. We propose a new index structure and query processing technique to improve retrieval effectiveness and efficiency. We also consider strategies to minimize the effects of users' inaccurate relevance feedback. Extensive experiments in simulated and realistic environments show that our approach significantly reduces the number of required iterations and improves overall retrieval performance. The experimental results also confirm that our approach can always retrieve intended targets even with poor selection of initial query points.

In this paper, a semi-automatic segmentation technique for brain mass-like lesions in magnetic resonance (MR) image sequences is proposed. With the graphical user interface of ImageJ, the user can interactively determine the lesion volume. The user needs to only provide the tumor contour on one MR slice using LiveWire, after which the system automatically segments and determines the gross lesion volume. Our experimental results, based on MR image sequences from Prasat Neurological Institute, indicate that the proposed system is effective.

Image clustering is to derive a salient grouping of images such that similar ones are placed in the same cluster, which is useful in many applications. In this paper, we propose a constrained clustering algorithm, which leverages the collected user query log to guide the clustering process. Our method models a set of images as a graph and randomly contracts two vertices into a meta vertex iteratively with regarding to their similarity until the desired number of image groups has been reached. The experimental results demonstrate the superiority of our proposal.

Nowadays’ image retrieval techniques focus on modifying a query contour based on the relative correlations of relevant images. The spatial relationship between the relevant images and all the other images in database (i.e. the directional information) is not explored and utilized well. From the aspect of feature space, when a user selects relevant images, the direction to the potential relevant images is implicitly expressed. In this paper, we propose a Dynamic Directional Navigation (DDN) system to explore the directional information and navigate in the data space to find similar images. Multiple queries will be used when the relevant images point to different directions. The experiment results indicate that our technique can address the semantic gap well in Content-Based Image Retrieval (CBIR) and achieves better precision and recall than the previous techniques.

Moving monitoring query on moving objects is an important type of query in location based services. Existing solutions suffer from high communication cost. In this paper, we propose a distributed solution to this problem. Our approach employs two ways of communications, on-demand access and broadcast channel, to reduce communication cost. Two different indexes are proposed and evaluated using simulations. The performance results indicate that our solution achieves from 30% to 60% savings in communications when compared to MobiEyes [2].

Data clustering is a difficult problem due to the complex and heterogeneous natures of multidimensional data. To improve clustering accuracy, we propose a scheme to capture the local correlation structures: associate each cluster with an independent weighting vector and embed it in the subspace spanned by an adaptive combination of the dimensions. Our clustering algorithm takes advantage of the known pairwise instance-level constraints. The data points in the constraint set are divided into groups through inference; and each group is assigned to the feasible cluster which minimizes the sum of squared distances between all the points in the group and the corresponding centroid. Our theoretical analysis shows that the probability of points being assigned to the correct clusters is much higher by the new algorithm, compared to the conventional methods. This is confirmed by our experimental results, indicating that our design indeed produces clusters which are closer to the ground truth than clusters created by the current state-of-the-art algorithms.

With the advances in medical imaging devices, large volumes of high-resolution 3-D medical image data have been produced. These high-resolution 3-D data are very large in size, and severely stress storage systems and networks. Most existing Internet-based 3-D medical image interactive applications therefore deal with only low- or medium-resolution image data. While it is possible to download the whole 3-D high-resolution image data from the server and perform the image visualization and analysis at the client site, such an alternative is infeasible when the high-resolution data are very large, and many users concurrently access the server. In this paper, we propose a novel framework for Internet-based interactive applications of high-resolution 3-D medical image data. Specifically, we first partition the whole 3-D data into buckets, remove the duplicate buckets, and then, compress each bucket separately. We also propose an index structure for these buckets to efficiently support typical queries such as 3-D slicer and region of interest, and only the relevant buckets are transmitted instead of the whole high-resolution 3-D medical image data. Furthermore, in order to better support concurrent accesses and to improve the average response time, we also propose techniques for efficient query processing, incremental transmission, and client sharing. Our experimental study in simulated and realistic environments indicates that the proposed framework can significantly reduce storage and communication requirements, and can enable real-time interaction with remote high-resolution 3-D medical image data for many concurrent users.

Surface transportation systems play a crucial role in responding to natural disasters and other catastrophic incidents that have devastating impacts on the lives of people all over the world. Intelligent transportation systems (ITS) can play an important role not only in improving the operational efficiency of a transportation system but also in enhancing its safety and security. In this paper, we propose new techniques for augmenting ITS to improve and support homeland security. In particular, we propose two evacuation algorithms, i.e., all-links and fastest-links, and perform simulation studies to compare their performance. These algorithms are part of a smart traffic evacuation management system (STEMS) developed to provide rapid and efficient response to human-caused threats and disasters by automatically generating dynamic evacuation plans based on incident location and scope and subsequently automatically controlling traffic lights to direct evacuation traffic in a safe manner.

We examine the problem of efficient distance-based similarity search over high-dimensional data. We show that a promising approach to this problem is to reduce dimensions and allow fast approximation. Conventional reduction approaches, however, entail a significant shortcoming: The approximation volume extends across the dataspace, which causes overestimation of retrieval sets and impairs performance. This paper focuses on a new criterion for dimensionality reduction methods: bounded approximation. We show that this requirement can be accomplished by a novel nonlinear transformation scheme that extracts two important parameters from the data. We devise two approximation formulations, namely, rectangular and spherical range search, each corresponding to a closed volume around the original search sphere. We discuss in detail how we can derive tight bounds for the parameters and prove further results, as well as highlight insights into the problems and our proposed solutions. To demonstrate the benefits of the new criterion, we study the effects of (un)boundedness on approximation performance, including selectivity, error toleration, and efficiency. Extensive experiments confirm the superiority of this technique over recent state-of-the-art schemes.

Various techniques have been developed for different query types in content-based image retrieval (CBIR) systems such as sampling queries, constrained sampling queries, multiple constrained sampling queries, k-NN queries, constrained k-NN queries, and multiple localized k-NN queries. In this paper, we propose a generalized query model suitable for expressing queries of different types, and investigate efficient processing techniques for this new framework. We develop new storage and query processing techniques to exploit sequential access and leverage inter-query concurrency to share computation. Our experimental results, based on the Corel dataset, indicates that the proposed optimization can significantly reduce average response time in a multiuser environment.

High-resolution 3D medical image data are typically huge in volume, varying from several hundred megabytes to several dozen gigabytes. Since such large-size data sets severely stress storage systems and networks, most existing Web-based interactive 3D medical imaging applications, such as 3D slicer and region-of-interest viewing, deal with only low-or medium-resolution images. In this paper, we introduce a single instance storage design, a client sharing technique, and a corresponding query processing method to enhance our existing remote medical image viewing system. We give performance results to show that the new design can significantly reduce storage and communication bandwidth requirements. Furthermore, it is more scalable to support a larger number of concurrent users.

With the proliferation of handheld devices, the demand of multimedia information retrieval on mobile devices has attracted more attention. A relevance feedback information retrieval process usually includes several rounds of query refinement. Each round incurs exchange of tens of images between the mobile device and the server. With limited wireless bandwidth, this process can incur substantial delay making the system unfriendly to use. We address this issue by considering a client-side relevance feedback (CRF) technique. Since relevance feedback is done on client side, system response is instantaneous significantly enhancing system usability. Furthermore, since the server is not involved in relevance feedback processing, it is able to support thousands more users simultaneously. Our experimental results indicate that this scheme also effectively address the semantic gap in content-based image retrieval.

In this paper, we propose Local and Global Structures Preserving Projection (LGSPP), which is to find a small set of projection directions so as to properly preserve the local and global structures for a given set of data. Specifically, for each point in the dataset, its local neighborhood is extracted as well as a set of sampled points far away from this point, which characterize the global structure. The embedding minimizes the distances of the points in each local neighborhood while dispersing them far apart from their corresponding remote points. In this way, the local-global relationships between data points are well kept.

In this work, we discuss how to support video-on-demand service in multi-hop WiMax mesh networks. We are interested in the scenario that end users connect to the video servers through the base station of the multi-hop WiMax networks. We propose a model that can jointly solve the admission control and channel scheduling problems. Our proposed approach guarantees the required data rate is achieved for video streams, which is crucial for multimedia streaming applications. An efficient multicast routing technique is also proposed to minimize the bandwidth cost of joining a multicast tree. Furthermore, we adopt the application layer patching technique to accommodate end users that join a video multicast group at different times. Overall, our solution efficiently utilizes the bandwidth resource of the networks and provides data rate guarantee for video streams. Simulation study shows that with the proposed approach, true video-on-demand in WiMax mesh networks can be achieved under high video request arrival rate.

It has long been acknowledged that TCP performance suffers in hybrid networks. A Split TCP approach has been proposed to address this problem. In this approach, a proxy is employed at the boundary of wired networks (e.g. the Internet) and wireless networks (e.g. cellular networks, WLan or mobile ad hoc networks). This strategy significantly improves TCP performance. However, it does not maintain the end-to-end semantics of TCP. The loss of end-to-end semantics may cause problems to applications that rely on such a guarantee provided by TCP. In this paper, we introduce a novel technique called Semi-Split TCP to address the problem without sacrificing the benefits of Split TCP. We present the architecture and algorithms of the proposed technique; and give implementation, simulation, and analytical results to illustrate the feasibility of this method. Our simulation results demonstrate that Semi-Split TCP can achieve similar performance as Split-TCP without sacrificing the end-to-end semantics.

Live video streaming over vehicular ad hoc networks (VANET) is an attractive feature to many applications, such as emergency live video transmission, road-side video advertisement broadcasting and inter-vehicle video conversation. Though vehicles have ample bandwidth, computation and storage capacity to support data intensive communication, the high mobility may cause persistent network partition. The performance of video streaming suffers from the delay and packet loss incurred by the long time disconnection. Although many solutions have been proposed to handle the high mobility problem, few of them addressed the problem in the context of video transmission. In this paper, we focus on video streaming between vehicles in highway, where the traffic density is adequate to mitigate frequent link disconnections and persistent network partitions. We study the performance of video streaming under different data forwarding and buffer management schemes. Real video data and the dedicated short range communications (DSRC) are used in the simulation study to better match the reality. The result of this paper gives insight for the design of the future inter-vehicle video streaming system.

Existing computer-based spinal stenosis diagnosis systems are not fully automatic. Their performance depends on the knowledge and experience of the user. Such a system is typically intended for specialists such as radiologists. We present in this paper a fully automatic system, more suitable for general practitioners for use in screening and initial diagnosis. To evaluate the performance of the proposed techniques, we build a system prototype with two environments - one for managing training images and building the classifiers, and the other environment for diagnosis use in practice. Our experimental results, based on an X-ray image database NHANES II available from the National Library of Medicine, indicates that the proposed system is effective for screening purpos

With the advances in medical imaging devices, large volumes of high-resolution 3D medical image data have been produced. These high-resolution 3D data are very large in size, and severely stress storage systems and networks. Most existing Web-based 3D medical image interactive applications therefore deal with only low- or medium-resolution image data. While it is possible to download the whole 3D highresolution image data from the server and perform the image visualization and analysis at the client site, such an alternative is infeasible when the high-resolution data are very huge, and many users concurrently access the server. In this paper, we propose a novel framework for Web-based interactive applications of high-resolution 3D medical image data. Specifically, we first partition the whole 3D data into buckets, and then compress each bucket separately. We also propose an indexing structure for these buckets to efficiently support typical queries such as 3D slicer and region of interest (ROI), and only the relevant buckets are transmitted instead of the whole highresolution 3D medical image data. Furthermore, in order to better support concurrent accesses and to improve the average response time, we also propose some techniques for bucket group access on the server side and incremental transmission. Our experimental study based on a human brain MRI data set indicates that the proposed framework can significantly reduce storage and communication requirements, and can enable real-time interaction with remote highresolution 3D medical image data for many concurrent users.

Today’s Content-Based Image Retrieval (CBIR) techniques are based on the "k-nearest neighbors" (k- NN) model. They retrieve images from a single neighborhood using low-level visual features. In this model, semantically similar images are assumed to be clustered in the high-dimensional feature space. Unfortunately, no visual-based feature vector is sufficient to facilitate perfect semantic clustering; and semantically similar images with different appearances are always clustered into distinct neighborhoods in the feature space. Confinement of the search results to a single neighborhood is an inherent limitation of the k-NN techniques. In this paper we consider a new image retrieval paradigm — the Query Decomposition model - that facilitates retrieval of semantically similar images from multiple neighborhoods in the feature space. The retrieval results are the k most similar images from different relevant clusters. We introduce a prototype, and present experimental results to illustrate the effectiveness and efficiency of this new approach to content-based image retrieval.

In a typical image retrieval system, all visual features of query images are used to determine image similarity. Thus, users are left to decide whether or not to include images that not only contain desirable features but also irrelevant ones. Fewer examples or a contaminated set of more could compromise the retrieval effectiveness of most similarity measures. In this paper, we extend our previous approach that allows users define queries by specifying relevant features present in image examples. The extended technique support queries decomposed in multiple clusters, each forming a subquery. Our experimental results have shown a remarkable improvement in retrieval performance

Broadcasting in ad hoc networks is required for many routing and other network-layer protocols to request information like routes or locations about destination nodes. Most of these routing protocols use a simple flooding mechanism that can cause broadcast storms, particularly in high density environments. Although many techniques have been proposed to address the problem of broadcast storms, they require additional periodic location beacons or do not satisfactorily reduce transmission redundancy in high density environments.We propose Cell Broadcast, a broadcast protocol that significantly reduces redundancy without the use of beaconing and while maintaining complete reachability in a high density environment. The proposed technique divides a terrain into cells. These cells help a node to determine its geographic relationship with a broadcasting node. This geographic relationship can eliminate rebroadcasts not only from nodes close to a broadcasting node but also from a majority of nodes near the transmission edge of the broadcasting node. The effect is that, in a high density environment, only a few nodes located near the 4 diagonal corners of a transmission range need to rebroadcast to maintain 100% reachability. To the best of our knowledge, this technique is not present in any existing techniques that do not use location beaconing.

Many current image retrieval techniques allow queries to be defined with multiple examples from a presented set. In these systems, all visual features are extracted from these images and used to determine relevant images from the database. As a result, users are left to decide whether or not to include images that not only contain desirable features but also irrelevant ones. Fewer examples or a contaminated set of more either would compromise the retrieval effectiveness of most similarity measures. In this work, we examine this popular case when desired features present in image examples define the intent of the queries. We show how this consideration affects the selection of the representative query points and retrieval sets, and discuss the options whether or not to retrieve partially relevant images. Our experimental results have shown a remarkable improvement in retrieval performance.

In this paper, we argue that two inferences can be made from the results of recent studies: the continuity of image representation and the non-homogeneity of feature space. These characteristics enable the identification of points that satisfy the constraints established in multipoint queries in any orthogonal feature representations. The set can be described by a linear system of equations with constraints. We look at several existing techniques and propose one that can retrieve the set efficiently. We evaluated the performance of our present technique on large sets of images. The results indicate that the new representation matches semantic classes of images very well. The superiority of our approach is evident in the experimental results and in actual implementation.

To enable efficient similarity search in large databases, many indexing techniques use a linear transformation scheme to reduce dimensions and allow fast approximation. In this reduction approach the approximation is unbounded, so that the approximation volume extends across the dataspace. This causes over-estimation of retrieval sets and impairs performance.This paper presents a non-linear transformation scheme that extracts two important parameters specifying the data. We prove that these parameters correspond to a bounded volume around the search sphere, irrespective of dimensionality. We use a special workspace-mapping mechanism to derive tight bounds for the parameters and to prove further results, as well as highlighting insights into the problems and our proposed solutions. We formulate a measure that lower-bounds the Euclidean distance, and discuss the implementation of the technique upon a popular index structure. Extensive experiments confirm the superiority of this technique over recent state-of-the-art schemes.

Unlike conventional range queries, a range-monitoring query is a continuous query. It requires retrieving mobile objects inside a user-defined region and providing continuous updates as the objects move into and out of the region. In this paper, we present an efficient technique for real-time processing of such queries. In our approach, each mobile object is associated with a resident domain, and when an object moves, it monitors its spatial relationship with its resident domain and the monitoring areas inside it. An object reports its location to the server when it crosses over some query boundary or moves out of its resident domain. In the first case, the server updates the affected query results accordingly, while in the second case, the server determines a new resident domain for the object. This distributive approach achieves an accurate and real-time monitoring effect with minimal mobile communication and server processing costs. Our approach also allows a mobile object to negotiate a resident domain based on its computing capability. By having a larger resident domain, a more capable object has less of a chance of moving out of it and having to request a new one. As a result, both communication and server processing costs are reduced. Our comprehensive performance study shows that the proposed technique can be highly scalable in supporting location-based services in a wireless environment that consists of a large number of mobile devices.

Flooding is a fundamental and frequently invoked operation in wireless ad hoc networks. Existing flooding techniques either are unreliable, generate overwhelming unnecessary retransmission, or incur excessive network control overhead. In this paper, we address these crucial problems and propose a new flooding technique called edge forwarding. The new scheme minimizes the flooding traffic by leveraging location information to limit broadcast retransmission to only hosts near the perimeter of each broadcast coverage. Unlike most existing techniques, edge forwarding requires each host to track only neighboring nodes within its one-hop distance. Therefore, it is more adaptive to host mobility and incurs less network control overhead. In particular, it can be easily incorporated into many existing routing protocols without any additional control overhead. Our performance studies indicate that with our strategy, a substantial portion of the unnecessary broadcast retransmission can be eliminated.

Image enhancement such as adjusting brightness and contrast is central to improving human visualization of images’ content. Images in desired enhanced quality facilitate analysis, interpretation, classification, information exchange, indexing and retrieval. The adjustment process, guided by diverse enhancement objectives and subjective human judgment, often produces various versions of the same image. Despite the preservation of content under these operations, enhanced images are treated as new in most existing techniques via their widely different features. This leads to difficulties in recognition and retrieval of images across application domains and user interest. To allow unrestricted enhancement flexibility, accurate identification of images and their enhanced versions is therefore essential. In this paper, we introduce a measure that theoretically guarantees the identification of all enhanced images originated from one. In our approach, images are represented by points in multidimensional intensity-based space. We show that points representing images of the same content are confined in a well-defined area that can be identified by a so-devised formula. We evaluated our technique on large sets of images from various categories, including medical, satellite, texture, color images and scanned documents. The proposed measure yields an actual recognition rate approaching 100% in all image categories, outperforming other well-known techniques by a wide margin. Our analysis at the same time can serve as a basis for determining the minimum criterion a similarity measure should satisfy. We discuss also how to apply the formula as a similarity measure in existing systems to support general image retrieval.

Performance analysis of computing systems is an increasingly difficult task due to growing system complexity. Traditional tools rely on ad hoc procedures. With these, determining which of the manifold system and workload parameters to examine is often a lengthy and highly speculative process. The analysis is often incomplete and, therefore, prone to revealing faulty conclusions and not uncovering useful tuning knowledge. We address this problem by introducing a data mining approach called ADMiRe (analyzer for data mining results). In this scheme, regression analysis is first applied to performance data to discover correlations between various system and workload parameters. The results of this analysis are summarized in sets of regression rules. The user can then formulate intuitive algebraic expressions to manipulate these sets of rules to capture critical information. To demonstrate this approach, we use ADMiRe to analyze an Oracle database system running the TPC-C (Transaction Processing Performance Council) benchmark. The results generated by ADMiRe were confirmed by Oracle experts. We also show that by applying ADMiRe to Microsoft Internet Information Server performance data, we can improve system performance by 20 percent.

We present a system for video-on-demand streaming in peer-to-peer environment. We start by realizing the major differences between two types of streaming: live and on-demand. These observations lead to a set of problems that need to be solved for a peer-to-peer video-on-demand system. To address these problems, we propose a solution, which includes detail algorithms for building and maintaining an application multicast tree. The novel ideas in this paper are the use of a new caching scheme at clients, and the introduction of generation for better client management. Performance study based on simulation is carried out. The results show that our system outperforms a recently proposed system in a number of important performance metrics.

We propose a novel, shape-matching algorithm using skeletal graphs. The topology of skeletal graphs is captured and compared at the node level. Such graph representation allows preservation of the skeletal graph's coherence without scarifying the flexibility of matching similar portions of graphs across different levels. By using an appropriate sampling resolution, we are able to achieve a high recognition rate, and at the same time, significantly reduce the space and time complexity of matching. We tested our approach against the directed acyclic graph (DAG) method on noisy graphs and occluded or cluttered scenes. The results show that our approach is an effective and efficient technique for shape recognition.

Today's communication techniques for mobile ad hoc networks take a connection-oriented approach. Mobile nodes need to discover routes and establish a connection before they can communicate. This strategy is not robust as it cannot adapt to frequent unpredictable topology changes due to high mobility. Constant reconnections incur significant overhead making these schemes unsuitable for applications such as voice and video. To address these issues, we explore a connectionless paradigm in this paper. We leverage technology such as GPS (global positioning system) to allow a source node to discover a grid path to the destination node. Data packets are relayed along this path toward the destination using different intermediate nodes at different times without having to first establish connections between them. The performance of this new solution is essentially unaffected by node mobility. As a result, it is suitable for a wide range of mobile applications.

We consider in this paper how to leverage heterogeneous mobile computing capability for efficient processing of real-time range-monitoring queries. In our environment, each mobile object is associated with a resident domain and when an object moves, it monitors its spatial relationship with its resident domain and the monitoring areas inside it. An object reports its location to server whenever its movement affects any query results (i.e., crossing any query boundaries) or it moves out of its resident domain. In the first case, the server updates the affected query results accordingly while in the second case, the server determines a new resident domain for the object. This distributive approach is able to provide accurate query results and real-time monitoring updates with minimal location update and server processing costs. In addition, the new scheme allows a mobile object to negotiate a resident domain based on its computing capability. Thus, a more capable object can have a larger resident domain reducing its chance of having to request a new resident domain because of moving out of it. This feature makes the new approach highly adaptive to the heterogeneity of mobile objects. In our performance study, we compare it with an existing approach using simulation. The study shows that the new technique is many times better in reducing mobile communication and server processing costs.

We present a design for a system that provides video-on-demand (VOD) services to mobile ad hoc clients. Such a system allows the clients to access video information anytime anywhere. MobiVoD, the proposed solution, overcomes many difficulties currently challenging video streaming in a mobile ad hoc network. The new environment includes a three-tier architecture, in which the mobile VOD system employs a periodic broadcast protocol to achieve maximum scalability; and the clients leverage an ad hoc network caching technique to minimize the service delay. This system can sustain client failure and mobility, and provide true VOD services to most clients.

In this paper, we present the Range Multicast protocol and the implemented prototype. We propose to demonstrate the system at the 2004 ACM Multimedia Conference.

Given that the Internet does not widely support Internet protocol multicast while content-distribution-network technologies are costly, the concept of peer-to-peer could be a promising start for enabling large-scale streaming systems. In our so-called Zigzag approach, we propose a method for clustering peers into a hierarchy called the administrative organization for easy management, and a method for building the multicast tree atop this hierarchy for efficient content transmission. In Zigzag, the multicast tree has a height logarithmic with the number of clients, and a node degree bounded by a constant. This helps reduce the number of processing hops on the delivery path to a client while avoiding network bottlenecks. Consequently, the end-to-end delay is kept small. Although one could build a tree satisfying such properties easily, an efficient control protocol between the nodes must be in place to maintain the tree under the effects of network dynamics. Zigzag handles such situations gracefully, requiring a constant amortized worst-case control overhead. Especially, failure recovery is done regionally with impact on, at most, a constant number of existing clients and with mostly no burden on the server.

Deployment of a large-scale multimedia streaming application requires an enormous amount of server and network resources. The simplest delivery technique allocates server resources for each specific request. This technique is very expensive and is not scalable to support a very large user community such as the Internet. Hence, the past decade has witnessed tremendous research efforts to facilitate cost-effective, large-scale deployment of multimedia streaming applications. In this paper, we describe three complementary research approaches: server transmission schemes using multicast, streaming strategies with application layer multicast, and proxy caching techniques. We discuss pros and cons of these technologies and provide our observations on current business solutions.

Segmentation of ultrasound liver images presents a unique challenge because these images contain strong speckle noise and attenuated artifacts. Most ultrasound image segmentation techniques focus on region growing or active contours. These are semi-automatic segmenting systems, in which seed points or initial contours have to be manually identified. In this paper, we propose a fully automatic segmentation system for ultrasound liver images. We apply the Peak-and-valley method to pixels scanned along the Hubert curve, and propose a "windows adaptive threshold" procedure to further reduce noise from the images. After Otsu's segmentation algorithm is applied to the images, a core area algorithm is employed to detect liver objects with the help of a feature knowledge base. We compared our method with other techniques and the manual segmentation method. The results indicate the accuracy of our system and our automatically segmented images contain less noise than the other methods.

A peer-to-peer technique called ZIGZAG for single-source media streaming is designed . ZIGZAG allows the media server to distribute content to many clients by organizing them into an appropriate tree rooted at the server. This application-layer multicast tree has a height logarithmic with the number of clients and a node degree bounded by a constant. This helps reduce the number of processing hops on the delivery path to a client while avoiding network bottleneck. Consequently, the end-to-end delay is kept small. Although one could build a tree satisfying such properties easily, an efficient control protocol between the nodes must be in place to maintain the tree under the effects of network dynamics and unpredictable client behaviors. ZIGZAG handles such situations gracefully requiring a constant amortized control overhead. Especially, failure recovery can be done regionally with little impact on the existing clients and mostly no burden on the server.

Query-by-example is the most popular query model in recent content-based image retrieval (CBIR) systems. A typical query image includes relevant objects (e.g., Eiffel Tower), but also irrelevant image areas (including background). The irrelevant areas limit the effectiveness of existing CBIR systems. To overcome this limitation, the system must be able to determine similarity based on relevant regions alone. We call this class of queries region-of-interest (ROI) queries and propose a technique for processing them in a sampling-based matching framework. A new similarity model is presented and an indexing technique for this new environment is proposed. Our experimental results confirm that traditional approaches, such as Local Color Histogram and Correlogram, suffer from the involvement of irrelevant regions. Our method can handle ROI queries and provide significantly better performance. We also assessed the performance of the proposed indexing technique. The results clearly show that our retrieval procedure is effective for large image data sets.

Video-cassette-recorder-like (VCR) capabilities such as jumping to a specific frame or fast forwarding a video are becoming essential services in video-on-demand (VOD) applications. To provide VCR functionalities in a broadcast environment, current techniques depend on data prefetching. However, a fast-forward or a fast-backward of a video for several seconds would certainly exhaust the prefetch buffer because the prefetching rate cannot sustain typical speeds. In this paper we address this practical problem where each video and its interactive version are broadcast repeatedly on the network. For example, interactive versions might contain only every fifth frame in the original videos. We propose a new technique that leverages these "interactive" broadcasts to provide better VCR service.

Despite the amelioration in communication technologies, the server network I/O bottleneck remains a severe obstacle in video-on-demand applications. All bandwidth-sharing techniques, proposed to overcome this, assume videos to be requested in their entirety. In this paper, we extend the video-on-demand delivery problem so that it allows users to request parts of video and be able to receive them at that instant. Specifically, we propose an efficient technique called multicast jumping (MJ) that provides many desirable properties such as: (1) the demand on the server bandwidth is significantly alleviated; (2) true and scaleable video on demand is achieved; (3) not only for streaming video segments on demand, but the technique also works for on-demand videos in their entirety.

Focuses on the problem of providing quality-of-service guarantee, scalability, and on-demand property to video streaming systems. We propose a solution called layered range multicast (LRM). LRM allows transmitting a range of data to a multicast group's members, which helps clients who request for service at different times join a same multicast efficiently without additional server bandwidth allocation. This is more advanced than the conventional multicast in which a late client joining an existing multicast, without bandwidth support from the server, must miss a certain portion of the video requested. Another advantage of LRM is its capability to support clients requesting various levels of service quality. In addition, LRM does not assume the existence of IP Multicast and therefore it can be implemented on the current Internet without degrading the very inefficient centralized approach. Our performance study results confirm the above benefits.

Various approaches have been proposed to discover patterns from system call trails of UNIX processes to better model application behavior. However, these techniques only consider the relationship between system calls (or system audit events). We first refine the definition of maximal patterns given in (Wespi et al., 2000) and provide a pattern extraction algorithm to identify such maximal patterns. We then add one additional dimension to the problem domain by also taking into consideration the overlap relationship between patterns. We argue that an execution path of an application is usually not an arbitrary combination of various patterns; but rather, they overlap each other in some specific order. Such overlap relationship characterizes the normal behavior of the application. Finally, a novel pattern matching module is proposed to detect intrusions based on both intra-pattern and inter-pattern anomalies. We test this idea using the data sets obtained from the University of New Mexico. The experimental results indicate that our scheme detects significantly more anomalies than the scheme presented in (Wespi et al., 2000) while maintaining a very low false alarm rate.

In video-on-demand (VOD) applications, it is desirable to provide the user with the video-cassette-recorder-like (VCR) capabilities such as fast-forwarding a video or jumping to a specific frame. We address this issue in the broadcast framework, where each video is broadcast repeatedly on the network. Existing techniques rely on data prefetching as the mechanism to provide this functionality. This approach provides limited usability since the prefetching rate cannot keep up with typical fast-forward speeds. Fast-forwarding a video for several seconds would inevitably exhaust the prefetch buffer. We address this practical problem in this paper by repeatedly broadcasting the interactive versions of the videos. For instance, an interactive version might contain only every fifth frame in the original video. Our client software leverages these "interactive" broadcasts to provide better VCR service. We formally prove the correctness of this approach, and compare its performance to a prefetch method, called active buffer management. This scheme has been shown to offer, in the broadcast environment, the best performance to date. Our simulation results indicate that the new technique is superior in handling long-duration VCR actions.

We design a peer-to-peer technique for single-source media streaming. This technique allows the media server to distribute content to many clients by organizing them into an appropriate tree rooted at the server. This application-layer multicast tree has a height O(logN) where N is the number of clients, and a node degree bounded by a constant. This helps reduce the number of processing hops on the delivery path to a client while avoiding network bottleneck. Consequently, the end-to-end delay is kept small. Although one could build a tree satisfying such properties easily, an efficient control protocol between the nodes must be in place to maintain the tree under the effects of network dynamics and unpredictable client behaviors. Our technique handles such situations gracefully requiring a constant amortized control overhead. Especially, failure recovery can be done regionally with little impact on the existing clients.

In this paper, we propose a novel segmenting system for ultrasound images. This solution is separated into three steps. First, we filter noise by using the "peak-and-valley" with scanning pixels along the Hilbert curve. Then we use the "Cubic Spline Interpolation" between local peaks and valleys to smooth the image. Second, we present windows adaptive threshold, to eliminate trial and error, as the method for obtaining the right threshold for beginning segmentation. Third, we label distinct, disconnected objects and use our "core area" to detect the object of interest based on the feature knowledge bases. Our method was experimented with liver ultrasound images. We compared the orientation and centroid feature vectors of our Full Automatic Segmenting Ultrasound (FASU) method with the manual segmentation method. The results are fully automatic and confirm the accuracy of our FASU method.

In limited and asymmetric bandwidth environments such as wireless networks, push strategy can be used to allow a large number of mobile users to access the shared data. Most of today's solutions assume that the server disseminates data on only one physical channel. In this paper, we focus on the problem of broadcasting data over multiple physical channels that cannot be coalesced into fewer high-bandwidth ones. This introduces new hurdles such as the heterogeneities of channels and data set. We propose a novel broadcast design at the server side, which is aimed at minimizing the response and download times. We also present a caching policy at the client side to further enhance the performance. Theoretical foundations and simulation-based studies are also presented to substantiate the near-optimality and to assess the advantages of the proposed technique.

A typical query image contains not only relevant objects, but also irrelevant image areas. The latter, referred to as noise, has limited the effectiveness of existing image retrieval systems. In this paper, we propose a technique that allows users to define arbitrary-shaped queries out of example images. We present a new similarity model, and introduce an indexing technique for this new environment. Our query model is more expressive than the standard query-by-example. The user can draw a contour around a number of objects to specify spatial (relative distance) and scaling (relative size) constraints among them, or use separate contours to disassociate these objects. Our experimental results confirm that traditional approaches, such as Local Color Histogram and Correlogram, suffer from noisy queries. In contrast, our method can leverage arbitrary-shaped queries to offer significantly better performance. This is achieved using only a fraction of the storage overhead required by the other two techniques.

Abstract Recent advances in multimedia processing technologies, internet‐working technologies, and the World Wide Web phenomenon have resulted in a vast creation and use of digital videos. Due to this reason, an efficient technique to locate and retrieve a desired video from a remote video archive is needed. A trial‐and‐error approach popularly used in current Web search engines is not applicable for searching for a desired video segment since the technique incurs intolerable delays. In this paper, we present the design and implementation of a video browsing system that lets the user view a summary of a selected video and search within the video while being downloaded so that the user can determine the relevance of the video as early as possible. The system is inexpensive and scalable, making it suitable for large‐scale distributed systems such as the Internet. The browsing system consists of two major software components: a video server, and a video browser and player calledVideoCenterimplemented using Microsoft DirectShow multimedia development kit. The implementation of VideoCenter enables us to assess the ease of use of DirectShow as well as its drawbacks in developing multimedia applications. Copyright © 2001 John Wiley & Sons, Ltd.

Investigates efficient ways of broadcasting data to mobile users over multiple physical channels, which cannot be coalesced into a lesser number of high-bandwidth channels. We propose the use of an MLMC (multi-level multi-channel) air cache, which can provide mobile users with data based on their popularity factor. We provide a wide range of design considerations for the server which broadcasts over the MLMC cache. We also investigate some novel techniques for a mobile user to access data from the MLMC cache and show the advantages of designing the broadcasting strategy in tandem with the access behavior of the mobile users. Finally, we provide experimental results to compare the techniques we introduce.

Shot boundary detection (SBD) is the first fundamental step to managing video databases. Existing automatic SBD techniques, however, are based on sequential search, and therefore too expensive for practical use. To address this problem, we investigate a non-linear approach in which most video frames do not need to be compared. It can improve their performance substantially. Our experiments show that this idea speeds up a conventional method based on color histograms up to 16 times (five times on average) while preserving the same accuracy.

We present in this paper a fully automatic content-based approach to organizing and indexing video data. Our methodology involves three steps:

RAID (redundant array of inexpensive disks) offers high performance for read accesses and large writes to many consecutive blocks. On small writes, however, it entails large penalties. Two approaches have been proposed to address this problem. The first approach records the update information on a separate log disk, and only brings the affected parity blocks to the consistent state when the system is idle. This strategy increases the chance of disk failure due to the additional log disks. Furthermore, heavy system loads for an extended period of time can overflow the log disks and cause sudden disastrous performance. The second approach avoids the above problems by grouping the updated blocks into new stripes and writing them as large writes. Unfortunately, this strategy improves write performance on the expense of read operations. After many updates, a set of logically consecutive data blocks can migrate to only a few disks making fetching them more expensive. We improve on the second approach by eliminating its negative side effects. Our simulation results indicate that the existing scheme sometime performs worse than the standard RAIDS design. Our method is consistently better than either of these techniques.

Patching is a cost efficient channel-sharing technique for video-on-demand systems. However, its performance is limited due to the fact that a video stream cannot be shared unless it delivers the video in its entirety. As a result, larger and larger patches are required to serve new requests as the temporal distance increases. To avoid the overwhelming accumulation of patching cost, the entire video must be delivered frequently. In this paper, we address this problem by introducing a new technique called Transition Patching. Our performance study shows that the new scheme outperforms the existing approach under all scenarios. In particular, the performance gain is more significant when the request rate is higher. We note that such improvement is achieved without extra download bandwidth required at the client site. The implementation cost, therefore, is the same as the original Patching scheme.

The rapid growth of digital image data increases the need for efficient and effective image retrieval systems. Such systems should provide functionality that tailors to the user's need at the query time. In this paper, we propose a new image retrieval technique that allows users to control the relevantness of the results. For each image, the color contents of its regions are captured and used to compute similarity. Various factors, assigned automatically or by the user, allow high recall and precision to be obtained. We implemented the proposed technique for a large database of 16,000 images. Our experimental results show that this technique is not only space-time efficient but also more effective than recently proposed color histogram techniques.

Several periodic broadcasting schemes have been shown to be very effective in addressing the bandwidth limitation in multimedia servers. Since this approach allows many users to share a server stream, its bandwidth requirement is independent of the number of users the system is designed to support. Existing broadcasting schemes use two or less download channels at the client end to receive data. We discuss the drawbacks of this approach, and propose a new technique which allows a video session to download data through several client channels. The number of channels which can be used simultaneously is limited only by the communication capability of the client system. We prove the correctness of this client-centric approach, and provide analytical evaluations to show that it has significantly better performance than skyscraper broadcasting technique which has been shown to offer the best performance to date.

Periodic broadcast and scheduled multicast have been shown to be very effective in reducing the demand on server bandwidth. While periodic broadcast is ideally suited for very popular videos, scheduled multicast is better for less demanded objects. Work has also been done to show that a hybrid of these techniques offers the best performance. Existing hybrid techniques, however, assume that the workload does not change with time. This assumption is not true for many applications, such as movie on demand, digital video libraries, or electronic commerce. In this paper we show evidence that existing scheduled multicast techniques are not suited for hybrid designs. To address this issue, we propose a new scheme, and use it to design an adaptive hybrid strategy which adjusts itself to cope with a changing workload. We provide simulation results to show that the proposed technique is significantly better than the best static approach in terms of service latency throughput, defection rate, and unfairness.

Until now, true video-on-demand can only be achieved using a dedicated data flow for each sen-ice request. This brute- force approach is prohibitively expensive. Using multicast can significantly reduce the system cost. This solution, however, must delay services in order to serve many requests as a batch. In this paper, we consider a third alternative called Patching. In our technique, an existing multicast can expand dynamically to serve new clients. Allowing new clients to join an existing multicast improves the efficiency of the multicast. Furthermore, since all requests can be served im-mediately, the clients experience no service delay and true video-on-demand can be achieved. A significant contribution of this work, is making multicast work for true video- on-demand services. In feet, we are able to eliminate the service latency and improve the efficiency of multicast at the same time. To assess the benefit of this scheme, we perform simulations to compare its performance with that of standard multicast. Our simulation results indicate convincingly that- Patching offers substantially better performance. © 1998 ACM.

The two main operating constraints of today's multimedia servers are the I/O bandwidth and communication bandwidth limitations. Both of these problems are addressed in this paper using a novel technique called Earthworm. In this scheme, the network memory is used as a huge cache for buffering multimedia data. Dramatic reduction in the demand on the I/O bandwidth, therefore, can be achieved. This scheme also chains display stations to allow them to forward video streams. This strategy eliminates the congestion at the communication port of the server. Removing this bottleneck allows our technique to operate on the vast aggregate bandwidth of the WAN rather than being constrained by the very limited local bandwidth available to the server. A unique feature of the Earthworm approach is that every display station using the server attempts to make some contribution to the caching space and communication bandwidth. The arrival of a new request, therefore, can be seen as a contributor, rather than just a burden to the server. This characteristic ensures the scalability of our design to support very large multimedia applications.

We present a technique, called bidirectional highly optimized pipelining (BiHOP), for managing disks as a buffer for the tertiary storage of a multimedia server. We implement a simulator to compare its performance to that of a recently proposed scheme called SEP. The results show that BiHOP performs significantly better. Its superior performance is attributed to a novel caching approach, which caches every other data fragment of the multimedia file, rather than caches consecutive fragments as in traditional practice. This new approach allows us to use tiny staging buffers for pipelining, which can be implemented in the memory to conserve disk bandwidth. Furthermore, the whole disk space can be dedicated for caching purposes to improve hit ratio. Another important advantage of BiHOP is its ability to pipeline in either forward or reverse direction with the same efficiency. This unique feature, not possible with existing schemes, makes it natural for implementing VCR functions.

We propose a novel delivery mechanism called 2-Phase Service Model to deliver video data to home users connected to the Internet through a low-bandwidth device such as a modem.In our scheme, non-adjacent fragments of the requested video file are first downloaded to the client during Initialization Phase.The missing fragments are transmitted to the client as the video is being played out, using a novel pipelining technique.This scheme offers several benefits as follows.First, it allows the user to perform a quick preview through the video with minimal delay.Second, it naturally supports VCR functionality with almost no delay as demonstrated by the simulation results shown in the paper.Finally, our mathematical analysis shows that despite the desirable features it offers, 2-Phase Service Model does not incur any more initialization delay than-that of the conventional pipelining technique.

We investigate a novel multicast technique, called Skyscraper Broadcasting (SB), for video-on-demand applications. We discuss the data fragmentation technique, the broadcasting strategy, and the client design. We also show the correctness of our technique, and derive mathematical equations to analyze its storage requirement. To assess its performance, we compare it to the latest designs known as Pyramid Broadcasting (PB) and Permutation-Based Pyramid Broadcasting (PPB). Our study indicates that PB offers excellent access latency. However, it requires very large storage space and disk bandwidth at the receiving end. PPB is able to address these problems. However, this is accomplished at the expense of a larger access latency and more complex synchronization. With SB, we are able to achieve the low latency of PB while using only 20% of the buffer space required by PPB.

There has been a wealth of research in the area of parallel join algorithms. Among them, hash-based algorithms are particularly suitable for shared-nothing database systems. The effectiveness of these techniques depends on the uniformity in the distribution of the join attribute values. When this condition is not met, a severe fluctuation may occur among the bucket sizes, causing uneven workload for the processing nodes. Many parallel join algorithms with load balancing capability have been proposed to address this problem. Among them, the sampling and incremental approaches have been shown to provide an improvement over the more conventional methods. The comparison between these two approaches, however, has not been investigated. In this paper, we improve these techniques and implement them on an nCUBE/2 parallel computer to compare their performance. Our study indicates that the sampling technique is the better approach.>

We adapt a competition-based connectionist model to information retrieval. This model, which has been proposed for diagnostic problem solving, treats documents as "disorders" and user information needs as "manifestations", and it uses a competitive activation mechanism which converges to a set of disorders that best explain the given manifestations. Our experimental results using four standard document collections demonstrate the efficiency and the retrieval precision of this model, comparable to or better than that of various information retrieval models reported in the literature. We also propose a parallel implementation of the model on a SIMD machine, MasPar's MP-I. Our experimental results demonstrate the potential to achieve significant speedups.>

Shared nothing multiprocessor architecture is known to be more scalable to support very large databases. Compared to other join strategies, a hash-based join algorithm is particularly efficient and easily parallelized for this computation model. However, this hardware structure is very sensitive to the skew in tuple distribution. Unless the parallel hash join algorithm includes some dynamic load balancing mechanism, the skew effect can severely deteriorate the system performance. In this paper, we investigate this issue. In particular, three parallel hash join algorithms are presented. We implement a simulator to study the effectiveness of these schemes. The simulation model is validated by comparing the simulation results to those produced by the actual implementation of the algorithms running on a multiprocessor system. Our performance study indicates that a naive approach is not able to provide tangible savings. However, the carefully designed strategies can offer substantial improvement over conventional techniques for a wide range of skew conditions.

One common requirement of object-oriented applications is the efficient support of complex objects. This requirement is one salient feature of object orientation. Access to a complex object involves true basic steps: (1) The predicate is evaluated to identify the complex object. (2) The qualified complex object is traversed to retrieve the required components. Over the past few years, several indexing schemes have been developed to support step 1. However, support structures for the efficient execution of step 2 has received little attention. To address this problem, we propose, in this paper, using networks of unique object identifiers (Object Skeletons) as a navigational structure to aid query processing of complex objects. In this approach, skeletons of complex objects contain only the semantic information. Once a skeleton has been loaded into memory, navigation along the complex object can be done with no further disk access. Furthermore, since the descriptive information of an object is stored separately from its object identifier, it is free to migrate anywhere in the database. To assess the efficiency of this approach, we built a prototype and compared its performance to some recently proposed indexing schemes. The results of our study indicate that this technique can provide very impressive savings of both space and time.>

It has been demonstrated that simulated annealing provides high-quality results for the data clustering problem. However, existing simulated annealing schemes are memory-based algorithms; they are not suited for solving large problems such as data clustering which typically are too big to fit in the memory space in its entirety. Various buffer replacement policies, assuming either temporal or spatial locality, are not useful in this case since simulated annealing is based on a randomized search process. Poor locality of references will cause the memory to thrash because too many replacements are required. This phenomenon will incur excessive disk accesses and force the machine to run at the speed of the I/O subsystem. In this paper, we formulate the data clustering problem as a graph partition problem (GPP), and propose a decomposition-based approach to address the issue of excessive disk accesses during annealing. We apply the statistical sampling technique to randomly select subgraphs of the GPP into memory for annealing. Both the analytical and experimental studies indicate that the decomposition-based approach can dramatically reduce the costly disk I/O activities while obtaining excellent optimized results.

Introduces the connectivity index, an access structure for the efficient evaluation of traversal-recursive queries. Unlike conventional bottom-up evaluation techniques that require the creation of temporary files and scanning of the relations many times in computing the relational operators, the new access strategy requires only a single-pass scan of the index file. The proposed scheme is illustrated using examples. Algorithms for the maintenance of the index structure are presented.>

The authors propose design techniques that may significantly simplify the cache access path, and hence offer the opportunity of shorter cycle time or fewer pipeline stages. Their proposals are based on highly accurate prediction methods that allow them to efficiently resolve address translation information early in the pipe.>

Two relational join strategies, broadcast-based join and bucket-based join, have been recently proposed for the hypercube interconnection topology. The first strategy, however, incurs many unnecessary comparisons of pairs of tuples of the two relations. Although the second technique compares only tuples of the relevant buckets, it may suffer from potential load imbalance, which is most critical to the performance of a shared-nothing system. To address these issues, a join algorithm for hypercube computers which includes dynamic load balancing capabilities to minimize the effect of skewness in tuple distribution is proposed. Simulation results indicate that the scheme provides significant improvement over the bucket-based join strategy. In fact, the technique is consistently superior even when the skew condition is very mild.>

The authors describe a synonym-resolution mechanism based on highly accurate real address-prediction methods prior to the completion of address generation. The prediction method uses the contents of the base registers and proper history tables. Such early resolution of translation information may allow a more efficient implementation of high-performance processors. Several techniques were developed and evaluated by trace-based simulations. The feasibility of achieving over 98% accuracy of prediction with reasonable approaches is demonstrated. Early resolution of translation information can be rather critical for certain high-performance processor designs. In practice, such results should be realized with careful design in order to effectively reduce the critical path for cache accessing.>