CISS: An efficient object clustering framework for DHT-based peer-to-peer applications

In most DHT-based peer-to-peer systems, objects are totally declustered since such systems use a hash function to distribute objects evenly. However, such an object de-clustering can result in significant inefficiencies in advanced access operations such as multi-dimensional range queries, continuous updates, etc, which are common in many emerging peer-to-peer applications. In this paper, we propose CISS (Cooperative Information Sharing System), a framework that supports efficient object clustering for DHT-based peer-to-peer applications. CISS uses a Locality Preserving Function (LPF) instead of a hash function, thereby achieving a high level of clustering without requiring any changes to existing DHT implementations. To maximize the benefit of object clustering, CISS provides efficient routing protocols for multi-dimensional range queries and continuous updates. Furthermore, our cluster-preserving load balancing schemes distribute loads without hotspots while preserving the object clustering property. We demonstrate the performance benefits of CISS through extensive simulation.     

\mathcal{MD}-HBase: design and implementation of an elastic data infrastructure for cloud-scale location services

The ubiquity of location enabled devices has resulted in a wide proliferation of location based applications and services. To handle the growing scale, database management systems driving such location based services (LBS) must cope with high insert rates for location updates of millions of devices, while supporting efficient real-time analysis on latest location. Traditional DBMSs, equipped with multi-dimensional index structures, can efficiently handle spatio-temporal data. However, popular open-source relational database systems are overwhelmed by the high insertion rates, real-time querying requirements, and terabytes of data that these systems must handle. On the other hand, key-value stores can effectively support large scale operation, but do not natively provide multi-attribute accesses needed to support the rich querying functionality essential for the LBSs. We present the design and implementation of $\mathcal {MD}$ -HBase, a scalable data management infrastructure for LBSs that bridges this gap between scale and functionality. Our approach leverages a multi-dimensional index structure layered over a key-value store. The underlying key-value store allows the system to sustain high insert throughput and large data volumes, while ensuring fault-tolerance, and high availability. On the other hand, the index layer allows efficient multi-dimensional query processing. Our optimized query processing technique accesses only the index and storage level entries that intersect with the query region, thus ensuring efficient query processing. We present the design of $\mathcal {MD}$ -HBase that demonstrates how two standard index structures—the K-d tree and the Quad tree—can be layered over a range partitioned key-value store to provide scalable multi-dimensional data infrastructure. Our prototype implementation using HBase, a standard open-source key-value store, can handle hundreds of thousands of inserts per second using a modest 16 node cluster, while efficiently processing multi-dimensional range queries and nearest neighbor queries in real-time with response times as low as few hundreds of milliseconds.     

Efficient implementation of a multi-dimensional index structure over flash memory storage systems

Flash memory is widely used in the storage system. The direct use of multi-dimensional index structure over flash memory would introduce a large number of redundant writes since such index structure requires fine-grained updates intensively. K-D-B-tree is a classic multi-dimensional index structure. In this paper, the implementation of K-D-B-tree over flash memory, namely F-KDB, is proposed to handle fine-grained updates. In F-KDB, a K-D-B-tree node is represented as a collection of logs (termed as logging entries) to efficiently process the updates of the node. Since the collecting and parsing of all the relevant logging entries to construct a node could degrade the query performance, a Workload Adaptive (WA) online algorithm is proposed to improve the query performance. A series of experiments are conducted to demonstrate the efficiency of F-KDB over flash memory. The response times of insertion/deletion are significantly reduced and the overall performance of F-KDB is improved.     

Inverse analysis method using MPP-based dimension reduction for reliability-based design optimization of nonlinear and multi-dimensional systems

There are two commonly used analytical reliability analysis methods: linear approximation - first-order reliability method (FORM), and quadratic approximation - second-order reliability method (SORM), of the performance function. The reliability analysis using FORM could be acceptable in accuracy for mildly nonlinear performance functions, whereas the reliability analysis using SORM may be necessary for accuracy of nonlinear and multi-dimensional performance functions. Even though the reliability analysis using SORM may be accurate, it is not as much used for probability of failure calculation since SORM requires the second-order sensitivities. Moreover, the SORM-based inverse reliability analysis is rather difficult to develop.This paper proposes an inverse reliability analysis method that can be used to obtain accurate probability of failure calculation without requiring the second-order sensitivities for reliability-based design optimization (RBDO) of nonlinear and multi-dimensional systems. For the inverse reliability analysis, the most probable point (MPP)-based dimension reduction method (DRM) is developed. Since the FORM-based reliability index (β) is inaccurate for the MPP search of the nonlinear performance function, a three-step computational procedure is proposed to improve accuracy of the inverse reliability analysis: probability of failure calculation using constraint shift, reliability index update, and MPP update. Using the three steps, a new DRM-based MPP is obtained, which estimates the probability of failure of the performance function more accurately than FORM and more efficiently than SORM. The DRM-based MPP is then used for the next design iteration of RBDO to obtain an accurate optimum design even for nonlinear and/or multi-dimensional system. Since the DRM-based RBDO requires more function evaluations, the enriched performance measure approach (PMA+) with new tolerances for constraint activeness and reduced rotation matrix is used to reduce the number of function evaluations.     

Design for six sigma through robust optimization

The current push in industry is focused on ensuring not only that a product performs as desired but also that the product consistently performs as desired. To ensure consistency in product performance, “quality” is measured, improved, and controlled. Most quality initiatives have originated and been implemented in the product manufacturing stages. More recently, however, it has been observed that much of a product’s performance and quality is determined by early design decisions, by the design choices made early in the product design cycle. Consequently, quality pushes have made their way into the design cycle, and “design for quality” is the primary objective. How is this objective measured and met? The most recent quality philosophy, also originating in a manufacturing setting, is six sigma. The concepts of six sigma quality can be defined in an engineering design context through relation to the concepts of design reliability and robustness – probabilistic design approaches. Within this context, design quality is measured with respect to probability of constraint satisfaction and sensitivity of performance objectives, both of which can be related to a design “sigma level”. In this paper, we define six sigma in an engineering design context and present an implementation of design for six sigma – a robust optimization formulation that incorporates approaches from structural reliability and robust design with the concepts and philosophy of six sigma. This formulation is demonstrated using a complex automotive application: vehicle side impact crash simulation. Results presented illustrate the tradeoff between performance and quality when optimizing for six sigma reliability and robustness.     

Supporting multi-dimensional queries in mobile P2P network

Nowadays, as the mobile services become widely used, there is a strong demand for mobile support in P2P search techniques. In this paper, we introduce a new cost model for searching multi-dimensional data in mobile P2P environment and propose a novel multi-dimensional mobile P2P search framework called MIME. MIME models the physical node layout in a two-dimensional plane and keeps records of the locations of the nodes to construct a proximity-aware P2P overlay. MIME is able to employ two different split schemes for the construction of the overlay. We propose query processing techniques for such P2P overlay. In addition, we employ a novel expanding method for tuning the performance of KNN queries in MIME. We also discuss two adaptive features incorporated into MIME to support mobility: an update algorithm that makes dynamic updates to the overlay, and a cache mechanism that reduces the load of data migration during the updates. The experimental results show that the proposed techniques are effective, and that MIME achieves significant performance improvements in Point, Range, and KNN queries compared to the conventional system.     

Robust design of stochastic controllers for nonlinear systems

The previous results are generalized on the stabilizing property of a control scheme designed for a class of discrete-time nonlinear stochastic systems. First, the existing controller is made more robust with a prescribed degree of stability by proper modifications. Next, the inherent robustness is illustrated by a design utilizing erroneous noise characteristics. Reconsideration of the stability analysis used allows one to treat a larger class of nonlinear stochastic systems with more general structures     

Design sensitivity and reliability-based structural optimization by univariate decomposition

This paper presents a new univariate decomposition method for design sensitivity analysis and reliability-based design optimization of mechanical systems subject to uncertain performance functions in constraints. The method involves a novel univariate approximation of a general multivariate function in the rotated Gaussian space for reliability analysis, analytical sensitivity of failure probability with respect to design variables, and standard gradient-based optimization algorithms. In both reliability and sensitivity analyses, the proposed effort has been reduced to performing multiple one-dimensional integrations. The evaluation of these one-dimensional integrations requires calculating only conditional responses at selected deterministic input determined by sample points and Gauss–Hermite integration points. Numerical results indicate that the proposed method provides accurate and computationally efficient estimates of the sensitivity of failure probability, which leads to accurate design optimization of uncertain mechanical systems.     

Predictors of user perceptions of web recommender systems: How the basis for generating experience and search product recommendations affects user responses

One critical question suggested by Web 2.0 is as follows: When is it better to leverage the knowledge of other users vs. rely on the product characteristic-based metrics for online product recommenders? Three recent and notable changes of recommender systems have been as follows: (1) a shift from characteristic-based recommendation algorithms to social-based recommendation algorithms; (2) an increase in the number of dimensions on which algorithms are based; and (3) availability of products that cannot be examined for quality before purchase. The combination of these elements is affecting users’ perceptions and attitudes regarding recommender systems and the products recommended by them, but the psychological effects of these trends remain unexplored. The current study empirically examines the effects of these elements, using a 2 (recommendation approach: content-based vs. collaborative-based, within)×2 (dimensions used to generate recommendations: 6 vs. 30, between)×2 (product type: experience products (fragrances) vs. search products (rugs), between) Web-based study (N=80). Participants were told that they would use two recommender systems distinguished by recommendation approach (in fact, the recommendations were identical). There were no substantive main effects, but all three variables exhibited two-way interactions, indicating that design strategies must be grounded in a multi-dimensional understanding of these variables. The implications of this research for the psychology and design of recommender systems are presented.     

MIRROR: a state-conscious concurrency control protocol for replicated real-time databases

Data replication can help database systems meet the stringent temporal constraints of current real-time applications, especially Web-based directory and electronic commerce services. A prerequisite for realizing the benefits of replication, however, is the development of high-performance concurrency control mechanisms. In this paper, we present managing isolation in replicated real-time object repositories (MIRROR), a concurrency control protocol specifically designed for firm-deadline applications operating on replicated real-time databases. MIRROR augments the classical O2PL concurrency control protocol with a novel state-based real-time conflict resolution mechanism. In this scheme, the choice of conflict resolution method is a dynamic function of the states of the distributed transactions involved in the conflict. A feature of the design is that acquiring the state knowledge does not require inter-site communication or synchronization, nor does it require modifications to the two-phase commit protocol.Using a detailed simulation model, we compare MIRROR's performance against the real-time versions of a representative set of classical replica concurrency control protocols for a range of transaction workloads and system configurations. Our performance studies show that (a) the relative performance characteristics of these protocols in the real-time environment can be significantly different from their performance in a traditional (non-real-time) database system, (b) MIRROR provides the best performance in both fully and partially replicated environments for real-time applications with low to moderate update frequencies, and (c) MIRROR's simple to implement conflict resolution mechanism works almost as well as more sophisticated strategies.     

Zone indexing: Optimizing the balance between searching and indexing in a loosely structured overlay

While structured peer-to-peer systems are efficient in terms of overhead, they still lack the unstructured system’s flexibility and ability to support a wide range of complex queries. This paper examines systems supporting complex queries, deterministic operation, and a fair load distribution between nodes. The aim is to minimize the bandwidth and node load using an optimal level of indexing. The paper first theoretically examines the optimal balance of search and index messages using a search/index space model. This balance is fundamentally determined by the frequency of search requests and index updates. Based on this study, the paper proposes a novel loosely structured peer-to-peer system, Zone indexing, that can balance between index update traffic and search traffic in order to minimize the bandwidth overhead. Nodes are organized into a ring structure. The ring is divided into overlapping zones, within which index updates are distributed. We present an overlay maintenance algorithm with low-cost join and leave operations and a high churn resistance. We further propose a method to dynamically adjust the zone size in order to maintain optimal performance when the network size or user behavior changes. Additionally, we propose a method to limit the search delay by introducing parallel searching. The proposed solutions are evaluated mathematically and the analysis is verified with simulation.     

Parameter sensitivity analysis of disk drive head load control system

The disk drive industry has employed head load/unload technology for mobile drives and desktop drives for more than 12 years. The read/write heads are parked on a ramp structure when the drive is non-operational. The velocity of loading the heads onto the disk and unloading them back onto the ramp is critical for both the head/media reliability and the drive performance. Head loading control is a typical mechatronic system that involves a firmware algorithm, control electronics, and drive mechanics. Key performance criteria of a load control system include the successful load, well-controlled head velocity, load time, acoustics and robustness. Various electrical and mechanical design parameters affect the load performance. This analysis investigates the sensitivity of these parameters for head load control system design using simulation model that has been verified by comparison to experimental measurement. Model parameters include the voice coil motor torque constant, composite load torque function, electronic circuit offsets, coil resistance and its calibration accuracy, and ramp alignment error. The information revealed by this analysis helps improve disk drive head load control system design, performance, and robustness in the face of parameter variations introduced by high volume manufacturing. The results are also very helpful for product failure analysis.     

Passivity-based designs for synchronized path-following

We consider a formation control system where individual systems are controlled by a path-following design and the path variables are to be synchronized. We first show a passivity property for the path-following system, and next, combine this with a passivity-based synchronization algorithm developed in Arcak [2007. Passivity as a design tool for group coordination. IEEE Transactions on Automatic Control, in press]. The passivity approach expands the classes of synchronization schemes available to the designer. This generality offers the possibility to optimize controllers to, e.g., improve robustness and performance. Two designs are developed in the proposed passivity framework: the first employs the path error information in the synchronization loop, while the second only uses synchronization errors. A sampled-data design, where the path variables are updated in discrete-time and the path-following controllers are updated in continuous time, is also developed.     

移动实时数据库系统中的更新分发

数据广播作为移动计算环境下有效的数据分发技术已有许多研究,当数据广播用于发送不断更新的数据时称它为更新分发．现有的更新分发协议因没有考虑实时数据库系统中数据和事务的定时要求而不适合移动实时只读事务的处理．重点研究了移动实时数据库系统中更新分发的问题,提出了混合前向多版本数据广播协议,该协议在保证事务一致性的同时满足了数据和事务的定时约束．模拟实验表明,该协议能够有效地降低事务错过率和提高数据流行性,较现有更新分发协议更适合移动实时只读事务的处理．     

基于产品特征解构的多维感知信息模型构建

基于现有一维感性工学模型难以充分表达用户对产品的感知信息,提出基于产品特 征解构的多维感知信息模型构建方法。首先运用产品特征解构方法构建产品多维造型特征空间和 情感意象认知空间;其次结合相似度理论、多维尺度法和K-mean 聚类分析量化意象词汇,提取 代表性情感维度;之后运用主成分分析判定多维造型特征中的主要影响因子;最后运用多元线性 回归构建出多维变量表达的KE 模型。以微波炉为例,验证了该方法的可行性,结果表明该方法 能有效指导产品的精准化设计。     

Robust control design using eigenstructure assignment and multi-objective optimization

This paper develops a new approach to multiple objective optimization design for robust multivariable control systems, based on eigenstructure assignment and genetic algorithms. It considers various performance indices (or cost functions) in the objectives, which are individual eigenvalue sensitivity functions, and the sensitivity and the complementary sensitivity functions in the frequency domain, instead of a single performance index for a control system. Based on these performance indices, the robustness criteria are expressed by a set of inequalities. The paper will make full use of the freedom provided by eigenstructure assignment to find a controller to satisfy the robustness criteria. A numerical algorithm for multi-objective optimization using genetic algorithm approaches is developed and applied to the simulation of a distillation column control system design     

Triggered Updates for Temporal Consistency in Real-Time Databases

A real-time database systemhas temporal consistency constraints in addition to timing constraints.The timing constraints require a transaction to be completedby a specified deadline, and the temporal consistency constraintsrequire that temporal data read by a transaction be up-to-date.If a transaction reads out-of-date data, it will become temporallyinconsistent. A real-time database system consists of differenttypes of temporal data objects, including derived objects. Thevalue of a derived object is computed from a set of other objects,known as the read-set of the derived object. The derived objectmay not always reflect the current state of its read-set; a derivedobject can become out-of-date even if its read-set is up-to-date.Any subsequent transaction reading the derived object will thenbecome temporally inconsistent. In this case, in order to readup-to-date objects, a transaction will have to wait until someother transaction updates the out-of-date object. However, indoing so, the waiting transaction may miss its deadline, particularlyif the update is not periodic but instead arrives randomly. Wepropose to update the outdated objects so that not only is thetemporal consistency improved, but also the number of misseddeadlines does not increase significantly, and as a result thereis an overall improvement in the performance of the system. Wepropose, implement and study a novel approach, to be known astriggered updates, to improve temporal consistency in firm real-timedatabase systems when updates are not periodic. We identify propertiesof triggered updates and explain how they work by giving bothan intuitive and a probabilistic analysis. We present strategiesfor generating triggered updates, discuss their suitability invarious contexts and perform a detailed simulation study to evaluatetheir performance. Results show that it is possible to improvetemporal consistency without degrading the timeliness of real-time database systems to a great deal.     

DCR-based causal design knowledge evaluation method and system for future CAD applications

This paper presents a new causal design knowledge evaluation method and system for future CAD applications. Current product development processes still include unintended feedback due to insufficient product design knowledge. Previous research on design knowledge support system focuses on search by matching keywords and file names, or search by specific indices, which has various drawbacks. Furthermore, current CAD systems need manual input to incorporate the designer’s knowledge. To systematize the knowledge management process for the next-generation CAD systems, a prerequisite is to capture ever-evolving causal design knowledge. In this paper, we present a new causal knowledge network evaluation method, which has not been well addressed in design knowledge support system research. For the network evaluation, we present a degree of causal representation (DCR)-based knowledge network evaluation method. In this method, causality and network connectivity are used for the causal knowledge network with weighted vertices and weighted network connectivity for a network with weighted edges. To validate the proposed method, this evaluation method has been compared with structural measures. Finally, the causal design knowledge evaluation system, KNOES, is implemented and tested with a new valve design scenario.     

On the relationship between propagating context-dependent lindenmayer systems and cellular automata systems

It is shown that any one-dimensional cellular automata system can be simulated in real time by a propagating context-dependent Lindenmayer system, PD(m, n)L. Further, any PD(m, n)L system can be simulated by a one-dimensional cellular system. Although real-time simulations exist, there are PD(m, n)L systems for which a linear-time simulation is impossible.     

Sensitivity analysis of arbitrary deadline real-time systems with EDF scheduling

The correctness of a real-time system depends on not only the system’s output but also on the time at which results are produced. A hard real-time system is required to complete its operations before all its timing deadlines. For a given task set it is useful to know what changes can be made to a task that will result in a system that is borderline schedulable. It is also beneficial in an engineering context to know the minimum speed of a processor that will deliver a schedulable system. We address the following sensitivity analysis (parameter computations) for EDF-scheduled systems on a uniprocessor: task execution times, speed of the processor, task periods and task relative deadlines. We prove that an optimal (minimum or maximum) system parameter can be determined by a single run of the Quick convergence Processor demand Analysis (QPA) algorithm. This algorithm provides efficient and exact sensitivity analysis for arbitrary deadline real-time systems. We also improve the implementation of this sensitivity analysis by using various starting values for the algorithms. The approaches developed for task parameter computations are therefore as efficient as QPA, and are easily incorporated into a system design support tool.