Современные методы поиска и индексации многомерных данных в приложениях моделирования больших динамических сцен
Аннотация
Статья посвящена современным методам поиска и индексации многомерных данных применительно к задачам моделирования больших динамических сцен. Подобные задачи имеют разнообразные приложения в компьютерной графике и анимации, мультимедийных базах данных, системах виртуальной и дополненной реальности, системах автоматизированного проектирования и производства, робототехнике, геоинформационных системах, системах комплексной инженерии и управления проектами, однако их решение часто оказывается невозможным из-за высокой вычислительной сложности алгоритмов пространственно-временной локализации объектов сцен и требует применения специальных схем индексации многомерных данных. В статье обсуждаются два фундаментальных подхода к организации подобных схем, а также проводится их сравнительный анализ в контексте комплексных требований, предъявляемых к приложениям обсуждаемого класса.
Список литературы
1. V. Semenov, K. Kazakov, S. Morozov, O. Tarlapan, V. Zolotov and T. Dengenis, "4D modeling of large industrial projects using spatio-temporal decomposition," in eWork and eBusiness in Architecture, Engineering and Construction, London, UK, 2010.
2. С. Кузнецов и Б. Костенко, «История и актуальные проблемы темпоральных баз данных,» Труды Института системного программирования, т. 2, № 13, стр. 77-114, 2007.
3. V. Semenov, K. Kazakov, V. Zolotov, H. Jones and S. Jones, "Combined strategy for efficient collision detection in 4D planning applications," in Computing in Civil and Building Engineering, Nottingham, UK, 2010.
4. R. Bayer and E. M. McCreight, "Organization and maintanence of large ordered indexes," Acta Informatica, vol. 3, no. 1, pp. 173-189, 1972.
5. D. J. Abel, "A B+-tree structure for large quadtrees," Computer Vision, Graphics, and Image Processing, vol. 1, no. 27, pp. 19-31, July 1984.
6. D. Comer, "The ubiquitos B-tree," ACM Computing Surveys, vol. 2, no. 11, pp. 121-137, June 1979.
7. H. Sagan, Space-Filling curves, New York: Springer-Verlag, 1994.
8. Guttman, "R-trees: a dynamic index structure for spatial searching," in Proceedings of the ACM SIGMOD Conference, Boston, USA, 1984.
9. T. Sellis, N. Roussopoulos and C. Faloutsos, "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. N. Beckmann, H. P. Kriegel, R. Schneider and B. Seeger, "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. C. Yu, B. C. Ooi, K.-L. Tan and H. V. Jagadish, "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, S. Kakade and J. Langford, "Cover Trees for Nearest Neighbor," in Proceedings of the International Conference on Machine Learning (ICML), 2006.
13. W. A. Burkhard and R. Keller, "Some approaches to best-match file searching," Communications of the ACM, vol. 4, no. 16, pp. 230-236, April 1973.
14. J. L. Bentley, "Decomposable searching problems," Information Processing Letters, vol. 5, no. 8, pp. 244-251, June 1979.
15. J. L. Bentley and D. Wood, "An optimal worst-case algorithm for reporting intersections of rectangles," IEEE Transactions on Computers, vol. 7, no. 29, pp. 571-577, July 1980.
16. H. Edelsbrunner, "A new approach to rectangle intersections: part II," International Journal of Computer Mathematics, Vols. 3-4, no. 13, pp. 221-229, 1983.
17. E. M. McCreight, "Priority search trees," SIAM Journal on Computing, vol. 2, no. 14, pp. 257-276, May 1985.
18. H. Fuchs, G. Abram and E. Grant, "Near real-time shaded display of rigid objects," Computer Graphics, vol. 3, no. 17, pp. 65-72, 1983.
19. H. Fuchs, Z. Kedem and B. Naylor, "On visible surface generation by a priori tree structures," Computer Graphics, vol. 3, no. 14, pp. 124-133, 1980.
20. Henrich, H. W. Six and P. Widmayer, "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. D. Lomet and B. Salzberg, "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. J. Xu, B. Zheng, W. C. Lee and D. L. Lee, "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. J. Bentley, "Multidimensional binary search trees used for associative searching," Communications of the ACM, vol. 9, no. 18, pp. 509-517, September 1975.
24. J. H. Friedman, J. L. Bentley and R. A. Finkel, "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. K. Chakrabarti and S. Mehrotra, "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. D. M. Mount and S. Arya, "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. D. A. White and R. Jain, "Similarity indexing with the SS-tree," in Proceedings of the 12th IEEE International Conference on Data Engineering, New Orleans, USA, 1996.
28. S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman and A. Y. Wu, "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. J. O'Rourke, "Dynamically quantized spaces for focusing Hough transform," in Proceedings of the 7th International Joint Conference on Artificial Intelligence, Vancouver, Canada, 1981.
30. K. R. S. Jr., "Dynamicaly quantized pyramids," in Proceedings of the 7th International Joint Conference on Artificial Intelligence, Vancouver, Canada, 1981.
31. L. Becker, K. Hinrichs and U. Finke, "A new algorithm for computing joins with grid files," in Proceedings of the 9th IEEE Conference on Data Engineering, Vienna, Austria, 1993.
32. H. Samet, Foundations of Multidimentional and Metric Data Structures, San Francisco: Morgan Kaufmann, 2006.
33. P. Bogdanovich and H. Samet, "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. K. Knowlton, "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. Y. Cohen, M. Landy and M. Pavel, "Hierarchical coding of binary images," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 3, no. 7, pp. 284-298, 1985.
36. G. Nagy and S. Wagle, "Hierarchical representation of optically scanned documents," in Proceedings of 7th International Conference on Pattern Recognition, 1984.
37. Dengel, "Object-oriented representation of image space by puzzle-trees," SPIE Visual Communications and Image Processing, pp. 20-30, 1991.
38. Shneiderman, "Tree visualization with tree maps: 2-d space-filling approach," ACM Transactions on Graphics, vol. 1, no. 11, pp. 92-99, 1992.
39. Kamel and C. Faloutsos, "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 and C. Faloutsos, "On packing R-trees," in Proceedings of 2nd International Conference on Information and Knowledge Management, 1993.
41. S. T. Leutenegger, M. A. Lopez and J. Edgington, "STR: a simple and efficient algorithm for R-tree packing," in Proceedings of the 13th IEEE International conference on Data Engineering, 1997.
42. T. Klosowski, M. Held, J. S. B. Mitchell, H. Sowizral and K. Zikan, "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. O. Gunther and J. Bilmes, "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. S. Gottschalk, M. C. Lin and D. Manocha, "OBB Tree: a hierarchical structure for rapid interference detection," in Proceedings of the SIGGRAPH'96 Conference, New Orleans, USA, 1996.
45. S. Gottschalk, Collision queries using oriented bounding boxes, Chapel Hill: The University of North Carolina, 2000.
46. Y. Theodoris and T. Sellis, "Optimization issues in R-tree construction," in IGIS’94: Geographic Information Systems, International Workshop on Advanced Research in Geographic Information Systems, 1994.
47. Y. Garcia, M. Lopez and S. Leutenneger, "A greedy algorithm for bulk loading R-trees," in Proceedings of the 6th ACM International Symposium on Advances in Geographic Information Systems, 1997.
48. B. Becker, P. Franciosa, S. Gschwind, T. Ohler, G. Thiemt and P. Widmayer, "Enclosing many boxes by an optimal pair of boxes," in Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, 1992.
49. Y. Garcia, M. Lopez and S. Leutenneger, "An optimal node splitting for R-trees," in Proceedings of the 24th International Conference on Very Large Data Bases, 1998.
50. C. Ang and T. Tan, "New linear node splitting algorithm for R-trees," in Advances in Spatial Databases – 5th International Symposium, SSD’97, 1997.
51. E. G. Hoel and H. Samet, "Benchmarking spatial join operations with spatial output," in Proceedings of the 21th International Conference on Very Large Databases (VLDB), Zurich, Switzerland, 1995.
52. M. Cai and P. Revesz, "Parametric rectangles: an index structure for moving objects," in Proceedings of the 10th COMAD International conference on management of data, 2000.
53. S. Saltenis, C. S. Jensen, S. T. Leuteenegger and M. A. Lopez, "Indexing the positions of continuously moving objects," in Proceedings of the ACM SIGMOD Conference, 2000.
54. Y. Tao, D. Papadias and J. Sun, "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. S. B. M. Bell, B. M. Diaz, F. Holroyd and M. J. Jackson, "Spatially referenced method of processing raster and vector data," Image and Vision Computing, vol. 4, no. 1, pp. 211-220, 1983.
56. Gibson and D. Lucas, "Vectorization of raster images using hierarchical methods," Computer Graphics and Image Processing, vol. 1, no. 20, pp. 82-29, 1982.
57. Г. М. Адельсон-Вельский и Е. М. Ландис, «Один алгоритм организации информации,» Доклады Академии Наук СССР, № 146, стр. 263-266, 1962.
58. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, "Red–Black Trees," in Introduction to Algorithms, MIT Press and McGraw-Hill, 2001, p. 273–301.
59. Amir, A. Efrat, P. Indyk and H. Samet, "Efficient algorithms and regular data structures for dilation, location and proximity problems," Algorithmica, vol. 2, no. 30, pp. 164-187, 2001.
60. G. Schrack, "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. G. Kedem, "The quad-CIF tree: a data structure for hierarchical on-line algorithms," in Proceedings of the 19th Design Automation Conference, 1992.
62. U. Frank, "Problems of realizing LIS: storage methods for space related data: the fieldtree," ETH, 1983.
63. U. Frank and R.Barrera, "The Fieldtree: a data structure for geographic information systems," in Springer-Verlag Lecture Notes in Computer Science, vol. 409, A. Buchmann, O. Gunter, T. Smith and Y. Wang, Eds., Springer-Verlag, 1989, pp. 29-44.
64. T. Ulrich, "Loose octrees," in Game programming gems, Rockland, Charles river media, 2000, pp. 444-453.
65. H. Samet, "Neighbor finding techniques for images represented by quadtrees," Computer Graphics and Image processing, vol. 1, no. 18, pp. 37-57, 1982.
Рецензия
Для цитирования:
Золотов В.А., Семенов В.А. Современные методы поиска и индексации многомерных данных в приложениях моделирования больших динамических сцен. Труды Института системного программирования РАН. 2013;24.
For citation:
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.)
Послать статью по эл. почте 