article

Free access

Comparison of access methods for time-evolving data

Authors:

Betty Salzberg,

Vassilis J. TsotrasAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 31, Issue 2

Pages 158 - 221

https://doi.org/10.1145/319806.319816

Published: 01 June 1999 Publication History

Abstract

This paper compares different indexing techniques proposed for supporting efficient access to temporal data. The comparison is based on a collection of important performance criteria, including the space consumed, update processing, and query time for representative queries. The comparison is based on worst-case analysis, hence no assumptions on data distribution or query frequencies are made. When a number of methods have the same asymptotic worst-case behavior, features in the methods that affect average case behavior are discussed. Additional criteria examined are the pagination of an index, the ability to cluster related data together, and the ability to efficiently separate old from current data (so that larger archival storage media such as write-once optical disks can be used). The purpose of the paper is to identify the difficult problems in accessing temporal data and describe how the different methods aim to solve them. A general lower bound for answering basic temporal queries is also introduced.

References

[1]

AGRAWAL, R., FALOUTSOS, C., AND SWAMI, A. 1993. Efficient similarity search in sequence databases. In Proceedings of FODO.

[2]

AHN, I. AND SNODGRASS, R. 1988. Partitioned storage for temporal databases. Inf. Syst. 13, 4 (May 1, 1988), 369-391.

[3]

ARGE, L. AND VITTER, J. 1996. Optimal dynamic interval management in external memory. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA.

[4]

BECKER, B., GSCHWIND, S., OHLER, T., SEEGER, B., AND WIDMAYER, P. 1996. An asymptotically optimal multiversion B-tree. VLDB J. 5, 4, 264-275.

[5]

BECKMANN, N., K_RIEGEL, H.-P., SCHNEIDER, R., AND SEEGER, B. 1990. The R*-tree: An efficient and robust access method for points and rectangles. In Proceedings of the 1990 ACM SIG- MOD International Conference on Management of Data (SIGMOD '90, Atlantic City, NJ, May 23-25, 1990), H. Garcia-Molina, Ed. ACM Press, New York, NY, 322-331.

[6]

BENTLEY, J. 1977. Algorithms for Klee's rectangle problems. Computer Science Department, Carnegie Mellon University, Pittsburgh, PA.

[7]

BEN-ZvI, J. 1982. The time relational model. Ph.D. Dissertation. University of California at Los Angeles, Los Angeles, CA.

[8]

BLANKENAGEL, G. AND GUTING, R. 1990. XP- trees, external priority search trees. Tech. Rep., Fern Universitat Hagen, Informatik- Bericht No.92.

[9]

BLANKENAGEL, G. AND GUTING, R. 1994. External segment trees. Algorithmica 12, 6, 498-532.

[10]

BLIUJUTE, R., JENSEN, C. S., SALTENIS, S., AND SLIVINSKAS, G. 1998. R-tree based indexing of now-relative bitemporal data. In Proceedings of the Conference on Very Large Data Bases.

[11]

B HLEN, M. H. 1995. Temporal database systern implementations. SIGMOD Rec. 24, 4 (Dec.), 53-60.

[12]

BOZKAYA, T. AND ZSOYOGLU, M. 1995. Indexing transaction-time databases. Tech. Rep. CES- 95-19. Case Western Reserve University, Cleveland, OH.

[13]

BURTON, F., HUNTBACH, M., AND KOLLIAS, J. 1985. Multiple generation text files using overlapping tree structures. Comput. J. 28, 414-416.

[14]

CHAZELLE, B. 1986. Filtering search: A new approach to query answering. SIAM J. Comput. 15, 3, 703-724.

[15]

CHIANG, Y. AND TAMASSIA, R. 1992. Dynamic algorithms in computational geometry. Proc. IEEE 80, 9, 362-381.

[16]

DIETZFELBINGER, M., KARLIN, A., MEHLHORN, K., MEYER, F., ROHNHERT, H., AND TARJAN, R. 1988. Dynamic perfect hashing: Upper and lower bounds. In Proceedings of the 29th IEEE Conference on Foundations of Computer Science. 524-531.

[17]

DRISCOLL, J. R., SARNAK, N., SLEATOR, D. D., AND TARJAN, R. E. 1989. Making data structures persistent. J. Comput. Syst. Sci. 38, 1 (Feb. 1989), 86-124.

[18]

DYRESON, C., GRANDI, F., K FER, W., KLINE, N., LORENTZOS, N., MITSOPOULOS, Y., MONTANARI, A., NONEN, D., PERESSI, E., PERNICI, B., ROD- DICK, J. F., SARDA, N. L., SCALAS, M. R., SEGEV, A., SNODGRASS, R. T., Soo, M. D., TANSEL, A., TIBERIO, P., WIEDERHOLD, G., AND JENSEN, C. S, Eds. 1994. A consensus glossary of temporal database concepts. SIGMOD Rec. 23, 1 (Mar. 1994), 52-64.

[19]

EASTON, M. C 1986. Key-sequence data sets on indelible storage. IBM J. Res. Dev. 30, 3 (May 1986), 230-241.

[20]

EDELSBRUNNER, H. 1983. A new approach to rectangle intersections, Parts I&II. Int. J. Comput. Math. 13, 209-229.

[21]

ELMASRI, R., KIM, Y., AND WUU, G. 1991. Efficient implementation techniques for the time index. In Proceedings of the Seventh International Conference on Data Engineering (Kobe, Japan). IEEE Computer Society Press, Los Alamitos, CA, 102-111.

[22]

ELMASRI, R., Wuu, G., AND KIM, Y. 1990. The time index: An access structure for temporal data. In Proceedings of the 16th VLDB Conference on Very Large Data Bases (VLDB, Brisbane, Australia). VLDB Endowment, Berkeley, CA, 1-12.

[23]

ELMASRI, R., Wuu, G., AND KOURAMAJIAN, V. 1993. The time index and the monotonic B+- tree. In Temporal Databases: Theory, Design, and Implementation, A. Tansel, J. Clifford, S. Gadia, S. Jajodia, A. Segev, and R. Snodgrass, Eds. Benjamin/Cummings, Redwood City, CA, 433-456.

[24]

FALOUTSOS, C., RANGANATHAN, M., AND MANOLO- POULOS, Y. 1994. Fast subsequence matching in time-series databases. In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data (SIGMOD '94, Minneapolis, MN, May 24-27, 1994), R. T. Snodgrass and M. Winslett, Eds. ACM Press, New York, NY, 419-429.

[25]

GRAY, J. AND REUTER, A. 1993. Transaction Processing: Concepts and Techniques. Morgan Kaufmann Publishers Inc., San Francisco, CA.

[26]

GUNADHI, H. AND SEGEV, A. 1993~ Efficient indexing methods for temporal relations. IEEE Trans~ Knowl. Data Eng. 5, 3 (June), 496-509~

[27]

GUNTHER, O~ 1989. The design of the cell-tree: An object-oriented index structure for geometric databases~ In Proceedings of the Fifth IEEE International Conference on Data Engineering (Los Angeles, CA, Feb. 1989). 598- 605.

[28]

GUTTMAN, A~ 1984. R-trees: A dynamic index structure for spatial searching. In Proceedings of the ACM SIGMOD Conference on Management of Data. ACM Press, New York, NY, 47-57.

[29]

HELLERSTEIN, J~ M~, KOUTSOUPIAS, E~, AND PAPAD- IMITRIOU, C~ H~ 1997. On the analysis of indexing schemes. In Proceedings of the 16th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '97, Tucson, AZ, May 12-14, 1997), A. Mendelzon and Z.M. zsoyoglu, Eds. ACM Press, New York, NY, 249-256.

[30]

ICKING, CH~, KLEIN, R~, AND OTTMANN, TH~ 1988. Priority search trees in secondary memory (extended abstract). In Proceedings of the International Workshop WG '87 Conference on Graph-Theoretic Concepts in Computer Science (Kloster Banz/Staffelstein, Germany, June 29-July 1, 1987), H. G ttler and H.-J. Schneider, Eds. Proceedings of the Second Symposium on Advances in Spatial Databases, vol. LNCS 314. Springer-Verlag, New York, NY, 84-93.

[31]

JAGADISH, H~ V~, MENDELZON, A~ O~, AND MILO, T~ 1995. Similarity-based queries. In Proceedings of the 14th ACM SIGACT-SIGMOD-SI- GART Symposium on Principles of Database Systems (PODS '95, San Jose, California, May 22-25, 1995), M. Yannakakis, Ed. ACM Press, New York, NY, 36-45.

[32]

JENSEN, C~ S~, MARK, L~, AND ROUSSOPOULOS, N~ 1991. Incremental implementation model for relational databases with transaction time. IEEE Trans. Knowl. Data Eng. 3, 4, 461-473.

[33]

JENSEN, C~ S~, MARK, L~, ROUSSOPOULOS, N~, AND SELLIS, T~ 1992. Using differential techniques to efficiently support transaction time- VLDB J. 2, 1, 75-111.

[34]

KAMEL, I. AND FALOUTSOS, C. 1994. Hilbert R- tree: An improved R-tree using fractals. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB'94, Santiago, Chile, Sept.). VLDB Endowment, Berkeley, CA, 500-509.

[35]

KANELLAKIS, P. C., RAMASWAMY, S., VENGROFF, D. E., AND VITTER, J. S. 1993. Indexing for data models with constraints and classes (extended abstract). In Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS, Washington, DC, May 25-28), C. Beeri, Ed. ACM Press, New York, NY, 233- 243.

[36]

KOLLIOS, G. AND TSOTRAS, V.J. 1998. Hashing methods for temporal data. TimeCenter TR- 24. Aalborg Univ~, Aalborg, Denmark. http:www.cs.auc.dk/general/DBS/tdb/ TimeCenter/publications.html

[37]

KOLOVSON, C. 1993. Indexing techniques for historical databases~ In Temporal Databases: Theory, Design, and Implementation, A. Tansel, J. Clifford, S. Gadia, S. Jajodia, A. Segev, and R. Snodgrass, Eds. Benjamin/ Cummings, Redwood City, CA, 418-432.

[38]

KOLOVSON, C. AND STONEBRAKER, M. 1989. Indexing techniques for historical databases. In Proceedings of the Fifth IEEE International Conference on Data Engineering (Los Angeles, CA, Feb. 1989). 127-137.

[39]

KOLOVSON, C. AND STONEBRAKER, M. 1991. Segment indexes: Dynamic indexing techniques for multi-dimensional interval data. In Proceedings of the 1991 ACM SIG- MOD International Conference on Management of Data (SIGMOD '91, Denver, CO, May 29-31, 1991), J. Clifford and R. King, Eds. ACM Press, New York, NY, 138- 147.

[40]

KOURAMAJIAN, V., ELMASRI, R., AND CHAUDHRY, A. 1994. Declustering techniques for parallelizing temporal access structures. In Proceedings of the l Oth IEEE Conference on Data Engineering. 232-242.

[41]

KOURAMAJIAN, V., KAMEL, I., KOURAMAJIAN, V., EL- MASRI, R., AND WAHEED, S. 1994. The time index + : an incremental access structure for temporal databases. In Proceedings of the 3rd International Conference on Information and Knowledge Management (CIKM '94, Gaithersburg, Maryland, Nov. 29-Dec. 2, 1994), N. R. Adam, B. K. Bhargava, and Y. Yesha, Eds. ACM Press, New York, NY, 296 -303.

[42]

KUMAR, A., TSOTRAS, V. J., AND FALOUTSOS, C. 1995. Access methods for bitemporal databases. In Proceedings of the international Workshop on Recent Advances in Temporal Databases (Zurich, Switzerland, Sept.), S. Clifford and A. Tuzhlin, Eds. Springer-Verlag, New York, NY, 235-254.

[43]

KUMAR, A., TSOTRAS, V. J., AND FALOUTSOS, C. 1998. Designing access methods for bitemporal databases. IEEE Trans. Knowl. Data Eng. 10, 1 (Jan./Feb.).

[44]

LANDAU, G. M., SCHMIDT, J. P., AND TSOTRAS, V. J. 1995. On historical queries along multiple lines of time evolution. VLDB J. 4, 4, 703- 726.

[45]

LANKA, S. AND MAYS, E. 1991. Fully persistent B+trees. In Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data (SIGMOD '91, Denver, CO, May 29-31, 1991), J. Clifford and R. King, Eds. ACM Press, New York, NY, 426-435.

[46]

LEUNG, T. Y. C. AND MUNTZ, R.R. 1992. Generalized data stream indexing and temporal query processing. In Proceedings of the Second International Workshop on Research Issues in Data Engineering: Transactions and Query Processing.

[47]

LEUNG, T. Y. C. AND MUNTZ, R. R. 1992. Ternporal query processing and optimization in multiprocessor database machines. In Proceedings of the 18th International Conference on Very Large Data Bases (Vancouver, B.C., Aug.). VLDB Endowment, Berkeley, CA, 383-394.

[48]

LEUNG, T. Y. C. AND MUNTZ, R.R. 1993. Stream processing: Temporal query processing and optimization. In Temporal Databases: Theory, Design, and Implementation, A. Tansel, J. Clifford, S. Gadia, S. Jajodia, A. Segev, and R. Snodgrass, Eds. Benjamin/Cummings, Redwood City, CA, 329-355.

[49]

LITWIN, W. 1980. Linear hashing: A new tool for file and table addressing. In Proceedings of the 6th International Conference on Very Large Data Bases (Montreal, Ont. Canada, Oct. 1-3). ACM Press, New York, NY, 212- 223.

[50]

LOMET, D. 1993. Using timestamping to optimize commit. In Proceedings of the Second International Conference on Parallel and Distributed Systems (Dec.). 48-55.

[51]

LOMET, D. AND SALZBERG, B. 1989. Access methods for multiversion data. In Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data (SIGMOD '89, Portland, OR, June 1989), J. Clifford, J. Clifford, B. Lindsay, D. Maier, and J. Clifford, Eds. ACM Press, New York, NY, 315-324.

[52]

LOMET, D. AND SALZBERG, B. 1990. The performance of a multiversion access method. In Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data (SIGMOD '90, Atlantic City, NJ, May 23-25, 1990), H. Garcia-Molina, Ed. ACM Press, New York, NY, 353-363.

[53]

LOMET, D. AND SALZBERG, B. 1990. The hB-tree: a multiattribute indexing method with good guaranteed performance. ACM Trans. Database Syst. 15, 4 (Dec. 1990), 625-658.

[54]

LOMET, D. AND SALZBERG, B. 1993. Transactiontime databases. In Temporal Databases: Theory, Design, and Implementation, A. Tansel, J. Clifford, S. Gadia, S. Jajodia, A. Segev, and R. Snodgrass, Eds. Benjamin/ Cummings, Redwood City, CA.

[55]

LOMET, D. AND SALZBERG, B. 1993. Exploiting a history database for backup. In Proceedings of the 19th International Conference on Very Large Data Bases (VLDB '93, Dublin, Ireland, Aug.). Morgan Kaufmann Publishers Inc., San Francisco, CA, 380-390.

[56]

LORENTZOS, N. A. AND JOHNSON, R.G. 1988. Extending relational algebra to manipulate ternporal data. Inf. Syst. 13, 3 (Oct., 1, 1988), 289 -296.

[57]

LUM, V., DADAM, P., ERBE, R., GUENAUER, J., PIS- TOR, P., WALCH, G., WERNER, H., AND WOOD- FILL, J. 1984. Designing DBMS support for the temporal database. In Proceedings of the ACM SIGMOD Conference on Management of Data. ACM Press, New York, NY, 115-130.

[58]

MANOLOPOULOS, Y. AND KAPETANAKIS, G. 1990. Overlapping B+trees for temporal data. In Proceedings of the Fifth Conference on JCIT (JCIT, Jerusalem, Oct. 22-25). 491-498.

[59]

MCCREIGHT, E. M. 1985. Priority search trees. SIAM J. Comput. 14, 2, 257-276.

[60]

MEHLHORN, K. 1984. Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry. EATCS monographs on theoretical computer science. Springer-Verlag, New York, NY.

[61]

MOTAKIS, I. AND ZANIOLO, C. 1997. Temporal aggregation in active database rules. In Proceedings of the International ACM Conference on Management of Data (SIGMOD '97, May). ACM, New York, NY, 440-451.

[62]

MUTH, P., KRAISS, A., AND WEIKUM, G. 1996. LoT: A dynamic declustering of TSB-tree nodes for parallel access to temporal data. In Proceedings of the Conference on EDBT. 553-572.

[63]

NASCIMENTO, M., DUNHAM, M. H., AND ELMASRI, R. 1996. M-IVTT: A practical index for bitemporal databases. In Proceedings of the Conference on DEXA (DEX '96, Zurich, Switzerland).

[64]

NASCIMENTO, M., DUNHAM, M. H., AND KOURAMA- JIAN, V. 1996. A multiple tree mappingbased approach for range indexing. J. Brazilian Comput. Soc. 2, 3 (Apr.).

[65]

NAVATHE, S. B. AND AHMED, R. 1989. A temporal relational model and a query language. Inf. Sci. 49, 1, 2 & 3 (Oct./Nov./Dec. 1989), 147-175.

[66]

O'NEIL, P. AND WEIKUM, G. 1993. A log-structured history data access method (LHAM). In Proceedings of the Workshop on High Performance Transaction System (Asilomar, CA).

[67]

ZSOYOGLU, G. AND SNODGRASS, R. 1995. Temporal and real-time databases: A survey. IEEE Trans. Knowl. Data Eng. 7, 4 (Aug.), 513-532.

[68]

RAMASWAMY, S. 1997. Efficient indexing for constraint and temporal databases. In Proceedings of the 6th International Conference on Database Theory (ICDT '97, Delphi, Greece, Jan. 9-10). Springer-Verlag, Berlin, Germany.

[69]

RAMASWAMY, S. AND SUBRAMANIAN, S. 1994. Path caching (extended abstract): a technique for optimal external searching. In Proceedings of the 13th ACM SIGACT-SIGMOD-SI- GART Symposium on Principles of Database Systems (PODS '94, Minneapolis, MN, May 24-26, 1994), V. Vianu, Ed. ACM Press, New York, NY, 25-35.

[70]

RICHARDSON, J., CAREY, M., DEWITT, D., AND SHE- KITA, E. 1986. Object and file management in the Exodus extensible system. In Proceedings of the 12th International Conference on Very Large Data Bases (Kyoto, Japan, Aug.). VLDB Endowment, Berkeley, CA, 91- 100.

[71]

RIVEST, R. 1976. Partial-match retrieval algorithms. SIAM J. Comput. 5, 1 (Mar.), 19-50.

[72]

ROBINSON, J. 1984. The K-D-B tree: A search structure for large multidimensional dynamic indexes. In Proceedings of the ACM SIG- MOD Conference on Management of Data. ACM Press, New York, NY, 10-18.

[73]

ROTEM, D. AND SEGEV, A. 1987. Physical organization of temporal data. In Proceedings of the Third IEEE International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, CA, 547-553.

[74]

SALZBERG, B. 1988. File Structures: An Analytic Approach. Prentice-Hall, Inc., Upper Saddle River, NJ.

[75]

SALZBERG, B. 1994. Timestamping after commit. In Proceedings of the 3rd International Conference on Parallel and Distributed Information Systems (PDIS, Austin, TX, Sept.). 160-167.

[76]

SALZBERG, B. AND LOMET, D. 1995. Branched and Temporal Index Structures. Tech. Rep. NU-CCS-95-17. Northeastern Univ., Boston, MA.

[77]

SEGEV, n. AND GUNADHI, H. 1989. Event-join optimization in temporal relational databases. In Proceedings of the 15th International Conference on Very Large Data Bases (VLDB '89, Amsterdam, The Netherlands, Aug 22- 25), R. P. van de Riet, Ed. Morgan Kaufmann Publishers Inc., San Francisco, CA, 205-215.

[78]

SELLIS, T., ROUSSOPOULOS, N., AND FALOUTSOS, C. 1987. The R+-tree: A dynamic index for multi-dimensional objects. In Proceedings of the 13th Confererence on Very Large Data Bases (Brighton, England, Sept., 1987). VLDB Endowment, Berkeley, CA.

[79]

SESHADRI, P., LIVNY, M., AND RAMAKRISHNAN, R. 1996. The design and implementation of a sequence database system. In Proceedings of the 22nd International Conference on Very Large Data Bases (VLDB '96, Mumbai, India, Sept.). 99-110.

[80]

SHOSHANI, A. AND KAWAGOE, K. 1986. Temporal data management. In Proceedings of the 12th International Conference on Very Large Data Bases (Kyoto, Japan, Aug.). VLDB Endowment, Berkeley, CA, 79-88.

[81]

SNODGRASS, R. T. AND AHN, I. 1985. A taxonomy of time in databases. In Proceedings of the ACM SIGMOD Conference on Management of Data. ACM Press, New York, NY, 236-246.

[82]

SNODGRASS, R. T. AND AHN, I. 1986. Temporal databases. IEEE Comput. 19, 9 (Sept. 1986), 35-41.

[83]

STONEBRAKER, M. 1987. The design of the Postgres storage system. In Proceedings of the 13th Confererence on Very Large Data Bases (Brighton, England, Sept., 1987). VLDB Endowment, Berkeley, CA, 289-300.

[84]

TSOTRAS, V. J. AND GOPINATH, B. 1990. Efficient algorithms for managing the history of evolving databases. In Proceedings of the Third International Conference on Database Theory (ICDT '90, Paris, France, Dec.), S. Abiteboul and P. C. Kanellakis, Eds. Proceedings of the Second Symposium on Advances in Spatial Databases, vol. LNCS 470. Springer- Verlag, New York, NY, 141-174.

[85]

TSOTRAS, V. J., GOPINATH, B., AND HART, G. W. 1995. Efficient management of time-evolving databases. IEEE Trans. Knowl. Data Eng. 7, 4 (Aug.), 591-608.

[86]

TSOTRAS, V. J., JENSEN, C. S., AND SNODGRASS, R. T. 1998. An extensible notation for spatiotemporal index queries. SIGMOD Rec. 27, 1, 47-53.

[87]

TSOTRAS, V. J. AND KANGELARIS, N. 1995. The snapshot index: An I/O-optimal access method for timeslice queries. Inf. Syst. 20, 3 (May 1995), 237-260.

[88]

TSOTRAS, V. J. AND KUMAR, A. 1996. Temporal database bibliography update. SIGMOD Rec. 25, 1 (Mar.), 41-51.

[89]

VAN DEN BERCKEN, g., SEEGER, B., AND WIDMAYER, P. 1997. A generic approach to bulk loading multidimensional index structures. In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB '97, Athens, Greece, Aug.). 406-415.

[90]

VARMAN, P. AND VERMA, R. 1997. An efficient multiversion access structure. IEEE Trans. Knowl. Data Eng. 9, 3 (May/June), 391-409.

[91]

VERMA, Z. AND VARMAN, P. 1994. Efficient archivable time index: A dynamic indexing scheme for temporal data. In Proceedings of the International Conference on Computer Systems and Education. 59-72.

[92]

VITTER, J.S. 1985. An efficient I/O interface for optical disks. ACM Trans. Database Syst. 10, 2 (June 1985), 129-162.

Cited By

Christodoulou GBouros PMamoulis N(2024)LIT: Lightning-fast In-memory Temporal IndexingProceedings of the ACM on Management of Data10.1145/36392752:1(1-27)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639275
Duc Luong DQuang Phuong VTung H(2023)AN IMPROVED INDEXING METHOD FOR QUERYING BIG XML FILESJournal of Computer Science and Cybernetics10.15625/1813-9663/19018(323-342)Online publication date: 25-Dec-2023
https://doi.org/10.15625/1813-9663/19018
Zeng CHu CWang HShen Z(2023)SciDG: Benchmarking Scientific Dynamic Graph QueriesProceedings of the 35th International Conference on Scientific and Statistical Database Management10.1145/3603719.3603724(1-12)Online publication date: 10-Jul-2023
https://dl.acm.org/doi/10.1145/3603719.3603724
Show More Cited By

Recommendations

Efficient Indexing Methods for Temporal Relations

The primary issues that affect the design of indexing methods are examined, and several structures and algorithms for specific cases are proposed. The append-only tree (AP-tree) structure indexes data for append-only databases to help event-join ...
Zoned-partitioning of tree-like access methods

The performance of access methods and the underlying disk system is a significant factor in determining the performance of database applications, especially with large sets of data. While modern hard disks are manufactured with multiple physical zones, ...
Efficient declustering techniques for temporal access structures
ADC '01: Proceedings of the 12th Australasian database conference

In this paper we address the problem of declustering temporal data and access structures for parallel architectures consisting of a single processor and multiple disks. To illustrate our techniques we choose the recently proposed Multi-Version Access ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Computing Surveys

ACM Computing Surveys Volume 31, Issue 2

June 1999

116 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/319806

Issue’s Table of Contents

Copyright © 1999 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1999

Published in CSUR Volume 31, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

248
Total Citations
View Citations
3,412
Total Downloads

Downloads (Last 12 months)203
Downloads (Last 6 weeks)33

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Christodoulou GBouros PMamoulis N(2024)LIT: Lightning-fast In-memory Temporal IndexingProceedings of the ACM on Management of Data10.1145/36392752:1(1-27)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639275
Duc Luong DQuang Phuong VTung H(2023)AN IMPROVED INDEXING METHOD FOR QUERYING BIG XML FILESJournal of Computer Science and Cybernetics10.15625/1813-9663/19018(323-342)Online publication date: 25-Dec-2023
https://doi.org/10.15625/1813-9663/19018
Zeng CHu CWang HShen Z(2023)SciDG: Benchmarking Scientific Dynamic Graph QueriesProceedings of the 35th International Conference on Scientific and Statistical Database Management10.1145/3603719.3603724(1-12)Online publication date: 10-Jul-2023
https://dl.acm.org/doi/10.1145/3603719.3603724
Christodoulou GBouros PMamoulis N(2023)HINT: a hierarchical interval index for Allen relationshipsThe VLDB Journal10.1007/s00778-023-00798-w33:1(73-100)Online publication date: 1-Jun-2023
https://doi.org/10.1007/s00778-023-00798-w
Christodoulou GBouros PMamoulis NIves ZBonifati AEl Abbadi A(2022)HINT: A Hierarchical Index for Intervals in Main MemoryProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517873(1257-1270)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517873
Arenas MBahamondes PAghasadeghi AStoyanovich J(2022)Temporal Regular Path Queries2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00226(2412-2425)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00226
Massri MMiklos ZRaipin PMeye P(2022)Clock-G: A temporal graph management system with space-efficient storage technique2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00215(2263-2276)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00215
Pereira AAlmeida JLopes ROliveira J(2022)Visualising Time-evolving Semantic Biomedical Data2022 IEEE 35th International Symposium on Computer-Based Medical Systems (CBMS)10.1109/CBMS55023.2022.00053(264-269)Online publication date: Jul-2022
https://doi.org/10.1109/CBMS55023.2022.00053
Harmer ROshurko E(2020)Reversibility and Composition of Rewriting in HierarchiesElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.330.9330(145-162)Online publication date: 3-Dec-2020
https://doi.org/10.4204/EPTCS.330.9
Bok KKim GLim JYoo J(2020)Historical Graph Management in Dynamic EnvironmentsElectronics10.3390/electronics90608959:6(895)Online publication date: 28-May-2020
https://doi.org/10.3390/electronics9060895
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents