Kyoosang Cho
ABSTRACT
Dynamic and complex computation in the area of Geographic Information System (GIS) or Mobile Computing System involves huge amount of spatial objects such as points, boxes, polygons, etc and requires a scalable data structure and an efficient management tool for this information. In this paper, for a dynamic management of spatial objects, we construct a hierarchical dynamic data structure, called an IST/OPG hierarchy, which may overcome some limitations of existing Spatial Access Methods (SAMs). The hierarchy is constructed by combining three primary components: (1) Minimum Boundary Rectangle (MBR), which is the most widely used method among SAMs; (2) the population-based domain slicing, which is modified from the Grid File [14]; (3) extended optimal Integer Searching algorithm [4]. For dynamic management of spatial objects in the IST/OPG hierarchy, a number of primary and supplementary operations are introduced. This paper includes a comparative analysis of our approach with previous SAMs, such as R-Tree, R+-Tree and R*-Tree and QSF-Tree. The results of analysis show that our approach is better than other SAMs in construction and query time and space requirements. Specifically, for a given search domain with n objects, our query operations yield $O($ \scriptsize $\sqrt {\frac {\log n} {\log\log n}}$\normalsize $)$ compared to $O(\log n)$ of the fast SAM and an IST/OPG hierarchy containing $n$ objects can be constructed in $O(n$ \scriptsize $\sqrt {\frac {\log n}{\log\log n}}$\normalsize $)$ time and O(n) space.
- 1.Amir, A., Efrat, A., Indyk, P., and Sam&, H. Eficient regular data structures and algorithms for location and proximity problems. manuscript (www.graphics.stanford.edu/ alon/regdata.html).Google Scholar
- 2.Andersson, A. Sublogarithmic searching without multiplications. In Proc. 36th IEEE Symposium on Foundations of Computer Science, 1995, pp. 655-663. Google ScholarDigital Library
- 3.Andersson, A. Faster deterministic sorting and searching in linear space. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, October 1996, pp. 135-141. Google ScholarDigital Library
- 4.Andersson, A., and Thorup, M. Tight(er) worst-case bounds on dynamic searching and priority queues. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing(STOC '00), ACM Press, New York, 2000, pp. 335-342. Google ScholarDigital Library
- 5.Beakmann. N. Kriegel, H., Schneider, R., and Seeger, B. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. Proceedings of ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990, pp. 322-331. Google ScholarDigital Library
- 6.Bently J. L. Miltidimensional binary search trees use for associative searching. Communications of the ACM M(9), 1975, pp. 509-517. Google ScholarDigital Library
- 7.Cho, K. "A Study on Spatial Access Method Based on Integer Searching Algorithms, " M.S. Thesis, Dept. of CST, University of Missouri Kansas City, December 2000.Google Scholar
- 8.Gaede, V., and Gunther, 0. Multi-dimensional Access Methods. ACM Computing Surveys, 30(2), June 1998, pp. 170-231. Google ScholarDigital Library
- 9.Boas, V. P., Kaas, R., and Zijlstra, E. Design and Implementation of an Efficient Priority Queue. Mathematical Systems Theory 10, Springer-Verlag New York Inc. 1977, pp. 99-127.Google Scholar
- 10.Gunther, O., and Bilmes, J. Tree-based access methods for spatial databases: implementation and performance evaluation. IEEE Transactions on Knowledge and Data Engineering, 3(3), Sept. 1991, pp. 342-356. Google ScholarDigital Library
- 11.Gunther, 0. The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases. Proc. 5th International Conference on Data Engineering, 1989, pp. 508-605. Google ScholarDigital Library
- 12.Guttman, A. R trees: A dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD Conference ACM, New York. 1984. PP. 47-57. Google ScholarDigital Library
- 13.Henrich. A. and Six. H. Ho& to Split &cketsin Spatial Data Structures. In Geographic Database Management &stems Gambosi. G. Scholl, M., and Six, H.W. eds., Springer-Verlag, Berlin, 1991: pp: 212-244.Google Scholar
- 14.Hinrichs, K. Implementation of the grid file: Design Concepts and experience. BIT 25, 1985, pp. 569-592. Google ScholarDigital Library
- 15.Hutflesz, A., Six, H. W., and Widmayer, P. The r-file: an efficient access structure for proximity queries. Proceedings of 6th IEEE International Conference on Data Engineering, 1990, pp. 372-379. Google ScholarDigital Library
- 16.Kamel, I., and Faloutsos, C. Hilbert R-Tree: An Improved R-Tree Using Fractals. Proc. 20th International Conference on Very Large Data Bases, 1994. pp. 500-509. Google ScholarDigital Library
- 17.Kriegel, H.- P., Horn, H., and Schiwietz, M. The performance of object decomposition techniques for spatial query processing. In Proc. 2nd Symposium on iarge Spatial Databases, Lecture Notes in Computer Science, 525, 1991, pp. 257-276. Google ScholarDigital Library
- 18.Kuan, J., and Lewis,.P. A study on data point search for HG-trees. SIGMOD Record, 28(l), March 1999, pp. 90-96. Google ScholarDigital Library
- 19.Nievergelt, J., Hinterberger, H., and Sevcik, K.C. The grid file: an adaptable, symmetric multikey file structure. ACM Trans. on database systems 9(l), 1984, pp. 38-71. Google ScholarDigital Library
- 20.Oosterom, P. "Reactive Data Structures for Geographic Information Systems," Ph.D. Thesis, Dept. of CS, Leiden University, December 1990.Google Scholar
- 21.Orenstein, J. A., and Merrett, T. A class of data structures for associative searching. In Proceedings of SIGART-SIGMOD 3rd Symposium on Principles of Database Systems, Waterloo, Canada, 1984, pp. 181-190. Google ScholarDigital Library
- 22.Orlandic, R. A High-Precision Spatial Access Method Based on a New Linear Representation of Quadtrees. Proceedings of 1st Conference on Information and Knowledge Management CIKM-92, Baltimore, MD, 1992, pp. 499-50s.Google Scholar
- 23.Papadias, D., Theodoridis, Y., Sellis, T., and Egenhofer, M. J. Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-Trees, Proce. ACM SIGMOD Int. Conj. On Management of Data, 1995, pp. 92-103. Google ScholarDigital Library
- 24.Sellis. T. Roussopoulos. N. and Faloutsos, C. The R-Tree A Dynamic Index For Multi-Dimensional Obiects. Proceedinos of the 13th VLDB Conference, Brighton 1987, pp. 507-518. Google ScholarDigital Library
- 25.Six, H., and Widmayer, P. Spatial searching in geometric databases. Proceedings of the 4th International Conference on Data Engineering, Los Angeles, 1988, pp. 496-503. Google ScholarDigital Library
- 26.Wang, W, Yang J., and Muntz R. PK-Tree: A Spatial Index Structure for High Dimensional Point Data, In Proceeding of 5th International Conference on Foundation of Data Organization (FODO98), Japan, November, 1998.Google Scholar
- 27.White, D. A., and Jain, R. Similarity indexing with the ss-tree, Proceedings of the 12th ICDE, Feb. 1996. pp. 516-523. Google ScholarDigital Library
- 28.Yu, B., Orlandic, R. and Evens, M. Simple QSF-Trees: An Efficient and Scalable Spatial Access Method. CKIM '99, Kansas City, MO, Nov. 1999, pp. 5-14. Google ScholarDigital Library
Index Terms
- Dynamic and hierarchical spatial access method using integer searching
Recommendations
Efficient processing of spatial selection and join operations using SB/sup +/-tree
IDEAS '97: Proceedings of the 1997 International Symposium on Database Engineering & ApplicationsIntroduces a spatial access method, the SB/sup +/-tree, that is based on the B/sup +/-tree structure. For each axis of the space, a set of indexing points is generated; an indexing point is created whenever a new minimum bounding rectilinear rectangle (...
Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search
FOCS '14: Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer ScienceWe present a data structure representing a dynamic set S of w-bit integers on a w-bit word RAM. With |S| = n and w ≥ log n and space O(n), we support the following standard operations in O(log n/log w) time: insert(x) sets S = S + {x}. delete(x) sets S =...
Parallel integer sorting and simulation amongst CRCW models
AbstractIn this paper a general technique for reducing processors in simulation without any increase in time is described. This results in an O(√logn) time algorithm for simulating one step of PRIORITY on TOLERANT with processor-time product of O(n log ...
Comments