Welcome to DiSC 2002
SIGMOD 2001
PODS 2001
SIGMOD RECORD 2001
CIKM 2001
= CIKM'01 Website
= CIKM'01 Papers
= CIKM Workshop_1
<<< = GIS'01 Papers>>>
= CIKM Workshop_2
= DOLAP'01 Papers
CoopIS 2001
DASFAA 2001
DASFAA 2000
DBPL 2001
Data Engineering Bul
DEXA_EC-WEB 2001
DMKD 2001
DPDJ 2001
HYPERTEXT 2001
ICDE 2001
ICDM 2001
ICDT 2001
JCDL 2001
KDD 2001
KDD_EXPLORATIONS 20
KRDB 2001
MDM 2001
MIR 2001
MIS 2001
RIDE 2001
SBBD 2001
SIGIR 2001
SIGIR FORUM 2001
SSDBM 2001
SSTD 2001
TODS 2001
TIME 2001
VLDB 2001
VLDBJ 2001

Flow Computation on Massive Grids


Laura Toma, Rajiv Wickremesinghe, Lars Arge, Jeffrey S. Chase, Jeffrey Scott Vitter, Patrick N. Halpin, and Dean Urban

  View Paper (PDF)  

Return to Spatial Query Processing Algorithms


Abstract

As detailed terrain becomes available, GIS applications target larger geographic areas at finer resolutions. Processing the massive data presents significant challenges to GIS systems and demands algorithms that are optimized for both data movement and computation.In this paper we develop effcient algorithms for flow routing on massive terrains, extending our previous work on flow accumulation. Our implementations of these algorithms constitute the first comprehensive terrain flow software system designed and optimized for massive data. We compare the performance of our system, called TERRAFLOW, with that of state of the art commercial and open-source GIS systems. On large terrains, TERRAFLOW outpreforms existing systems by a factor of 2 to 1000, and is capable of solving problems of a scope and scale that are impractical with previous algorithms.


DiSC'02 © 2003 Association for Computing Machinery