42000677
Real-Time Database Benchmark Design for Avionics Systems
Traditionally, database systems have been developed for data processing applications. With the development of CAD/CAM applications, object-oriented databases have been shown to be more flexible and effective in providing the kind of performance more adequate for CAD users. Recently, as a result of the rapid growth in embedded and autonomous systems applications, many database applications are moving toward the real-time domain that is defined by high data access and/or transaction execution rates as well as stringent timing constraints. These real-time characteristics require databases to have special capabilities to handle time-critical transactions. Some examples are databases for safety-critical applications like air traffic control, avionics systems, process control, and medical service systems.
15072976
The design and implementation of real-time schedulers in RED-linux
Researchers in the real-time system community have designed and studied many advanced scheduling algorithms. However, most of these algorithms have not been implemented since it is very difficult to support new scheduling algorithms on most operating systems. To address this problem, we enhance the scheduling mechanism in Linux to provide a flexible scheduling framework. In the real-time and embedded Linux (RED-Linux) project, we implement a general scheduling framework which divides the system scheduler into two components: dispatcher and allocator. The dispatcher provides the mechanism of system scheduling and resides in the kernel space. The allocator is used to define the scheduling policy and implemented as a user space function. This framework allows users to implement application-specific schedulers in the user space which is easy to program and to debug. The framework also relieves the deficiency from the stock Linux scheduler which is not designed for real-time applications. To further enhance its power, a hierarchical scheduling mechanism has been provided in RED-Linux to allow a system designer to integrate different real-time applications together. Using scheduling groups, real-time jobs can be managed and scheduled in a hierarchical manner. In this paper, we discuss how the group mechanism is implemented in RED-Linux.
14104203
SM: real-time multicast protocols for simultaneous message delivery
Traditionally, a multicast message is sent once by a sender. All receivers will receive the same message but may receive it at different times. This may result in unfair advantage for some receivers. Simultaneous Multicast (SM) applications require that all receivers receive the same message at the same time. SM protocols therefore need to meet a strict deadline to ensure that each receiver will receive a message at the same time, regardless of the network conditions, heterogeneity of the environment and differences between the local clocks in the receivers. Such a real time SM protocol is proposed so that the coordinated deadline can be met by controlling the reserved bandwidth and without the overhead of clock synchronization. A sensing protocol is also proposed to continuously search for better levels of quality and to avoid the overhead of an external feedback protocol. The protocols are bandwidth conscious, enforce fairness and provide scalability.
13997680
Distributed real-time system design using CBS-based end-to-end scheduling
Distributed real-time applications share a group of processors connected by some local area network. A rigorous and sound methodology to design real-time systems from independently designed distributed real-time applications is needed. In this paper, we study a distributed real-time system design scheme using CBS-based end-to-end scheduling. The scheduling scheme utilizes CBS to allocate both CPU shares and network bandwidth to a distributed real-time application when it arrives at the system. Our proposed solution uses the same scheduling paradigm for both resources. In this way, we believe the system can have a more consistent scheduling objective and may achieve a tighter schedulability condition.
15828117
Enhancing external consistency in real-time transactions
Real-time computing brings two new requirements to database management. The first is the deadline constraint which requires better scheduling algorithms to meet transaction deadfines. The second requirement is the temporal validity, or external consistency[Lin89], requirement of data: a real-time database must prevent data from being corrupted not only by the executions of concurrent transactions but also by the delay from sharing computing resources and real-time scheduler decisions. In this paper, we study the external consistency requirement in real-time databases. We propose a semantic-based concurrency control scheme that prefers the external consistency to the traditional serializability. Two new concepts are introduced in our work. An update of a physical object value is considered to be compatible to those read operations that need to access the most recent data. Secondly, if a transaction depends strongly on the validity of the value of an object, a new update may cause the transaction to be aborted since continuing the transaction may be harmful to the appfication. A real-Life example is the stock market database. A trading program may be executed for a long time and its read operations should not block any new updates. Moreover, if there is a big sudden change in a particular stock price, it may be better to abort an on-going transaction rather than letting it make some invalid decisions.
22001959
A Pinwheel Scheduler for Three Distinct Numbers with a Tight Schedulability Bound
Abstract. Given a multiset of positive integers 
 $A=\{a_1,a_2,\ldots,a_n\}$ , the pinwheel problem is to find an infinite sequence over 
 $\{1,2,\ldots,n\}$ such that there is at least one symbol i within any subsequence of length ai. The density of A is defined as 
 $\rho(A)=\sum^n_{i=1} (1/a_i)$ . In this paper we limit ourselves to instances composed of three distinct integers. The best scheduler [5] published previously can schedule all instances with a density of less than 0.77. A new and fast scheduling scheme based on spectrum partitioning is presented in this paper which improves the 0.77 result to a new 
 $\frac{5}{6}\approx 0.83$ density threshold. This scheduler has achieved the tight schedulability bound of this problem.
15481025
Rule Discovery from Time Series
We consider the problem of finding rules relating patterns in a time series to other patterns in that series, or patterns in one series to patterns in another series. A simple example is a rule such as "a period of low telephone call activity is usually followed by a sharp rise in call volume". Examples of rules relating two or more time series are "if the Microsoft stock price goes up and Intel falls, then IBM goes up the next day," and "if Microsoft goes up strongly for one day, then declines strongly on the next day, and on the same days Intel stays about level, then IBM stays about level." Our emphasis is in the discovery of local patterns in multivariate time series, in contrast to traditional time series analysis which largely focuses on global models. Thus, we search for rules whose conditions refer to patterns in time series. However, we do not want to define beforehand which patterns are to be used; rather, we want the patterns to be formed from the data in the context of rule discovery. We describe adaptive methods for finding rules of the above type from time-series data. The methods are based on discretizing the sequence by methods resembling vector quantization. We first form subsequences by sliding a window through the time series, and then cluster these subsequences by using a suitable measure of time-series similarity. The discretized version of the time series is obtained by taking the cluster identifiers corresponding to the subsequence. Once the time-series is discretized, we use simple rule finding methods to obtain rules from the sequence. We present empirical results on the behavior of the method.
46019766
A Study on Textual Entailment
In this paper we study a graph-based approach to the task of textual entailment between a text and hypothesis. The approach takes into account the full lexico-syntactic context of both the text and hypothesis and relies heavily on the concept of subsumption. It starts with mapping the text and hypothesis into graph structures where nodes represent concepts and edges represent lexico-syntactic relations among concepts. Based on a subsumption score between the text-graph and hypothesis-graph an entailment decision is then made. The impact of synonymy on entailment is quantified and discussed. An important advantage of our solution is the ability to customize it so that high-confidence results are obtained
362708
Low-Cost RFID Identification Variation
Interests continue to grow in recent years for the adoption of Radio Frequency Identification (RFID) in many different areas including transportation and supply chain management. Those RFID-included objects can be targeted more efficiently by real-time tracking and instant management. However, because of the contact-less type of RFID remote retrieval, the transmission of data in the air is very vulnerable to eavesdropping or appropriation. A primary security concern surrounding RFID technology is the illicit tracking of consumer location and analyzing of their shopping habits or behavior. This paper proposes a more secure and lightweight RFID variation protection protocol which enhances the security of the transmission of information as well as the consumer privacy protection by using randomized control access and two-way identification. In addition, this protocol also improves the overall performance and lowers the cost of RFID tag without any complicated calculation.
16978334
Evaluating a class of distance-mapping algorithms for data mining and clustering
A distance-mapping algorithm takes a set of objects and a distance metric and then maps those objects to a Euclidean or pseudoEuclidean space in such a way that the distances among objects are approximately preserved. Distance mapping algorithms are a useful tool for clustering and visualization in data intensive applications, because they replace expensive distance calculations by sum-of-square calculations. This can make clustering in large databases with expensive distance metrics practical. In this paper we present five distance-mapping algorithms and conduct experiments to compare their performance in data clustering applications. These include two algorithms called FastMap and MetricMap, and three hybrid heuristics that combine the two algorithms in different ways. Experimental results on both synthetic and RNA data show the superiority of the hybrid algorithms. The results imply that FastMap and MetricMap capture complementary information about distance metrics and therefore can be used together to great benefit. The net effect is that multi-day computations may be done in minutes.
13951248
A survey on evaluating and realizing IS/IT benefits in Taiwanese b2bec companies
A number of issues have emerged from the analysis of the data collected via a survey conducted in Taiwanese B2BEC companies. The results show relatively high usage of IS/IT investment evaluation and benefits realization methodologies, and yet, these methodologies were generally not used effectively within the responding organizations. Most of these organizations were not yet mature in terms of their IT. However, there was a clear association between level of IT maturity and both wide and effective use of methodologies for IS/IT investment evaluation and benefits management.