{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T15:10:15Z","timestamp":1778253015143,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":106,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540405528","type":"print"},{"value":"9783540450818","type":"electronic"}],"license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45081-8_6","type":"book-chapter","created":{"date-parts":[[2010,10,23]],"date-time":"2010-10-23T07:51:08Z","timestamp":1287820268000},"page":"203-261","source":"Crossref","is-referenced-by-count":6,"title":["Chapter 6: Access Methods and Query Processing Techniques"],"prefix":"10.1007","author":[{"given":"Adriano","family":"Di Pasquale","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Forlizzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yannis","family":"Manolopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enrico","family":"Nardelli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"Pfoser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simonas","family":"\u0160altenis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yannis","family":"Theodoridis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Theodoros","family":"Tzouramanis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Vassilakopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Arge, L., Argawal, P., Erickson, J.: Indexing moving points. In: Proceedings 19th ACM PODS Symposium (PODS 2000), pp. 175\u2013186 (2000)","DOI":"10.1145\/335168.335220"},{"issue":"1","key":"6_CR2","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0734-189X(84)90079-3","volume":"27","author":"D.J. Abel","year":"1984","unstructured":"Abel, D.J.: A B\u2009+\u2009-tree structure for large quadtrees. Computer Vision, Graphics and Image Processing\u00a027(1), 19\u201331 (1984)","journal-title":"Computer Vision, Graphics and Image Processing"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Acharya, S., Poosala, V., Ramaswamy, S.: Selectivity estimation in spatial databases. In: Proceedings ACM SIGMOD Conference on Management of Data, pp. 13\u201324 (1999)","DOI":"10.1145\/304182.304184"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Arge, L., Samoladas, V., Vitter, J.S.: On two-dimensional indexability and optimal range search indexing. In: Proceedings 19th ACM PODS Symposium (PODS 2000), pp. 346\u2013357 (1999)","DOI":"10.1145\/303976.304010"},{"key":"6_CR5","unstructured":"Belussi, A., Faloutsos, C.: Estimating the selectivity of spatial queries using the correlation fractal dimension. In: Proceedings 21st Conference on Very Large Data Bases (VLDB 1995), pp. 299\u2013310 (1995)"},{"key":"6_CR6","unstructured":"Basch, J., Guibas, L., Hershberger, J.: Data structures for mobile data. In: Proceedings 8th ACM-SIAM Symposium on Discrete Algorithms (SODA 1997), pp. 747\u2013756 (1997)"},{"issue":"4","key":"6_CR7","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/s007780050028","volume":"5","author":"B. Becker","year":"1996","unstructured":"Becker, B., Gschwind, S., Ohler, T., Seeger, B., Widmayer, P.: An asymptotically optimal multiversion B-tree. The VLDB Journal\u00a05(4), 264\u2013275 (1996)","journal-title":"The VLDB Journal"},{"issue":"4","key":"6_CR8","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1093\/comjnl\/28.4.414","volume":"28","author":"F.W. Burton","year":"1985","unstructured":"Burton, F.W., Huntbach, M.W., Kollias, J.: Multiple generation text files using overlapping tree structures. The Computer Journal\u00a028(4), 414\u2013416 (1985)","journal-title":"The Computer Journal"},{"key":"6_CR9","unstructured":"Bliuj\u016bt\u0117, R., Jensen, C.S., \u0160altenis, S., Slivinskas, G.: R-tree based indexing of now-relative bitemporal data. In: Proceedings 24th Conference on Very Large Data Bases (VLDB 1998), pp. 345\u2013356 (1998)"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Bliuj\u016bt\u0117, R., Jensen, C.S., \u0160altenis, S., Slivinskas, G.: Light-weight indexing of bitemporal data. In: Proceedings 9th Conference on Statistical and Scientific Database Management Systems (SSDBM 2000), pp. 125\u2013138 (2000)","DOI":"10.1109\/SSDM.2000.869783"},{"issue":"3","key":"6_CR11","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1093\/comjnl\/33.3.279","volume":"33","author":"F.W. Burton","year":"1990","unstructured":"Burton, F.W., Kollias, J.G., Matsakis, D.G.: Implementation of overlapping B-trees for time and space efficient representation of collection of similar files. The Computer Journal\u00a033(3), 279\u2013280 (1990)","journal-title":"The Computer Journal"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Beckmann, N., Kriegel, H.-P., Schneider, R., Seeger, B.: The R*-tree: An efficient and robust method for points and rectangles. In: Proceedings ACM SIGMOD Conference on Management of Data, pp. 322\u2013331 (1990)","DOI":"10.1145\/93597.98741"},{"key":"6_CR13","unstructured":"Barillari, F., Nardelli, E., Pepe, M.: Fully dynamic search trees can be balanced in O(log2 n) time. Technical Report 146, Universit\u00e1 di L\u2019Aquila (1997); Accepted in Journal of Parallel and Distributed Computing"},{"key":"6_CR14","unstructured":"Bercken, J., Seeger, B.: Query processing techniques for multiversion access methods. In: Proceedings 22nd Conference on Very Large Data Bases (VLDB 1996), pp. 168\u2013179 (1996)"},{"key":"6_CR15","unstructured":"Breitbart, Y., Vingralek, R.: Addressing and balancing issues in distributed B\u2009+\u2009-trees. In: Proceedings 1st Workshop on Distributed Data and Structures, WDAS 1998 (1998)"},{"issue":"2","key":"6_CR16","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1145\/249978.249980","volume":"22","author":"J. Clifford","year":"1997","unstructured":"Clifford, J., Dyreson, C.E., Isakowitz, T., Jensen, C.S., Snodgrass, R.T.: On the semantics of \u201cnow\u201d. ACM Transactions on Database Systems\u00a022(2), 171\u2013214 (1997)","journal-title":"ACM Transactions on Database Systems"},{"issue":"2","key":"6_CR17","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1145\/329.318578","volume":"9","author":"S. Christodoulakis","year":"1984","unstructured":"Christodoulakis, S.: Implications of certain assumptions in database performance evaluation. ACM Transactions on Database Systems\u00a09(2), 163\u2013186 (1984)","journal-title":"ACM Transactions on Database Systems"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/3-540-54414-3_29","volume-title":"Advances in Spatial Databases","author":"J.P. Cheiney","year":"1991","unstructured":"Cheiney, J.P., Tourir, A.: Fi-quadtree - A new data structure for contentoriented retrieval and fuzzy search. In: G\u00fcnther, O., Schek, H.-J. (eds.) SSD 1991. LNCS, vol.\u00a0525, pp. 23\u201332. Springer, Heidelberg (1991)"},{"key":"#cr-split#-6_CR19.1","unstructured":"Dieker, S., G\u00fcting, R.H.: Efficient handling of tuples with embedded large objects. Technical Report Informatik-236, FernUniversit\u00e4t Hagen (1998)"},{"key":"#cr-split#-6_CR19.2","doi-asserted-by":"crossref","unstructured":"Also in Data and Knowledge Engineering 32, 247-268 (2000)","DOI":"10.1016\/S0169-023X(99)00040-3"},{"key":"6_CR20","unstructured":"Di Pasquale, A., Nardelli, E.: Balanced and distributed search trees. In: Proceedings 2nd Workshop on Distributed Data and Structures (WDAS 1999), pp. 73\u201390 (1999)"},{"key":"6_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/3-540-44472-6_19","volume-title":"Current Issues in Databases and Information Systems","author":"A. Di Pasquale","year":"2000","unstructured":"Di Pasquale, A., Nardelli, E.: Distributed searching of k-dimensional data with almost constant cost. In: Masunaga, Y., Thalheim, B., \u0160tuller, J., Pokorn\u00fd, J. (eds.) ADBIS 2000 and DASFAA 2000. LNCS, vol.\u00a01884, pp. 239\u2013250. Springer, Heidelberg (2000)"},{"key":"6_CR22","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"J.R. Driscoll","year":"1989","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. Journal of Computer and System Sciences\u00a038, 86\u2013124 (1989)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"6_CR23","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0146-664X(82)90020-X","volume":"19","author":"C.R. Dyer","year":"1982","unstructured":"Dyer, C.R.: The space efficiency of quadtrees. Computer Graphics and Image Processing\u00a019(4), 335\u2013348 (1982)","journal-title":"Computer Graphics and Image Processing"},{"issue":"3","key":"6_CR24","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1023\/A:1009805532638","volume":"3","author":"M. Erwig","year":"1999","unstructured":"Erwig, M., G\u00fcting, R.H., Schneider, M., Vazirgiannis, M.: Spatio-temporal data types: An approach to modelling and querying moving objects in databases. GeoInformatica\u00a03(3), 269\u2013296 (1999)","journal-title":"GeoInformatica"},{"key":"6_CR25","unstructured":"Faloutsos, C., Gaede, V.: Analysis of n-dimensional quadtrees using the Hausdorff fractal dimension. In: Proceedings 22nd Conference on Very Large Data Bases (VLDB 1996), pp. 40\u201350 (1996)"},{"key":"6_CR26","doi-asserted-by":"crossref","unstructured":"Forlizzi, L., G\u00fcting, R.H., Nardelli, E., Schneider, M.: A data model and data structures for moving objects databases. In: Proceedings ACM SIGMOD Conference on Management of Data, pp. 319\u2013330 (2000)","DOI":"10.1145\/342009.335426"},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Faloutsos, C., Kamel, I.: Beyond uniformity and independence: Analysis of R-trees using the concept of fractal dimension. In: Proceedings 13th ACM PODS Symposium (PODS 1994), pp. 4\u201313 (1994)","DOI":"10.1145\/182591.182593"},{"issue":"12","key":"6_CR28","doi-asserted-by":"publisher","first-page":"905","DOI":"10.1145\/358728.358741","volume":"25","author":"I. Gargantini","year":"1982","unstructured":"Gargantini, I.: An effective way to represent quadtrees. Communications of the ACM\u00a025(12), 905\u2013910 (1982)","journal-title":"Communications of the ACM"},{"key":"6_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-60159-7_14","volume-title":"Advances in Spatial Databases","author":"R.H. G\u00fcting","year":"1995","unstructured":"G\u00fcting, R.H., de Ridder, T., Schneider, M.: Implementation of the ROSE algebra: Efficient algorithms for realm-based spatial data types. In: Egenhofer, M.J., Herring, J.R. (eds.) SSD 1995. LNCS, vol.\u00a0951, pp. 216\u2013239. Springer, Heidelberg (1995)"},{"issue":"2","key":"6_CR30","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1145\/280277.280279","volume":"30","author":"V. Gaede","year":"1998","unstructured":"Gaede, V., G\u00fcnther, O.: Multidimensional access methods. ACM Computer Surveys\u00a030(2), 170\u2013231 (1998)","journal-title":"ACM Computer Surveys"},{"key":"6_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/3-540-48344-6_9","volume-title":"Spatio-Temporal Database Management","author":"C. Gurret","year":"1999","unstructured":"Gurret, C., Manolopoulos, Y., Papadopoulos, A., Rigaux, P.: BASIS: A benchmarking approach for spatial index structures. In: B\u00f6hlen, M.H., Jensen, C.S., Scholl, M.O. (eds.) STDBM 1999. LNCS, vol.\u00a01678, pp. 152\u2013170. Springer, Heidelberg (1999)"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"G\u00fcnther, O., Oria, V., Picouet, P., Saglio, J.-M., Scholl, M.: Benchmarking spatial joins a la carte. In: Proceedings 7th Conference on Statistical and Scientific Database Management Systems (SSDBM 1998), pp. 32\u201341 (1998)","DOI":"10.1109\/SSDM.1998.688109"},{"key":"6_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/BFb0054531","volume-title":"Database and Expert Systems Applications","author":"C. Gurret","year":"1998","unstructured":"Gurret, C., Rigaux, P.: An integrated platform for the evaluation of spatial query processing strategies. In: Quirchmayr, G., Bench-Capon, T.J.M., Schweighofer, E. (eds.) DEXA 1998. LNCS, vol.\u00a01460, pp. 757\u2013766. Springer, Heidelberg (1998)"},{"key":"6_CR34","doi-asserted-by":"crossref","unstructured":"Guttman, A.: R-trees: A dynamic index structure for spatial searching. In: Proceedings ACM SIGMOD Conference on Management of Data, pp. 47\u201357 (1984)","DOI":"10.1145\/971697.602266"},{"issue":"1","key":"6_CR35","first-page":"3","volume":"31","author":"O. G\u00fcnther","year":"1991","unstructured":"G\u00fcnther, O., Wong, E.: A dual approach to detect polyhedral intersections in arbitrary dimensions. BIT\u00a031(1), 3\u201314 (1991)","journal-title":"BIT"},{"issue":"4","key":"6_CR36","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0306-4379(96)00017-8","volume":"21","author":"C.S. Jensen","year":"1996","unstructured":"Jensen, C.S., Snodgrass, R.: Semantics of time-varying information. Information Systems\u00a021(4), 311\u2013352 (1996)","journal-title":"Information Systems"},{"issue":"1","key":"6_CR37","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1109\/TPAMI.1980.4766967","volume":"2","author":"E. Kawaguchi","year":"1980","unstructured":"Kawaguchi, E., Endo, T.: On a method of binary picture representation and its application to data compression. IEEE Transactions on Pattern Analysis and Machine Intelligence\u00a02(1), 27\u201335 (1980)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"6_CR38","doi-asserted-by":"crossref","unstructured":"Kamel, I., Faloutsos, C.: On packing R-trees. In: Proceedings 2nd Conference on Information and Knowledge Management (CIKM 1993), pp. 490\u2013499 (1993)","DOI":"10.1145\/170088.170403"},{"key":"6_CR39","doi-asserted-by":"crossref","unstructured":"Kollios, G., Gunopoulos, D., Tsotras, V.J.: On indexing mobile objects. In: Proceedings 18th ACM PODS Symposium (PODS 1999), pp. 261\u2013272 (1999)","DOI":"10.1145\/303976.304002"},{"key":"6_CR40","series-title":"Sorting and Searching","volume-title":"The Art of Computer Programming","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The Art of Computer Programming. Sorting and Searching, vol.\u00a03. Addison-Wesley, Reading (1973)"},{"key":"6_CR41","doi-asserted-by":"crossref","unstructured":"Kumar, A., Tsotras, V.J., Faloutsos, C.: Access methods for bi-temporal databases. In: Proceedings Workshop on Temporal Databases, pp. 235\u2013254 (1995)","DOI":"10.1007\/978-1-4471-3033-8_13"},{"issue":"1","key":"6_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/69.667079","volume":"10","author":"A. Kumar","year":"1998","unstructured":"Kumar, A., Tsotras, V.J., Faloutsos, C.: Designing access methods for bitemporal databases. IEEE Transactions on Knowledge and Data Engineering\u00a010(1), 1\u201320 (1998)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"6_CR43","doi-asserted-by":"crossref","unstructured":"Kr\u00f6ll, B., Widmayer, P.: Distributing a search tree among a growing number of processor. In: Proceedings ACM SIGMOD Conference on Management of Data, pp. 265\u2013276 (1994)","DOI":"10.1145\/191839.191891"},{"key":"6_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/3-540-60220-8_50","volume-title":"Algorithms and Data Structures","author":"B. Kr\u00f6ll","year":"1995","unstructured":"Kr\u00f6ll, B., Widmayer, P.: Balanced distributed search trees do not exists. In: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol.\u00a0955, pp. 50\u201361. Springer, Heidelberg (1995)"},{"key":"6_CR45","doi-asserted-by":"crossref","unstructured":"Lang, S.D., Driscoll, J.R.: Improving the differential file technique via batch operations for tree structured file organizations. In: Proceedings 2nd IEEE Conference on Data Engineering (ICDE 1986), pp. 524\u2013532 (1986)","DOI":"10.1109\/ICDE.1986.7266259"},{"key":"6_CR46","unstructured":"Litwin, W., Neimat, M.A.: ${\\rm} k-RP^{*}_{s}$- A high performance multi-attribute scalable data structure. In: Proceedings 4th Conference on Parallel and Distributed Information System (PDIS 1996), pp. 120\u2013131 (1996)"},{"key":"6_CR47","doi-asserted-by":"crossref","unstructured":"Litwin, W., Neimat, M.-A., Schneider, D.A.: LH* - linear hashing for distributed files. In: Proceedings ACM SIGMOD Conference on Management of Data, pp. 327\u2013336 (1993)","DOI":"10.1145\/170035.170084"},{"key":"6_CR48","unstructured":"Litwin, W., Neimat, M.-A., Schneider, D.A.: RP*: A family of order preserving scalable distributed data structures. In: Proceedings 20th Conference on Very Large Data Bases (VLDB 1994), pp. 342\u2013353 (1994)"},{"key":"6_CR49","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"J. Van Leeuwen","year":"1984","unstructured":"Van Leeuwen, J., Tarjan, R.E.: Worst-case analysis of set union algorithms. Journal of the ACM\u00a031, 245\u2013281 (1984)","journal-title":"Journal of the ACM"},{"key":"6_CR50","doi-asserted-by":"crossref","unstructured":"Manolopoulos, Y., Kapetanakis, G.: Overlapping B\u2009+\u2009-trees for temporal data. In: Proceedings 5th Jerusalem Conference on Information Technology (JCIT 1990), pp. 491\u2013498 (1990)","DOI":"10.1109\/JCIT.1990.128320"},{"issue":"8","key":"6_CR51","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1016\/S0306-4379(97)00029-X","volume":"22","author":"Y. Manolopoulos","year":"1997","unstructured":"Manolopoulos, Y., Nardelli, E., Papadopoulos, A., Proietti, G.: MOF-tree: A spatial access method to manipulate multiple overlapping features. Information Systems\u00a022(8), 465\u2013481 (1997)","journal-title":"Information Systems"},{"key":"6_CR52","volume-title":"Advanced Database Indexing","author":"Y. Manolopoulos","year":"1999","unstructured":"Manolopoulos, Y., Theodoridis, Y., Tsotras, V.: Advanced Database Indexing. Kluwer Academic Publishers, Dordrecht (1999)"},{"key":"6_CR53","unstructured":"Nardelli, E.: Distributed k-d trees. In: Proceedings 16th Conference of Chilean Computer Science Society (SCCC 1996), pp. 142\u2013154 (1996)"},{"key":"6_CR54","unstructured":"Nardelli, E., Barillari, F., Pepe, M.: Design issues in distributed searching of multi-dimensional data. In: Proceedings 3rd International Symposium on Programming and Systems, ISPS 1997 (1997)"},{"issue":"1","key":"6_CR55","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1006\/jpdc.1998.1428","volume":"49","author":"E. Nardelli","year":"1998","unstructured":"Nardelli, E., Barillari, F., Pepe, M.: Distributed searching of multi-dimensional data: A performance evaluation study. Journal of Parallel and Distributed Computing\u00a049(1), 111\u2013134 (1998)","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"6_CR56","doi-asserted-by":"crossref","unstructured":"Nishida, S., Nozawa, H., Saiwaki, N.: Proposal of spatio-temporal indexing methods for moving objects. In: Proceedings Entity-Relationship Workshop (ER 1998), pp. 484\u2013495 (1998)","DOI":"10.1007\/978-3-540-49121-7_43"},{"key":"6_CR57","unstructured":"Nardelli, E., Proietti, G.: Managing overlapping features in spatial database applications. In: International Computer Symposium (ICS 1994), pp. 1297\u20131302 (1994)"},{"key":"6_CR58","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0255(94)00107-M","volume":"84","author":"E. Nardelli","year":"1995","unstructured":"Nardelli, E., Proietti, G.: Efficient secondary memory processing of window queries on spatial data. Information Sciences\u00a084, 67\u201383 (1995)","journal-title":"Information Sciences"},{"key":"6_CR59","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/3-540-44472-6_18","volume-title":"Current Issues in Databases and Information Systems","author":"E. Nardelli","year":"2000","unstructured":"Nardelli, E., Proietti, G.: Size estimation of the intersection join between two line segment datasets. In: Masunaga, Y., Thalheim, B., \u0160tuller, J., Pokorn\u00fd, J. (eds.) ADBIS 2000 and DASFAA 2000. LNCS, vol.\u00a01884, pp. 229\u2013238. Springer, Heidelberg (2000)"},{"key":"6_CR60","unstructured":"Nelson, R., Samet, H.: A population analysis of quadtrees with variable node size. Technical Report CAR-TR-241, University of Maryland, Computer Science Department (1986)"},{"key":"6_CR61","doi-asserted-by":"crossref","unstructured":"Nascimento, M.A., Silva, J.R.O.: Towards historical R-trees. In: Proceedings 13th ACM Symposium on Applied Computing (ACM-SAC 1998) (1998)","DOI":"10.1145\/330560.330692"},{"key":"6_CR62","unstructured":"Nascimento, M.A., Silva, J.R.O., Theodoridis, Y.: Access structures for moving points. Technical Report TR-33, TimeCenter (1998)"},{"key":"6_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/3-540-48344-6_10","volume-title":"Spatio-Temporal Database Management","author":"M.A. Nascimento","year":"1999","unstructured":"Nascimento, M.A., Silva, J.R.O., Theodoridis, Y.: Evaluation for access structures for discretely moving points. In: B\u00f6hlen, M.H., Jensen, C.S., Scholl, M.O. (eds.) STDBM 1999. LNCS, vol.\u00a01678, pp. 171\u2013188. Springer, Heidelberg (1999)"},{"key":"6_CR64","doi-asserted-by":"crossref","unstructured":"Orenstein, J.: Spatial query processing in an object-oriented database system. In: Proceedings ACM SIGMOD Conference on Management of Data, pp. 326\u2013336 (1986)","DOI":"10.1145\/16894.16886"},{"key":"#cr-split#-6_CR65.1","unstructured":"Proietti, G., Faloutsos, C.: Accurate modeling of region data. Technical Report 98-137, Carnegie-Mellon University (1998)"},{"key":"#cr-split#-6_CR65.2","doi-asserted-by":"crossref","unstructured":"Also in IEEE Transactions on Knowledge and Data Engineering 13(6), 874-883 (2001)","DOI":"10.1109\/69.971184"},{"key":"6_CR66","doi-asserted-by":"crossref","unstructured":"Proietti, G., Faloutsos, C.: Selectivity estimation of windows queries for line segment datasets. In: Proceedings 7th Conference on Information and Knowledge Management (CIKM 1998), pp. 340\u2013347 (1998)","DOI":"10.1145\/288627.288675"},{"key":"6_CR67","doi-asserted-by":"crossref","unstructured":"Proietti, G., Faloutsos, C.: I\/O complexity for range queries on region data stored using an R-tree. In: Proceedings 15th IEEE Conference on Data Engineering (ICDE 1999), pp. 628\u2013635 (1999)","DOI":"10.1109\/ICDE.1999.754979"},{"issue":"5","key":"6_CR68","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1109\/69.877506","volume":"12","author":"G. Proietti","year":"2000","unstructured":"Proietti, G., Faloutsos, C.: Analysis of range queries and self spatial join queries on real region datasets stored using an R-tree. IEEE Transactions on Knowledge and Data Engineering\u00a012(5), 751\u2013762 (2000)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"6_CR69","unstructured":"Pfoser, D., Jensen, C.S., Theodoridis, Y.: Novel approaches in query processing for moving objects. In: Proceedings 26th Conference on Very Large Data Bases (VLDB 2000), pp. 395\u2013406 (2000)"},{"key":"6_CR70","series-title":"Lecture Notes in Computer Science","first-page":"394","volume-title":"Database Theory - ICDT \u201997","author":"A. Papadopoulos","year":"1996","unstructured":"Papadopoulos, A., Manolopoulos, Y.: Performance of nearest neighbor queries in R-trees. In: Afrati, F.N., Kolaitis, P.G. (eds.) ICDT 1997. LNCS, vol.\u00a01186, pp. 394\u2013408. Springer, Heidelberg (1996)"},{"key":"6_CR71","first-page":"42","volume":"2","author":"G. Proietti","year":"1996","unstructured":"Proietti, G.: The MOF\u2009+\u2009-tree: A space efficient representation of images containing multiple overlapping features. Journal of Computing and Information\u00a02, 42\u201356 (1996)","journal-title":"Journal of Computing and Information"},{"issue":"4","key":"6_CR72","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s002360050160","volume":"36","author":"G. Proietti","year":"1999","unstructured":"Proietti, G.: An optimal algorithm for decomposing a window into its maximal blocks. Acta Informatica\u00a036(4), 257\u2013266 (1999)","journal-title":"Acta Informatica"},{"key":"6_CR73","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1007\/3-540-48482-5_18","volume-title":"Advances in Spatial Databases","author":"A. Papadopoulos","year":"1999","unstructured":"Papadopoulos, A., Rigaux, P., Scholl, M.: A performance evaluation of spatial processing strategies. In: G\u00fcting, R.H., Papadias, D., Lochovsky, F.H. (eds.) SSD 1999. LNCS, vol.\u00a01651, pp. 286\u2013307. Springer, Heidelberg (1999)"},{"key":"6_CR74","doi-asserted-by":"crossref","unstructured":"Pagel, B., Six, H., Toben, H., Widmayer, P.: Towards an analysis of range query performance. In: Proceedings 12th ACM PODS Symposium (PODS 1993), pp. 214\u2013221 (1993)","DOI":"10.1145\/153850.153878"},{"key":"6_CR75","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/3-540-48482-5_21","volume-title":"Advances in Spatial Databases","author":"S. Ravada","year":"1999","unstructured":"Ravada, S., Sharma, J.: Oracle8i spatial: Experiences with extensible databases. In: G\u00fcting, R.H., Papadias, D., Lochovsky, F.H. (eds.) SSD 1999. LNCS, vol.\u00a01651, pp. 355\u2013359. Springer, Heidelberg (1999)"},{"key":"6_CR76","doi-asserted-by":"crossref","unstructured":"Snodgrass, R.T., Ahn, T.: A taxonomy of time in databases. In: Proceedings ACM SIGMOD Conference on Management of Data, pp. 236\u2013246 (1985)","DOI":"10.1145\/318898.318921"},{"issue":"2","key":"6_CR77","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0022-0000(86)90021-8","volume":"3","author":"Y. Sagiv","year":"1986","unstructured":"Sagiv, Y.: Concurrent operations on B*-trees with overtaking. Journal of Computer and System Sciences\u00a03(2), 275\u2013296 (1986)","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR78","volume-title":"Applications of Spatial Data Structures","author":"H. Samet","year":"1990","unstructured":"Samet, H.: Applications of Spatial Data Structures. Addison-Wesley, Reading (1990)"},{"key":"6_CR79","volume-title":"The Design and Analysis of Spatial Data Structures","author":"H. Samet","year":"1990","unstructured":"Samet, H.: The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading (1990)"},{"key":"6_CR80","unstructured":"\u0160altenis, S., Jensen, C.S.: R-tree based indexing of general spatio-temporal data. Technical Report TR-45 and Chorochronos CH-99-18, TimeCenter (1999)"},{"key":"6_CR81","doi-asserted-by":"crossref","unstructured":"\u0160altenis, S., Jensen, C.S., Leutenegger, S., Lopez, M.: Indexing the positions of continuously moving objects. In: Proceedings ACM SIGMOD Conference on Management of Data, pp. 331\u2013342 (2000)","DOI":"10.1145\/342009.335427"},{"key":"6_CR82","unstructured":"Saiwaki, N., Naka, A., Nishida, S.: Spatio-temporal data management for highly interactive environment. In: Proceedings 6th IEEE Workshop on Robot and Human Communication (ROMAN 1997), pp. 571\u2013576 (1997)"},{"issue":"2","key":"6_CR83","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1145\/22952.22956","volume":"12","author":"R.T. Snodgrass","year":"1987","unstructured":"Snodgrass, R.T.: The temporal query language TQuel. ACM Transactions on Database Systems\u00a012(2), 247\u2013298 (1987)","journal-title":"ACM Transactions on Database Systems"},{"issue":"2","key":"6_CR84","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1145\/319806.319816","volume":"31","author":"B. Salzberg","year":"1999","unstructured":"Salzberg, B., Tsotras, V.: A comparison of access methods for time evolving data. ACM Computing Surveys\u00a031(2), 158\u2013212 (1999)","journal-title":"ACM Computing Surveys"},{"issue":"3","key":"6_CR85","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/S0169-023X(98)00046-9","volume":"29","author":"T. Tzouramanis","year":"1999","unstructured":"Tzouramanis, T., Manolopoulos, Y., Lorentzos, N.: Overlapping B\u2009+\u2009-trees: An implementation of a temporal access method. Data and Knowledge Engineering\u00a029(3), 381\u2013404 (1999)","journal-title":"Data and Knowledge Engineering"},{"key":"6_CR86","doi-asserted-by":"crossref","unstructured":"Teraoka, T., Maruyama, M., Nakamura, Y., Nishida, S.: The MP-tree: A data structure for spatio-temporal data. In: Proceedings 14th IEEE Annual Phoenix Conference on Computers and Communications, pp. 326\u2013333 (1995)","DOI":"10.1109\/PCCC.1995.472473"},{"key":"6_CR87","unstructured":"Tourir, A.: A multi-layer quadtree: A spatial data structure for multi-layer processing. Geoinformatica (2001)"},{"key":"6_CR88","doi-asserted-by":"crossref","unstructured":"Theodoridis, Y., Sellis, T.: A model for the prediction of R-tree performance. In: Proceedings 15th ACM PODS Symposium (PODS 1996), pp. 161\u2013171 (1996)","DOI":"10.1145\/237661.237705"},{"key":"6_CR89","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/3-540-48482-5_11","volume-title":"Advances in Spatial Databases","author":"Y. Theodoridis","year":"1999","unstructured":"Theodoridis, Y., Silva, J.R.O., Nascimento, M.A.: On the generation of spatiotemporal datasets. In: G\u00fcting, R.H., Papadias, D., Lochovsky, F.H. (eds.) SSD 1999. LNCS, vol.\u00a01651, pp. 147\u2013164. Springer, Heidelberg (1999)"},{"key":"6_CR90","doi-asserted-by":"crossref","unstructured":"Theodoridis, Y., Sellis, T., Papadopoulos, A., Manolopoulos, Y.: Specifications for efficient indexing in spatiotemporal databases. In: Proceedings 7th Conference on Statistical and Scientific Database Management Systems (SSDBM 1998), pp. 123\u2013132 (1998)","DOI":"10.1109\/SSDM.1998.688117"},{"issue":"3","key":"6_CR91","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1093\/comjnl\/41.3.185","volume":"41","author":"J. Tayeb","year":"1998","unstructured":"Tayeb, J., Ulusoy, O., Wolfson, O.: A quadtree based dynamic attribute indexing method. The Computer Journal\u00a041(3), 185\u2013200 (1998)","journal-title":"The Computer Journal"},{"key":"6_CR92","doi-asserted-by":"crossref","unstructured":"Tzouramanis, T., Vassilakopoulos, M., Manolopoulos, Y.: Overlapping linear quadtrees: A spatio-temporal access method. In: Proceedings 6th ACM Symposium on Advances in Geographic Information Systems (ACM-GIS 1998), pp. 1\u20137 (1998)","DOI":"10.1145\/288692.288695"},{"key":"6_CR93","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/3-540-48252-0_7","volume-title":"Advances in Databases and Information Systems","author":"T. Tzouramanis","year":"1999","unstructured":"Tzouramanis, T., Vassilakopoulos, M., Manolopoulos, Y.: Processing of spatiotemporal queries in image databases. In: Eder, J., Rozman, I., Welzer, T. (eds.) ADBIS 1999. LNCS, vol.\u00a01691, pp. 85\u201397. Springer, Heidelberg (1999)"},{"key":"6_CR94","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/3-540-44472-6_22","volume-title":"Current Issues in Databases and Information Systems","author":"T. Tzouramanis","year":"2000","unstructured":"Tzouramanis, T., Vassilakopoulos, M., Manolopoulos, Y.: Multiversion linear quadtrees for spatio-temporal data. In: Masunaga, Y., Thalheim, B., \u0160tuller, J., Pokorn\u00fd, J. (eds.) ADBIS 2000 and DASFAA 2000. LNCS, vol.\u00a01884, pp. 279\u2013292. Springer, Heidelberg (2000)"},{"issue":"4","key":"6_CR95","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1093\/comjnl\/43.4.325","volume":"43","author":"T. Tzouramanis","year":"2000","unstructured":"Tzouramanis, T., Vassilakopoulos, M., Manolopoulos, Y.: Overlapping linear quadtrees and window query processing in spatio-temporal databases. The Computer Journal\u00a043(4), 325\u2013344 (2000)","journal-title":"The Computer Journal"},{"key":"6_CR96","doi-asserted-by":"crossref","unstructured":"Theodoridis, Y., Vazirgiannis, M., Sellis, T.: Spatio-temporal indexing for large multimedia applications. In: Proceedings 3rd IEEE Conference on Multimedia Computing and Systems (ICMCS 1996), pp. 441\u2013448 (1996)","DOI":"10.1109\/MMCS.1996.535011"},{"issue":"6","key":"6_CR97","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1016\/0306-4379(95)00026-Z","volume":"20","author":"M. Vassilakopoulos","year":"1995","unstructured":"Vassilakopoulos, M., Manolopoulos, Y.: Dynamic inverted quadtrees - A structure for pictorial databases. Information Systems\u00a020(6), 483\u2013500 (1995)","journal-title":"Information Systems"},{"issue":"5","key":"6_CR98","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0262-8856(93)90002-X","volume":"11","author":"M. Vassilakopoulos","year":"1993","unstructured":"Vassilakopoulos, M., Manolopoulos, Y., Economou, K.: Overlapping for the representation of similar images. Image and Vision Computing\u00a011(5), 257\u2013262 (1993)","journal-title":"Image and Vision Computing"},{"key":"6_CR99","first-page":"70","volume":"2","author":"M. Vassilakopoulos","year":"1995","unstructured":"Vassilakopoulos, M., Manolopoulos, Y., Kr\u00f6ll, B.: Efficiency analysis of overlapped quadtrees. Nordic Journal of Computing\u00a02, 70\u201384 (1995)","journal-title":"Nordic Journal of Computing"},{"issue":"4","key":"6_CR100","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/s005300050094","volume":"6","author":"M. Vazirgiannis","year":"1998","unstructured":"Vazirgiannis, M., Theodoridis, Y., Sellis, T.: Spatio-temporal composition and indexing large multimedia applications. Multimedia Systems\u00a06(4), 284\u2013298 (1998)","journal-title":"Multimedia Systems"},{"key":"6_CR101","doi-asserted-by":"crossref","unstructured":"Wolfson, O., Xu, B., Chamberlain, S., Jiang, L.: Moving objects databases: Issues and solutions. In: Proceedings 10th Conference on Scientific and Statistical Database Management, pp. 111\u2013122 (1998)","DOI":"10.1109\/SSDM.1998.688116"},{"key":"6_CR102","unstructured":"Xu, X., Han, J., Lu, W.: RT-tree - An improved R-tree index structure for spatiotemporal databases. In: Proceedings 4th Symposium on Spatial Data Handling (SDH 1990), pp. 1040\u20131049 (1990)"},{"key":"6_CR103","unstructured":"Zimbrao, G., Moreira de Souza, J., Chaomey Wo, R., Teixeira de Almeida, V.: Efficient processing of spatiotemporal queries in temporal geographical information systems. In: Proceedings 4th Multiconference on Systemics, Cybernetics and Informatics, 6th Conference on Information Systems, Analysis and Synthesis (SCI\/ISAS 2000), vol.\u00a08, Part.II, pp. 46\u201351 (2000)"},{"key":"6_CR104","unstructured":"Zimbrao, G., Moreira de Souza, J., Teixeira de Almeida, V.: The temporal Rtree. Technical Report ES-429\/99, Federal University of Rio de Janeiro, Computer Science Department (1999)"}],"container-title":["Lecture Notes in Computer Science","Spatio-Temporal Databases"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45081-8_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T14:16:31Z","timestamp":1778249791000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-45081-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405528","9783540450818"],"references-count":106,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45081-8_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}