Show simple item record

dc.contributor.authorArge, Lars
dc.contributor.authorProcopiuc, Octavian
dc.contributor.authorRamaswamy, Sridhar
dc.contributor.authorSuel, Torsten
dc.contributor.authorVitter, Jeffrey Scott
dc.date.accessioned2011-03-18T18:25:15Z
dc.date.available2011-03-18T18:25:15Z
dc.date.issued1998
dc.identifier.citationL. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter. “Theory and Practice of I/Oefficient Algorithms for Multidimensional Batched Searching Problems,” Proceedings of the 9th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA ’98), San Francisco, CA, January 1998, 685–694
dc.identifier.urihttp://hdl.handle.net/1808/7191
dc.descriptionExtended Abstract
dc.description.abstractWe describe a powerful framework for designing efficient batch algorithms for certain large-scale dynamic problems that must be solved using external memory. The class of problems we consider, which we call colorable external decomposable problems, include rectangle intersection, orthogonal line segment intersection, range searching, and point location. We are particularly interested in these problems in two and higher dimensions. They have numerous applications in geographic information systems (GIS), spatial databases, and VLSI and CAD design. We present simplified algorithms for problems previously solved by more complicated approaches (such as rectangle intersection), and we present efficient algorithms for problems not previously solved in an efficient way (such as point location and higher dimensional versions of range searching and rectangle intersection). We give experimental results concerning the running time for our approach applied to the red-blue rectangle intersection problem, which is a key component of the extremely important database operation spatial join. Our algorithm scales well with the problem size, and for large problems sizes it greatly outperforms the well-known sweepline approach.
dc.language.isoen
dc.publisherSociety for Industrial and Applied Mathematics
dc.relation.isversionofhttp://portal.acm.org/citation.cfm?id=315048
dc.titleTheory and Practice of I/O efficient Algorithms for Multidimensional Batched Searching Problems
dc.typeArticle
kusw.kuauthorVitter, Jeffrey Scott
kusw.oastatusfullparticipation
kusw.oaversionScholarly/refereed, publisher version
kusw.oapolicyThis item meets KU Open Access policy criteria.
dc.rights.accessrightsopenAccess


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record