Abstract
We consider the 2-dimensional space with integer coordinates in the range [1, N] x [1, N]. We present the MPST (Modified Priority Search Tree) index structure which reports the k points that lie inside the quadrant query range (- ∞, b] x (- ∞, c] in optimal O(k) time. Our Index Scheme is simple, fast and it can be used in various geometric or spatial applications such as: (1) 2 D dominance reporting on a grid (2) 2D maximal elements on a grid. Then, based on structures of Gabow et al. [6] and Beam and Fich [31] we describe an index scheme, which handles in an efficient way window queries in spatial database applications. In the general case in which the plane has real coordinates the above time results are slowed down by adding a logarithmic factor due to the normalization technique.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, P.K.: Range searching, Technical Report CS-1996-05, Dept. of Computer Science, Duke University (1996)
Arge, L., Vitter, J.S.:Optimal dynamic interval management in external memory, Proceedings of the IEEE Symposium on Foundations of Computer Science (1996)
Driscoll, J. R., Sarnak, N., Sleator, D. D., Tarjan, R. E.: Making data structures persistent, J. Comp. Syst. Sci. 38 pp. 86–124 (1989)
Comer, D.: The ubiquitous B-tree, ACM Computing Surveys, 11(2) (1979)
Fries, O., Mehlhorn, K., Naher, S. and Tsakalidis, A.: A loglogn data structure for three sided rane queries, Inform. Process. Lett. 25, pp. 269–273 (1987)
Gabow, H. N., Bentley, J. L., and Tarjan, R. E.: Scaling and related techniques for geometry problems, in Proceedings, l6th Annual ACM Symp. on Theory of Computing, pp. 135–143 (1984)
Gupta, P., Janardan, R., Smid, M. and Dasgupta, B.: The rectangle enclosure and point dominance problem revisited, in, Proceedings, 11th Annual ACM Symp. on Comp. Geometry, pp. 162–171 (1995)
Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestor, SIAM J. Comput. 13, pp. 338–355 (1994)
Karlsson, R.G. and Overmars, M. H.: Scanline algorithms on a grid, Technical Rep. RUU-CS-86-18, Dept. of Computer Science, University of Utrecht (1986)
Matousek, J.: Geometric range searching, ACM Computing Surveys 26, pp. 421–561 (1994)
McCreight, E.M.: Priority search trees, SIAM J. Comput. 14, pp. 257–276 (1985)
Overmars, M.H.: Efficient data structures for range searching on a grid, J. Algorithms 9, pp. 254–275 (1988)
Preparata, F.P. and Shamos, M. I.: Computational Geometry, Springer-Verlag, New York, (1985)
Vuillemin, J.: A unifying look at data structures, C. ACM 23 pp. 229–239 (1980)
Grossi, R., Italiano, G., F.: Efficient cross-trees for external memory, In J. Abello and J.S. Vitter, editors, External Algorithms and Visualization (1998)
Guttman, A.: R-trees: A Dynamic Index Structure for Spatial Searching, ACM SIGMOD, (1984)
Sellis, T., Roussopoulos, N., Faloutsos, C.,: The R+-tree: A Dynamic Index for Multidimensional Objects, VLDB (1987)
Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, B.: The R*-tree: an Efficient and Robust Access Method for Points and Rectangles, ACM SIGMOD (1990)
Papadias, D., Theodoridis, Y.: Spatial Relations, Minimum Bounding Rectangles, and Spatial Data Structures, International Journal of Geographic Information Science, Vol. 11(2) (1997)
Theodoridis, Y., Papadias, D., Stefanakis, E., Sellis, T.: Direction Relations and Two-Dimensional Range Queries: Optimization Techniques, Data & Knowledge Engineering, vol. 27(3) (1998)
Theodoridis, Y., Vazirgiannis, M., Sellis, T.:Spatio-Temporal Indexing for Large Multimedia Applications, 3” IEEE Conference on Multimedia Computing and Systems, (1996)
Theodoridis, Y., Sellis, T.: A Model for The Prediction of R-Tree Performance, ACM PODS(1996)
Gaede, V.: Optimal Redundancy in Spatial Database Systems, International Symposium on Spatial Databases (SSD) (1995)
Hoel, E., Samet, H.: Benchmarking Spatial Join Operations with Spatial Output, VLDB Conference (1995)
Kanellakis, P.C., Ramaswamy, S., Vengroff, D.E., Vitter, J.S.: Indexing for data models with constraints and classes, Journal of Computer and System Sciences, 52(3) (1996)
Mehlhorn., K., Data Structures and Algorithms 3-Multidimensional Searching and Computational Geometry, Springer Verlag (1984)
Ramaswamy, S., Subramanian, S.: Path Caching: a technique for optimal external searching in Proceedings of the 13th ACM Conference on Principles of Database Systems (1994)
Subramanian, S., Ramaswamy, S.: The P-range tree: a new data structure for range searching in secondary memeory, ACM-SIAM Symposium on Discrete Algorithms (1995)
Vengroff, D.,E., Vitter, J.,S., Efficient 3-d range searching in external memory, ACM Symposium on Theory of Computation (1996)
Vitter, J.S.: External Memory Algorithms invited paper in European Symposium on Algorithms (1998)
Beam, P., Fich, F.: Optimal Bounds for the Predecessor Problem, In Proceedings of the Thirty First Annual ACM Symposium on Theory of Computing, Atlanta, GA (1999)
Arge, L., Samoladas, V., Vitter, J.S.: Two dimensional indexability and optimal range search indexing, in Proceedings of the ACM Symposium on Principles of Database Systems, (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kitsios, N., Makris, C., Sioutas, S., Tsakalidis, A., Tsaknakis, J., Vassiliadis, B. (2000). 2-D Spatial Indexing Scheme in Optimal Time. In: Štuller, J., Pokorný, J., Thalheim, B., Masunaga, Y. (eds) Current Issues in Databases and Information Systems. ADBIS DASFAA 2000 2000. Lecture Notes in Computer Science, vol 1884. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44472-6_9
Download citation
DOI: https://doi.org/10.1007/3-540-44472-6_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67977-6
Online ISBN: 978-3-540-44472-5
eBook Packages: Springer Book Archive