區間接合問題常見於資料庫中的時間查詢，尋找在相同時間區間內的所有資料再進一步分析，在大氣學、神經學、運輸、犯罪學、社會科學等都有廣泛的應用。合併連接的方法會導致許多多餘的比較，因此後人陸續提出基於平面掃描、基於索引、基於分區的方法來解決此問題，主要都是要減少比較次數帶來的時間
成本。本篇論文結合基於分區的方法，能有效省略許多不必要的比較，再加上基於索引方法的樹狀結構，用多棵完全樹來加速搜索過程。實驗結果顯示，我們提出的方法在長區間資料搜索時，能迅速有效獲得所需的時間重疊資料。

Generally, interval join query is often used for time query in the database to find
all the data in the same time interval before further analysis. This operation can be applied in the fields of atmosphere, neurology, transportation, criminology, social science, etc. Since the nested loops and merge join algorithms will cause many redundant comparisons, there are various algorithms proposed based on index, partitioning, and plane-sweep to solve this problem. These solutions are mainly dedicated to reducing the time cost caused by the number of comparisons. Our proposed method combines index-based and partitioning-based algorithms, which can effectively omit many unnecessary comparisons, coupled with the tree structure based on the index method, multiple complete trees are used to further accelerate the search process. According to the experimental results, the performances of our proposed method for long data query are more quick and effective.

[1] L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter, “Scalable sweepingbased spatial join,” in VLDB, vol. 98. Citeseer, 1998, pp. 570–581.
[2] G. Atluri, A. Karpatne, and V. Kumar, “Spatiotemporal data mining: A survey of problems and methods,” ACM Computing Surveys (CSUR), vol. 51, no. 4, pp. 1–41, 2018.
[3] 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 1990 ACM SIGMOD International Conference on Management of Data, 1990, pp. 322–331.
[4] N. Beckmann and B. Seeger, “A revised r*tree in comparison with related index structures,” in Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, 2009, pp.799–812.
[5] M. Böhlen, J. Gamper, and C. S. Jensen, “Multidimensional aggregation for temporal data,” in International Conference on Extending Database Technology. Springer, 2006, pp. 257–275.
[6] P. Bouros and N. Mamoulis, “A forward scan based plane sweep algorithm for parallel interval joins,”Proceedings of the VLDB Endowment, vol. 10, no. 11, pp. 1346–1357, 2017.
[7] F. Cafagna and M. H. Böhlen, “Disjoint interval partitioning,” The VLDB Journal, vol. 26, no. 3, pp.447–466, 2017.
[8] B. Chawda, H. Gupta, S. Negi, T. A. Faruquie, L. V. Subramaniam, and M. K. Mohania, “Processing interval joins on mapreduce.” in EDBT, 2014, pp. 463–474.
[9] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, “Introduction to algorithms, 3rdedition,” The MIT Press, 2009.
[10] A. Dignös, M. H. Böhlen, and J. Gamper, “Temporal alignment,” in Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, 2012, pp. 433–444.
[11] R. Elmasri, G. Wuu, and Y.-J. Kim, “An access structure for temporal data,” in Proceedings of 16th VLDB Conference. pp. Brisbane, Australia, 1990.
[12] D. Gao, C. S. Jensen, R. T. Snodgrass, and M. D. Soo, “Join operations in temporal databases,” The VLDB Journal, vol. 14, no. 1, pp. 2–29, 2005.
[13] H. Gunadhi and A. Segev, “Query processing algorithms for temporal intersection joins,” in Proceedings. Seventh International Conference on Data Engineering. IEEE, 1991, pp. 336–344.
[14] N. Koudas and K. C. Sevcik, “Size separation spatial join,” in Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data, 1997, pp. 324–335.
[15] H.-P. Kriegel, P. Kunath, M. Pfeifle, and M. Renz, “Distributed intersection join of complex interval sequences,” in International Conference on Database Systems for Advanced Applications. Springer, 2005, pp. 748–760.
[16] K. Kulkarni and J.-E. Michels, “Temporal features in sql: 2011,” ACM Sigmod Record, vol. 41, no. 3, pp. 34–43, 2012.
[17] T. C. Leung and R. R. Muntz, Temporal query processing and optimization in multiprocessor database machines. University of California (Los Angeles). Computer Science Department, 1991.
[18] I. V. Lopez, R. T. Snodgrass, and B. Moon, “Spatiotemporal aggregate computation: A survey,” IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 2, pp. 271–286, 2005.
[19] J.-Z. Luo, S.-F. Shi, G. Yang, H.-Z. Wang, and J.-Z. Li, “O2ijoin: An efficient indexbased algorithm for overlap interval join,” Journal of Computer Science and Technology, vol. 33, no. 5, pp. 1023–1038, 2018.
[20] M. F. Mokbel, T. M. Ghanem, and W. G. Aref, “Spatiotemporal access methods: a survey (20102017),” GeoInformatica, vol. 23, no. 1, pp. 1–36, 2019.
[21] D. Pfoser and C. S. Jensen, “Incremental join of timeoriented data,” in Proceedings. Eleventh International Conference on Scientific and Statistical Database Management. IEEE, 1999, pp. 232–243.
[22] D. Piatov, S. Helmer, and A. Dignös, “An interval join optimized for modern hardware,” in 2016 IEEE 32nd International Conference on Data Engineering (ICDE). IEEE, 2016, pp. 1098–1109.
[23] H. Samet, Foundations of multidimensional and metric data structures. Morgan Kaufmann, 2006.
[24] A. Segev and H. Gunadhi, “Eventjoin optimization in temporal relational databases,” in Proceedings of the Fifteenth International Conference on Very Large Data Bases, vol. 205, 1989.
[25] H. Shen, B. C. Ooi, and H. Lu, “The tpindex: A dynamic and efficient indexing mechanism for temporal databases,” in Proceedings of 1994 IEEE 10th International Conference on Data Engineering. IEEE, 1994, pp. 274–281.
[26] I. Sitzmann and P. J. Stuckey, “Improving temporal joins using histograms,” in International Conference on Database and Expert Systems Applications. Springer, 2000, pp. 488–498.
[27] D. Son and R. Elmasri, “Efficient temporal join processing using time index,” in Proceedings of 8th International Conference on Scientific and Statistical Data Base Management. IEEE, 1996, pp. 252–261.
[28] M. D. Soo, R. T. Snodgrass, and C. S. Jensen, “Efficient evaluation of the validtime natural join,” in Proceedings of 1994 IEEE 10th International Conference on Data Engineering. IEEE, 1994, pp. 282–292.
[29] C. Zhang, J. Naughton, D. DeWitt, Q. Luo, and G. Lohman, “On supporting containment queries in relational database management systems,” in Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, 2001, pp. 425–436.
[30] D. Zhang, V. J. Tsotras, and B. Seeger, “Efficient temporal join processing using indices,” in Proceedings 18th International Conference on Data Engineering. IEEE, 2002, pp. 103–113.