We present results related to satisfying shortest path queries on a planar graph stored in externalmemory. Let N denote the number of vertices in the graph and sort(N) denote the number of input/output (I/O) operatio...
详细信息
We present results related to satisfying shortest path queries on a planar graph stored in externalmemory. Let N denote the number of vertices in the graph and sort(N) denote the number of input/output (I/O) operations required to sort an array of length N: (1) We describe a blocking for rooted trees to support bottom-up traversals of these trees in O(K/B) I/Os, where K is the length of the traversed path. The space required to store the tree is O(N/B) blocks, where N is the number of vertices of the tree and B is the block size. (2) We give an algorithm for computing a (2)/(3)-separator of size O(rootN) for a given embedded planar graph. Our algorithm takes O(sort(N)) I/Os, provided that a breadth-first spanning tree is given. (3) We give an algorithm for triangulating embedded planar graphs in O(sort(N)) I/Os. We use these results to construct a data structure for answering shortest path queries on planar graphs. The data structure uses O(N-3/2/B) blocks of externalmemory and allows for a shortest path query to be answered in O((rootN + K)/DB) I/Os, where K is the number of vertices on the reported path and D is the number of parallel disks. (C) 2002 Elsevier Science B.V. All rights reserved.
We present results related to satisfying shortest path queries on a planar graph stored in externalmemory. Let N denote the number of vertices in the graph and sort(N) denote the number of input/output (I/O) operatio...
详细信息
ISBN:
(纸本)3540662006
We present results related to satisfying shortest path queries on a planar graph stored in externalmemory. Let N denote the number of vertices in the graph and sort(N) denote the number of input/output (I/O) operations required to sort an array of length N: (1) We describe a blocking for rooted trees to support bottom-up traversals of these trees in O(K/B) I/Os, where K is the length of the traversed path. The space required to store the tree is O(N/B) blocks, where N is the number of vertices of the tree and B is the block size. (2) We give an algorithm for computing a (2)/(3)-separator of size O(rootN) for a given embedded planar graph. Our algorithm takes O(sort(N)) I/Os, provided that a breadth-first spanning tree is given. (3) We give an algorithm for triangulating embedded planar graphs in O(sort(N)) I/Os. We use these results to construct a data structure for answering shortest path queries on planar graphs. The data structure uses O(N-3/2/B) blocks of externalmemory and allows for a shortest path query to be answered in O((rootN + K)/DB) I/Os, where K is the number of vertices on the reported path and D is the number of parallel disks. (C) 2002 Elsevier Science B.V. All rights reserved.
We present the tile-cached kd-tree, an efficient external-memory (disk) implementation of two-dimensional region query for use in a detailed area router Most researchers have heretofore focused on in-memoryalgorithms...
详细信息
ISBN:
(纸本)0769517005;0769517013
We present the tile-cached kd-tree, an efficient external-memory (disk) implementation of two-dimensional region query for use in a detailed area router Most researchers have heretofore focused on in-memoryalgorithms. However as the need to tackle very large problems increases, conventional in-memoryalgorithms suffer from unpredictable caching and paging behavior and their performance may degrade considerably. In addition, since the region-query data structure is only part of the overall system, its consumption of large memory resources affects other parts of the system as well. Our implementation takes advantage of spatial locality in the detailed-routing process. We partition the routing space into tiles, each storing the data of objects (rectangles) that lie strictly within it. Objects that cross tile boundaries are separately stored. The data within a tile are then written out to disk, and a configurable cache is used to hold in memory the most recently visited tiles. Experimental results on large real-life routing problems show that this scheme significantly reduces memory usage with tolerable performance penalty.
We study cache effects in distribution sorting algorithms for sorting keys drawn independently at random from a uniform distribution (‘uniform keys’). We note that the performance of a recently-published distributio...
详细信息
暂无评论