We present an I/O-efficient algorithm for topologically sorting directed acyclic graphs (DAGs). No provably I/O-efficient algorithm for this problem is known. Similarly, the performance of our algorithm, which we call...
详细信息
We study the following problem: Given an array A storing N real numbers, preprocess it to allow fast reporting of the K smallest elements in the subarray A[i,j] in sorted order, for any triple (i,j,K) with 1 ≤ i ≤ j...
详细信息
ISBN:
(纸本)9780898719932
We study the following problem: Given an array A storing N real numbers, preprocess it to allow fast reporting of the K smallest elements in the subarray A[i,j] in sorted order, for any triple (i,j,K) with 1 ≤ i ≤ j ≤ N and 1 ≤ K ≤ j - i + 1. We are interested in scenarios where the array A is large, necessitating an I/O-efíicient solution. For a parameter / with 1 m n, we construct a data structure that uses 0((N/f)logmn) space and achieves a query bound of O(logB N + fK/B) I/Os,1 where B is the block size, M is the size of the main memory, n :- N/B, and m := M/B. Our main contribution is to show that this solution is nearly optimal. To be precise, we show that achieving a query bound of O(logαn + fK/B) I/Os, for any constant a, requires Ω(N f-1logMn/log(f-1logMn)) space assuming B = Ω(logN). For M ≥ B1+Ε, this is within a log logm n factor of the upper bound. The lower bound assumes indivisibility of records and holds even if we assume K is always set to j - 1 + 1. We also show that it is the requirement that the K smallest elements be reported in sorted order which makes the problem hard. If the K smallest elements in the query range can be reported in any order, then we can obtain a linear-size data structure with a query bound of O(logB N + K/B) I/Os.
We study the following problem: Given an array A storing N real numbers, preprocess it to allow fast reporting of the K smallest elements in the subarray A[i, j] in sorted order, for any triple (i, j, K) with 1 ≤ i ...
详细信息
ISBN:
(纸本)9780898719932
We study the following problem: Given an array A storing N real numbers, preprocess it to allow fast reporting of the K smallest elements in the subarray A[i, j] in sorted order, for any triple (i, j, K) with 1 ≤ i ≤ j ≤ N and 1 ≤ K ≤ j - i + 1. We are interested in scenarios where the array A is large, necessitating an I/O-efficient solution. For a parameter f with 1 ≤ f ≤ log_mn, we construct a data structure that uses O((N/f) log_mn) space and achieves a query bound of O(log_BN + fK/B) I/Os, where B is the block size, M is the size of the main memory, n := N/B, and m := M/B. Our main contribution is to show that this solution is nearly optimal. To be precise, we show that achieving a query bound of O((logn)~α + fK/B) I/Os, for any constantα, requires Ω(N((f~(-1)log_M n)/log(f~(-1)log_M n)) space, assuming B = Ω(logN). For M ≥ B~(1+ε), this is within a log log_mn factor of the upper bound. The lower bound assumes indivisibility of records and holds even if we assume K is always set to j - 1 + 1. We also show that it is the requirement that the K smallest elements be reported in sorted order which makes the problem hard. If the K smallest elements in the query range can be reported in any order, then we can obtain a linear-size data structure with a query bound of O(log~B N + K/B) I/Os.
Several existing cache-oblivious dynamic dictionaries achieve O(log_B N) (or slightly better O(log_B N/M)) memory transfers per operation, where N is the number of items stored, M is the memory size, and B is the bloc...
详细信息
ISBN:
(纸本)9780898716986
Several existing cache-oblivious dynamic dictionaries achieve O(log_B N) (or slightly better O(log_B N/M)) memory transfers per operation, where N is the number of items stored, M is the memory size, and B is the block size, which matches the classic B-tree data structure. One recent structure achieves the same query bound and a sometimes-better amortized update bound of O (1/B{direct}(1/(log log_B)~2) log_B N ＋ 1/B log~2 N) memory transfers.
This study examines the potential impact of 21st century sea-level rise on Aarhus, the second largest city in Denmark, emphasizing the economic risk to the city's real estate. Furthermore, it assesses which possib...
This study examines the potential impact of 21st century sea-level rise on Aarhus, the second largest city in Denmark, emphasizing the economic risk to the city's real estate. Furthermore, it assesses which possible adaptation measures that can be taken to prevent flooding in areas particularly at risk from flooding. We combine a new national Digital Elevation Model in very fine resolution (~2 meter), a new highly computationally efficient flooding algorithm that accurately models the influence of barriers, and geospatial data on real-estate values to assess the economic real-estate risk posed by future sea-level rise to Aarhus. Under the A2 and A1FI (IPCC) climate scenarios we show that relatively large residential areas in the northern part of the city as well as areas around the river running through the city are likely to become flooded in the event of extreme, but realistic weather events. In addition, most of the large Aarhus harbour would also risk flooding. As much of the area at risk represent high-value real estate, it seems clear that proactive measures other than simple abandonment should be taken in order to avoid heavy economic losses. Among the different possibilities for dealing with an increased sea level, the strategic placement of flood-gates at key potential water-inflow routes and the construction or elevation of existing dikes seems to be the most convenient, most socially acceptable, and maybe also the cheapest solution. Finally, we suggest that high-detail flooding models similar to those produced in this study will become an important tool for a climate-change-integrated planning of future city development as well as for the development of evacuation plans.
Quicksort was first introduced in 1961 by Hoare. Many variants have been developed, the best of which are among the fastest generic-sorting algorithms available, as testified by the choice of Quicksort as the default ...
详细信息
暂无评论