ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331
@inproceedings{DBLP:conf/sigmod/BeckmannKSS90,
  author    = {Norbert Beckmann and
               Hans-Peter Kriegel and
               Ralf Schneider and
               Bernhard Seeger},
  editor    = {Hector Garcia-Molina and
               H. V. Jagadish},
  title     = {The R*-Tree: An Efficient and Robust Access Method for Points
               and Rectangles},
  booktitle = {Proceedings of the 1990 ACM SIGMOD International Conference on
               Management of Data, Atlantic City, NJ, May 23-25, 1990},
  publisher = {ACM Press},
  year      = {1990},
  pages     = {322-331},
  ee        = {http://doi.acm.org/10.1145/93597.98741, db/conf/sigmod/BeckmannKSS90.html},
  crossref  = {DBLP:conf/sigmod/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The R-tree, one of the most popular access methods for rectangles, is based on the heuristic optimization of the area of the enclosing rectangle in each inner node. By running numerous experiments in a standardized testbed under highly varying data, queries and operations, we were able to design the R*-tree which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory. Using our standardized testbed in an exhaustive performance comparison, it turned out that the R*-tree clearly outperforms the existing R-tree variants Guttman's linear and quadratic R-tree and Greene's variant of the R-tree. This superiority of the R*-tree holds for different types of queries and operations, such as map overlay, for both rectangles and multidimensional points in all experiments. From a practical point of view the R*-tree is very attractive because of the following two reasons: 1 it efficiently supports point and spatial data at the same time and 2 its implementation cost is only slightly higher than that of other R-trees.

Copyright © 1990 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Hector Garcia-Molina, H. V. Jagadish (Eds.): Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. ACM Press 1990 BibTeX , SIGMOD Record 19(2), June 1990
Contents

Online Edition: ACM Digital Library

References

[Gre 89]
Diane Greene: An Implementation and Performance Analysis of Spatial Data Access Methods. ICDE 1989: 606-615 BibTeX
[Gut 84]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[Hin 85]
...
[Knu 73]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[KSSS 89]
Hans-Peter Kriegel, Michael Schiwietz: Performance Comparison of Point and Spatial Access Methods. SSD 1989: 89-114 BibTeX
[NHS 84]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
[RL 85]
Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31 BibTeX
[SK 88]
Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371 BibTeX
[SK 90]
Bernhard Seeger, Hans-Peter Kriegel: Design, Implementation and Performance Comparison of the Buddy-Tree. DEXA 1990: 203-207 BibTeX

Referenced by

  1. Stefan Berchtold, Christian Böhm, Daniel A. Keim, Florian Krebs, Hans-Peter Kriegel: On Optimizing Nearest Neighbor Queries in High-Dimensional Data Spaces. ICDT 2001: 435-449
  2. Costas Vassilakis: An Optimisation Scheme for Coalesce/Valid Time Selection Operator Sequences. SIGMOD Record 29(1): 38-43(2000)
  3. Timos K. Sellis: Review - The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. ACM SIGMOD Digital Review 2: (2000)
  4. Haifeng Yu, Amin Vahdat: Efficient Numerical Error Bounding for Replicated Network Services. VLDB 2000: 123-133
  5. Theodore Johnson, Laks V. S. Lakshmanan, Raymond T. Ng: The 3W Model and Algebra for Unified Data Mining. VLDB 2000: 21-32
  6. Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, Mario A. Lopez: Indexing the Positions of Continuously Moving Objects. SIGMOD Conference 2000: 331-342
  7. Sridhar Ramaswamy, Rajeev Rastogi, Kyuseok Shim: Efficient Algorithms for Mining Outliers from Large Data Sets. SIGMOD Conference 2000: 427-438
  8. Hyoseop Shin, Bongki Moon, Sukho Lee: Adaptive Multi-Stage Distance Join Processing. SIGMOD Conference 2000: 343-354
  9. Flip Korn, S. Muthukrishnan: Influence Sets Based on Reverse Nearest Neighbor Queries. SIGMOD Conference 2000: 201-212
  10. H. V. Jagadish, Nick Koudas, Divesh Srivastava: On Effective Multi-Dimensional Indexing for Strings. SIGMOD Conference 2000: 403-414
  11. Antonio Corral, Yannis Manolopoulos, Yannis Theodoridis, Michael Vassilakopoulos: Closest Pair Queries in Spatial Databases. SIGMOD Conference 2000: 189-200
  12. Beng Chin Ooi, Kian-Lee Tan, Cui Yu, Stéphane Bressan: Indexing the Edges - A Simple and Yet Efficient Approach to High-Dimensional Indexing. PODS 2000: 166-174
  13. Roger Weber, Klemens Böhm: Trading Quality for Time with Nearest Neighbor Search. EDBT 2000: 21-35
  14. Caetano Traina Jr., Agma J. M. Traina, Bernhard Seeger, Christos Faloutsos: Slim-Trees: High Performance Metric Trees Minimizing Overlap Between Nodes. EDBT 2000: 51-65
  15. Jochen Van den Bercken, Martin Schneider, Bernhard Seeger: Plug&Join: An easy-to-use Generic Algorithm for Efficiently Processing Equi and Non-Equi Joins. EDBT 2000: 495-509
  16. Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jan Vahrenhold, Jeffrey Scott Vitter: A Unified Approach for Indexed and Non-Indexed Spatial Joins. EDBT 2000: 413-429
  17. Gísli R. Hjaltason, Hanan Samet: Distance Browsing in Spatial Databases. ACM Trans. Database Syst. 24(2): 265-318(1999)
  18. Tolga Bozkaya, Z. Meral Özsoyoglu: Indexing Large Metric Spaces for Similarity Search Queries. ACM Trans. Database Syst. 24(3): 361-404(1999)
  19. Joseph K. P. Kuan, Paul H. Lewis: A Study on Data Point Search for HG-Trees. SIGMOD Record 28(1): 90-96(1999)
  20. Zu-Kuan Wei, Young-Hwan Oh, Jae-dong Lee, Jae-Hong Kim, Dong-Sun Park, Young-Geol Lee, Hae-Young Bae: Efficient Spatial Transmission in Web-Based GIS. Workshop on Web Information and Data Management 1999: 38-42
  21. Elisa Bertino, Silvana Castano, Elena Ferrari, Marco Mesiti: Controlled Access and Dissemination of XML Documents. Workshop on Web Information and Data Management 1999: 22-27
  22. Apostol Natsev, Rajeev Rastogi, Kyuseok Shim: WALRUS: A Similarity Retrieval Algorithm for Image Databases. SIGMOD Conference 1999: 395-406
  23. Nikos Mamoulis, Dimitris Papadias: Integration of Spatial Join Algorithms for Processing Multiple Inputs. SIGMOD Conference 1999: 1-12
  24. Daniel A. Keim: Efficient Geometry-based Similarity Search of 3D Spatial Databases. SIGMOD Conference 1999: 419-430
  25. Kothuri Venkata Ravi Kanth, Siva Ravada, Jayant Sharma, Jay Banerjee: Indexing Medium-dimensionality Data in Oracle. SIGMOD Conference 1999: 521-522
  26. Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg Sander: OPTICS: Ordering Points To Identify the Clustering Structure. SIGMOD Conference 1999: 49-60
  27. Charu C. Aggarwal, Joel L. Wolf, Philip S. Yu: A New Method for Similarity Indexing of Market Basket Data. SIGMOD Conference 1999: 407-418
  28. Swarup Acharya, Viswanath Poosala, Sridhar Ramaswamy: Selectivity Estimation in Spatial Databases. SIGMOD Conference 1999: 13-24
  29. Dimitris Papadias, Nikos Mamoulis, Yannis Theodoridis: Processing and Optimization of Multiway Spatial Joins Using R-Trees. PODS 1999: 44-55
  30. George Kollios, Dimitrios Gunopulos, Vassilis J. Tsotras: On Indexing Mobile Objects. PODS 1999: 261-272
  31. Kelvin Kam Wing Chu, Man Hon Wong: Fast Time-Series Searching with Scaling and Shifting. PODS 1999: 237-248
  32. Kothuri Venkata Ravi Kanth, Ambuj K. Singh: Optimal Dynamic Range Searching in Non-replicating Index Structures. ICDT 1999: 257-276
  33. Joseph M. Hellerstein, Lisa Hellerstein, George Kollios: On the Generation of 2-Dimensional Index Workloads. ICDT 1999: 113-130
  34. Hongjun Zhu, Jianwen Su, Oscar H. Ibarra: An Index Structure for Spatial Joins in Linear Constraint Databases. ICDE 1999: 636-643
  35. Davood Rafiei: On Similarity-Based Queries for Time Series Data. ICDE 1999: 410-417
  36. Guido Proietti, Christos Faloutsos: I/O Complexity for Range Queries on Region Data Stored Using an R-tree. ICDE 1999: 628-635
  37. Surya Nepal, M. V. Ramakrishna: Query Processing Issues in Image (Multimedia) Databases. ICDE 1999: 22-29
  38. Venkatesh Ganti, Raghu Ramakrishnan, Johannes Gehrke, Allison L. Powell, James C. French: Clustering Large Datasets in Arbitrary Metric Spaces. ICDE 1999: 502-511
  39. Kin-pong Chan, Ada Wai-Chee Fu: Efficient Time Series Matching by Wavelets. ICDE 1999: 126-133
  40. Rasa Bliujute, Simonas Saltenis, Giedrius Slivinskas, Christian S. Jensen: Developing a DataBlade for a New Index. ICDE 1999: 314-323
  41. Botao Wang, Hiroyuki Horinokuchi, Kunihiko Kaneko, Akifumi Makinouchi: Parallel R-Tree Search Algorithm on DSVM. DASFAA 1999: 237-245
  42. Ho-Hyun Park, Chan-Gun Lee, Yong-Ju Lee, Chin-Wan Chung: Early Separation of Filter and Refinement Steps in Spatial Query Optimization. DASFAA 1999: 161-168
  43. Miyeon Kim, Sumi Lim, Jangsu Kim: Development of Multi-step Filtering Processor. DASFAA 1999: 169-176
  44. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
    Contents
  45. Pavel Zezula, Pasquale Savino, Giuseppe Amato, Fausto Rabitti: Approximate Similarity Retrieval with M-Trees. VLDB J. 7(4): 275-293(1998)
  46. Michael Ortega, Yong Rui, Kaushik Chakrabarti, Kriengkrai Porkaew, Sharad Mehrotra, Thomas S. Huang: Supporting Ranked Boolean Similarity Queries in MARS. IEEE Trans. Knowl. Data Eng. 10(6): 905-925(1998)
  47. Ming-Ling Lo, Chinya V. Ravishankar: The Design and Implementation of Seeded Trees: An Efficient Method for Spatial Joins. IEEE Trans. Knowl. Data Eng. 10(1): 136-152(1998)
  48. Anil Kumar, Vassilis J. Tsotras, Christos Faloutsos: Designing Access Methods for Bitemporal Databases. IEEE Trans. Knowl. Data Eng. 10(1): 1-20(1998)
  49. Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas: Fast and Effective Retrieval of Medical Tumor Shapes. IEEE Trans. Knowl. Data Eng. 10(6): 889-904(1998)
  50. King Lum Cheung, Ada Wai-Chee Fu: Enhanced Nearest Neighbour Search on the R-tree. SIGMOD Record 27(3): 16-21(1998)
  51. Chialin Chang, Anurag Acharya, Alan Sussman, Joel H. Saltz: T2: A Customizable Parallel Database for Multi-Dimensional Data. SIGMOD Record 27(1): 58-66(1998)
  52. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  53. Roger Weber, Hans-Jörg Schek, Stephen Blott: A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. VLDB 1998: 194-205
  54. Dimitris Papadias, Nikos Mamoulis, Vasilis Delis: Algorithms for Querying by Spatial Structure. VLDB 1998: 546-557
  55. Beng Chin Ooi, Cheng Hian Goh, Kian-Lee Tan: Fast High-Dimensional Data Search in Incomplete Databases. VLDB 1998: 357-367
  56. Yoshiharu Ishikawa, Ravishankar Subramanya, Christos Faloutsos: MindReader: Querying Databases Through Multiple Examples. VLDB 1998: 218-227
  57. Yván J. García, Mario A. Lopez, Scott T. Leutenegger: On Optimal Node Splitting for R-trees. VLDB 1998: 334-344
  58. Martin Ester, Hans-Peter Kriegel, Jörg Sander, Michael Wimmer, Xiaowei Xu: Incremental Clustering for Mining in a Data Warehousing Environment. VLDB 1998: 323-333
  59. Rasa Bliujute, Christian S. Jensen, Simonas Saltenis, Giedrius Slivinskas: R-Tree Based Indexing of Now-Relative Bitemporal Data. VLDB 1998: 345-356
  60. Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter: Scalable Sweeping-Based Spatial Join. VLDB 1998: 570-581
  61. Mihael Ankerst, Bernhard Braunmüller, Hans-Peter Kriegel, Thomas Seidl: Improving Adaptable Similarity Query Processing by Using Approximations. VLDB 1998: 206-217
  62. Yannis Theodoridis, Timos K. Sellis, Apostolos Papadopoulos, Yannis Manolopoulos: Specifications for Efficient Indexing in Spatiotemporal Databases. SSDBM 1998: 123-132
  63. Oliver Günther, Vincent Oria, Philippe Picouet, Jean-Marc Saglio, Michel Scholl: Benchmarking Spatial Joins À La Carte. SSDBM 1998: 32-41
  64. Apostolos Papadopoulos, Yannis Manolopoulos: Similarity Query Processing Using Disk Arrays. SIGMOD Conference 1998: 225-236
  65. Kothuri Venkata Ravi Kanth, Divyakant Agrawal, Ambuj K. Singh: Dimensionality Reduction for Similarity Searching in Dynamic Databases. SIGMOD Conference 1998: 166-176
  66. Gísli R. Hjaltason, Hanan Samet: Incremental Distance Join Algorithms for Spatial Databases. SIGMOD Conference 1998: 237-248
  67. Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: CURE: An Efficient Clustering Algorithm for Large Databases. SIGMOD Conference 1998: 73-84
  68. Stéphane Grumbach, Philippe Rigaux, Luc Segoufin: The DEDALE System for Complex Spatial Queries. SIGMOD Conference 1998: 213-224
  69. Stefan Berchtold, Christian Böhm, Hans-Peter Kriegel: The Pyramid-Technique: Towards Breaking the Curse of Dimensionality. SIGMOD Conference 1998: 142-153
  70. Jeffrey Scott Vitter: External Memory Algorithms. PODS 1998: 119-128
  71. Ronald Fagin: Fuzzy Queries in Multimedia Database Systems. PODS 1998: 1-10
  72. Paolo Ciaccia, Marco Patella, Pavel Zezula: A Cost Model for Similarity Queries in Metric Spaces. PODS 1998: 59-68
  73. Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo Giulio Franciosa, Jeffrey Scott Vitter: Efficient Searching with Linear Constraints. PODS 1998: 169-178
  74. Xiaowei Xu, Martin Ester, Hans-Peter Kriegel, Jörg Sander: A Distribution-Based Clustering Algorithm for Mining in Large Spatial Databases. ICDE 1998: 324-331
  75. Yannis Theodoridis, Emmanuel Stefanakis, Timos K. Sellis: Cost Models for Join Queries in Spatial Databases. ICDE 1998: 476-483
  76. Renato Pajarola, Thomas Ohler, Peter Stucki, Kornel Szabo, Peter Widmayer: The Alps at Your Fingertips: Virtual Reality and Geoinformation Systems. ICDE 1998: 550-557
  77. Scott T. Leutenegger, Mario A. Lopez: The Effect of Buffering on the Performance of R-Trees. ICDE 1998: 164-171
  78. Nick Koudas, Kenneth C. Sevcik: High Dimensional Similarity Joins: Algorithms and Performance Evaluation. ICDE 1998: 466-475
  79. Andreas Henrich: The LSDh-Tree: An Access Structure for Feature Vectors. ICDE 1998: 362-369
  80. Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft: Compressing Relations and Indexes. ICDE 1998: 370-379
  81. Kaushik Chakrabarti, Sharad Mehrotra: Dynamic Granular Locking Approach to Phantom Protection in R-Trees. ICDE 1998: 446-454
  82. Stefan Berchtold, Bernhard Ertl, Daniel A. Keim, Hans-Peter Kriegel, Thomas Seidl: Fast Nearest Neighbor Search in High-Dimensional Space. ICDE 1998: 209-218
  83. Yutaka Ohsawa, Kyungwol Kim: A Spatiotemporal Data Management Method Using Inverse Differential Script. ER Workshops 1998: 542-553
  84. Yasuaki Nakamura, Hiroyuki Dekihara, Ryo Furukawa: Spatio-Temporal Data Management for Moving Objects Using the PMD-Tree. ER Workshops 1998: 496-507
  85. Hiroyuki Horinokuchi, Botao Wang, Susumu Kuroki, Akifumi Makinouchi: A Spatiotemporal Query Processor Based on Simplicial Representation. ER Workshops 1998: 520-531
  86. Toshiyuki Amagasa, Masayoshi Aritsugi, Takayuki Tanaka, Yoshinari Kanamori: Implementing Class Library and Index for Managing Spatio-Temporal Data. ER Workshops 1998: 532-541
  87. Stefan Berchtold, Christian Böhm, Hans-Peter Kriegel: Improving the Query Performance of High-Dimensional Index Structures by Bulk-Load Operations. EDBT 1998: 216-230
  88. Georgios Evangelidis, David B. Lomet, Betty Salzberg: The hB-Pi-Tree: A Multi-Attribute Index Supporting Concurrency, Recovery and Node Consolidation. VLDB J. 6(1): 1-25(1997)
  89. Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: Using Extended Feature Objects for Partial Similarity Retrieval. VLDB J. 6(4): 333-348(1997)
  90. Euripides G. M. Petrakis, Christos Faloutsos: Similarity Searching in Medical Image Databases. IEEE Trans. Knowl. Data Eng. 9(3): 435-447(1997)
  91. Daniel Barbará, William DuMouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis E. Ioannidis, H. V. Jagadish, Theodore Johnson, Raymond T. Ng, Viswanath Poosala, Kenneth A. Ross, Kenneth C. Sevcik: The New Jersey Data Reduction Report. IEEE Data Eng. Bull. 20(4): 3-45(1997)
  92. Thomas Seidl, Hans-Peter Kriegel: Efficient User-Adaptable Similarity Search in Large Multimedia Databases. VLDB 1997: 506-515
  93. Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations. VLDB 1997: 396-405
  94. Paolo Ciaccia, Marco Patella, Pavel Zezula: M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. VLDB 1997: 426-435
  95. Jochen Van den Bercken, Bernhard Seeger, Peter Widmayer: A Generic Approach to Bulk Loading Multidimensional Index Structures. VLDB 1997: 406-415
  96. Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: A Cost Model for Estimating the Performance of Spatial Joins Using R-trees. SSDBM 1997: 30-38
  97. Davood Rafiei, Alberto O. Mendelzon: Similarity-Based Queries for Time Series Data. SIGMOD Conference 1997: 13-25
  98. Jignesh M. Patel, Jie-Bing Yu, Navin Kabra, Kristin Tufte, Biswadeep Nag, Josef Burger, Nancy E. Hall, Karthikeyan Ramasamy, Roger Lueder, Curt J. Ellmann, Jim Kupsch, Shelly Guo, David J. DeWitt, Jeffrey F. Naughton: Building a Scaleable Geo-Spatial DBMS: Technology, Implementation, and Evaluation. SIGMOD Conference 1997: 336-347
  99. Norio Katayama, Shin'ichi Satoh: The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries. SIGMOD Conference 1997: 369-380
  100. Ching-Tien Ho, Rakesh Agrawal, Nimrod Megiddo, Ramakrishnan Srikant: Range Queries in OLAP Data Cubes. SIGMOD Conference 1997: 73-88
  101. Tolga Bozkaya, Z. Meral Özsoyoglu: Distance-Based Indexing for High-Dimensional Metric Spaces. SIGMOD Conference 1997: 357-368
  102. Stefan Berchtold, Hans-Peter Kriegel: S3: Similarity Search in CAD Database Systems. SIGMOD Conference 1997: 564-567
  103. Stefan Berchtold, Christian Böhm, Bernhard Braunmüller, Daniel A. Keim, Hans-Peter Kriegel: Fast Parallel Similarity Search in Multimedia Databases. SIGMOD Conference 1997: 1-12
  104. Banu Özden, Rajeev Rastogi, Abraham Silberschatz: Multimedia Support for Databases. PODS 1997: 1-11
  105. Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft, Jie-Bing Yu: Processing Queries By Linear Constraints. PODS 1997: 257-267
  106. Stefan Berchtold, Christian Böhm, Daniel A. Keim, Hans-Peter Kriegel: A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space. PODS 1997: 78-86
  107. Sridhar Ramaswamy: Efficient Indexing for Constraint and Temporal Databases. ICDT 1997: 419-431
  108. Apostolos Papadopoulos, Yannis Manolopoulos: Performance of Nearest Neighbor Queries in R-Trees. ICDT 1997: 394-408
  109. Kyuseok Shim, Ramakrishnan Srikant, Rakesh Agrawal: High-Dimensional Similarity Joins. ICDE 1997: 301-311
  110. Scott T. Leutenegger, J. M. Edgington, Mario A. Lopez: STR: A Simple and Efficient Algorithm for R-Tree Packing. ICDE 1997: 497-506
  111. Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Integrated Query Processing Strategies for Spatial Path Queries. ICDE 1997: 477-486
  112. Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer: An Asymptotically Optimal Multiversion B-Tree. VLDB J. 5(4): 264-275(1996)
  113. Edwin M. Knorr, Raymond T. Ng: Finding Aggregate Proximity Relationships and Commonalities in Spatial Data Mining. IEEE Trans. Knowl. Data Eng. 8(6): 884-897(1996)
  114. Ming-Syan Chen, Jiawei Han, Philip S. Yu: Data Mining: An Overview from a Database Perspective. IEEE Trans. Knowl. Data Eng. 8(6): 866-883(1996)
  115. Kenneth C. Sevcik, Nick Koudas: Filter Trees for Managing Spatial Data over a Range of Size Granularities. VLDB 1996: 16-27
  116. Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas: Fast Nearest Neighbor Search in Medical Image Databases. VLDB 1996: 215-226
  117. Christos Faloutsos, Volker Gaede: Analysis of n-Dimensional Quadtrees using the Hausdorff Fractal Dimension. VLDB 1996: 40-50
  118. Ajit A. Diwan, Sanjeeva Rane, S. Seshadri, S. Sudarshan: Clustering Techniques for Minimizing External Path Length. VLDB 1996: 342-353
  119. Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: The X-tree : An Index Structure for High-Dimensional Data. VLDB 1996: 28-39
  120. Nasser Yazdani, Z. Meral Özsoyoglu: Sequence Matching of Images. SSDBM 1996: 53-62
  121. Ramakrishnan Srikant, Rakesh Agrawal: Mining Quantitative Association Rules in Large Relational Tables. SIGMOD Conference 1996: 1-12
  122. Jignesh M. Patel, David J. DeWitt: Partition Based Spatial-Merge Join. SIGMOD Conference 1996: 259-270
  123. Ming-Ling Lo, Chinya V. Ravishankar: Spatial Hash-Joins. SIGMOD Conference 1996: 247-258
  124. Surajit Chaudhuri, Luis Gravano: Optimizing Queries over Multimedia Repositories. SIGMOD Conference 1996: 91-102
  125. Stephen Blott, Lukas Relly, Hans-Jörg Schek: An Open Storage System for Abstract Objects. SIGMOD Conference 1996: 330-340
  126. Yannis Theodoridis, Timos K. Sellis: A Model for the Prediction of R-tree Performance. PODS 1996: 161-171
  127. Bernd-Uwe Pagel, Hans-Werner Six: Are Window Queries Representative for Arbitrary Range Queries? PODS 1996: 150-160
  128. David A. White, Ramesh Jain: Similarity Indexing with the SS-tree. ICDE 1996: 516-523
  129. Andreas Henrich: Improving the Performance of Multi-Dimensional Access Structures Based on k-d-Trees. ICDE 1996: 68-75
  130. Daniel Alexander Ford, Jussi Myllymaki: A Log-Structured Organization for Tertiary Storage. ICDE 1996: 20-27
  131. Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Parallel Processing of Spatial Joins Using R-trees. ICDE 1996: 258-265
  132. Nick Koudas, Christos Faloutsos, Ibrahim Kamel: Declustering Spatial Databases on a Multi-Computer Architecture. EDBT 1996: 592-614
  133. Maxim Martynov, Boris Novikov: An Indexing Algorithm for Text Retrieval. ADBIS 1996: 171-175
  134. Christos Faloutsos: Fast Searching by Content in Multimedia Databases. IEEE Data Eng. Bull. 18(4): 31-40(1995)
  135. Harry Leslie, Rohit Jain, Dave Birdsall, Hedieh Yaghmai: Efficient Search of Multi-Dimensional B-Trees. VLDB 1995: 710-719
  136. Marcel Kornacker, Douglas Banks: High-Concurrency Locking in R-Trees. VLDB 1995: 134-145
  137. Erik G. Hoel, Hanan Samet: Benchmarking Spatial Join Operations with Spatial Output. VLDB 1995: 606-618
  138. Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562-573
  139. Alberto Belussi, Christos Faloutsos: Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension. VLDB 1995: 299-310
  140. Rakesh Agrawal, King-Ip Lin, Harpreet S. Sawhney, Kyuseok Shim: Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases. VLDB 1995: 490-501
  141. Paradise Team: Paradise: A Database System for GIS Applications. SIGMOD Conference 1995: 485
  142. Nick Roussopoulos, Stephen Kelley, Frédéic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79
  143. Dimitris Papadias, Yannis Theodoridis, Timos K. Sellis, Max J. Egenhofer: Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees. SIGMOD Conference 1995: 92-103
  144. Christos Faloutsos, King-Ip Lin: FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets. SIGMOD Conference 1995: 163-174
  145. Bernd-Uwe Pagel, Hans-Werner Six, Mario Winter: Window Query-Optimal Clustering of Spatial Objects. PODS 1995: 86-94
  146. Alexander Brodsky, Catherine Lassez, Jean-Louis Lassez, Michael J. Maher: Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data. PODS 1995: 54-65
  147. M. G. Martynov: Spatial Joins and R-trees. ADBIS 1995: 295-304
  148. King-Ip Lin, H. V. Jagadish, Christos Faloutsos: The TV-Tree: An Index Structure for High-Dimensional Data. VLDB J. 3(4): 517-542(1994)
  149. Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994)
  150. Wesley W. Chu, Ion Tim Ieong, Ricky K. Taira: A Semantic Modeling Approach for Image Retrieval by Content. VLDB J. 3(4): 445-477(1994)
  151. Maurício R. Mediano, Marco A. Casanova, Marcelo Dreux: V-Trees - A Storage Method for Long Vector Data. VLDB 1994: 321-330
  152. Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509
  153. Erik G. Hoel, Hanan Samet: Performance of Data-Parallel Spatial Operations. VLDB 1994: 156-167
  154. David J. DeWitt, Navin Kabra, Jun Luo, Jignesh M. Patel, Jie-Bing Yu: Client-Server Paradise. VLDB 1994: 558-569
  155. Thomas Brinkhoff, Hans-Peter Kriegel: The Impact of Global Clustering on Spatial Database Systems. VLDB 1994: 168-179
  156. Ming-Ling Lo, Chinya V. Ravishankar: Spatial Joins Using Seeded Trees. SIGMOD Conference 1994: 209-220
  157. Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos: Fast Subsequence Matching in Time-Series Databases. SIGMOD Conference 1994: 419-429
  158. Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: GENESYS: A System for Efficient Spatial Query Processing. SIGMOD Conference 1994: 519
  159. Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994: 197-208
  160. Christos Faloutsos, Ibrahim Kamel: Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension. PODS 1994: 4-13
  161. Manish Arya, William F. Cody, Christos Faloutsos, Joel E. Richardson, Arthur Toya: QBISM: Extending a DBMS to Support 3D Medical Images. ICDE 1994: 314-325
  162. Boris Novikov: Indices for Set-Theoretical Operations in Object Bases. ADBIS 1994: 208-216
  163. M. G. Martynov: Variations of R-Tree Structure for Indexing of Spatial Objects. ADBIS 1994: 217-221
  164. Yasuaki Nakamura, Shigeru Abe, Yutaka Ohsawa, Masao Sakauchi: A Balanced Hierarchical Data Structure for Multidimensional Data with Highly Efficient Dynamic Characteristics. IEEE Trans. Knowl. Data Eng. 5(4): 682-694(1993)
  165. Hongjun Lu, Beng Chin Ooi: Spatial Indexing: Past and Future. IEEE Data Eng. Bull. 16(3): 16-21(1993)
  166. Hans-Peter Kriegel, Thomas Brinkhoff, Ralf Schneider: Efficient Spatial Query Processing in Geographic Database Systems. IEEE Data Eng. Bull. 16(3): 10-15(1993)
  167. Christos Faloutsos, Ibrahim Kamel: High Performance R-trees. IEEE Data Eng. Bull. 16(3): 28-33(1993)
  168. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  169. Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246
  170. Bernd-Uwe Pagel, Hans-Werner Six, Heinrich Toben, Peter Widmayer: Towards an Analysis of Range Query Performance in Spatial Data Structures. PODS 1993: 214-221
  171. Rajiv Mehrotra, James E. Gary: Feature-Based Retrieval of Similar Shapes. ICDE 1993: 108-115
  172. Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider: Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems. ICDE 1993: 40-49
  173. Ibrahim Kamel, Christos Faloutsos: Parallel R-trees. SIGMOD Conference 1992: 195-204
  174. Erik G. Hoel, Hanan Samet: A Qualitative Comparison Study of Data Structures for Large Line Segment Databases. SIGMOD Conference 1992: 205-214
  175. Curtis P. Kolovson, Michael Stonebraker: Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data. SIGMOD Conference 1991: 138-147
  176. Bruno Becker, Hans-Werner Six, Peter Widmayer: Spatial Priority Search: An Access Technique for Scaleless Maps. SIGMOD Conference 1991: 128-137
  177. Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601
  178. H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:03 2009