A direction-aware augmented spatial keyword top-$k$query (DAT$k\text{Q}$) returns the top-$k$objects based on a ranking function that considers spatial distance, textual similarity, query numeric attributes, and query direction. When a user initiates a DAT$k\text{Q}$, some user-desired objects (missing objects) may not appear in the query result set, and then the user wonders why they do not appear, which is called the why-not question. This paper focuses on answering why-not questions on DAT$k$Qs. We first discuss how to obtain the refined query direction by analyzing the position relationship between missing objects and original query direction in Polar coordinates. Then a DAPC index structure is designed, which can cut down irrelevant search space based on not only conventional distance pruning, keyword pruning, and attribute pruning but also query direction pruning. Particularly, by comparing the position relationship between the query direction and the sector (sector ring) region segmented by the DAPC-based method, the search space that does not meet the query direction is pruned. In addition, we discuss the applicability of our scheme for handling why-not questions on regional spatial keyword queries (SKQ), ordinary direction-aware top-$k$SKQ queries and complex scoring SKQ queries. Finally, a series of experiments are conducted on two real datasets to show the efficiency of our DAPC-based method.

Structured publish/subscribe (pub/sub) is a promising technique adopted on kinds of vehicle applications of Internet of industrial vehicles (IoIV), which uses Boolean expressions to capture the items with thousands of different attributes, values and spatial locations, and then processes and analyzes the vast amounts of data collected to obtain users' interests. However, existing pub/sub work with Boolean expressions either ignores spatial requirement or focuses on Euclidean space. This paper aims to fill this gap by addressing the issue of fog-based spatial-textual pub/sub problem with Boolean expressions in IoIV. A novel hybrid index called RnetBE is proposed, which exquisitely organizes traffic network structure, Boolean expressions, and spatial information of subscriptions. And RnetBE can prune huge numbers of unqualified subscriptions based on both spatial constraint and Boolean expressions, thus achieving high efficiency in indexing and matching. Moreover, range-tree deletion and orderly group processing optimization techniques are proposed to save storage space and further improve the subscription pruning efficiency. Simulation results show that RnetBE and the proposed algorithm are efficient in terms of memory consumption and matching time.

Chip multiprocessors have been proposed for many years and have become the prevalent architecture for high-performance general-purpose processors. Currently, the search for automatic parallelization techniques that can take full advantage of processor resources is still an active research area. The cyclic multi-threading (CMT) approach, a popular parallelization paradigm, is widely applicable to many applications and delivers good performance scalability. Despite so, its performance could be quite sensitive to fluctuations in communication latencies without substantive operations that prefetch synchronization signals. To address this problem, we propose a novel CMT technique called ${\\rm DO}_{{\\rm cyclical}}$ that employs a priority-based scheme to reduce greatly the frequency of cross-core loop-carried dependences, hence removes considerable amount of communication latency from critical paths of loop executions. Further, it is the priority-based scheme that keeps all processors busy most of time while maintaining processor load balanced. To demonstrate the capacities of ${\\rm DO}_{{\\rm cyclical}}$ , we have evaluated it by using the SPEC CPU2006 and StreamIt benchmarks on three real platforms. Experimental results show that our method is much less sensitive to fluctuations in communication latencies, compared with traditional cyclical multi-threading techniques. Besides, ${\\rm DO}_{{\\rm cyclical}}$ outperforms other well-known parallelization methods, including decoupled software pipelines (DSWP), PS-DSWP and HELIX, in terms of speedup by 21–50, 16–27 and 15–25%, respectively, on the three platforms.

The utilization bounds for partitioned multiprocessor scheduling are a function of task allocation algorithms and the schedulability conditions selected for uniprocessor scheduling algorithms. In this paper, we use rate-monotonic scheduling on each processor and present the lower and upper limits of the utilization bounds for all reasonable task allocation heuristics. Unlike previous work, the hyperbolic bound due to Bini , instead of the Liu & Layland bound, is adopted to do the schedulability test on uniprocessors. We also derive the utilization bounds with respect to the worst fit allocation algorithm and reasonable allocation decreasing heuristics, and the two bounds are found to coincide with the worst and best achievable multiprocessor utilization bounds, respectively. Analytical and experimental results show that the proposed utilization bound performs better than the existing bound under quite a lot of parameter settings, and combining these two bounds together can significantly (up to 3 times) increase the number of schedulable task sets with little extra overhead.

Locality Sensitive Hashing (LSH) is widely recognized as one of the most promising approaches to similarity search in high-dimensional spaces. Based on LSH, a considerable number of nearest neighbor search algorithms have been proposed in the past, with some of them having been used in many real-life applications. Apart from their demonstrated superior performance in practice, the popularity of the LSH algorithms is mainly due to their provable performance bounds on query cost, space consumption and failure probability.

Deriving deadlines and periods for update transactions so as to maintain timeliness and data freshness while minimizing imposed workload has long been recognized an important problem in real-time database research. Despite years of active research, the state-of-the-art still has much room for improvement, particularly for periodic transactions scheduled by the Earliest Deadline First (EDF) algorithm. In this paper, we propose a practical and efficient two-phase algorithm, GEneral EDF (GEEDF), for assigning periods and deadlines to EDF-scheduled update transactions. Phase 1 of GEEDFaims at finding solutions for most inputs in linear time, based on the observation that the execution times of update transactions are relatively small compared to the validity interval lengths of real-time data objects in many real-time applications. In the remaining cases for which Phase 1 fails to derive solutions, Phase 2 is invoked by employing an existing deadline-monotonic-based algorithm, which we show is also applicable to our problem. Meanwhile, we have devised several techniques which significantly reduce the cost of schedulability test, and hence greatly improve time efficiency. Our experimental results demonstrate that GEEDFoutperforms existing approaches in terms of generated workloads. Although Phase 2 has a pseudopolynomial time complexity, our experimental study shows that it runs much faster than other solutions with comparable quality.

In the past decade, the development of mobile and embedded systems has demanded energy efficiency for improving the lifetime of embedded devices. To avoid preemption overhead or ease timing verification, nonpreemptive scheduling has been deemed useful or necessary in meeting system timing requirements for certain applications built on embedded devices. In this paper, our aim is to design nonpreemptive scheduling algorithms that ensure timing correctness and optimize energy consumption on a processor with variable speeds. We propose a representative algorithm, ISA, which can produce lower speeds for a variety of nonpreemptive task sets than other comparable methods, and hence resulting in significant energy savings. When combined with a selective frequency-inheritance policy we design to efficiently determine if processor speedup can be disabled without jeopardizing any task deadlines, ISA can achieve even larger gains, up to 30% reduction in energy consumption. Finally, we propose a dynamic slack reclamation policy built on ISA, namely ISA-DR, which can result in additional energy savings when a task consumes less than its worst-case execution time.

To verify the feasibility of real-time task sets on homogeneous multiprocessor systems, Lopez et al. derived the utilization bound based on Best Fit Decreasing allocation algorithm and Rate-Monotonic scheduling, which coincides with the maximum achievable multiprocessor utilization bound, using Liu & Lyland bound as the uniprocessor schedulability condition. In this paper, a novel feasibility test for the same target problem is developed based on the hyperbolic bound due to Bini et al., instead of the Liu \& Layland bound. Analytical and experimental results show that the proposed utilization bound performs better than the existing bound under quite a lot of parameter settings, and combining these two bounds together can significantly increase the number of schedulable task sets with little extra overhead.

On-demand broadcast is a promising data dissemination approach in mobile computing environments thanks to its adaptability and scalability for large-scale and dynamic workload. An important class of emerging data broadcast applications needs to monitor multiple time-varying data items continuously to be kept aware of the up-to-date information. This paper investigates the broadcast schedule problem for disseminating timely data to periodic continuous queries, and a systematic and highly efficient solution for applications of this type is provided. In particular, we propose a novel measure, called Bandwidth Utilization, to quantify the minimum bandwidth demand of a periodic continuous query set. The timing predictability can be ensured if a set of periodic continuous queries passes a bandwidth utilization based schedulability test. The schedulability test techniques are also extended to deal with dynamic query arrival and departure. An efficient online scheduling algorithm, called RM-UO, is developed, which can fulfill the timing constraints combined with the proposed query release and deletion policies. To demonstrate the effectiveness of theoretical results, an illustrative algorithm implementation is presented along with comprehensive performance analysis. Simulation results show that our solution offers nice timing predictability whereas other comparable best effort scheduling algorithms such as SIN-Q and DTIU experience different deadline miss ratios at different query workloads.

Real-time stream processing applications must be prepared to operate under overloaded conditions. Existing load shedding techniques are not suitable for processing real-time data streams because their tuple dropping policies may violate application deadlines in an uncontrolled way. We'd argue that a more precise load shedding model, e.g., the (m, k) deadline model adopted in this paper, is much appropriate than the commonly used random dropping policy. Based on the (m, k) load shedding model and a novel load shedding approach, we propose a concrete (m, k) scheduling algorithm called SOSA-DBP by exploiting application semantics. Experimental results show that SOSA-DBP has significant performance gain over the existing (m, k) scheduling algorithm.

Fault-tolerant mobile computing systems have different requirements and restrictions, not taken into account by conventional distributed systems. This paper presents a coordinated checkpointing scheme which reduces the delay involved in a global checkpointing process for mobile systems. A piggyback technique is used to track and record the checkpoint dependency information among processes during normal message transmission. During checkpointing, a concurrent checkpointing technique is designed to use the pre-recorded process dependency information to minimize process blocking time by sending checkpoint requests to dependent processes at once, hence saving the time to trace the dependency tree. We show that our checkpoint algorithm forces a minimum number of processes to take checkpoints, which is an important property for checkpointing mobile applications. Via probability-based analysis, we show that our scheme can significantly reduce the latency associated with checkpoint request propagation, compared with traditional coordinated checkpointing approaches. Experimental results indicate that we have <2% overhead in transmitting piggybacked information during normal runtime. However, we can achieve up to a 60% reduction in checkpoint latency time.

Fault-tolerant mobile computing systems have different requirements and restrictions, not taken into account by conventional distributed systems. This paper presents a coordinated checkpointing scheme which reduces the delay involved in a global checkpointing process for mobile systems. A piggyback technique is used to track and record the checkpoint dependency information among processes during normal message transmission. During checkpointing, a concurrent checkpointing technique is designed to use the pre-recorded process dependency information to minimize process blocking time by sending checkpoint requests to dependent processes at once, hence saving the time to trace the dependency tree. Our checkpoint algorithm forces a minimum number of processes to take checkpoints. Via probability-based analysis, we show that our scheme can significantly reduce the latency associated with checkpoint request propagation, compared to traditional coordinated checkpointing approach.

In this study, we propose an object-based multimedia model for specifying quality of service (QoS) requirements, such as the maximum data-dropping rate or the maximum data-delay rate. We also present a resource allocation model, the net-profit model, in which the satisfaction of users' QoS requirements is measured by the net profit earned by the system. Based on the net-profit model, the system is rewarded if it can allocate enough resources to a multimedia delivery request and fulfill the QoS requirements specified by the user. At the same time, the system is penalized if it cannot allocate enough resources to a multimedia delivery request. The paper examines the problem of how to allocate a resource efficiently such that the QoS satisfaction is maximized, based on the net-profit model. We derive optimal scheduling schemes according to the QoS requirements specified by users. Partial data dropping can reduce the bandwidth consumption, while some important data for multimedia playback might be missed. Transmission delay allows transmitting more data with loose QoS requirements, but it might be unacceptable for real-time multimedia data. Thus, our scheduling policy is based on the hybrid scheme of the dropping and delaying policies.

Real-time databases (RTDBs) are increasingly being used as an integral part of many computer systems. During normal operation, transactions in RTDBs must be executed in such a way that transaction timing and data time validity constraints can be met. RTDBs must also prepare for possible failures and provide fault tolerance capability. Principles for fault tolerance in RTDBs must take timing requirements into consideration and are distinct from those for conventional databases. We discuss these issues in this paper and describe a logging and recovery technique that is time-cognizant and is suitable for an important class of RTDB applications. The technique minimizes normal runtime overhead caused by logging and has a predictable impact on transaction timing constraints. Upon a failure, the system can recover critical data to a consistent and temporally valid state within predictable time bounds. The system can then resume its major functioning while non-critical data are being recovered in the background. As a result, the recovery time is bounded and shortened. In short, we are providing a bounded and predictable logging and recovery technique for critical transactions accessing critical variant and invariant data, while the database may consist of all kinds of data. Our performance evaluation via simulation shows that logging overhead has a small effect on missing transaction deadlines while adding recovery capability. In addition, our algorithm scales well with respect to large I/O page sizes, indicating that it can be adapted to future generations of storage devices with larger I/O page sizes. We compare our algorithm with another approach that does more frequent checkpointing for data with certain special characteristics. Simulation results disclose conditions under which each approach performs better than the other. Experiments also show that recovery using our approach is 3–6 times faster than traditional recovery.

This paper proposes a generic framework to integrate real-time scheduling algorithms, conventional concurrency control algorithms, and aborting algorithms. The schedulability of a transaction system is improved by aborting excessive blocking from lower priority transactions. A schedulability analysis model is proposed to better manage the schedulability of a transaction system.

There has been growing interest in the performance of transaction systems that have significant response time requirements. These requirements are usually specified as hard or soft deadlines on individual transactions and a concurrency control algorithm must attempt to meet the deadlines as well as preserve data consistency. This paper proposes a class of simple and efficient abort-oriented concurrency control algorithms in which the schedulability of a transaction system is improved by aborting transactions that introduce excessive blockings. We consider different levels of the aborting relationship among transactions and evaluate the impacts of the aborting relationship when the relationship is built in an online or offline fashion. We measure aborting overheads on a system running the LynxOS real time operating system. The strengths of the work are demonstrated by improving the worst-case schedulability of an avionics example, a satellite control system, and randomly generated transaction sets.

Predictable performance in the event of failures is of paramount importance in most safety critical real-time database systems. Our research addresses new crash recovery techniques that accommodate pre-run-time timing analysis and utilize design-time information about transactions' data access patterns to improve performance at run time and system restart time. The schemes we will propose are based on a form of shadowing. In contrast to the shadow version algorithm as described previously our schemes reduce overheads at run time, shorten the blocking duration necessary in the transactions' atomic commitment stage, eliminate dynamic storage allocation and reclamation, and permit very fast and bounded-time recovery after a crash by simply retrieving the master record and system version directory from nonvolatile storage. The data structures and algorithms used by our recovery schemes differ when different concurrency control protocols are used. We analyze their characteristics and their impacts on the performance of real-time database systems. Quantitative evaluation of our technique indicates the schemes are much more efficient than traditional log-based techniques.