This benchmark suite provides a comprehensive evaluation framework for assessing both individual LLMs and multi-agent systems in real-world planning and scheduling scenarios. The suite encompasses 14 designed planning and scheduling problems that progress from basic to highly complex, incorporating key aspects such as multi-agent coordination, inter-agent dependencies, and dynamic environmental disruptions. Each problem can be scaled along three dimensions: the number of parallel planning threads, the complexity of inter-dependencies, and the frequency of unexpected disruptions requiring real-time adaptation. The benchmark includes 14 detailed problem specifications, 15 comparison methods including Random, LPT, SPT, STPT, MPSR, DRL-Liu, GP, GEP, LSO, SPT/TWKR, DRL-Chen, DRL-Zhang, 2+ evaluation metrics, and baseline implementations using 3+ LLMs including GPT-4o, Claude-3.7, DeepSeek-R1, and 4 contemporary frameworks including LangGraph, AutoGen, CrewAI, and Swarm, enabling rigorous testing of both single-agent and multi-agent planning capabilities. Through standardized evaluation criteria and scalable complexity, this benchmark aims to be open-sourced to drive progress in developing more adaptable, robust, and scalable AI planning systems for real-world applications.

This paper introduces a checks-and-balances framework for ethical alignment of Large Language Models (LLMs), inspired by three-branch governmental systems. It implements three independent yet interacting components: LLMs as the executive branch for knowledge generation, DIKE as the legislative branch establishing ethical guardrails, and ERIS as the judicial branch for contextual interpretation. Beyond structural separation, we address a fundamental challenge: regulating emotion to shape behaviors. Drawing from psychological theories where managing emotional responses prevents harmful behaviors, we develop a self-supervised learning pipeline that maps emotions to linguistic behaviors, enabling precise behavioral modulation through emotional conditioning. By integrating this approach with adversarial testing, our framework demonstrates how DIKE and ERIS direct linguistic behaviors toward ethical outcomes while preserving independence throughout knowledge generation, ethical oversight, and contextual interpretation.

This paper introduces SagaLLM, a structured multi-agent architecture designed to address four foundational limitations of current LLM-based planning systems: unreliable self-validation, context loss, lack of transactional safeguards, and insufficient inter-agent coordination. While recent frameworks leverage LLMs for task decomposition and multi-agent communication, they often fail to ensure consistency, rollback, or constraint satisfaction across distributed workflows. SagaLLM bridges this gap by integrating the Saga transactional pattern with persistent memory, automated compensation, and independent validation agents. It leverages LLMs' generative reasoning to automate key tasks traditionally requiring hand-coded coordination logic, including state tracking, dependency analysis, log schema generation, and recovery orchestration. Although SagaLLM relaxes strict ACID guarantees, it ensures workflow-wide consistency and recovery through modular checkpointing and compensable execution. Empirical evaluations across planning domains demonstrate that standalone LLMs frequently violate interdependent constraints or fail to recover from disruptions. In contrast, SagaLLM achieves significant improvements in consistency, validation accuracy, and adaptive coordination under uncertainty—establishing a robust foundation for real-world, scalable LLM-based multi-agent systems.

In this paper we propose the macroblock scaling (MBS) algorithm, which can be applied to various CNN architectures to reduce their model size. MBS adaptively reduces each CNN macroblock depending on its information redundancy measured by our proposed effective flops. Empirical studies conducted with ImageNet and CIFAR-10 attest that MBS can reduce the model size of some already compact CNN models, e.g., MobileNetV2 (25.03% further reduction) and ShuffleNet (20.74%), and even ultra-deep ones such as ResNet-101 (51.67%) and ResNet-1202 (72.71%) with negligible accuracy degradation. MBS also performs better reduction at a much lower cost than the state-of-the-art optimization-based methods do. MBS's simplicity and efficiency, its flexibility to work with any CNN model, and its scalability to work with models of any depth make it an attractive choice for CNN model size reduction.

Multi-domain image-to-image translation has gained increasing attention recently. Previous methods take an image and some target attributes as inputs and generate an output image with the desired attributes. However, such methods have two limitations. First, these methods assume binary-valued attributes and thus cannot yield satisfactory results for fine-grained control. Second, these methods require specifying the entire set of target attributes, even if most of the attributes would not be changed. To address these limitations, we propose RelGAN, a new method for multi-domain image-to-image translation. The key idea is to use relative attributes, which describes the desired change on selected attributes. Our method is capable of modifying images by changing particular attributes of interest in a continuous manner while preserving the other attributes. Experimental results demonstrate both the quantitative and qualitative effectiveness of our method on the tasks of facial attribute transfer and interpolation.

Online symptom checkers have been deployed by sites such as WebMD and Mayo Clinic to identify possible causes and treatments for diseases based on a patient’s symptoms. Symptom checking first assesses a patient by asking a series of questions about their symptoms, then attempts to predict potential diseases. The two design goals of a symptom checker are to achieve high accuracy and intuitive interactions. In this paper we present our context-aware hierarchical reinforcement learning scheme, which significantly improves accuracy of symptom checking over traditional systems while also making a limited number of inquiries.

This paper proposes REFUEL, a reinforcement learning method with two techniques: {\em reward shaping} and {\em feature rebuilding}, to improve the performance of online symptom checking for disease diagnosis. Reward shaping can guide the search of policy towards better directions. Feature rebuilding can guide the agent to learn correlations between features. Together, they can find symptom queries that can yield positive responses from a patient with high probability. Experimental results justify that the two techniques in REFUEL allows the symptom checker to identify the disease more rapidly and accurately.

With the revival of neural networks, many studies try to adapt powerful sequential neural models, ıe Recurrent Neural Networks (RNN), to sequential recommendation. RNN-based networks encode historical interaction records into a hidden state vector. Although the state vector is able to encode sequential dependency, it still has limited representation power in capturing complicated user preference. It is difficult to capture fine-grained user preference from the interaction sequence. Furthermore, the latent vector representation is usually hard to understand and explain. To address these issues, in this paper, we propose a novel knowledge enhanced sequential recommender. Our model integrates the RNN-based networks with Key-Value Memory Network (KV-MN). We further incorporate knowledge base (KB) information to enhance the semantic representation of KV-MN. RNN-based models are good at capturing sequential user preference, while knowledge-enhanced KV-MNs are good at capturing attribute-level user preference. By using a hybrid of RNNs and KV-MNs, it is expected to be endowed with both benefits from these two components. The sequential preference representation together with the attribute-level preference representation are combined as the final representation of user preference. With the incorporation of KB information, our model is also highly interpretable. To our knowledge, it is the first time that sequential recommender is integrated with external memories by leveraging large-scale KB information.

This article studies the problem of learning effective representations for Location-Based Social Networks (LBSN), which is useful in many tasks such as location recommendation and link prediction. Existing network embedding methods mainly focus on capturing topology patterns reflected in social connections, while check-in sequences, the most important data type in LBSNs, are not directly modeled by these models. In this article, we propose a representation learning method for LBSNs called as JRLM++, which models check-in sequences together with social connections. To capture sequential relatedness, JRLM++ characterizes two levels of sequential contexts, namely fine-grained and coarse-grained contexts. We present a learning algorithm tailored to the hierarchical architecture of the proposed model. We conduct extensive experiments on two important applications using real-world datasets. The experimental results demonstrate the superiority of our model. The proposed model can generate effective representations for both users and locations in the same embedding space, which can be further utilized to improve multiple LBSN tasks.

This paper proposes a data-driven approach for image alignment. Our main contribution is a novel network architecture that combines the strengths of convolutional neural networks (CNNs) and the Lucas-Kanade algorithm. The main component of this architecture is a Lucas-Kanade layer that performs the inverse compositional algorithm on convolutional feature maps. To train our network, we develop a cascaded feature learning method that incorporates the coarse-to-fine strategy into the training process. This method learns a pyramid representation of convolutional features in a cascaded manner and yields a cascaded network that performs coarse-to-fine alignment on the feature pyramids. We apply our model to the task of homography estimation, and perform training and evaluation on a large labeled dataset generated from the MS-COCO dataset. Experimental results show that the proposed approach significantly outperforms the other methods.

Quality, cost, and accessibility together form an iron triangle that has prevented healthcare from achieving accelerated advancement in the last few decades. Improving any one of the three iron triangle vertices may lead to degradation of the other two. For example, a policy that increases healthcare accessibility would lower quality and/or increase cost. Thanks to recent breakthroughs in artificial intelligence (AI) and virtual reality (VR), this iron triangle may finally be shattered. In this talk, I will share our experience of developing DeepQ, an AI platform, for supporting AI-aided diagnosis and VR-aided surgery. I will present two healthcare initiatives that we have been undertaking since 2013: XPRIZE Tricorder and VR surgery, and explain how AI and VR play pivotal roles in improving diagnosis accuracy and treatment effectiveness. More specifically, I will depict how we have dealt with not only big data machine learning, but also small data learning, which is typical in the medical domain. The talk concludes with roadmaps and a list of open research issues in multimodal signal processing, fusion, and mining to achieve precision medicine and precision surgery.

This paper introduces our augmented reality platform, Aristo, which aims to provide users with physical feedback when interacting with virtual objects. We use Vivepaper, a product we launched on Aristo in 2016, to illustrate the platform's performance requirements and key algorithms. We specifically depict Vivepaper's tracking and gesture recognition algorithms, which involve several trade-offs between speed and accuracy to achieve an immersive experience.

Two characteristics of location-based services are mobile trajectories and the ability to facilitate social networking. The recording of trajectory data contributes valuable resources towards understanding users’ geographical movement behaviors. Social networking is possible when users are able to quickly connect to anyone nearby. A social network with location based services is known as location-based social network (LBSN). As shown in Cho et al. [2013], locations that are frequently visited by socially related persons tend to be correlated, which indicates the close association between social connections and trajectory behaviors of users in LBSNs. To better analyze and mine LBSN data, we need to have a comprehensive view of each of these two aspects, i.e., the mobile trajectory data and the social network. Specifically, we present a novel neural network model that can jointly model both social networks and mobile trajectories. Our model consists of two components: the construction of social networks and the generation of mobile trajectories. First we adopt a network embedding method for the construction of social networks: a networking representation can be derived for a user. The key to our model lies in generating mobile trajectories. Second, we consider four factors that influence the generation process of mobile trajectories: user visit preference, influence of friends, short-term sequential contexts, and long-term sequential contexts. To characterize the last two contexts, we employ the RNN and GRU models to capture the sequential relatedness in mobile trajectories at the short or long term levels. Finally, the two components are tied by sharing the user network representations. Experimental results on two important applications demonstrate the effectiveness of our model. In particular, the improvement over baselines is more significant when either network structure or trajectory data is sparse.

The task of tweet timeline generation (TTG) aims at selecting a small set of representative tweets to generate a meaningful timeline and providing enough coverage for a given topical query. This paper presents an approach based on determinantal point processes (DPPs) by jointly modeling the topical relevance of each selected tweet and overall selectional diversity. Aiming at better treatment for balancing relevance and diversity, we introduce two novel strategies, namely spectral rescaling and topical prior. Extensive experiments on the public TREC 2014 dataset demonstrate that our proposed DPP model along with the two strategies can achieve fairly competitive results against the state-of-the-art TTG systems.

We present in this article an automated framework that extracts product adopter information from online reviews and incorporates the extracted information into feature-based matrix factorization for more effective product recommendation. In specific, we propose a bootstrapping approach for the extraction of product adopters from review text and categorize them into a number of different demographic categories. The aggregated demographic information of many product adopters can be used to characterize both products and users in the form of distributions over different demographic categories. We further propose a graph-based method to iteratively update user- and product-related distributions more reliably in a heterogeneous user--product graph and incorporate them as features into the matrix factorization approach for product recommendation. Our experimental results on a large dataset crawled from J ing D ong , the largest B2C e-commerce website in China, show that our proposed framework outperforms a number of competitive baselines for product recommendation.

In recent years, the boundaries between e-commerce and social networking have become increasingly blurred. Many e-commerce Web sites support the mechanism of social login where users can sign on the Web sites using their social network identities such as their Facebook or Twitter accounts. Users can also post their newly purchased products on microblogs with links to the e-commerce product Web pages. In this paper, we propose a novel solution for cross-site cold-start product recommendation, which aims to recommend products from e-commerce Web sites to users at social networking sites in “cold-start” situations, a problem which has rarely been explored before. A major challenge is how to leverage knowledge extracted from social networking sites for cross-site cold-start product recommendation. We propose to use the linked users across social networking sites and e-commerce Web sites (users who have social networking accounts and have made purchases on e-commerce Web sites) as a bridge to map users' social networking features to another feature representation for product recommendation. In specific, we propose learning both users' and products' feature representations (called user embeddings and product embeddings, respectively) from data collected from e-commerce Web sites using recurrent neural networks and then apply a modified gradient boosting trees method to transform users' social networking features into user embeddings. We then develop a feature-based matrix factorization approach which can leverage the learnt user embeddings for cold-start product recommendation. Experimental results on a large dataset constructed from the largest Chinese microblogging service Sina Weibo and the largest Chinese B2C e-commerce website JingDong have shown the effectiveness of our proposed framework.

With the pervasiveness of location-based social networks, it becomes increasingly important to consider the social characteristics of locations shared among persons. Several studies have been proposed to infer social strength by using trajectory similarity. However, these studies have two major shortcomings. First, they rely on the explicit co-occurrence of check-in locations. In this situation, a user pair of two friends who seldom share common locations or a user pair of two strangers who heavily share common visited locations will receive an unreliable estimation of the real social strength between them. Second, these studies do not consider how the overall trajectory patterns of users change with the varying of living styles. In this article, we propose a probabilistic generative model to mine latent lifestyle-related patterns from human trajectory data for inferring social strength. It can automatically learnfunctionality topicsconsisting of locations with similar service functions and transition probabilities over the set of functionality topics. Furthermore, a lifestyle is modeled as a unique transition probability matrix over the set of functionality topics. A user has a preference distribution over the set of lifestyles, and he or she is able to select over multiple lifestyles to adapt to different living contexts. The learned lifestyle-related patterns are subsequently used as features in a supervised learner for both strength estimation and link prediction. We conduct extensive experiments to evaluate the performance of the proposed method on two real-world datasets. The experimental results demonstrate the effectiveness of our proposed method.

Subspace recovery from noisy or even corrupted data is critical for various applications in machine learning and data analysis. To detect outliers, Robust PCA (R PCA) via Outlier Pursuit was proposed and had found many successful applications. However, the current theoretical analysis on Outlier Pursuit only shows that it succeeds when the sparsity of the corruption matrix is of O(n/r), where n is the number of the samples and r is the rank of the intrinsic matrix which may be comparable to n. Moreover, the regularization parameter is suggested as 3/(7 squareroot gamma n}, where gamma is a parameter that is not known a priori. In this paper, with incoherence condition and proposed ambiguity condition we prove that Outlier Pursuit succeeds when the rank of the intrinsic matrix is of O(n log n) and the sparsity of the corruption matrix is of O(n). We further show that the orders of both bounds are tight. Thus R-PCA via Outlier Pursuit is able to recover intrinsic matrix of higher rank and identify much denser corruptions than what the existing results could predict. Moreover, we suggest that the regularization parameter be chosen as 1 squareroot{log n}, which is definite. Our analysis waives the necessity of tuning the regularization parameter and also significantly extends the working range of the Outlier Pursuit. Experiments on synthetic and real data verify our theories.

The Riemannian three-factor matrix completion (R3MC) algorithm is one of the state-of-the-art geometric optimization methods for the low-rank matrix completion problem. It is a nonlinear conjugate-gradient method optimizing on a quotient Riemannian manifold. In the line search step, R3MC approximates the minimum point on the searching curve by minimizing on the line tangent to the curve. However, finding the exact minimum point by iteration is too expensive. We address this issue by proposing a new retraction with a minimizing property. This special property provides the exact minimization for the line search by establishing correspondences between points on the searching curve and points on the tangent line. Accelerated R3MC, which is R3MC equipped with this new retraction, outperforms the original algorithm and other geometric algorithms for matrix completion in our empirical study.

Optimization on Riemannian manifolds is an intuitive generalization of the traditional optimization algorithms in Euclidean spaces. In these algorithms, minimizing along a search direction becomes minimizing along a search curve lying on a manifold. Computing such a curve to be subsequently searched upon is itself computational intensive. We propose a new minimization scheme aiming to find a better step size utilizing the first order information of the search curve. We prove that this scheme can provide further reduction for the cost function when the retraction and the vector transport are collinear. Then we adapt this scheme to propose a heuristic strategy for line search. In numerical experiments, we apply this heuristic strategy to one of the geometric algorithms for matrix completion and show its feasibility and the potential in accelerating computation.

This article describes Pan360, a 360 X 180 panorama capturing and viewing product developed and launched by our team, and our demo plan.

The essence of distantly supervised relation extraction is that it is an incomplete multi-label classification problem with sparse and noisy features.To tackle the sparsity and noise challenges, we propose solving the classification problem using matrix completion on factorized matrix of minimized rank.We formulate relation classification as completing the unknown labels of testing items (entity pairs) in a sparse matrix that concatenates training and testing textual features with training labels.Our algorithmic framework is based on the assumption that the rank of item-byfeature and item-by-label joint matrix is low.We apply two optimization models to recover the underlying low-rank matrix leveraging the sparsity of feature-label matrix.The matrix completion problem is then solved by the fixed point continuation (FPC) algorithm, which can find the global optimum.Experiments on two widely used datasets with different dimensions of textual features demonstrate that our low-rank matrix completion approach significantly outperforms the baseline and the state-of-the-art methods.

Sensors on mobile phones and wearables, and in general sensors on IoT (Internet of Things), bring forth a couple of new challenges to big data research. First, the power consumption for analyzing sensor data must be low, since most wearables and portable devices are power-strapped. Second, the velocity of analyzing big data on these devices must be high, otherwise the limited local storage may overflow. This paper presents our hardware-software co-design of a classifier for wearables to detect a person's transportation mode (i.e., still, walking, running, biking, and on a vehicle). We particularly focus on addressing the big-data small-footprint requirement by designing a classifier that is low in both computational complexity and memory requirement. Together with a sensor-hub configuration, we are able to drastically reduce power consumption by 99%, while maintaining competitive mode-detection accuracy. The data used in the paper is made publicly available for conducting research.

A 2011 Gartner report [3] describes context-aware computing as a game-changing opportunity for enterprises to improve both productivity and profits. Context-aware computing is about making applications and content more relevant to a user's context, e.g., when and where the user is, thereby improving user experience. For instance, a coupon delivered to a user at a wrong time or at a wrong location is considered a nuisance. On the contrary, receiving a timely, usable coupon before purchasing a merchandise is a treat. Context-aware computing is not a new concept, but the ongoing mobile revolution makes it both necessary and feasible. • Necessary because the mobile phone display is small and information must be delivered with much higher relevance and precision to meet user needs. • Feasible because small, light-weight mobile devices allow users to almost always carry them around, and much can be learned via a phone about its user's habits and states. Context-aware computing involves first acquiring context and then taking context-dependent actions. For instance, a phone can sense a user's location and turn off its GPS unit to conserve power when the user enters a building, or it can collect EKG signals of a user and trigger an alert if the user's heart beats irregularly. Similarly, a restaurant can send a coupon to a user when that user is queued up in front of a nearby restaurant. The useful context can be divided into three categories: information on the user (knowledge of habits, emotional state, biophysiological conditions), the user's environment (time, location, co-location of others, social interaction), and the user's tasks (transportation mode, engaged tasks, general goals) [4]. Context-aware computing can be applied to benefit applications in many areas including but not limited to information retrieval, facility management, productivity enhancement, in addition to the aforementioned three examples representing power management, health care, and commerce, respectively.

Automatic Subjective Question Answering (ASQA), which aims at answering users'subjective questions using summaries of multiple opinions, becomes increasingly important. One challenge of ASQA is that expected answers for subjective questions may not readily exist in the Web. The rising and popularity of Community Question Answering (CQA) sites, which provide platforms for people to post and answer questions, provides an alternative to ASQA. One important task of ASQA is question subjectivity identification, which identifies whether a user is asking a subjective question. Unfortunately, there has been little labeled training data available for this task. In this paper, we propose an approach to collect training data automatically by utilizing social signals in CQA sites without involving any manual labeling. Experimental results show that our data-driven approach achieves 9.37% relative improvement over the supervised approach using manually labeled data, and achieves 5.15% relative gain over a state-of-the-art semi-supervised approach. In addition, we propose several heuristic features for question subjectivity identification. By adding these features, we achieve 11.23% relative improvement over word n-gram feature under the same experimental setting.

There has been much interest in offering multimedia location-based service (LBS) to indoor users (e.g., sending video/audio streams according to user locations). Offering good LBS largely depends on accurate indoor localization of mobile stations (MSs). To achieve that, in this paper we first model and analyze the error characteristics of important indoor localization schemes, using Radio Frequency Identification (RFID) and Wi-Fi. Our models are simple to use, capturing important system parameters and measurement noises, and quantifying how they affect the accuracies of the localization. Given that there have been many indoor localization techniques deployed, an MS may receive simultaneously multiple co-existing estimations on its location. Equipped with the understanding of location errors, we then investigate how to optimally combine, or fuse, all the co-existing estimations of an MS's location. We present computationally-efficient closed-form expressions to fuse the outputs of the estimators. Simulation and experimental results show that our fusion technique achieves higher location accuracy in spite of location errors in the estimators.

Entity disambiguation with a knowledge base becomes increasingly popular in the NLP community. In this paper, we employ Freebase as the knowledge base, which contains significantly more entities than Wikipedia and others. While huge in size, Freebase lacks context for most entities, such as the descriptive text and hyperlinks in Wikipedia, which are useful for disambiguation. Instead, we leverage two features of Freebase, namely the naturally disambiguated mention phrases (aka aliases) and the rich taxonomy, to perform disambiguation in an iterative manner. Specifically, we explore both generative and discriminative models for each iteration. Experiments on 2, 430, 707 English sentences and 33, 743 Freebase entities show the effectiveness of the two features, where 90% accuracy can be reached without any labeled data. We also show that discriminative models with proposed split training strategy is robust against over fitting problem, and constantly outperforms the generative ones.

The articles in this special issue focus on web-scale multimedia processing as well as applications for its use.

Location-Based Service (LBS) is rapidly becoming the next ubiquitous technology for a wide range of mobile applications. To support applications that demand nearest-neighbor and history queries, an LBS spatial indexer must be able to efficiently update, query, archive and mine location records, which can be in contention with each other. In this work, we propose MOIST, whose baseline is a recursive spatial partitioning indexer built upon BigTable. To reduce update and query contention, MOIST groups nearby objects of similar trajectory into the same school, and keeps track of only the history of school leaders. This dynamic clustering scheme can eliminate redundant updates and hence reduce update latency. To improve history query processing, MOIST keeps some history data in memory, while it flushes aged data onto parallel disks in a locality-preserving way. Through experimental studies, we show that MOIST can support highly efficient nearest-neighbor and history queries and can scale well with an increasing number of users and update frequency.

In this paper, we investigate the novel problem of automatic question identification in the microblog environment. It contains two steps: detecting tweets that contain questions (we call them "interrogative tweets") and extracting the tweets which really seek information or ask for help (so called "qweets") from interrogative tweets. To detect interrogative tweets, both traditional rule-based approach and state-of-the-art learning-based method are employed. To extract qweets, context features like short urls and Tweet-specific features like Retweets are elaborately selected for classification. We conduct an empirical study with sampled one hour's English tweets and report our experimental results for question identification on Twitter.

To provide live streaming service to mobile users, traditionally each user pulls content from a server over his cellular network. In order to overcome the scalability problem of last-hop bandwidth bottleneck, mobile peer-to-peer (P2P) streaming can be used where mobile devices relay their stream received in a multi-hop manner by means of a secondary channel (such as Wi-Fi or bluetooth). We investigate the design of distributed algorithm termed LocalTree, which minimizes the number of broadcasters while meeting a certain video quality requirement under peer churns. We first formulate the problem and show that it is NP-hard, and hence propose LocalTree which achieves robustness similar to an unstructured mesh and low delay similar to a global tree. Simulation results show that LocalTree outperforms other algorithms substantially in terms of number of broadcasters used (by as much as 50%).

The number of "smart" mobile devices such as wireless phones and tablet computers has been rapidly growing. These mobile devices are equipped with a variety of sensors such as camera, gyroscope, accelerometer, compass, NFC, WiFi, GPS, etc. These sensors can be used to capture images and voice, detect motion patterns, and predict locations, to name just a few. This keynote depicts techniques in configuration, calibration, computation, and fusion for improving sensor performance and conserving power consumption. We also present novel mobile information management and retrieval applications that can benefit a great deal from enhanced sensor technologies.

Spectral clustering algorithms have been shown to be more effective in finding clusters than some traditional algorithms, such as k-means. However, spectral clustering suffers from a scalability problem in both memory use and computational time when the size of a data set is large. To perform clustering on large data sets, we investigate two representative ways of approximating the dense similarity matrix. We compare one approach by sparsifying the matrix with another by the Nyström method. We then pick the strategy of sparsifying the matrix via retaining nearest neighbors and investigate its parallelization. We parallelize both memory use and computation on distributed computers. Through an empirical study on a document data set of 193,844 instances and a photo data set of 2,121,863, we show that our parallel algorithm can effectively handle large problems.

Previous methods of distributed Gibbs sampling for LDA run into either memory or communication bottlenecks. To improve scalability, we propose four strategies: data placement , pipeline processing , word bundling , and priority-based scheduling . Experiments show that our strategies significantly reduce the unparallelizable communication bottleneck and achieve good load balancing, and hence improve scalability of LDA.

The Internet brings us access to multimedia databases with billions of data instances. The massive amount of data available to researchers and application developers brings both opportunities and challenges. In particular, massive amount of data makes data-driven approach feasible, but at the same time, it demands scalable algorithms.

In this paper, we present AdHeat, a social ad model considering user influence in addition to relevance for matching ads. Traditionally, ad placement employs the relevance model. Such a model matches ads with Web page content, user interests, or both. We have observed, however, on social networks that the relevance model suffers from two shortcomings. First, influential users (users who contribute opinions) seldom click ads that are highly relevant to their expertise. Second, because influential users' contents and activities are attractive to other users, hint words summarizing their expertise and activities may be widely preferred. Therefore, we propose AdHeat, which diffuses hint words of influential users to others and then matches ads for each user with aggregated hints. We performed experiments on a large online Q&A community with half a million users. The experimental results show that AdHeat outperforms the relevance model on CTR (click through rate) by significant margins.

Q&A sites continue to flourish as a large number of users rely on them as useful substitutes for incomplete or missing search results. In this paper, we present our experience with developing Confucius, a Google Q&A service launched in 21 countries and four languages by the end of 2009. Confucius employs six data mining subroutines to harness synergy between web search and social networks. We present these subroutines' design goals, algorithms, and their effects on service quality. We also describe techniques for and experience with scaling the subroutines to mine massive data sets.

Confucius is a great teacher in ancient China. His theories and principles were effectively spread throughout China by his disciples. Confucius is the product code name of Google's Knowledge Search product, which is developed at Google Beijing office. In this talk, I present Knowledge Search's key disciples, which are data management subroutines that generate labels for questions, that match existing answers to a question, that evaluate quality of answers, that rank users based on their contributions, that distill high-quality answers for search engines to index, and that route questions to domain experts, and etc. This talk presents scalable algorithms that we have devised to make these disciples effective in dealing with huge datasets. Efforts in making these algorithms run even faster on thousands of machines, and some open research problems will also be presented.

Information extraction from unstructured text has much in common with querying in databases systems. Despite some differences on how data is modeled or represented, the general goal remains the same, i.e. to retrieve data or tag elements that satisfy some user-specified constraints. In recent years, the two paradigms have become much closer thanks to the large volume of data on the World Wide Web and the need for more automated search tools for information extraction and often the need for relating the extracted pieces. Several developments have contributed to the growth of the area including the work on named entity recognition (marked by MUC-6 and subsequent conferences) and natural language processing, Web information retrieval and mining, and Web query languages inspired by the query languages in the relational world. This panel explores the areas where the two paradigms overlap, the impacts and contributions they have had on each other and the areas that may be open for further research. The panel will bring together researchers who have worked in some established areas that closely relate to extracting structured information from unstructured text. In the first (role-playing) round, each panelist will strongly take a side on where the intersection is heading, arguing that one area will subsume the other area in near future. In the second round, the panelists will counter one or two others, pointing out the challenges that one area would be facing in subsuming the other and implications for future research directions.

The amount of online photos and videos is now at the scale of tens of billions. To organize, index, and retrieve these large-scale rich-media data, a system must employ scalable data management and mining algorithms. The research community needs to consider solving large scale problems rather than solving problems with small datasets that do not reflect real life scenarios. This tutorial introduces key challenges in large-scale rich-media data mining, and presents parallel algorithms for tackling such challenges. We present our parallel implementations of Spectral Clustering (PSC), FP-Growth (PFP), Latent Dirichlet Allocation (PLDA), and Support Vector Machines (PSVM).

Users of social networking services can connect with each other by forming communities for online interaction. Yet as the number of communities hosted by such websites grows over time, users have even greater need for effective community recommendations in order to meet more users. In this paper, we investigate two algorithms from very different domains and evaluate their effectiveness for personalized community recommendation. First is association rule mining (ARM), which discovers associations between sets of communities that are shared across many users. Second is latent Dirichlet allocation (LDA), which models user-community co-occurrences using latent aspects. In comparing LDA with ARM, we are interested in discovering whether modeling low-rank latent structure is more effective for recommendations than directly mining rules from the observed data. We experiment on an Orkut data set consisting of 492,104 users and 118,002 communities. Our empirical comparisons using the top-k recommendations metric show that LDA performs consistently better than ARM for the community recommendation task when recommending a list of 4 or more communities. However, for recommendation lists of up to 3 communities, ARM is still a bit better. We analyze examples of the latent information learned by LDA to explain this finding. To efficiently handle the large-scale data set, we parallelize LDA on distributed computers and demonstrate our parallel implementation's scalability with varying numbers of machines.

Rapid growth in the amount of data available on social networking sites has made information retrieval increasingly challenging for users. In this paper, we propose a collaborative filtering method, Combinational Collaborative Filtering (CCF), to perform personalized community recommendations by considering multiple types of co-occurrences in social data at the same time. This filtering method fuses semantic and user information, then applies a hybrid training strategy that combines Gibbs sampling and Expectation-Maximization algorithm. To handle the large-scale dataset, parallel computing is used to speed up the model training. Through an empirical study on the Orkut dataset, we show CCF to be both effective and scalable.

Frequent itemset mining (FIM) is a useful tool for discovering frequently co-occurrent items. Since its inception, a number of significant FIM algorithms have been developed to speed up mining performance. Unfortunately, when the dataset size is huge, both the memory use and computational cost can still be prohibitively expensive. In this work, we propose to parallelize the FP-Growth algorithm (we call our parallel algorithm PFP) on distributed machines. PFP partitions computation in such a way that each machine executes an independent group of mining tasks. Such partitioning eliminates computational dependencies between machines, and thereby communication between them. Through empirical study on a large dataset of 802,939 Web pages and 1,021,107 tags, we demonstrate that PFP can achieve virtually linear speedup. Besides scalability, the empirical study demonstrates that PFP to be promising for supporting query recommendation for search engines.

Rich media data, such as video, imagery, music, and gaming, do no longer play just a supporting role on the World Wide Web to text data. Thanks to Web 2.0, rich media is the primary content on sites such as Flickr, PicasaWeb, YouTube, and QQ. Because of massive user generated content, the volume of rich media being transmitted on the Internet has surpassed that of text. It is vital to properly manage these data to ensure efficient bandwidth utilization, to support effective indexing and search, and to safeguard copyrights (just to name a few). This panel invites both researchers and practitioners to discuss the challenges of Web-scale media-data management. In particular, the panelists will address issues such as leveraging Rich Media and Web 2.0, indexing, search, and scalability.

As the first decade of the 21st century comes to a close, growth in multimedia delivery infrastructure and public demand for applications built on this backbone are converging like never before. The push towards reaching truly interactive multimedia technologies becomes stronger as our media consumption paradigms continue to change. In this paper, we profile a technology leading the way in this revolution: active learning. Active learning is a strategy that helps alleviate challenges inherent in multimedia information retrieval through user interaction. We show how active learning is ideally suited for the multimedia information retrieval problem by giving an overview of the paradigm and component technologies used with special attention given to the application scenarios in which these technologies are useful. Finally, we give insight into the future of this growing field and how it fits into the larger context of multimedia information retrieval.

The kernel methods play a pivotal role in machine learning algorithms. Unfortunately, working with the kernel methods must deal with an n times n kernel matrix, which is memory intensive. In this paper, we present a parallel, approximate matrix factorization algorithm, which loads only essential data to individual processors to enable parallel processing of data. Our method reduces space requirement for the kernel matrix from O(n2) to O(np/m), where n is the amount of data, p the reduced matrix dimension (p << n), and m the number of processors.

Support Vector Machines (SVMs) suffer from a widely recognized scalability problem in both memory use and computational time. To improve scalability, we have developed a parallel SVM algorithm (PSVM), which reduces memory use through performing a row-based, approximate matrix factorization, and which loads only essential data to each machine to perform parallel computation. Let $n$ denote the number of training instances, $p$ the reduced matrix dimension after factorization ($p$ is significantly smaller than $n$), and $m$ the number of machines. PSVM reduces the memory requirement from $\MO$($n^2$) to $\MO$($np/m$), and improves computation time to $\MO$($np^2/m$). Empirical studies on up to $500$ computers shows PSVM to be effective.

For many applications in computer vision and multimedia, similarity between objects is measured by a dissimilarity function that is complex, expensive to compute, and often non-metric. To allow fast distance computations, these objects may be embedded into a vector space, where the distance between the embedding of two objects approximates the actual dissimilarity between them. Traditional sparse embedding methods like FastMap and SparseMap allow embedding a new object into a vector space based on its dissimilarities with only a small set of objects. However, these methods do not optimize embedding quality, and may create embeddings that do not approximate the original dissimilarities well. BoostMap improves embedding quality, but incurs high computational cost. In this work, we propose RCMap, a technique that offers significant speedup over Boostmap, with minimal loss in embedding quality.

In this paper, we propose a latent factor regression model, in which priors are assigned to both the latent regression vector and the error term, by using reproducing kernels. The resulting regression function follows a stochastic process known as a student process. The model is attractive because its implementation is based on a tractable posterior predictive distribution and a simple expectation-maximization (EM) estimation algorithm. In addition, treating the transductive inference as a missing data problem, we devise the EM algorithm to deal with the parameter estimation as well as the response prediction in a single paradigm. The model is also elaborated for multivariate-response regression problems. For this purpose, we present a generalization of multivariate models and some of its properties. Experimental results show our approaches to be effective.

The performance of streaming media servers has been limited by the dual requirements of high disk throughput (to service more clients simultaneously) and low memory use (to decrease system cost). To achieve high disk throughput, disk drives must be accessed with large IOs to amortize disk access overhead. Large IOs imply an increased requirement of expensive DRAM, and, consequently, greater overall system cost. MEMS-based storage, an emerging storage technology, is predicted to offer a price-performance point between those of DRAM and disk drives. In this study, we propose storage architectures that use the relatively inexpensive MEMS-based storage devices as an intermediate layer (between DRAM and disk drives) for temporarily staging large disk IOs at a significantly lower cost. We present data layout mechanisms and synchronized IO scheduling algorithms for the real-time storage and retrieval of streaming data within such an augmented storage system. Analytical evaluation suggests that MEMS-augmented storage hierarchies can reduce the cost and improve the throughput of streaming servers significantly.

Data stream clustering has emerged as a challenging and interesting problem over the past few years. Due to the evolving nature, and one-pass restriction imposed by the data stream model, traditional clustering algorithms are inapplicable for stream clustering. This problem becomes even more challenging when the data is high-dimensional and the clusters are not linearly separable in the input space. In this paper, we propose a nonlinear stream clustering algorithm that adapts to the stream's evolutionary changes. Using the kernel methods for dealing with the non-linearity of data separation, we propose a novel 2-tier stream clustering architecture. Tier-1 captures the temporal locality in the stream, by partitioning it into segments, using a kernel-based novelty detection approach. Tier-2 exploits this segment structure to continuously project the streaming data nonlinearly onto a low-dimensional space (LDS), before assigning them to a cluster. We demonstrate the effectiveness of our approach through extensive experimental evaluation on various real-world datasets.

In recent years, weblogs, or blogs for short, have become an important form of online content. The personal nature of blogs, online interactions between bloggers, and the temporal nature of blog entries, differentiate blogs from other kinds of Web content. Bloggers interact with each other by linking to each other's posts, thus forming online communities. Within these communities, bloggers engage in discussions of certain issues, through entries in their blogs. Since these discussions are often initiated in response to online or offline events, a discussion typically lasts for a limited time duration. We wish to extract such temporal discussions, or stories, occurring within blogger communities, based on some query keywords. We propose a Content-Community-Time model that can leverage the content of entries, their timestamps, and the community structure of the blogs, to automatically discover stories. Doing so also allows us to discover hot stories. We demonstrate the effectiveness of our model through several case studies using real-world data collected from the blogosphere.

Identifying or matching the surface color of a moving object in surveillance video is critical for achieving reliable object-tracking and searching. Traditional color models provide little help, since the surface of an object is usually not flat, the object’s motion can alter the surface’s orientation, and the lighting conditions can vary when the object moves. To tackle this research problem, we conduct extensive data mining on video clips collected under various lighting conditions and distances from several video-cameras. We observe how each of the eleven culture colors can drift in the color space when an object’s surface is in motion. In the color space, we then learn the drift pattern of each culture color for classifying unseen surface colors. Finally, we devise a distance function taking color drift into consideration to perform color identification and matching. Empirical studies show our approach to be very promising: achieving over 95% color-prediction accuracy.

Support Vector Machines (SVMs) suffer from an O(n2) training cost, where n denotes the number of training instances. In this paper, we propose an algorithm to select boundary instances as training data to substantially reduce n. Our proposed algorithm is motivated by the result of (Burges, 1999) that, removing non-support vectors from the training set does not change SVM training results. Our algorithm eliminates instances that are likely to be non-support vectors. In the concept-independent preprocessing step of our algorithm, we prepare nearest-neighbor lists for training instances. In the concept-specific sampling step, we can then effectively select useful training data for each target concept. Empirical studies show our algorithm to be effective in reducing n, outperforming other competing downsampling algorithms without significantly compromising testing accuracy.

Kernel machines have been shown as the state-of-the-art learning techniques for classification. In this paper, we propose a novel general framework of learning the Unified Kernel Machines (UKM) from both labeled and unlabeled data. Our proposed framework integrates supervised learning, semi-supervised kernel learning, and active learning in a unified solution. In the suggested framework, we particularly focus our attention on designing a new semi-supervised kernel learning method, i.e., Spectral Kernel Learning (SKL), which is built on the principles of kernel target alignment and unsupervised kernel design. Our algorithm is related to an equivalent quadratic programming problem that can be efficiently solved. Empirical results have shown that our method is more effective and robust to learn the semi-supervised kernels than traditional approaches. Based on the framework, we present a specific paradigm of unified kernel machines with respect to Kernel Logistic Regresions (KLR), i.e., Unified Kernel Logistic Regression (UKLR). We evaluate our proposed UKLR classification scheme in comparison with traditional solutions. The promising results show that our proposed UKLR paradigm is more effective than the traditional classification approaches.

Traditional decomposition-based solutions to Support Vector Machines (SVMs) suffer from the widely-known scalability problem. For example, given a one-million training set, it takes about six days for SVMLight to run on a Pentium-4 sever with 8G-byte memory. In this paper, we propose an incremental algorithm, which performs approximate matrix-factorization operations, to speed up SVMs. Two approximate factorization schemes, Kronecker and incomplete Cholesky, are utilized in the primal-dual interior-point method (IPM) to directly solve the quadratic optimization problem in SVMs. We found out that a coarse approximate algorithm enjoys good speedup performance but may suffer from poor training accuracy. Conversely, a fine-grained approximate algorithm enjoys good training quality but may suffer from long training time. We subsequently propose an incremental training algorithm, which uses the approximate IPM solution of a coarse factorization to initialize the IPM of a fine-grained factorization. Extensive empirical studies show that our proposed incremental algorithm with approximate factorizations substantially speeds up SVM training while maintaining high training accuracy. In addition, we show that our proposed algorithm is highly parallelizable on an Intel dual-coreprocessor.

Fotowiki (FW) is a wiki-based map service that integrates visual and textual information with map. FW divides a geographical area into sub-areas. An individual responsible for providing information about a sub-area enters collected data into a wiki page. FW uploads distributed wiki-pages, and overlays the information on the map. This demonstration shows FW's architecture and functionalities.

In this work, we present Fotofiti(FF), a web-based personal photo organizer with automatic image annotation, event management and social network integration. We describe our technique for real-time online semantic annotation of user photos. Additionally, a landmark recognition system which utilizes local features is discussed.

In this work we present the details of the implementation of Fotofiti(FF), a website that provides automatic semantic annotation of digital photographs, event management and social network integration. We describe our technique for real-time online semantic annotation using global features from both content and context. Classification experiments using various learning techniques were performed on a realworld data-set. Additionally, a scalable landmark recognition system which utilizes local features is discussed.

A query can be answered by a binary classifier, which separates the instances that are relevant to the query from the ones that are not. When kernel methods are employed to train such a classifier, the class boundary is represented as a hyperplane in a projected space. Data instances that are farthest from the hyperplane are deemed to be most relevant to the query, and that are nearest to the hyperplane to be most uncertain to the query. In this paper, we address the twin problems of efficient retrieval of the approximate set of instances (a) farthest from and (b) nearest to a query hyperplane. Retrieval of instances for this hyperplane-based query scenario is mapped to the range-query problem allowing for the reuse of existing index structures. Empirical evaluation on large image datasets confirms the effectiveness of our approach.

Support vector machines (SVMs) have been adopted by many data mining and information-retrieval applications for learning a mining or query concept, and then retrieving the "top-k" best matches to the concept. However, when the data set is large, naively scanning the entire data set to find the top matches is not scalable. In this work, we propose a kernel indexing strategy to substantially prune the search space and, thus, improve the performance of top-k queries. Our kernel indexer (KDX) takes advantage of the underlying geometric properties and quickly converges on an approximate set of top-k instances of interest. More importantly, once the kernel (e.g., Gaussian kernel) has been selected and the indexer has been constructed, the indexer can work with different kernel-parameter settings (e.g., /spl gamma/ and /spl sigma/) without performance compromise. Through theoretical analysis and empirical studies on a wide variety of data sets, we demonstrate KDX to be very effective. An earlier version of this paper appeared in the 2005 SIAM International Conference on Data Mining. This version differs from the previous submission in providing a detailed cost analysis under different scenarios, specifically designed to meet the varying needs of accuracy, speed, and space requirements, developing an approach for insertion and deletion of instances, presenting the specific computations as well as the geometric properties used in performing the same, and providing detailed algorithms for each of the operations necessary to create and use the index structure.

We present EXTENT, an image annotation system that combines the context and content information to annotate images with metadata that cannot be reliably inferred from either the context or the content alone. EXTENT first applies contextual information for restricting the search scope in an image database and reducing the complexity of ensuing content analysis. It can then afford to use more expensive (hence more robust) algorithms for performing content analysis within the restricted database scope. Our experiments show that effectively combining content with context information can infer metadata with high accuracy

Tasks of image clustering and classification often deal with data of very high dimensions. To alleviate the dimensionality curse, several methods, such as isomap, LLE and KPCA, have recently been proposed and applied to learn low-dimensional, non-linear embedded manifolds in high-dimensional spaces. Unfortunately, the scenarios in which these methods appear to be effective are very contrived. In this work, we empirically examine these methods on a realistic but not-so-difficult dataset. We discuss the promises and limitations of these dimension-reduction schemes.

Tasks of data mining and information retrieval depend on a good distance function for measuring similarity between data instances. The most effective distance function must be formulated in a context-dependent (also application-, data-, and user-dependent) way. In this paper, we propose to learn a distance function by capturing the nonlinear relationships among contextual information provided by the application, data, or user. We show that through a process called the "kernel trick," such nonlinear relationships can be learned efficiently in a projected space. Theoretically, we substantiate that our method is both sound and optimal. Empirically, using several datasets and applications, we demonstrate that our method is effective and useful.

Tasks of information retrieval depend on a good distance function for measuring similarity between data instances. The most effective distance function must be formulated in a context-dependent (also application-, data-, and user-dependent) way. In this paper, we present a novel method, which learns a distance function by capturing the nonlinear relationships among contextual information provided by the application, data, or user. We show that through a process called the "kernel trick," such nonlinear relationships can be learned efficiently in a projected space. In addition to using the kernel trick, we propose two algorithms to further enhance efficiency and effectiveness of function learning. For efficiency, we propose a SMO-like solver to achieve O(N2) learning performance. For effectiveness, we propose using unsupervised learning in an innovative way to address the challenge of lack of labeled data (contextual information). Theoretically, we substantiate that our method is both sound and optimal. Empirically, we demonstrate that our method is effective and useful.

We propose a probabilistic framework that uses influence diagrams to fuse metadata of multiple modalities for photo annotation. We fuse contextual information (location, time, and camera parameters), visual content (holistic and local perceptual features), and semantic ontology in a synergistic way. We use causal strengths to encode causalities between variables, and between variables and semantic labels. Through analytical and empirical studies, we demonstrate that our fusion approach can achieve high-quality photo annotation and good interpretability, substantially better than traditional methods.

Many emerging applications formulate non-metric proximity matrices (non-positive semidefinite), and hence cannot fit into the framework of kernel machines. A popular approach to this problem is to transform the spectrum of the similarity matrix so as to generate a positive semidefinite kernel matrix. In this paper, we explore four representative transformation methods: denoise, flip, diffusion, and shift. Theoretically, we discuss a generalization problem where the test data are not available during transformation, and thus propose an efficient algorithm to address the problem of updating the cross-similarity matrix between test and training data. Extensive experiments have been conducted to evaluate the performance of these methods on several real-world (dis)similarity matrices with semantic meanings.

Support Vector Machines (SVMs) have been adopted by many data-mining and information-retrieval applications for learning a mining or query concept, and then retrieving the “top-k” best matches to the concept. However, when the dataset is large, naively scanning the entire dataset to find the top matches is not scalable. In this work, we propose a kernel indexing strategy to substantially prune the search space and thus improve the performance of top-k queries. Our kernel indexer (KDX) takes advantage of the underlying geometric properties and quickly converges on an approximate set of top-k instances of interest. More importantly, once the kernel (e.g., Gaussian kernel) has been selected and the indexer has been constructed, the indexer can work with different kernel-parameter settings (e.g., γ and δ) without performance compromise. Through theoretical analysis, and empirical studies on a wide variety of datasets, we demonstrate KDX to be very effective.

In kernel machines, such as kernel principal component analysis (KPCA), Gaussian Processes (GPs), and Support Vector Machines (SVMs), the computational complexity of finding a solution is O(n3), where n is the number of training instances. To reduce this expensive computational complexity, we propose using Kronecker factorization, which approximates a positive definite kernel matrix by the Kronecker product of two smaller positive definite matrices. This approximation can speed up the calculation of the kernel-matrix inverse or eigen-decomposition involved in kernel machines. When the two factorized matrices have about the same dimensions, the computational complexity is improved from O(n3) to O(n2). We propose two methods to carry out Kronecker factorization and apply them to speed up KPCA. In Experiments show that our methods can drastically reduce the computation time of kernel machines without any significant degradation in their effectiveness.

The proliferation of digital images and the widespread distribution of digital data that has been made possible by the Internet has increased problems associated with copyright infringement on digital images. Watermarking schemes have been proposed to safeguard copyrighted images, but watermarks are vulnerable to image processing and geometric distortions and may not be very effective. Thus, the content-based detection of pirated images has become an important application. In this paper, we discuss two important aspects of such a replica detection system: distance functions for similarity measurement and scalability. We extend our previous work on perceptual distance functions, which proposed the Dynamic Partial Function (DPF), and present enhanced techniques that overcome the limitations of DPF. These techniques include the Thresholding, Sampling, and Weighting schemes. Experimental evaluations show superior performance compared to DPF and other distance functions. We then address the issue of using these perceptual distance functions to efficiently detect replicas in large image data sets. The problem of indexing is made challenging by the high-dimensionality and the nonmetric nature of the distance functions. We propose using Locality Sensitive Hashing (LSH) to index images while using the above perceptual distance functions and demonstrate good performance through empirical studies on a very large database of diverse images.

Allowing higher-priority requests to preempt ongoing disk IOs is of particular benefit to delay-sensitive and real-time systems. In this paper, we present semi-preemptible IO, which divides disk IO requests into small temporal units of disk commands to improve the preemptibility of disk access. We first lay out main design strategies to allow preemption of each component of a disk access-seek, rotation, and data transfer, namely, seek-splitting, JIT-seek, and chunking. We then present the preemption mechanisms for single and multidisk systems-JIT-preemption and JIT-migration. The evaluation of our prototype system showed that semi-preemptible IO substantially improved the preemptibility of disk access with little loss in disk throughput and that preemptive disk scheduling could improve the response time for high-priority interactive requests.

We propose using one-class, two-class, and multiclass SVMs to annotate images for supporting keyword retrieval of images. Providing automatic annotation requires an accurate mapping of images' low-level perceptual features (e.g., color and texture) to some high-level semantic labels (e.g., landscape, architecture, and animals). Much work has been performed in this area; however, there is a lack of ability to assess the quality of annotation. In this paper, we propose a confidence-based dynamic ensemble (CDE), which employs a three-level classification scheme. At the base-level, CDE uses one-class support vector machines (SVMs) to characterize a confidence factor for ascertaining the correctness of an annotation (or a class prediction) made by a binary SVM classifier. The confidence factor is then propagated to the multiclass classifiers at subsequent levels. CDE uses the confidence factor to make dynamic adjustments to its member classifiers so as to improve class-prediction accuracy, to accommodate new semantics, and to assist in the discovery of useful low-level features. Our empirical studies on a large real-world data set demonstrate CDE to be very effective.

An imbalanced training data set can pose serious problems for many real-world data mining tasks that employ SVMs to conduct supervised learning. In this paper, we propose a kernel-boundary-alignment algorithm, which considers THE training data imbalance as prior information to augment SVMs to improve class-prediction accuracy. Using a simple example, we first show that SVMs can suffer from high incidences of false negatives when the training instances of the target class are heavily outnumbered by the training instances of a nontarget class. The remedy we propose is to adjust the class boundary by modifying the kernel matrix, according to the imbalanced data distribution. Through theoretical analysis backed by empirical study, we show that our kernel-boundary-alignment algorithm works effectively on several data sets.

Providing accurate and scalable solutions to map low-level perceptual features to high-level semantics is essential for multimedia information organization and retrieval. In this paper, we propose a confidence-based dynamic ensemble (CDE) to overcome the shortcomings of the traditionalstaticclassifiers. In contrast to the traditional models, CDE can make dynamic adjustments to accommodate new semantics, to assist the discovery of useful low-level features, and to improve class-prediction accuracy. We depict two key components of CDE: a multi-level function that asserts class-prediction confidence, and the dynamic ensemble method based upon the confidence function. Through theoretical analysis and empirical study, we demonstrate that CDE is effective in annotating large-scale, real-world image datasets.

Sequence-data mining plays a key role in many scientific studies and real-world applications such as bioinformatics, data stream, and sensor networks, where sequence data are processed and their semantics interpreted. In this paper we address two relevant issues: sequence-data representation, and representation-to-semantics mapping. For representation, since the best one is dependent upon the application being used and even the type of query, we propose representing sequence data in multiple views. For each representation, we propose methods to construct a valid kernel as the distance function to measure similarity between sequences. For mapping, we then find the best combination of the individual distance functions, which measure similarity of different views, to depict the target semantics. We propose a super-kernel function-fusion scheme to achieve the optimal mapping. Through theoretical analysis and empirical studies on UCI and real world datasets, we show our approach of multi-view representation and fusion to be mathematically valid and very effective for practical purposes.

An imbalanced training dataset poses serious problem for many real-world supervised learning tasks. In this paper, we propose a kernel-boundary-alignment algorithm, which considers training-data imbalance as prior information to augment SVMs to improve class-prediction accuracy. Using a simple example, we first show that SVMs can suffer from high incidences of false negatives when the training instances of the target class are heavily outnumbered by the training instances of a nontarget class. The remedy we propose is to adjust the class boundary by modifying the kernel matrix, according to the imbalanced data distribution. Through theoretical analysis backed by empirical study, we show that our kernel-boundary-alignment algorithm works effectively on several datasets.

Video media carries multimodal information including visual, audio, textual data. Considerable research has been focused on utilizing multimodal features for better understanding of video content. However, many problems remain such as how to combine multimodal features and what are the effects of different combinations. In this paper, we propose to find the optimal combination of multimodal information in order to improve the performance of video concept detection using two methods, one is gradient-descent-optimization linear fusion and the other is super-kernel nonlinear fusion. Gradient-descent-optimization linear fusion learns an optimal weighted linear combination of single modalities based on fusing individual kernel matrices with gradient descent techniques. Super-kernel nonlinear fusion trains separate classifiers for single modalities as the first step. Once individual models have been designed, super-kernel nonlinear fusion learns an optimal nonlinear combination of individual models by fusing single-modality classifiers. Our experiments show that both methods improve performance significantly on TREC-Video 2003 benchmarks.

For over a decade, query-by-one-example has been a popular query paradigm for multimedia information retrieval. We show, by analyzing feature-to-semantics mapping, that such a paradigm cannot realistically lead to a scalable, satisfactory query performance. More specifically, we cluster a small image dataset based on the images' perceptual features, and show that these image clusters are not coherent to the semantic categories of the images. Though some image categories are well separated from the others in the input space formed by the perceptual features, most categories are colocated in more than one cluster. For a query-concept that is mixed with others in a number of clusters, the query-by-one-example paradigm simply lacks information to identify clearly the target query-concept, and hence cannot achieve satisfactory query results.

Active learning has been shown to be a viable tool for learning complex, subjective query concepts with a small number of training instances. In this work, we compare four active-learning algorithms and study the best sample-selection strategies. We also discuss two scalability issues of active learning: scalability in dataset size, and scalability in concept complexity. To address these challenges, we suggest future directions that research might take.

With the proliferation of inexpensive cameras, availability of large-capacity disk storage, and the ubiquitous presence of high-speed, broad-band communication networks, it is now economically and technically feasible to construct and deploy multi-camera video surveillance systems. In line with this is the need of intelligent, robust, (semi-)automated video analysis paradigms to assist the operators in scene analysis and event classification. In this paper, we summarize our current research work toward realizing such a multi-camera video surveillance system. Interested readers can visit our web sites http://www.ece.ucsb.edu//sup /spl sim//echang and http://www.cs.ucsb.edu//sup /spl sim//yfwang for more information.

It has been established that active learning is effective for learning complex, subjective query concepts for image retrieval. However, active learning has been applied in a concept independent way, (i.e., the kernel-parameters and the sampling strategy are identically chosen) for learning query concepts of differing complexity. In this work, we first characterize a concept's complexity using three measures: hit-rate, isolation and diversity. We then propose a multimodal learning approach that uses images' semantic labels to guide a concept-dependent, active-learning process. Based on the complexity of a concept, we make intelligent adjustments to the sampling strategy and the sampling pool from which images are to be selected and labeled, to improve concept learnability. Our empirical study on a $300$K-image dataset shows that concept-dependent learning is highly effective for image-retrieval accuracy.

Considerable research has been devoted to utilizing multimodal features for better understanding multimedia data. However, two core research issues have not yet been adequately addressed. First, given a set of features extracted from multiple media sources (e.g., extracted from the visual, audio, and caption track of videos), how do we determine the best modalities? Second, once a set of modal-ities has been identified, how do we best fuse them to map to se-mantics? In this paper, we propose a two-step approach. The first step finds statistically independent modalities from raw features. In the second step, we use super-kernel fusion to determine the optimal combination of individual modalities. We carefully ana-lyze the tradeoffs between three design factors that affect fusion performance: modality independence, curse of dimensionality, and fusion-model complexity. Through analytical and empirical studies, we demonstrate that our two-step approach, which achieves a care-ful balance of the three design factors, can improve class-prediction accuracy over traditional techniques.

To answer user queries efficiently, a stream management system must handle continuous, high-volume, possibly noisy, and time-varying data streams. One major research area in stream management seeks to allocate resources (such as network bandwidth and memory) to query plans, either to minimize resource usage under a precision requirement, or to maximize precision of results under resource constraints. To date, many solutions have been proposed; however, most solutions are ad hoc with hard-coded heuristics to generate query plans. In contrast, we perceive stream resource management as fundamentally a filtering problem, in which the objective is to filter out as much data as possible to conserve resources, provided that the precision standards can be met. We select the Kalman Filter as a general and adaptive filtering solution for conserving resources. The Kalman Filter has the ability to adapt to various stream characteristics, sensor noise, and time variance. Furthermore, we realize a significant performance boost by switching from traditional methods of caching static data (which can soon become stale) to our method of caching dynamic procedures that can predict data reliably at the server without the clients' involvement. In this work we focus on minimization of communication overhead for both synthetic and real-world streams. Through examples and empirical studies, we demonstrate the flexibility and effectiveness of using the Kalman Filter as a solution for managing trade-offs between precision of results and resources in satisfying stream queries.

Using cameras for detecting hazardous or suspicious events has spurred new research for security concerns. To make such detection reliable, researchers trust overcome difficulties such as variation in camera capabilities, environmental factors. imbalances of positive and negative training data, and asymmetric costs of misclassifying events of different classes. Following up on the event-detection framework (Wu et al. (2003)) that we have proposed, we present in this paper the framework's two major components: invariant feature extraction and biased statistical inference. We report results of our experiments using the framework for detecting suspicious motion events in a parking lot.

Dynamic Partial Function (DPF), which dynamically selects a subset of features to measure pairwise image similarity, has been shown to be very effective in near-replica image recognition. DPF, however, suffers from the one-size-fits-all problem: it requires that all pairwise similarity measurements must use the same number of features. We propose methods for enhancing DPF's performance by allowing different numbers of features to be selected in a pairwise manner. Through extensive empirical studies, we show that our three schemes: thresholding, sampling and weighting, and hybrid schemes of these three basic approaches, substantially outperform DPF in near-replica image recognition.

The performance of streaming media servers has been limited due to the dual requirements of high throughput and low memory use. Although disk throughput has been enjoying a 40% annual increase, slower improvements in disk access times necessitate the use of large DRAM buffers to improve the overall streaming throughput. MEMS-based storage is an exciting new technology that promises to bridge the widening performance gap between DRAM and disk-drives in the memory hierarchy. We explore the impact of integrating these devices into the memory hierarchy on the class of streaming media applications. We evaluate the use of MEMS-based storage for buffering and caching streaming data. We also show how a bank of k MEMS devices can be managed in either configuration and that they can provide a k-fold improvement in both throughput and access latency. An extensive analytical study shows that using MEMS storage can reduce the buffering cost and improve the throughput of streaming servers significantly.

For effective retrieval of visual information, statistical learning plays a pivotal role. Statistical learning in such a context faces at least two major mathematical challenges: scarcity of training data, and imbalance of training classes. We present these challenges and outline our methods for addressing them: active learning, recursive subspace co-training, adaptive dimensionality reduction, class-boundary alignment, and quasi-bagging.

The proliferation of objectionable information on the Internet has reached a level of serious concern. To empower end-users with the choice of blocking undesirable and offensive websites, we propose a multimodal information filter, named MORF. In this paper, we present MORF's core components: its confidence-based classifier, a Cross-bagging ensemble scheme, and multimodal classification algorithm. Empirical studies and initial statistics collected from the MORF filters deployed at sites in the U.S. and Asia show that MORF is both efficient and effective, due to our classification methods.

Providing accurate and scalable solutions to map low-level perceptual features to high-level semantics is critical for multimedia information organization and retrieval. In this paper, we propose a confidence-based dynamic ensemble (CDE) to overcome the shortcomings of the traditional static classifiers. In contrast to the traditional models, CDE can make dynamic adjustments to accommodate new semantics, to assist the discovery of useful low-level features, and to improve class-prediction accuracy. We depict two key components of CDE: a multi-level function that asserts class-prediction confidence, and the dynamic ensemble method based upon the confidence function. Through theoretical analysis and empirical study, we demonstrate that CDE is effective in annotating large-scale, real-world image datasets.

We present a framework for multi-camera video surveillance. The framework consists of three phases: detection, representation, and recognition. The detection phase handles multi-source spatio-temporal data fusion for efficiently and reliably extracting motion trajectories from video. The representation phase summarizes raw trajectory data to construct hierarchical, invariant, and content-rich descriptions of the motion events. Finally, the recognition phase deals with event classification and identification on the data descriptors. Because of space limits, we describe only briefly how we detect and represent events, but we provide in-depth treatment on the third phase: event recognition. For effective recognition, we devise a sequence-alignment kernel function to perform sequence data learning for identifying suspicious events. We show that when the positive training instances (i.e., suspicious events) are significantly outnumbered by the negative training instances (benign events), then SVMs (or any other learning methods) can suffer a high incidence of errors. To remedy this problem, we propose the kernel boundary alignment (KBA) algorithm to work with the sequence-alignment kernel. Through empirical study in a parking-lot surveillance setting, we show that our spatio-temporal fusion scheme and biased sequence-data learning method are highly effective in identifying suspicious events.

We propose a content-based soft annotation (CBSA) procedure for providing images with semantical labels. The annotation procedure starts with labeling a small set of training images, each with one single semantical label (e.g., forest, animal, or sky). An ensemble of binary classifiers is then trained for predicting label membership for images. The trained ensemble is applied to each individual image to give the image multiple soft labels, and each label is associated with a label membership factor. To select a base binary-classifier for CBSA, we experiment with two learning methods, support vector machines (SVMs) and Bayes point machines (BPMs), and compare their class-prediction accuracy. Our empirical study on a 116-category 25K-image set shows that the BPM-based ensemble provides better annotation quality than the SVM-based ensemble for supporting multimodal image retrievals.

The use of interactive media has already gained considerable popularity. Interactivity gives viewers VCR controls like slow-motion, pause, fast-forward, and instant replay. However, traditional server-based or client-based approaches for supporting interactivity either consume too much network bandwidth or require large client buffering; and hence they are economically unattractive. We propose the architecture and design of an interactive media proxy (IMP) server that transforms noninteractive broadcast or multicast streams into interactive ones for servicing a large number of end users. For IMP to work cost-effectively, it must carefully manage its storage devices, which are needed for caching voluminous media data. In this regard, we propose a fine-grained device management strategy consisting of three complementary components: disk profiler, data placement, and IO scheduler. Through quantitative analysis and experiments, we show that these fine-grained strategies considerably improve device throughput under various workload scenarios.

Specifying exact query concepts has become increasingly challenging to end-users. This is because many query concepts (e.g., those for looking up a multimedia object) can be hard to articulate, and articulation can be subjective. In this study, we propose a query-concept learner that learns query criteria through an intelligent sampling process. Our concept learner aims to fulfill two primary design objectives: (1) it has to be expressive in order to model most practical query concepts and (2) it must learn a concept quickly and with a small number of labeled data since online users tend to be too impatient to provide much feedback. To fulfill the first goal, we model query concepts in k -CNF, which can express almost all practical query concepts. To fulfill the second design goal, we propose our maximizing expected generalization algorithm (MEGA), which converges to target concepts quickly by its two complementary steps: sample selection and concept refinement. We also propose a divide-and-conquer method that divides the concept-learning task into G subtasks to achieve speedup. We notice that a task must be divided carefully, or search accuracy may suffer. Through analysis and mining results, we observe that organizing image features in a multiresolution manner, and minimizing intragroup feature correlation, can speed up query-concept learning substantially while maintaining high search accuracy. Through examples, analysis, experiments, and a prototype implementation, we show that MEGA converges to query concepts significantly faster than traditional methods.

For almost a decade, Content-Based Information Retrieval has been an active research area, yet two fundamental problems remain largely unsolved: how best to learn users' query concepts, and how to measure perceptual similarity. To learn subjective query concepts, most systems use relevance feedback techniques. However, these traditional techniques often require a large number of training instances to converge to a concept, and a typical online user may be too impatient to provide much feedback. Thus traditional relevance feedback techniques are ineffective. To measure perceptual similarity, most researchers employ the Minkowski metric or the L-norm distance function. Our extensive data-mining experiments on visual data show that, unfortunately, the Minkowski-type metric is ineffective in modeling perceptual similarity. In this paper, we report the progress we have made recently in developing more effective methods for learning and measuring perceptual similarity, and our future research plans.

This paper presents the architecture and implementation of XTREAM, a high-performance streaming multimedia system. XTREAM is supported by its three core components: IO scheduler, request handler, and admission controller. Via extensive experiments, we show that, thanks to these core components, XTREAM can achieve a low response time as well as high throughput and high-quality service to simultaneous clients.

Images must be annotated to support keyword searches. Sometimes, annotation can be extracted from the surrounding text, but often times, laborious manual annotation cannot be avoided. To minimize effort in manual annotation, we propose using active learning. Active learning selects the most semantically ambiguous images for users to label, and then propagates these labels to the rest of the images. Our experiments on a sample image-dataset show that active learning can drastically reduce manual annotation effort (by as much as 70%) to achieve high annotation accuracy.

A shot transition occurs when a frame fails to maintain perceptual continuity with its previous frame. To maintain perceptual continuity, two consecutive frames must contain similar perceptual features. We propose using the dynamic partial function (DPF) as the inter-frame distance function to detect perceptual discontinuity, and hence the boundary of a shot. Through analysis and experiments, we show that DPF is more effective than traditional distance functions for detecting shot transitions. We also discuss the foundation of DPF in cognitive psychology.

The Bayes point machine (BPM) has been demonstrated theoretically to have better learning ability than the support vector machine (SVM). We describe these two machines and tell how they differ. We empirically compare the performance of the BPM and the SVM on an image dataset. We conclude that the SVM is more attractive for the image classification task because it requires a much shorter training time, despite the fact that the BPM achieves slightly higher classification accuracy.

Supporting preemptible disk access is essential for interactive multimedia applications that require short response time. In this study, we propose Virtual IO, an abstraction for disk IO, that transforms a non-preemptible IO request into a preemptible one. In order to achieve its objective efficiently, Virtual IO uses disk profiling to obtain accurate and detailed knowledge about the disk. Upon implementation of Virtual IO, we show that not only does Virtual IO enable highly preemptible disk access, but it does so with little or no loss in disk throughput.

To date, almost all research work in the Content-Based Image Retrieval (CBIR) community has used Minkowski-like functions to measure similarity between images. In this paper, we first present a non-metric distance function, dynamic partial function (DPF), which works significantly better than Minkowski-like functions for measuring perceptual similarity; and we explain DPF's link to similarity theories in cognitive science. We then propose DynDex, an indexing method that deals with both the dynamic and non-metric aspects of the distance function. DynDex employs statistical methods including distance-based classification and bagging to enable efficient indexing with DPF. In addition to its efficiency for conducting similarity searches in very high-dimensional spaces, we show that DynDex remains effective when features are weighted dynamically for supporting personalized searches.

We demonstrate PBIR-MM, an integrated system that we have built for conducting multimodal image retrieval. The system combines the strengths of content-based soft annotation (CBSA), multimodal relevance feedback through active learning, and perceptual distance formulation and indexing. PBIR-MM supports multimodal query and annotation in any combination of its three basic modes: seed-by-nothing, seed-by-keywords, and seed-by-content. We demonstrate PBIR-MM on a couple of very large image sets provided by image vendors and crawled from the Internet.

We present a clustering and indexing paradigm (called Clindex) for high-dimensional search spaces. The scheme is designed for approximate similarity searches, where one would like to find many of the data points near a target point, but where one can tolerate missing a few near points. For such searches, our scheme can find near points with high recall in very few IOs and perform significantly better than other approaches. Our scheme is based on finding clusters and, then, building a simple but efficient index for them. We analyze the trade-offs involved in clustering and building such an index structure, and present extensive experimental results.

We study how the SVM-based binary classifiers can be effectively combined to tackle the multi-class image classification problem. We study several ensemble schemes, including OPC (one per class), PWC (pairwise coupling), and ECOC (error-correction output coding), that aim to achieve good error correction capability through redundancy. To enhance these ensemble schemes' accuracy, we propose methods that on the one hand boost the margins (i.e., confidence) of the SVM-based binary classifiers, and, on the other hand, remove the noise of irrelevant classifiers from class prediction. From empirical study we show that our margin boosting and noise reduction methods lead to higher classification accuracy than ensemble schemes that are solely designed for maximum error correction capability.

In this paper we discuss how to use a one-dimensional classifier for solving high dimensional classification problems. We propose Spin Discriminant Analysis (SDA), which enables us to construct a family of new classifiers. We prove that SDA is equivalent to ridged Linear Discriminant Analysis (LDA) when two classes are Gaussians with common covariance matrices. Moreover, we prove that classification based on Parzen's window, is a special case of SDA. In addition to theoretical investigations, we conduct extensive empirical studies, implementing SDA using Support Vector Machines (SVMs) as its one-dimensional classifiers. This SVM-based SDA implementation is named SpinSVM. Our experiments show that SpinSVM outperforms traditional high dimensional classifiers like SVMs, Classification Using Spline (CUS), classification-based Parzen's window, and LDA on most standard and synthetic datasets we tested.

True-VOD provides an interactive on-demand (i.e., virtually zero start-up delay) video service by allocating each user a dedicated stream. Such a streaming technique, however, cannot scale up to accommodate a large number of users. A more scalable solution is to use multicasting and client buffering. In this paper, we propose a client-initiated (client-pull) on-demand scheme in which short unicast streams are used to "merge" users onto the existing multicast streams by means of pre-buffering. The scheme is observed to trade-off some bandwidth with lower buffer requirement as compared with a previously proposed scheme. We then propose and analyze a server-initiated (server-push) scheme for on-demand interactive applications. The scheme is shown to offer a service level similar to true-VOD with substantially (many times) lower bandwidth, even with high user interactivity (e.g., averaged ten VCR commands/viewing).

The number of features required to depict an image can be very large. Using all features simultaneously to measure image similarity and to learn image query-concepts can suffer from the problem of dimensionality curse, which degrades both search accuracy and search speed. Regarding search accuracy, the presence of irrelevant features with respect to a query can contaminate similarity measurement, and hence decrease both the recall and precision of that query. To remedy this problem, we present a mining method that learns online users' query concepts and identifies important features quickly. Regarding search speed, the presence of a large number of features can slow down query-concept learning and indexing performance. We propose a divide-and-conquer method that divides the concept-learning task into G subtasks to achieve speedup. We notice that a task must be divided carefully, or search accuracy may suffer. We thus propose a genetic-based mining algorithm to discover good feature groupings. Through analysis and mining results, we observe that organizing image features in a multi-resolution manner and minimizing intra-group feature correlation, can speed up query-concept learning substantially while maintaining high search accuracy.

In this paper, we propose an active and inductive combined learning method to learn users’ image query concepts. We model query concepts in -CNF, which can be used to express most practical queries. To learn a user’s query concept, we propose MEGA. MEGA initializes a user’s query concept as the conjunction of all disjunctions of at most length of the predicates. It then intelligently selects unlabeled data to present to the user for gathering information to eliminate the maximum expected number of disjunctions. MEGA maximizes the usefulness of each example it generates for learning a user’s query concept and hence expedites the convergence to the target concept. Through analysis and experiments, we show that MEGA can learn a complex image query concept much faster than some traditional schemes.

In this paper, we propose an interactive DTV design that converts non-interactive broadcast DTV streams into interactive ones for multiple simultaneous viewers. To enable viewing interactivity, we show that it is critical to organize data intelligently for improving IO resolution, reducing disk latency and minimizing storage cost. We propose three data placement schemes that offer different tradeoffs between IO resolution, disk latency and storage. By employing different schemes under different workload scenarios, an intelligent system can minimize memory use and hence the system cost.

Various systems have been developed for supporting content-based image retrieval. Most systems make very strong assumptions in modeling users’ query concepts. However, since the information need of users can be very diverse, these assumptions may not always hold and hence can lead to poor search results. For instance, if a system assumes that the query-concept is convex but a user issues a disjunctive query, and vice versa, the search result cannot be satisfactory. In this study, we propose a method that can approximate more complex (non-convex and disjunctive) query concepts. Our method uses intelligent modeling and learning to increase query speed and accuracy. Empirical results show that our method converges consistently faster than some traditional approaches on different datasets.

We describe the Perception-Based Image Retrieval (PBIR) system that we have built on our recently developed query-concept learning algorithms, MEGA and SVMActive. We show that MEGA and SVMActive can learn a complex image-query concept in a small number of user iterations (usually three to four) on a large, multi-category, high-dimensional image database.

Relevance feedback is often a critical component when designing image databases. With these databases it is difficult to specify queries directly and explicitly. Relevance feedback interactively determinines a user's desired output or query concept by asking the user whether certain proposed images are relevant or not. For a relevance feedback algorithm to be effective, it must grasp a user's query concept accurately and quickly, while also only asking the user to label a small number of images. We propose the use of a support vector machine active learning algorithm for conducting effective relevance feedback for image retrieval. The algorithm selects the most informative images to query a user and quickly learns a boundary that separates the images that satisfy the user's query concept from the rest of the dataset. Experimental results show that our algorithm achieves significantly higher search accuracy than traditional query refinement schemes after just three to four rounds of relevance feedback.

We demonstrate a system that we have built on our proposed perception-based image retrieval (PBIR) paradigm. This PBIR system achieves accurate similarity measurements by rooting image characterization in human perception and by learning user's query concept through an intelligent sampling process. We show that our system can usually grasp a user's query concept with a small number of labeled instances.

In information-integration systems, sources may have diverse and limited query capabilities. To obtain maximum information from these restrictive sources to answer a query, one can access sources that are not specified in the query (i.e., off-query sources). In this article, we propose a query-planning framework to answer queries in the presence of limited access patterns. In the framework, a query and source descriptions are translated to a recursive datalog program. We then solve optimization problems in this framework, including how to decide whether accessing off-query sources is necessary, how to choose useful sources for a query, and how to test query containment. We develop algorithms to solve these problems, and thus construct an efficient program to answer a query.

In information-integration systems, sources may have diverse and limited query capabilities. We show that because sources have restrictions on retrieving their information, sources not mentioned in a query can contribute to the query result by providing useful bindings. In some cases we can access sources repeatedly to retrieve bindings to answer a query, and query planning thus becomes considerably more challenging. We find all the obtainable answers to a query by translating the query and source descriptions to a simple recursive Datalog program, and evaluating the program on the source relations. This program often accesses sources that are not in the query. Some of these accesses are essential, as they provide bindings that let us query sources, which we could not do otherwise. However, some of these accesses can be proven not to add anything to the query's answer. We show in which cases these off-query accesses are useless, and prove that in these cases we can compute the complete answer to the query by using only the sources in the query. In the cases where off-query accesses are necessary, we propose an algorithm for finding all the useful sources for a query. We thus solve the optimization problem of eliminating the unnecessary source accesses, and optimize the program to answer the query.

Article πDTV: a client-based interactive DTV architecture Share on Author: Edward Y. Chang Department of Electrical & Computer Engineering, University of California, Santa Barbara Department of Electrical & Computer Engineering, University of California, Santa BarbaraView Profile Authors Info & Claims MULTIMEDIA '99: Proceedings of the seventh ACM international conference on Multimedia (Part 2)October 1999 Pages 111–114https://doi.org/10.1145/319878.319908Online:01 October 1999Publication History 1citation334DownloadsMetricsTotal Citations1Total Downloads334Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

article Free Access Share on PowerBookmarks: a system for personalizable Web information organization, sharing, and management Authors: Wen-Syan Li C&C Research Laboratories, NEC USA, Inc., 110 Rio Robles, M/S SJ1OO, San Jose, CA C&C Research Laboratories, NEC USA, Inc., 110 Rio Robles, M/S SJ1OO, San Jose, CAView Profile , Quoc Vu C&C Research Laboratories, NEC USA, Inc., 110 Rio Robles, M/S SJ1OO, San Jose, CA C&C Research Laboratories, NEC USA, Inc., 110 Rio Robles, M/S SJ1OO, San Jose, CAView Profile , Edward Chang C&C Research Laboratories, NEC USA, Inc., 110 Rio Robles, M/S SJ1OO, San Jose, CA C&C Research Laboratories, NEC USA, Inc., 110 Rio Robles, M/S SJ1OO, San Jose, CAView Profile , Divyakant Agrawal View Profile , Kyoji Hirata View Profile , Sougata Mukherjea View Profile , Yi-Leh Wu View Profile , Corey Bufi View Profile , Chen-Chuan Kevin Chang View Profile , Yoshinori Hara C&C Research Laboratories, NEC USA, Inc., 110 Rio Robles, M/S SJ1OO, San Jose, CA C&C Research Laboratories, NEC USA, Inc., 110 Rio Robles, M/S SJ1OO, San Jose, CAView Profile , Reiko Ito 5th Development Department, 2nd Computers Software Division, NEC Corporation, 1-10, Nisshin-Cho, Fuchu-Shi, Tokyo 183-8501, Japan 5th Development Department, 2nd Computers Software Division, NEC Corporation, 1-10, Nisshin-Cho, Fuchu-Shi, Tokyo 183-8501, JapanView Profile , Yutaka Kimura 5th Development Department, 2nd Computers Software Division, NEC Corporation, 1-10, Nisshin-Cho, Fuchu-Shi, Tokyo 183-8501, Japan 5th Development Department, 2nd Computers Software Division, NEC Corporation, 1-10, Nisshin-Cho, Fuchu-Shi, Tokyo 183-8501, JapanView Profile , Kezuyuki Shimazu 5th Development Department, 2nd Computers Software Division, NEC Corporation, 1-10, Nisshin-Cho, Fuchu-Shi, Tokyo 183-8501, Japan 5th Development Department, 2nd Computers Software Division, NEC Corporation, 1-10, Nisshin-Cho, Fuchu-Shi, Tokyo 183-8501, JapanView Profile , Yukiyoshi Saito 5th Development Department, 2nd Computers Software Division, NEC Corporation, 1-10, Nisshin-Cho, Fuchu-Shi, Tokyo 183-8501, Japan 5th Development Department, 2nd Computers Software Division, NEC Corporation, 1-10, Nisshin-Cho, Fuchu-Shi, Tokyo 183-8501, JapanView Profile Authors Info & Claims ACM SIGMOD RecordVolume 28Issue 2June 1999 pp 565–567https://doi.org/10.1145/304181.304578Online:01 June 1999Publication History 22citation480DownloadsMetricsTotal Citations22Total Downloads480Last 12 Months6Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Interactive multimedia applications require fast response time.Traditional disk scheduling schemes can incur high latencies, and caching data in memory to reduce latency is usually not feasible, especially if fast-scans need to be supported.In this study we propose a disk-based solution called BubbleUp.It significantly reduces the initial latency for new requests, as well as for fast-scan requests.The throughput of the scheme is comparable to that of traditional schemes, and it may even provide better throughput than mechanisms based on elevator disk scheduling.BubbleUp incurs a slight disk storage overhead, but we argue that through effective allocation, this cost can be minimized.

We consider the placement of scalable video data on single and multiple disks for storage and real-time retrieval. For the single-disk case, we extend the principle of constant frame grouping from constant bit rate (CBR) to variable bit rate (VBR) scalable video data. When the number of admitted users exceeds the server capacity, the rate of data sent to each user is reduced to relieve the disk system overload, offering a graceful degradation in comparison with nonscalable data. We examine the qualities of video reconstructions obtained from a real disk video server and find the scalable video more visually appealing. In the VBR case, scalability is also used to improve interactivity by reducing the delay associated with using interactive functions in a predictive admission control environment. Finally, we consider the multiple disk scenario and prove that periodic interleaving results in lower system delay than striping in a video server using round-robin scheduling. We verify the results through detailed simulation of a four-disk array.

In this paper we compare techniques for storage and real-time retrieval of variable bit rate (VBR) video data for multiple simultaneous users. We compare two main classes of data placement techniques: constant time length (CTL) and constant data length (CDL). For each technique, we consider both deterministic and statistical admissions control policies and show that the statistical policies are more suitable for interactive applications. CDL-based data placement is shown to be able to achieve lower overload probabilities than CTL-based ones for a given user distribution at the expense of a much higher buffer requirement and higher delays. A "burst mode" technique for CDL is discussed that can reduce the delays at the expense of even higher buffer usage. We verify our theoretical overload probabilities for the statistical admissions control policies with experiments run on a discrete event simulator.>

Presents a compositional proof system for the verification of real-time systems. Real-time systems are modeled as timed transition modules, which explicitly model interaction with the environment and may be combined using composition operators. Composition rules are devised such that the correctness of a system may be determined from the correctness of its components. These proof rules are demonstrated on Fischer's mutual exclusion algorithm, for which mutual exclusion and bounded response are proven.>