This paper concerns the following problem: given a set of multi-attribute records, a fixed number of buckets and a two-disk system, arrange the records into the buckets and then store the buckets between the disks in such a way that, over all possible orthogonal range queries (ORQs), the disk access concurrency is maximized. We shall adopt the multiple key hashing (MKH) method for arranging records into buckets and use the disk modulo (DM) allocation method for storing buckets onto disks. Since the DM allocation method has been shown to be superior to any other allocation methods for allocating an MKH file onto a two-disk system for answering ORQs, the real issue is knowing how to determine an optimal way for organizing the records into buckets based upon the MKH concept.
A performance formula that can be used to evaluate the average response time, over all possible ORQs, of an MKH file in a two-disk system using the DM allocation method is first presented. Based upon this formula, it is shown that our design problem is related to a notoriously difficult problem, namely the Prime Number Problem. Then a performance lower bound and an efficient algorithm for designing optimal MKH files in certain cases are presented. It is pointed out that in some cases the optimal MKH file for ORQs in a two-disk system using the DM allocation method is identical to the optimal MKH file for ORQs in a single-disk system and the optimal average response time in a two-disk system is slightly greater than one half of that in a single-disk system. 相似文献
Pointing tasks in human–computer interaction obey certain speed–accuracy tradeoff rules. In general, the more accurate the task to be accomplished, the longer it takes and vice versa. Fitts’ law models the speed–accuracy tradeoff effect in pointing as imposed by the task parameters, through Fitts’ index of difficulty (Id) based on the ratio of the nominal movement distance and the size of the target. Operating with different speed or accuracy biases, performers may utilize more or less area than the target specifies, introducing another subjective layer of speed–accuracy tradeoff relative to the task specification. A conventional approach to overcome the impact of the subjective layer of speed–accuracy tradeoff is to use the a posteriori “effective” pointing precision We in lieu of the nominal target width W. Such an approach has lacked a theoretical or empirical foundation. This study investigates the nature and the relationship of the two layers of speed–accuracy tradeoff by systematically controlling both Id and the index of target utilization Iu in a set of four experiments. Their results show that the impacts of the two layers of speed–accuracy tradeoff are not fundamentally equivalent. The use of We could indeed compensate for the difference in target utilization, but not completely. More logical Fitts’ law parameter estimates can be obtained by the We adjustment, although its use also lowers the correlation between pointing time and the index of difficulty. The study also shows the complex interaction effect between Id and Iu, suggesting that a simple and complete model accommodating both layers of speed–accuracy tradeoff may not exist. 相似文献
Network survivability is a crucial requirement in WDM mesh networks. In this paper, we systematically consider the problem of dynamic survivability with dynamic single link failure in WDM networks under dynamic traffic demands. Specifically, we investigate various protection schemes, such as dedicated path protection (DPP), shared path protection (SPP), dedicated link protection (DLP), shared link protection (SLP), and two restoration schemes, path restoration (PR) and link restoration (LR). Moreover, two new shared protection methods are proposed, i.e., SRLG-based shared link protection (SRLG-SLP) and SRLG-based shared path protection (SRLG-SPP). The SRLG (shared risk link group) constraint defines the availability of protection resources to a working path, which requires that any two working paths sharing the same risk of failure (or in the same SRLG) cannot share the same protection resources. Furthermore, in our study, we consider a more practical dynamic single-link failure model, in which the link-failure-interarrival time and link-failure-holding time are considered as two independent parameters. Based on this link-failure model, extensive simulations are done to analyze and compare the dynamic survivable performance of various protection and restoration schemes. Resource utilization, protection efficiency, restoration efficiency, and service disruption ratio are employed as survivable performance metrics versus traffic load, link-failure frequency, and link-failure reparation time to evaluate the survivable performance. Many meaningful results are given. In addition, we show that the developed SRLG-SLP and SRLG-SPP protection schemes perform very well in terms of protection efficiency and service disruption ratio, while sacrificing some performance in terms of resource utilization. 相似文献