21143930
An I/O Optimal and Scalable Skyline Query Algorithm
Given a set of d-dimensional points, skyline query returns the points that are not dominated by any other point on all dimensions. Currently, BBS (branch-and-bound skyline) is the most efficient skyline processing method over static data in a centralized setting. Although BBS has some desirable features (e.g., I/O optimal and flexibility), it requires large main-memory consumption. In this paper, we present an improved skyline computation algorithm based on best-first nearest neighbor search, called IBBS, which captures the optimal I/O and less memory space (i.e., IBBS visits and stores only those entries that contribute to the final skyline). Its core enables several effective pruning strategies to discard non-qualifying entries. Extensive experimental evaluations show that IBBS outperforms BBS in both scalability and efficiency for most cases, especially in low dimensions.
17619661
Your way your missions: from location-based to route-based pervasive gaming
In this paper, we describe the design and implementation of a route-based pervasive game named Your Way Your Missions (YWYM). Since the game obtains the planned routes of players and returns missions in the routes, players can play the game in a casual way, without changing their routes to respond to picked up missions. A self-reporting method is proposed to obtain the planned routes of players, and a corresponding route defining tool is developed upon Google Maps. Two approaches to realize route-based mission adaptation with spatial databases are presented.
11794423
An adaptive consistency maintenance approach for replicated continuous applications
Consistency maintenance is a key problem to replicated continuous applications and dead reckoning (DR) algorithm is widely used in this area. In order to eliminate short-term inconsistency caused by DR algorithm, local-lag approach was proposed. For the purpose of simplicity, fixed lag value is used by local-lag approach and the performance of the approach is greatly deteriorated. In this paper, an adaptive consistency maintenance approach, which is based on local-lag approach, is proposed. The new approach can adjust lag value according to the estimated typical network latency. In order to ensure the criterion of consistency correctness, a lag value adjustment method is also proposed. Through two experiments, the performance of the new approach is evaluated and the results indicate that it is feasible and can greatly improve the performance of the application.
41643555
A Fuzzy Dead Reckoning Algorithm for Distributed Interactive Applications
A fuzzy Dead Reckoning (DR) algorithm for distributed interactive applications is proposed in this paper. Since fixed threshold cannot adequately handle the dynamic relationships between moving entities, some multi-level threshold DR algorithms were proposed in the past few years. In these algorithms the level of threshold is adaptively adjusted based on the distance between entities. The proposed fuzzy DR algorithm is based on multi-level threshold DR algorithm and takes all properties of entity (e.g. position, size and view angle etc.) into consideration when adjusting the level of threshold. This algorithm employs fuzzy correlation degree to measure the relationships between entities and determine the level of threshold for DR algorithm. Fuzzy consistent relation is used to distribute weight for each property. Simulation results indicate that fuzzy DR algorithm can achieve a considerable reduction in the number of state update messages while maintaining adequate accuracy in extrapolation.
14850996
Effects of network characteristics on task performance in a desktop CVE system
The influences of network characteristics on the task performance in a desktop collaborative virtual environment (CVE) system were studied. In the experiment, two participants worked together to accomplish a collaborative task and a network emulator was utilized to simulate real network characteristics. The task used in the experiment was designed to be highly interactive and had rigid requirements on network characteristics (e.g. latency and packet loss). The objective performance and subjective assessment were recorded and analyzed quantitatively as a function of network latency and packet loss rate. The experiment results show that network latency has no distinct effect on task performance when network latency is less than 200 ms and lightly affect task performance when network latency is between 200 and 600 ms; packet loss has no effect on task performance when there are 40 state update messages received per second and lightly affect task performance when there are between 15 and 40 state update messages received per second.
40616325
A Color Bar Based Affective Annotation Method for Media Player
Multimedia technology has been developing quickly since the computer was invented. Nowadays, more and more people use media players to watch movies and TV shows on their computer. But it seems that we are too busy sometimes to spare nearly two hours watching a movie from beginning to end. We’d like to find and watch the most exciting episodes that we are interested in as soon as possible. The media players we use often only provide a slider bar for locating, which is rather low in efficiency. Respecting this, an affective annotation method for video clips is proposed in this paper and the method is implemented in an affectively annotated media player. In addition, two experiments were set up to evaluate the proposed method. Experiment results indicate that affective annotation facilitates the subjects in quick locating target events and helps them understand the scenarios better.
6076707
Bridging Nonliving and Living Matter
Assembling non-biological materials (geomaterials) into a proto-organism constitutes a bridge between nonliving and living matter. In this article we present a simple step-by-step route to assemble a proto-organism. Many pictures have been proposed to describe this transition within the origins-of-life and artificial life communities, and more recently alternative pictures have been emerging from advances in nanoscience and biotechnology. The proposed proto-organism lends itself to both traditions and defines a new picture based on a simple idea: Given a set of required functionalities, minimize the physicochemical structures that support these functionalities, and make sure that all structures self-assemble and mutually enhance each other's existence. The result is the first concrete, rational design of a simple physicochemical system that integrates the key functionalities in a thermodynamically favorable manner as a lipid aggregate integrates proto-genes and a proto-metabolism. Under external pumping of free energy, the metabolic processes produce the required building blocks, and only specific gene sequences enhance the metabolic kinetics sufficiently for the whole system to survive. We propose an experimental implementation of the proto-organism with a discussion of our experimental results, together with relevant results produced by other experimental groups, and we specify what is still missing experimentally. Identifying the missing steps is just as important as providing the road map for the transition. We derive the kinetic and thermodynamic conditions of each of the proto-organism subsystems together with relevant theoretical and computational results about these subsystems. We present and discuss detailed 3D simulations of the lipid aggregation processes. From the reaction kinetics we derive analytical aggregate size distributions, and derive key properties of the metabolic efficiency and stability. Thermodynamics and kinetics of the ligation directed self-replication of the proto-genes is discussed, and we summarize the full life cycle of the proto-organism by comparing size, replication time, and energy with the biomass efficiency of contemporary unicells. Finally, we also compare our proto-organism picture with existing origins-of-life and protocell pictures. By assembling one possible bridge between nonliving and living matter we hope to provide a piece in the ancient puzzle about who we are and where we come from.
13758632
A new differential LSI space-based probabilistic document classifier
We have developed a new effective probabilistic classifier for document classification by introducing the con differential document vectors and DLSI (differential latent semantic indexing) spaces. A combined use of the projection the distances to the DLSI spaces introduced from the differential document vectors improves the adaptability of the LS semantic indexing) method by capturing unique characteristics of documents. Using the intraand extra-document both a simple posteriori calculation on a small example and an experiment on a large Reuters-21578 database demo advantage of the DLSI space-based probabilistic classifier over the LSI space-based classifier in classification perform  2003 Elsevier B.V. All rights reserved.
2603707
Evaluating Critiquing-based Recommender Agents
We describe a user study evaluating two critiquing-based recommender agents based on three criteria: decision accuracy. decision effort, and user confidence. Results show that user-motivated critiques were more frequently applied and the example critiquing system employing only this type of critiques achieved the best results. In particular, the example critiquing agent significantly improves users' decision accuracy with less cognitive effort consumed than the dynamic critiquing recommender with system-proposed critiques. Additionally, the former is more likely to inspire users' confidence of their choice and promote their intention to purchase and return to the agent for future use.
6316461
Partitioned optimization algorithms for multiple sequence alignment
Multiple sequence alignment is an important and difficult problem in molecular biology and bioinformatics. In this paper, we propose a partitioning approach that significantly improves the solution time and quality by utilizing the locality structure of the problem. The algorithm solves the multiple sequence alignment in three stages. First, an automated and suboptimal partitioning strategy is used to divide the set of sequences into several subsections. Then a multiple sequence alignment algorithm based on ant colony optimization is used to align the sequences of each subsection. Finally, the alignment of original sequences can be obtained by assembling the result of each subsection. The ant colony algorithm is highly optimized in order to avoid local optimal traps and converge to global optimal efficiently. Experimental results show that the algorithm can significantly reduce the running time and improve the solution quality on large-scale multiple sequence alignment benchmarks.
21260780
An efficient incremental algorithm for identifying consistent checkpoints
In a distributed system, identifying consistent checkpoints is essential for error recovery and debugging. We design an efficient incremental algorithm capable of identifying all the consistent and removable checkpoints each time a new checkpoint is reported. By doing so, the required memory space can be minimized by removing those removables. While minimizing the memory space, the algorithm requires only O(p/sup 2/M) time in total, where p is the number of processes and M is the number of checkpoints.