Advanced indexing methods for large spatial data in complex dynamic scenes
Abstract
This paper is dedicated to review of recent methods for indexing of multidimensional data and their use for modeling of large-scale dynamic scenes. The problem arises in many application domains such as computer graphics systems, virtual and augmented reality systems, CAD systems, robotics, geographical information systems, project management systems, etc. Two fundamental approaches to the indexing of multidimensional data, namely object aggregation and spatial decomposition, have been outlined. In the context of the former approach balanced search trees, also referred as object pyramids, have been discussed. In particular, generalizations of B-trees such as R-trees, R*-trees, R+-trees have been discussed in conformity to indexing of large data located in external memory and accessible by pages. The conducted analysis shows that object aggregation methods are well suited for static scenes but very limited for dynamic environments. The latter approach assumes the recursive decomposition of scene volume in accordance with the cutting rules. Space decomposition methods are octrees, A-trees, bintrees, K-D-trees, X-Y-trees, treemaps and puzzle-trees. They support more reasonable compromise between performance of spatial queries and expenses required to update indexing structures and to keep their in concordant state under permanent changes in the scenes. Compared to object pyramids, these methods look more promising for dramatically changed environments. It is concluded that regular dynamic octrees are most effective for the considered applications of modeling of large-scale dynamic scenes.
About the Authors
V. A. Zolotov
ISP RAS, Moscow
Russian Federation
Russian Federation
V. A. Semenov
ISP RAS, Moscow
Russian Federation
Russian Federation
References
1. Semenov V.A., Kazakov K.A., Morozov S.V., Tarlapan O.A., Zolotov V.A., Dengenis T., "4D modeling of large industrial projects using spatio-temporal decomposition" in eWork and eBusiness in Architecture, Engineering and Construction, London, UK, pp. 89-95, 2010.
2. Kuznecov S.D., Kostenko B.B. "Istoriya i aktual'nye problemy temporal'nykh baz dannykh" [History and actual state of temporal databases]. Trudy ISP RАN [The Proceedings of ISP RAS], vol. 2, № 13, pp. 77-114, 2007. (in Russian)
3. Semenov V.A., Kazakov K.A., Zolotov V.A., Jones H., Jones S. "Combined strategy for efficient collision detection in 4D planning applications" in Computing in Civil and Building Engineering, Nottingham, UK, pp. 31-39, 2010.
4. Bayer R., McCreight E. M., "Organization and maintanence of large ordered indexes" Acta Informatica, vol. 3, no. 1, pp. 173-189, 1972.
5. Abel D. J. "A B+-tree structure for large quadtrees" Computer Vision, Graphics, and Image Processing, vol. 1, no. 27, pp. 19-31, July 1984.
6. Comer D. "The ubiquitos B-tree" ACM Computing Surveys, vol. 2, no. 11, pp. 121-137, June 1979.
7. Sagan H. "Space-Filling curves", New York: Springer-Verlag, 1994.
8. Guttman A. "R-trees: a dynamic index structure for spatial searching" in Proceedings of the ACM SIGMOD Conference, Boston, USA, 1984.
9. Sellis T., Roussopoulos N., Faloutsos C. "The R+-tree: a dynamic index for multi-dimentional objects" in Proceedings of the 13th International Conference on Very Large Databases (VLDB), Brighton, UK, 1987.
10. Beckmann N., Kriegel H. P., Schneider R., Seeger B. "The R*-tree: an efficient and robust access method for points and rectangles" in Proceedings of the ACM SIGMOD Conference, Atlantic City, USA, 1990.
11. Yu C., Ooi B. C., Tan K.-L., Jagadish H. V. "Indexing the distance: an efficient method to KNN processing" in Proceedings of the 27st international Conference on Very Large Databases (VLDB), Roma, Italy, 2001.
12. Beygelzimer A., Kakade S., Langford J., "Cover Trees for Nearest Neighbor" in Proceedings of the International Conference on Machine Learning (ICML), 2006.
13. Burkhard W. A., Keller R. "Some approaches to best-match file searching" Communications of the ACM, vol. 4, no. 16, pp. 230-236, April 1973.
14. Bentley J. L. "Decomposable searching problems" Information Processing Letters, vol. 5, no. 8, pp. 244-251, June 1979.
15. Bentley J. L., Wood D. "An optimal worst-case algorithm for reporting intersections of rectangles" IEEE Transactions on Computers, vol. 7, no. 29, pp. 571-577, July 1980.
16. Edelsbrunner H. "A new approach to rectangle intersections: part II" International Journal of Computer Mathematics, Vols. 3-4, no. 13, pp. 221-229, 1983.
17. McCreight E. M. "Priority search trees" SIAM Journal on Computing, vol. 2, no. 14, pp. 257-276, May 1985.
18. Fuchs H., Abram G., Grant E. "Near real-time shaded display of rigid objects" Computer Graphics, vol. 3, no. 17, pp. 65-72, 1983.
19. Fuchs H., Kedem Z., Naylor B. "On visible surface generation by a priori tree structures" Computer Graphics, vol. 3, no. 14, pp. 124-133, 1980.
20. Henrich A., Six H. W., Widmayer P. "The LSD-tree: spatial access to multidimentional point an non-point data" in Proceedings of the 15th International Conference on Very Large Databases (VLDB), Amsterdam, Netherlands, 1989.
21. Lomet D., Salzberg B. "The hB-tree: a multi-attribute indexing method with good guaranteed performance" ACM Transactions on Database Systems, vol. 4, no. 15, pp. 625-658, December 1990.
22. Xu J., Zheng B., Lee W. C., Lee D. L. "The D-tree: an index structure for planar point queries in location-based wireless services" IEEE Transactions on Knowledge and Data Engineering, vol. 12, no. 16, pp. 1526-1542, December 2004.
23. Bentley J.L. "Multidimensional binary search trees used for associative searching" Communications of the ACM, vol. 9, no. 18, pp. 509-517, September 1975.
24. Friedman J. H., Bentley J. L., Finkel R. A. "An algorithm for finding best matches in logarithmic expected time" ACM Transactions on Mathematical Software, vol. 3, no. 3, pp. 209-226, September 1977.
25. Chakrabarti K., Mehrotra S. "The hybrid tree: an index structure for high dimentional feature spaces" in Proceedings of the 15th IEEE International Conference on Data Engineering, Sydney, Australia, 1999.
26. Mount D. M., Arya S. "ANN: a library for aproximate nearest neighbour searching" in Proceedings of the 2nd Annual Center for Geometric Computing Workshop on Computational Geometry, Durham, 1997.
27. White D. A., Jain R. "Similarity indexing with the SS-tree" in Proceedings of the 12th IEEE International Conference on Data Engineering, New Orleans, USA, 1996.
28. Arya S., Mount D. M., Netanyahu N. S., Silverman R., Wu A. Y. "An optimal algorithm for approximate nearest neighbour searching in fixed dimentions" Journal of the ACM, vol. 6, no. 45, pp. 891-923, November 1998.
29. O'Rourke J. "Dynamically quantized spaces for focusing Hough transform" in Proceedings of the 7th International Joint Conference on Artificial Intelligence, Vancouver, Canada, 1981.
30. Kenneth R. Sloan Jr., "Dynamicaly quantized pyramids" in Proceedings of the 7th International Joint Conference on Artificial Intelligence, Vancouver, Canada, 1981.
31. Becker L., Hinrichs K., Finke U. "A new algorithm for computing joins with grid files" in Proceedings of the 9th IEEE Conference on Data Engineering, Vienna, Austria, 1993.
32. Samet H. "Foundations of Multidimentional and Metric Data Structures", San Francisco: Morgan Kaufmann, 2006.
33. Bogdanovich P., Samet H. "The ATree: a data structure to support a very large scientific databases" in Springer-Verlag Lecture Notes in Computer Science, vol. 1737, P. Agouris and A. Stefanidis, Eds., Springer-Verlag, 1990, pp. 235-248.
34. Knowlton K. "Progressive transmission of gray-scale and binary pictures by simple efficient and lossless encoding schemes" Proceedings of IEEE, vol. 7, no. 68, pp. 885-896, 1980.
35. Cohen Y., Landy M., Pavel M. "Hierarchical coding of binary images" IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 3, no. 7, pp. 284-298, 1985.
36. Nagy G., Wagle S. "Hierarchical representation of optically scanned documents" in Proceedings of 7th International Conference on Pattern Recognition, 1984.
37. Dengel A. "Object-oriented representation of image space by puzzle-trees" SPIE Visual Communications and Image Processing, pp. 20-30, 1991.
38. Shneiderman B. "Tree visualization with tree maps: 2-d space-filling approach" ACM Transactions on Graphics, vol. 1, no. 11, pp. 92-99, 1992.
39. Kamel I., Faloutsos C. "Hilbert R-tree: an improved R-tree using fractals" Proceedings of 20th International Conference on Very Large Data Bases, vol. 3, no. 3, 1994.
40. Kamel I., Faloutsos C. "On packing R-trees" in Proceedings of 2nd International Conference on Information and Knowledge Management, 1993.
41. Leutenegger S. T., Lopez M. A., Edgington J. "STR: a simple and efficient algorithm for R-tree packing" in Proceedings of the 13th IEEE International conference on Data Engineering, 1997.
42. Klosowski J. T., Held M., Mitchell J. S. B., Sowizral H., Zikan K. "Efficient collision detection using bounding volume hierarchies of k-DOPs" IEEE Transactions on Visualization and Computer Graphics, vol. 1, no. 4, pp. 21-36, Januray 1998.
43. Gunther O., Bilmes J. "Tree-based access methods for spatial databases: implementation and performance evaluation" IEEE Transactions on Knowledge and Data Engineering, vol. 3, no. 3, pp. 342-356, 1991.
44. Gottschalk S., Lin M. C., Manocha D. "OBB Tree: a hierarchical structure for rapid interference detection" in Proceedings of the SIGGRAPH'96 Conference, New Orleans, USA, 1996.
45. Gottschalk S. "Collision queries using oriented bounding boxes", Chapel Hill: The University of North Carolina, 2000.
46. Theodoris Y., Sellis T. "Optimization issues in R-tree construction" in IGIS’94: Geographic Information Systems, International Workshop on Advanced Research in Geographic Information Systems, 1994.
47. Garcia Y., Lopez M., Leutenneger S. "A greedy algorithm for bulk loading R-trees" in Proceedings of the 6th ACM International Symposium on Advances in Geographic Information Systems, 1997.
48. Becker B., Franciosa P., Gschwind S., Ohler T., Thiemt G., Widmayer P., "Enclosing many boxes by an optimal pair of boxes" in Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, 1992.
49. Garcia Y., Lopez M., Leutenneger S. "An optimal node splitting for R-trees" in Proceedings of the 24th International Conference on Very Large Data Bases, 1998.
50. Ang C., Tan T. "New linear node splitting algorithm for R-trees" in Advances in Spatial Databases – 5th International Symposium, SSD’97, 1997.
51. Hoel E. G., Samet H. "Benchmarking spatial join operations with spatial output" in Proceedings of the 21th International Conference on Very Large Databases (VLDB), Zurich, Switzerland, 1995.
52. Cai M., Revesz P. "Parametric rectangles: an index structure for moving objects" in Proceedings of the 10th COMAD International conference on management of data, 2000.
53. Saltenis S., Jensen C. S., Leuteenegger S. T., Lopez M. A., "Indexing the positions of continuously moving objects" in Proceedings of the ACM SIGMOD Conference, 2000.
54. Tao Y., Papadias D., Sun J. "The TRP*-tree: an optimized spatio-temporal access for predictive queries" in Proceedings of the 29th international conference on Very Large Data Bases (VLDB), 2003.
55. Bell S. B. M., Diaz B. M., Holroyd F., Jackson M. J. "Spatially referenced method of processing raster and vector data" Image and Vision Computing, vol. 4, no. 1, pp. 211-220, 1983.
56. Gibson L., Lucas D. "Vectorization of raster images using hierarchical methods" Computer Graphics and Image Processing, vol. 1, no. 20, pp. 82-29, 1982.
57. Adel’son-Vel’sky G.M, Landis E.M. "Odin algoritm organizatsii informatsii"[An algorithm for information organization] Proceedings of RAS USSR, № 146, pp. 263-266, 1962.
58. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. "Red–Black Trees" in Introduction to Algorithms, MIT Press and McGraw-Hill, 2001, p. 273–301.
59. Amir A., Efrat A., Indyk P., Samet H. "Efficient algorithms and regular data structures for dilation, location and proximity problems" Algorithmica, vol. 2, no. 30, pp. 164-187, 2001.
60. Schrack G. "Finding neighbors of equal size in linear quadtrees and octrees in constant time" CVGIP: Image Understanding, vol. 3, no. 55, pp. 221-230, 1992.
61. Kedem G. "The quad-CIF tree: a data structure for hierarchical on-line algorithms" in Proceedings of the 19th Design Automation Conference, 1992.
62. Frank A. U., "Problems of realizing LIS: storage methods for space related data: the fieldtree" ETH, 1983.
63. Frank A. U., Barrera R. "The Fieldtree: a data structure for geographic information systems" in Springer-Verlag Lecture Notes in Computer Science, vol. 409, [ed] Buchmann A., Gunter O., Smith T., Wang Y., Springer-Verlag, 1989, pp. 29-44.
64. Ulrich T., "Loose octrees" in Game programming gems, Rockland, Charles river media, 2000, pp. 444-453.
65. Samet H. "Neighbor finding techniques for images represented by quadtrees" Computer Graphics and Image processing, vol. 1, no. 18, pp. 37-57, 1982.
Review
For citations:
Zolotov V.A., Semenov V.A. Advanced indexing methods for large spatial data in complex dynamic scenes. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2013;24. (In Russ.)
Email this article 