×

A new framework for addressing temporal range queries and some preliminary results. (English) Zbl 1070.68029

Summary: Given a set of \(n\) objects, each characterized by \(d\) attributes specified at \(m\) fixed time instances, we are interested in the problem of designing space efficient indexing structures such that a class of temporal range search queries can be handled efficiently. When \(m=1\), our problem reduces to the \(d\)-dimensional orthogonal search problem. We establish efficient data structures to handle several classes of the general problem. Our results include a linear size data structure that enables a query time of \(O(\log n \log m+f)\) for one-sided querieswhen \(d=1\), where \(f\) is the number of objects satisfying the query. A similar result is shown for counting queries. We also show that the most general problem can be solved with a polylogarithmic query time using superlinear space data structures.

MSC:

68P10 Searching and sorting
68P15 Database theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, P. K.; Arge, L.; Erickson, J., Indexing moving points, (19th ACM Symp. on Principles of Database Systems (2000)), 175-186
[2] P.K. Agarwal, S. Govindarajan, S. Muthukrishnan, Range search in categorical data: color range searching on grid, in: Proc. 10th European Sympos. Algorithms, 2002, pp. 17-28.; P.K. Agarwal, S. Govindarajan, S. Muthukrishnan, Range search in categorical data: color range searching on grid, in: Proc. 10th European Sympos. Algorithms, 2002, pp. 17-28. · Zbl 1019.68529
[3] M.A. Bender, M. Farach-Colton, The LCA problem revisited, in: Proc. Latin American Theoretical Informatics, 2000, pp. 88-94.; M.A. Bender, M. Farach-Colton, The LCA problem revisited, in: Proc. Latin American Theoretical Informatics, 2000, pp. 88-94. · Zbl 0959.68133
[4] Chazelle, B., Filtering searcha new approach to query-answering, SIAM J. Comput., 15, 3, 703-724 (1986) · Zbl 0612.68088
[5] Chazelle, B., A functional approach to data structures and its use in multidimensional searching, SIAM J. Comput., 17, 3, 427-463 (1988) · Zbl 0679.68074
[6] Chazelle, B., Lower bounds for orthogonal range search I. The reporting case, J. ACM, 37, 2, 200-212 (1990) · Zbl 0696.68051
[7] Chazelle, B., Lower bounds for orthogonal range search I. The arithmetic model, J. ACM, 37, 3, 439-463 (1990) · Zbl 0699.68058
[8] H.N. Gabow, J.L. Bentley, R.E. Tarjan, Scaling and related techniques for geometry problems, in: Proc. 16th Annual ACM Symp. on Theory of Computing, Washington, DC, 1984, pp. 135-143.; H.N. Gabow, J.L. Bentley, R.E. Tarjan, Scaling and related techniques for geometry problems, in: Proc. 16th Annual ACM Symp. on Theory of Computing, Washington, DC, 1984, pp. 135-143.
[9] P. Gupta, R. Janardan, M.H.M. Smid, Efficient algorithms for generalized intersection searching on non-iso-oriented objects, in: Symp. on Computational Geometry, 1994, pp. 369-378.; P. Gupta, R. Janardan, M.H.M. Smid, Efficient algorithms for generalized intersection searching on non-iso-oriented objects, in: Symp. on Computational Geometry, 1994, pp. 369-378.
[10] Gupta, P.; Janardan, R.; Smid, M., Further results on generalized intersection searching problemscounting, reporting, and dynamization, J. Algorithms, 19, 282-317 (1995) · Zbl 0839.68106
[11] P. Gupta, R. Janardan, M. Smid, Computational geometry: generalized intersection searching, in: D. Mehta, S. Sahni (Eds.), Handbook of Data Structures and Applications, CRC Press, Boca Raton, FL, 2004.; P. Gupta, R. Janardan, M. Smid, Computational geometry: generalized intersection searching, in: D. Mehta, S. Sahni (Eds.), Handbook of Data Structures and Applications, CRC Press, Boca Raton, FL, 2004. · Zbl 1387.68261
[12] Harel, D.; Tarjan, R. E., Fast algorithms for finding nearest common ancestors, SIAM J. Comput., 13, 2, 338-355 (1984) · Zbl 0535.68022
[13] J. JaJa, J. Kim, Q. Wang, Temporal range exploration of large scale multidimensional time series data, in: Proc. 16th Internat. Conf. on Scientific and Statistical Database Management, Santorini Island, Greece, 2004, pp. 95-106.; J. JaJa, J. Kim, Q. Wang, Temporal range exploration of large scale multidimensional time series data, in: Proc. 16th Internat. Conf. on Scientific and Statistical Database Management, Santorini Island, Greece, 2004, pp. 95-106.
[14] J. JaJa, J. Kim, Q. Wang, Efficient serial and parallel algorithms for querying large scale multidimensional time series data, Technical Report CS-TR-4608 and UMIACS-TR-2004-50, Institute for Advanced Computer Studies, University of Maryland, College Park, 2004.; J. JaJa, J. Kim, Q. Wang, Efficient serial and parallel algorithms for querying large scale multidimensional time series data, Technical Report CS-TR-4608 and UMIACS-TR-2004-50, Institute for Advanced Computer Studies, University of Maryland, College Park, 2004.
[15] Janardan, R.; Lopez, M., Generalized intersection searching problems, Internat. J. Comput. Geometry Appl., 3, 1, 39-69 (1993) · Zbl 0777.68078
[16] Kolovson, C.; Stonebraker, M., Segment indexesdynamic indexing techniques for multi-dimensional interval data, (Proc. ACM SIGMOD Internat. Conf. on Management of Data (1991)), 138-147
[17] Lanka, S.; Mays, E., Fully persistent \(B^+\)-trees, (Proc. ACM SIGMOD Internat. Conf. on Management of Data (1991)), 426-435
[18] Makris, C.; Tsakalidis, A. K., Algorithms for three-dimensional dominance searching in linear space, Inform. Process. Lett., 66, 6, 277-283 (1998) · Zbl 1078.68805
[19] Manolopoulos, Y.; Kapetanakis, G., Overlapping \(B^+\)-trees for temporal data, (Proc. 5th Jerusalem Conf. on Information Technology (1990)), 491-498
[20] McCreight, E. M., Priority search trees, SIAM J. Comput., 14, 2, 257-276 (1985) · Zbl 0564.68050
[21] C.W. Mortensen, Generalized static orthogonal range searching in less space, Technical Report TR-2003-22, The IT University of Copenhagen, 2003.; C.W. Mortensen, Generalized static orthogonal range searching in less space, Technical Report TR-2003-22, The IT University of Copenhagen, 2003.
[22] Nascimento, M. A.; Silva, J. R.O., Towards historical R-trees, (Proc. ACM Symp. on Applied Computing (1998)), 235-240
[23] Saltenis, S.; Jensen, C. S.; Leutenegger, S. T.; Lopez, M. A., Indexing the positions of continuously moving objects, (Proc. 2000 ACM SIGMOD Internat. Conf. on Management of Data (2000)), 331-342
[24] Q. Shi, J. JaJa, Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines, Technical Report CS-TR-4542, Institute of Advanced Computer Studies (UMIACS), University of Maryland, 2003.; Q. Shi, J. JaJa, Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines, Technical Report CS-TR-4542, Institute of Advanced Computer Studies (UMIACS), University of Maryland, 2003. · Zbl 1185.68835
[25] Q. Shi, J. JaJa, Fast algorithms for 3-d dominance reporting and counting, Technical Report CS-TR-4437, Institute of Advanced Computer Studies (UMIACS), University of Maryland, 2003.; Q. Shi, J. JaJa, Fast algorithms for 3-d dominance reporting and counting, Technical Report CS-TR-4437, Institute of Advanced Computer Studies (UMIACS), University of Maryland, 2003.
[26] Tao, Y.; Papadias, D., Efficient historical R-trees, (Proc. 13th Internat. Conf. on Scientific and Statistical Database Management (2001)), 223-232
[27] Tao, Y.; Papadias, D., The MV3R-Treea spatio-temporal access method for timestamp and interval queries, (Proc. 27th Very Large Data Bases Conference (VLDB) (2001)), 431-440
[28] T. Tzouramanis, Y. Manolopoulos, M. Vassilakopoulos, Overlapping linear quadtrees: a spatio-temporal access method, in: Proc. 6th ACM Symp. on Advances in Geographic Information Systems (ACM-GIS), Bethesda, MD, 1998, pp. 1-7.; T. Tzouramanis, Y. Manolopoulos, M. Vassilakopoulos, Overlapping linear quadtrees: a spatio-temporal access method, in: Proc. 6th ACM Symp. on Advances in Geographic Information Systems (ACM-GIS), Bethesda, MD, 1998, pp. 1-7. · Zbl 0969.68570
[29] T. Tzouramanis, M. Vassilakopoulos, Y. Manolopoulos, Processing of spatio-temporal queries in image databases, in: Proc. 3rd East-European Conf. on Advances in Databases and Information Systems (ADBIS’99), 1999, pp. 85-97.; T. Tzouramanis, M. Vassilakopoulos, Y. Manolopoulos, Processing of spatio-temporal queries in image databases, in: Proc. 3rd East-European Conf. on Advances in Databases and Information Systems (ADBIS’99), 1999, pp. 85-97.
[30] Varman, P. J.; Verma, R. M., An efficient multiversion access structure, IEEE Trans. Knowledge Data Eng., 9, 3, 391-409 (1997)
[31] Vuillemin, J., A unifying look at data structures, Comm. ACM, 23, 4, 229-239 (1980) · Zbl 0434.68047
[32] Willard, D. E., Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion three, SIAM J. Comput., 29, 3, 1030-1049 (2000) · Zbl 0943.68042
[33] X. Xu, J. Han, W. Lu, RT-tree: an improved R-tree index structure for spatiotemporal data, in: Proc. of the 4th Internat. Symp. on Spatial Data Handling (SDH), 1990.; X. Xu, J. Han, W. Lu, RT-tree: an improved R-tree index structure for spatiotemporal data, in: Proc. of the 4th Internat. Symp. on Spatial Data Handling (SDH), 1990.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.