Lars Arge  Home/Search
Context Related
| duke.edu/~large/Papers/gisnotes.ps Cached: PS.gz PS PDF DjVu Image Update Help From: uci.edu/~eppstein/gina/gina.ff (more) Homepages: L.Arge HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: In the design of algorithms for large-scale applications it is essential to consider the problem of minimizing Input/Output (I/O) communication. Geographical information systems (GIS) are good examples of such large-scale applications as they frequently handle huge amounts of spatial data. In this note we survey the recent developments in external-memory algorithms with applications in GIS. First we discuss the Aggarwal-Vitter I/O-model and illustrate why normal internal-memory algorithms for... (Update)
Context of citations to this paper: More
.... O efficient algorithms and data structures have been developed for numerous problems see recent surveys for a sample of these results [3,4, 28]. Most previous results on point location in external memory have been either static or batched dynamic: Goodrich et al. 18] designed...
...problem domains, including computational geometry, graph theory, and string processing. Refer to recent surveys for references [3, 4, 32]. The practical merits of the developed algorithms have been explored byanumber of authors [11, 31, 6, 5] 1 For simplicitywe concentrate...
Cited by: More
On the performance of LEDA-SM - Crauser, Mehlhorn, Althaus, Brengel, .. (1997) (Correct)
Indexing Animated Objects Using Spatiotemporal Access.. - Kollios, Gunopulos.. (2001) (Correct)
Efficient Bulk Operations on Dynamic R-trees (Extended.. - Arge, Hinrichs, al. (Correct)
Similar documents (at the sentence level):
20.1%: Efficient External-Memory Data Structures and Applications - Arge (1996) (Correct)
Active bibliography (related documents): More All
1.7: External-Memory Algorithms for Processing Line Segments.. - Arge, Vengroff, Vitter (1998) (Correct)
1.5: Parallel Algorithms in External Memory - Hutchinson (2000) (Correct)
0.9: External Memory Data Structures - Arge (2000) (Correct)
Similar documents based on text: More All
0.7: External-Memory Algorithms for Processing Line Segments.. - Arge, Vengroff, Vitter (1995) (Correct)
0.6: Reducing I/O Complexity by Simulating Coarse.. - Dehne, Dittrich.. (Correct)
0.6: External-Memory Algorithms for Processing Line Segments.. - Arge, Vengroff, Vitter (1995) (Correct)
Related documents from co-citation: More All
12: Output Complexity of Sorting and Related Problems (context) - Aggarwal, Vitter - 1988
10: Efficient External-Memory Data Structures and Applications - Arge - 1996
10: The Buffer Tree: A New Technique for Optimal I/O-Algorithms (context) - Arge - 1995
BibTeX entry: (Update)
L. Arge. External-memory algorithms with applications in geographic information systems. In M. van Kreveld, J. Nievergelt, T. Roos, and P. Widmayer, editors, Algorithmic Foundations of GIS. Springer-Verlag, Lecture Notes in Computer Science 1340, 1997. http://citeseer.nj.nec.com/article/arge97externalmemory.html More
@incollection{ arge97externalmemory,
author = "Lars Arge",
title = "External-memory algorithms with applications in {GIS}",
booktitle = "Algorithmic foundations of geographic information systems",
volume = "1340",
publisher = "Springer-Verlag",
editor = "Marc van Kreveld and Jurg Nievergelt and Thomas Roos and Peter Widmayer",
pages = "213--254",
year = "1997",
url = "citeseer.nj.nec.com/article/arge97externalmemory.html" }
Citations (may not include all citations):2998 Introduction to Algorithms (context) - Cormen, Leiserson et al. - 1990
1643 The Art of Computer Programming (context) - Knuth - 1973
1257 The Design and Analysis of Computer Algorithms (context) - Aho, Hopcroft et al. - 1974
1114 Computational Geometry: An Introduction (context) - Preparata, Shamos - 1985
230 An introduction to disk drive modeling - Ruemmler, Wilkes - 1994
223 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
166 Applications of Spatial Data Structures: Computer Graphics (context) - Samet - 1989
154 Organization and maintenance of large ordered indexes (context) - Bayer, McCreight - 1972
131 Time bounds for selection (context) - Blum, Floyd et al. - 1973
113 Output complexity of sorting and related problems (context) - Aggarwal, Vitter - 1988
103 An optimal algorithm for intersecting line segments in the p.. (context) - Chazelle, Edelsbrunner - 1992
98 External-memory computational geometry - Goodrich, Tsay et al. - 1993
95 Fundamentals of Spatial Information Systems (context) - Laurini, Thompson - 1992
95 Indexing for data models with constraints and classes - Kanellakis, Ramaswamy et al. - 1996
93 Handbook of Theoretical Computer Science (context) - van Leeuwen - 1990
88 External-memory graph algorithms - Chiang, Goodrich et al. - 1995
85 Computational Geometry -- Algorithms and Applications (context) - de Berg, van Kreveld et al. - 1997
71 Amortized computational complexity (context) - Tarjan - 1985
70 A model for hierarchical memory (context) - Aggarwal, Alpern et al. - 1987
70 Hierarchical memory with block transfer (context) - Aggarwal, Chandra et al. - 1987
62 A data structuring technique (context) - Chazelle, Guibas - 1986
61 An efficient algorithm for determining the convex hull of a .. (context) - Graham - 1972
60 The buffer tree: A new technique for optimal I/O-algorithms (context) - Arge - 1995
53 Simple randomized mergesort on parallel disks - Barve, Grove et al. - 1996
52 Optimal dynamic interval management in external memory - Arge, Vitter - 1996
51 Path caching: A technique for optimal external searching - Ramaswamy, Subramanian - 1994
51 Algorithms for bichromatic linesegment problems and polyhedr.. (context) - Chazelle, Edelsbrunner et al. - 1994
51 Deterministic distribution sort in shared and distributed me.. (context) - Nodine, Vitter - 1993
51 A new data structure for representing sorted lists (context) - Huddleston, Mehlhorn - 1982
50 The ultimate planar convex hull algorithm (context) - Kirkpatrick, Seidel - 1986
48 complexity: The red-blue pebble game (context) - Hong, Kung - 1981
44 The uniform memory hierarchy model of computation - Alpern, Carter et al. - 1994
44 Triangulating simple polygons and equivalent problems (context) - Fournier, Montuno - 1984
42 Virtual Memory for Data Parallel Computing (context) - Cormen - 1992
40 External-memory algorithms for processing line segments in g.. - Arge, Vengroff et al.
40 range tree: A new data structure for range searching in seco.. (context) - Subramanian, Ramaswamy - 1995
38 Blocking for external graph searching - Goodrich, Nodine et al. - 1996
35 Sun Microsystems Inc (context) - Cockcroft, Tuning et al. - 1995
34 Algorithms for klee's rectangle problems (context) - Bentley - 1977
34 Improved algorithms and data structures for solving graph pr.. - Kumar, Schwabe - 1996
31 Fast permuting in disk arrays (context) - Cormen - 1993
31 An introduction through randomized algorithms (context) - Mulmuley - 1994
31 Efficient External-Memory Data Structures and Applications - Arge - 1996
30 Asymptotically tight bounds for performing BMMC permutations.. - Cormen, Wisniewski - 1993
29 Permuting information in idealized two-level storage (context) - Floyd - 1972
27 efficient scientific computation using TPIE (context) - Vengroff, Vitter et al. - 1996
27 Batched dynamic solutions to decomposable searching problems (context) - Edelsbrunner, Overmars - 1985
26 A simple randomized parallel algorithm for list-ranking (context) - Anderson, Miller - 1990
25 Reporting and counting intersections between two sets of lin.. (context) - Mairson, Stolfi - 1988
25 Spatial data structures: Concepts and design choices (context) - Nievergelt, Widmayer - 1997
24 efficiency of geometric algorithms: Distribution sweep vs (context) - Chiang, the - 1995
23 Algorithms for parallel memory (context) - Vitter, Shriver - 1994
22 range searching in external memory (context) - Vengroff, Vitter et al. - 1996
22 A fully-dynamic data structure for external substring search (context) - Ferragina, Grossi - 1995
21 complexity of ordered binary-decision diagram manipulation (context) - Arge, O- - 1995
21 Exploiting extensible dbms in integrated geographic informat.. (context) - Haas, Cody - 1991
20 Priority search trees in secondary memory (context) - Icking, Klein et al. - 1987
19 An optimal worst case algorithm for reporting intersections .. (context) - Bentley, Wood - 1980
19 Theory and practice of I/Oefficient algorithms for multidime.. - Arge, Procopiuc et al. - 1998
19 Optimal parallel sorting in multi-level storage - Aggarwal, Plaxton - 1994
19 high-reliability storage subsystems (context) - Ganger, Worthington et al. - 1994
18 Large-scale sorting in uniform memory hierarchies - Vitter, Nodine - 1993
18 A transparent parallel I/O environment (context) - Vengroff - 1994
17 An intellegent information fusion system for handling the ar.. (context) - Cromp - 1993
16 Counting and reporting red/blue segment intersections - Palazzi, Snoeyink - 1993
16 A simple trapezoid sweep algorithm for reporting red/blue se.. - Chan - 1994
15 Further comparisons of algorithms for geometric intersection.. - Andrews, Snoeyink et al. - 1994
15 The TWA reservation system (context) - Gifford, Spector - 1984
15 trees and their applications (context) - Callahan, Goodrich et al. - 1995
15 Greed sort: An optimal sorting algorithm for multiple disks (context) - Nodine, Vitter - 1995
15 Paradigms for optimal sorting with multiple disks (context) - Nodine, Vitter - 1993
14 XP-trees---External priority search trees (context) - Blankenagel, Guting - 1990
14 Efficient suffix trees on secondary storage (context) - Clark, Munro - 1996
14 Fast string searching in secondary storage: Theoretical deve.. (context) - Ferragina, Grossi - 1996
13 On sorting strings in external memory - Arge, Ferragina et al. - 1997
13 Efficient Algorithms for Computational Geometry and Graph Pr.. (context) - Chiang, O- - 1995
13 A general lower bound on the I/O-complexity of comparison-ba.. (context) - Arge, Knudsen et al. - 1993
12 On showing lower bounds for external-memory computational ge.. - Arge, Miltersen
12 Rectilinear line segment intersection (context) - Vaishnavi, Wood - 1982
12 efficient algorithms for contour line extraction and planar .. (context) - Agarwal, Arge et al. - 1998
11 Efficient memory access in large-scale computation (context) - Vitter - 1991
10 Understanding GIS---the ARC/INFO method (context) - INFO - 1993
9 Virtual memory algorithms (context) - Aggarwal, Chandra - 1988
9 Further computational geometry in secondary memory (context) - Zhu - 1994
9 Guest Editor's Introduction in IEEE Computer (context) - Patt, candidate et al. - 1994
8 II: Hierarchical multilevel memories (context) - Vitter, Shriver et al. - 1994
7 sets representation and fast halfplane searching (context) - Franciosa, Talamo et al. - 1994
7 The parallel hierarchical memory model - Juurlink, Wijshoff - 1993
6 Dynamic Data Structures on Multiple Storage Media (context) - Smid - 1989
6 Geographic information systems (context) - van Kreveld - 1995
5 Available via WWW at http://www (context) - Vengroff, Manual et al. - 1995
5 efficient scientific computation in TPIE (context) - Vengroff, Vitter et al. - 1995
5 Maintaining range trees in secundary memory (context) - Overmars, Smid et al. - 1990
5 Maintaining range trees in secundary memory (context) - Smid, Overmars - 1990
4 complexity of comparison and permutation problems (context) - Knudsen, Larsen et al. - 1992
4 Space-time tradeoffs in memory hierarchies - Savage - 1993
3 Private communication (context) - Vengroff - 1995
1 Master student project (context) - Knudsen, Larsen et al. - 1993
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.ics.uci.edu/~eppstein/gina/gina.ff): More
Chaining Multiple-Alignment Fragments in Sub-Quadratic Time - Miller (1995) (Correct)
Dealing with Higher Dimensions: The Well-Separated Pair.. - Paul B. Callahan (1995) (Correct)
Generating Automatically-Tuned Bitmaps from Outlines - Hobby (1993) (Correct)
Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents Feedback
CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute