×

I/O-efficient point location using persistent B-trees. (English) Zbl 1085.68565


MSC:

68P05 Data structures
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

TPIE
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] {1} P. K. Agarwal, L. Arge, G. S. Brodal, and J. S. Vitter. I/O-efficient dynamic point location in monotone planar subdivisions. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 1116-1127, 1999.]]
[2] {2} A. Aggarwal and J. S. Vitter. The Input/Output complexity of sorting and related problems. Communications of the ACM, 31(9):1116-1127, 1988.]]
[3] {3} L. Arge. The buffer tree: A technique for designing batched external data strutures. Algorithmica , 37(1):1-24, 2003.]] · Zbl 1058.68041
[4] {4} L. Arge. External memory data structures. In J. Abello, P. M. Pardalos, and M. G. C. Resende, editors, Handbook of Massive Data Sets, pages 313-358. Kluwer Academic Publishers, 2002.]] · Zbl 1010.68039
[5] {5} L. Arge, R. Barve, D. Hutchinson, O. Procopiuc, L. Toma, D. E. Vengroff, and R. Wickremesinghe. TPIE User Manual and Reference (edition 082902). Duke University, 2002. The manual and software distribution are available on the web at http://www.cs.duke.edu/TPIE/.]]
[6] {6} L. Arge, K. H. Hinrichs, J. Vahrenhold, and J. S. Vitter. Effcient bulk operations on dynamic R-trees. Algorithmica, 33(1):104-128, 2002.]] · Zbl 0994.68054
[7] {7} L. Arge, O. Procopiuc, and J. S. Vitter. Implementing I/O-effcient data structures using TPIE. In Proc. Annual European Symposium on Algorithms, pages 88-100, 2002.]] · Zbl 1019.68823
[8] {8} L. Arge and J. Vahrenhold. I/O-effcient dynamic planar point location. In Proc. ACM Symp. on Computational Geometry, pages 191-200, 2000.]] · Zbl 1373.68186
[9] {9} L. Arge, D. E. Vengroff, and J. S. Vitter. External-memory algorithms for processing line segments in geographic information systems. In Proc. Annual European Symposium on Algorithms, LNCS 979, pages 295-310, 1995. To appear in special issues of Algorithmica on Geographical Information Systems.]] · Zbl 1512.68436
[10] {10} R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173-189, 1972.]] · Zbl 0226.68008
[11] {11} B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer. An asymptotically optimal multiversion B-tree. VLDB Journal, 5(4):264-275, 1996.]]
[12] {12} D. Comer. The ubiquitous B-tree. ACM Computing Surveys, 11(2):121-137, 1979.]] · Zbl 0419.68034
[13] {13} A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer, and E. Ramos. Randomized external-memory algorithms for some geometric problems. International Journal of Computational Geometry & Applications, 11(3):305-337, June 2001.]] · Zbl 1074.68669
[14] {14} J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. Tarjan. Making data structures persistent. Journal of Computer and System Sciences, 38:86-124, 1989.]] · Zbl 0667.68026
[15] {15} M. Edahiro, I. Kokubo, and T. Asano. A new point-location algorithm and its practical efficiency – Comparison with existing algorithms. ACM Trans. Graph., 3(2):86-109, 1984.]] · Zbl 0592.68059
[16] {16} H. Edelsbrunner and H. A. Maurer. A space-optimal solution of general region location. Theoret. Comput. Sci., 16:329-336, 1981.]] · Zbl 0468.68075
[17] {17} M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter. External-memory computational geometry. In Proc. IEEE Symp. on Foundations of Comp. Sci., pages 714-723, 1993.]]
[18] {18} S. Huddleston and K. Mehlhorn. A new data structure for representing sorted lists. Acta Informatica, 17:157-184, 1982.]] · Zbl 0481.68061
[19] {19} D. G. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Comput., 12(1):28-35, 1983.]] · Zbl 0501.68034
[20] {20} N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29:669-679, 1986.]]
[21] {21} J. Snoeyink. Point location. In J. E. Goodman and J. O’Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 30, pages 559-574. CRC Press LLC, Boca Raton, FL, 1997.]] · Zbl 0907.68196
[22] {22} TIGER/LineTM Files, 1997 Technical Documentation. Washington, DC, September 1998. http://www.census.gov/geo/tiger/TIGER97D.pdf.]]
[23] {23} U.S. Geological Survey. 1:100,000-scale line graphs (DLG). Accessible via URL. http://edcwww.cr.usgs.gov/doc/edchome/ndcdb_bk/ (Accessed 9 September 2002).]]
[24] {24} J. Vahrenhold and K. H. Hinrichs. Planar point location for large data sets: To seek or not to seek. In Proc. Workshop on Algorithm Engineering, LNCS 1982, pages 184-194, 2001.]]
[25] {25} J. van den Bercken, B. Seeger, and P. Widmayer. A generic approach to bulk loading multidimensional index structures. In Proc. International Conf. on Very Large Databases, pages 406-415, 1997.]]
[26] {26} P. J. Varman and R. M. Verma. An efficient multiversion access structure. IEEE Transactions on Knowledge and Data Engineering, 9(3):391-409, 1997.]]
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.