R-Trees?
Erik Radmall
spatial indexing algorithm that use a bounding-rectangle approach to
quickly search a large number of graphical objects. They seem to be the
best approach for object "picking" within a large data set.
Any pointers to the R-Tree algorithm source, or additional information
would be greatly appreciated.
Erik.
Luigi Perrotta
so,
Please post or email me whatever information you have/ receive.
Untill your posting, I did not even know that the problem
I started working on had a name or known algorithms. The
bliss of ignorance.
Ouij
Dan Benson
Erik,
I tried replying by email to your posting but it bounced back, so I'll reply
with a followup.
About a year or so ago I obtained a c++ implementation of an R-Tree from a guy
in Holland. He sent it to me via email but I inadvertantly deleted the files.
However, luckily I did make a print out. If you'd like a hard copy of the
source I'd be happy to look for it and mail a copy to you. I noticed that
another person (Luigi Perrotta) posted a message requesting the same
information. If there are too many requests I don't think I can afford to send
hard copies to everyone. In this posting I've included a list of references
from the literature related to spatial indexing methods that may be of
interest. I haven't added to it for about the last year so there's lots more
recent papers not listed.
Incidently, I've written my own implementations of the R-Tree and R*Tree in
Smalltalk-80. I didn't look at the c++ code but merely followed the
descriptions from the literature. My Smalltalk source probably wouldn't do you
any good.
What sort of work are you doing with R-Trees? I'm developing an object-oriented
3-D spatial database for biomedical imaging applications. I'm using the R-Tree
indexes for spatial object collections in the database for faster retrieval
based on spatial properties.
Dan Benson
Dept. of Elec. Engr., FT-10
University of Washington
Seattle, WA 98195
(206) 685-7567
ben...@ee.washington.edu
References________________________________
Literature associated with Spatial Databases, Data Structures, Algorithms, etc.
Beckley, D. A., Evens, M. W., Raman, V. K., "Multikey Retrieval from K-d trees
and Quad-trees," Proceedings of ACM SIGMOD 1985 International Conference on the
Management of Data, pp. 291-301, 1985.
Chen, H. H., Huang, T. S., "A Survey of Construction and Manipulation of
Octrees," Computer Vision, Graphics, Image Processing 43, pp. 409-431, 1988.
Davis, R., Shrobe, H., Hamscher, W., Wieckert, K., Shirley, M., and Polit, S.,
"Diagnosis Based on Description of Structure and Function," in Proceeding of
the National Conference on AI, pp. 137-142, AAAI, 1982.
Faloutsos, C., Sellis, R., Roussopoulos, N., "Analysis of Object Oriented
Spatial Access Methods," in Proceedings of ACM SIGMOD 1987 Annual Conference,
San Francisco, CA, pp. 426-439, June 1987.
Finkel, R. A., Bentley, J. L., "Quad Trees - A Data Structure for Retrieval on
Composite Keys," Acta Informatica, Vol. 4 pp. 1-9, 1974.
Guttman, A., "R-trees: A Dynamic Index Structure for Spatial Searching," Proc.
1984 ACM-SIGMOD International Conference on Management of Data, Boston, MA,
SIGMOD Record Vol. 14, No. 2, pp. 47-57, June 1984.
Gunther, O., Efficient Structures for Geometric Data Management, Lecture Notes
in Computer Science 337, edited by G. Goos and J. Hartmanis, Springer Verlag,
1988.
Guting, R. H., "Geo-Relational Algebra: A Model and Query Language for
Geometric Database Systems," Advances in Database Technology - EDBT '88,
Proceedings of the International Conference on Extending Database Technology,
Lecture Notes in Computer Science 303, J. W. Schmidt, S. Ceri, M. Missikoff
(eds.), Springer-Verlag, pp. 506-527, 1988.
Hutflesz, A., Six, H.W., Widmayer, P., "The Twin Grid File: A Nearly Space
Optimal Index Structure," Advances in Database Technology - EDBT '88,
Proceedings of the International Conference on Extending Database Technology,
Lecture Notes in Computer Science 303, J. W. Schmidt, S. Ceri, M. Missikoff
(eds.), Springer-Verlag, pp. 352-363, 1988.
Hutflesz, A., Six, H.W., Widmayer, P., "Twin Grid Files: Space Optimizing
Access Schemes," Proceedings of the ACM SIGMOD Conference, pp. 183-190, 1988.
Kriegel, H. P., Seeger, B. "PLOP-Hashing: A Grid File without Directory,"
Proceedings of the Fourth International Conference on Data Engineering, Los
Angeles, CA, pp. 369-376, February 1988.
Mao, X., Kunii, T. L., Fujishiro, I., Noma, T., "Hierarchical Representations
of 2D/3D Gray-Scale Images and Their 2D/3D Two-Way Conversion," IEEE Computer
Graphics and Applications, pp. 37-44, December 1987.
Nievergelt, J., Hinterberger, H. and Sevcik, K. C., "The Grid File: An
Adaptable, Symmetric Multikey File Structure," ACM Transactions on Database
Systems, Vol. 9, No. 1, pp. 38-71, March 1984.
Orenstein, J. A., "Spatial Query Processing in an Object-Oriented Database
System," Proceedings of SIGMOD 1986 International Conference on the Management
of Data, pp. 326-336, 1986.
Ouksel, M., "The Interpolation-Based Grid File," Proceedings of the Fourth ACM
SIGACT/SIGMOD Symposium on PODS, 1985.
Overmars, M. H., van Leeuwen, J., "Dynamic Multi-Dimensional Data Structures
Based on Quad- and K-D Trees," Acta Informatica 17, pp. 267-285, 1982.
Ponce, J., Faugeras, O., "An Object Centered Hierarchical Representation for 3D
Objects: The Prism Tree," Computer Vision, Graphics, Image Processing 38, pp.
1-28, 1987.
Requicha, A. A. G., "Representations for rigid solids: theory, methods, and
systems," ACM Computing Surveys, Vol. 12, No. 4, pp. 437-464, Dec. 1980.
Requicha, A. A. G., Voelcker, H. B., "Solid Modeling: A Historical Summary and
Contemporary Assessment," IEEE Computer Graphics Applications, pp. 9-24, March
1982.
Robinson, J. T., "The k-d-B tree: A Search Structure for Large Multidimensional
Dynamic Indexes," Proceedings of the 1981 ACM SIGMOD International Conference
on Management of Data, Ann Arbor, Mich., May 1981.
Roussopoulos, N., Leifker, D., "Direct Spatial Search on Pictorial Databases
Using Packed R-trees," Proceedings of ACM SIGMOD 1985 International Conference
on the Management of Data, pp. 17-31, 1985.
Samet, H., "The Quadtree and Related Hierarchical Data Structure," ACM
Computing Surveys, Vol. 16, No. 2, pp. 187-260, June 1984.
Samet, H., Webber, R. E., "Hierarchical Data Strctures and Algorithms for
Computer Graphics, Part I: Fundamentals," IEEE Computer Graphics and
Applications, pp. 48-68, May 1988.
Samet, H., Webber, R. E., "Hierarchical Data Strctures and Algorithms for
Computer Graphics, Part II: Applications," IEEE Computer Graphics and
Applications, pp. 59-75, July 1988.
Samet, H., Webber, R. E., "Hierarchical Data Structures and Algorithms for
Computer Graphics," IEEE Computer Graphics and Applications, pp. 59-75, July
1988.
Six, H.W., Widmayer, P., "Spatial Searching in Geometric Databases,"
Proceedings of the Fourth International Conference on Data Engineering, Los
Angeles, CA, pp. 496-503, February 1988.
Stonebraker, M., Chapter 9, Storage Management Issues, Readings in Database
Systems, edited by Michael Stonebraker,Morgan Kaufmann Publishers, Inc., pp.
567-569, 1988.
Stonebraker, M., Hanson, E., Sellis, T., "Rule Indexing Implementations in
Database Systems," Proceeding of the First International Conference on Expert
Database Systems, Charleston, SC, October 1986.
Stonebraker, M., Rubenstein, B., Guttman, A., "Application of Abstract Data
Types and Abstract Indices to CAD Databases," Proceedings of Engineering Design
Applications of ACM/IEEE Database Week, San Jose, 1983.
Tamminen, M., "Comment on Quad and Oct trees," Communications of the ACM, 27,
pp. 248-249, 1984.
Tamminen, M., "Efficient Spatial Access to a Data Base," Proceedings of the ACM
SIGMOD Conference, pp. 200-206, 1982.
Vaidya, P. D., "An Experimental Spatial Information System," Master's Thesis,
Virginia Polytechnic Institute and State University, January, 1982.
Yu, C. T., Jiang, T. M., "Adaptive Algorithms for balanced Multidimensional
Clustering," Proceedings of the Fourth International Conference on Data
Engineering, Los Angeles, CA, pp. 386-393, February 1988.
Peter van Oosterom
>About a year or so ago I obtained a c++ implementation of an R-Tree from a guy
>in Holland. He sent it to me via email but I inadvertantly deleted the files.
>However, luckily I did make a print out. If you'd like a hard copy of the
>source I'd be happy to look for it and mail a copy to you. I noticed that
>another person (Luigi Perrotta) posted a message requesting the same
>information. If there are too many requests I don't think I can afford to send
>hard copies to everyone. In this posting I've included a list of references
>from the literature related to spatial indexing methods that may be of
>interest. I haven't added to it for about the last year so there's lots more
>recent papers not listed.
This implementation was made by me. At least I live in Holland and have made
a C++ implementation of the R-tree (and several other trees: Cell-tree,
KD2B-tree, BSP-tree, and other new spatial data structures described in
my PhD-thesis "Reactive Data Structures for Geographic Information Systems",
Peter van Oosterom, Leiden University, December 1990).
The R-tree implementation is distributed with GEO, a GIS frontend for the
DBMS Postgres. By the way, Postgres also has it's own R-tree implementation
(which is included in the with Postgres distribution).
Both systems can be ftp'ed from postgres.berkeley.edu (in the /pub dir).
Regards, Peter van Oosterom. (email: oost...@fel.tno.nl)
James Helman
[an extensive bibliography on spatial data structures]
Don't overlook Samet's excellent two volume treatment of spatial data
structures. He includes a brief section on R-trees.
AUTHOR: Samet, Hanan.
TITLE: The design and analysis of spatial data structures / Hanan Samet.
IMPRINT: Reading, Mass. : Addison-Wesley, c1990.
AUTHOR: Samet, Hanan.
TITLE: Applications of spatial data structures : computer graphics, image
processing, and GIS / Hanan Samet.
IMPRINT: Reading, Mass. : Addison-Wesley, c1990.
-jim
jim helman - silicon graphics - ji...@surreal.asd.sgi.com - 415.335.1151
--
Moderated by SCRI Vis <> Submissions to: grap...@scri1.scri.fsu.edu
Guy, John R. Murray <> Administrivia to: graphics...@scri1.scri.fsu.edu