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

Direct Spatial Search on Pictorial Databases Using Packed R-Trees.

Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31
@inproceedings{DBLP:conf/sigmod/RoussopoulosL85,
  author    = {Nick Roussopoulos and
               Daniel Leifker},
  editor    = {Shamkant B. Navathe},
  title     = {Direct Spatial Search on Pictorial Databases Using Packed R-Trees},
  booktitle = {Proceedings of the 1985 ACM SIGMOD International Conference on
               Management of Data, Austin, Texas, May 28-31, 1985},
  publisher = {ACM Press},
  year      = {1985},
  pages     = {17-31},
  ee        = {http://doi.acm.org/10.1145/318898.318900, db/conf/sigmod/RoussopoulosL85.html},
  crossref  = {DBLP:conf/sigmod/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Pictorial databases require efficient and direct spatial search based on the analog form of spatial objects and relationships instead of search based on some cumbersome alphanumeric encodings of the pictures. R-trees (two-dimensional B-trees) are excellent devices for indexing spatial objects and relationships found on pictures. Their most important feature is that they provide high level object oriented search rather than search based on the low level elements of spatial objects. This paper presents an efficient initial packing technique for creating R-trees to indexspatial objects. Since pictorial databases are not update intensive but rather static, the benefits of this technique are very significant.

Copyright © 1985 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

Shamkant B. Navathe (Ed.): Proceedings of the 1985 ACM SIGMOD International Conference on Management of Data, Austin, Texas, May 28-31, 1985. ACM Press 1985 BibTeX , SIGMOD Record 14(4)
Contents

Online Edition: ACM Digital Library

References

[Bayer & McCreight 1972]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[Chamberlin et al 1976]
...
[Chang 1981]
...
[Chang & Fu 1981]
...
[Chang & Kunil 1981]
...
[Finkel & Bentkey 1984]
Raphael A. Finkel, Jon Louis Bentley: Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Inf. 4: 1-9(1974) BibTeX
[Guttman 1984]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[Kent 1979]
William Kent: Limitations of Record-Based Information Models. ACM Trans. Database Syst. 4(1): 107-131(1979) BibTeX
[Lin & Chang 1980]
...
[McKeown 1983a]
...
[McKeown 1983b]
...
[Powell & Linton]
...
[Roussopoulos 1984]
...
[Roussopoulos & Leifker 1984]
...
[Stonebraker et al 1983]
...
[Stonebraker et al 1984]
Michael Stonebraker, Erika Anderson, Eric N. Hanson, W. Bradley Rubenstein: Quel as a Data Type. SIGMOD Conference 1984: 208-214 BibTeX
[Tang 1980]
...
[Zaniolo 1983]
Carlo Zaniolo: The Database Language GEM. SIGMOD Conference 1983: 207-218 BibTeX

Referenced by

  1. H. V. Jagadish, Nick Koudas, Divesh Srivastava: On Effective Multi-Dimensional Indexing for Strings. SIGMOD Conference 2000: 403-414
  2. Gísli R. Hjaltason, Hanan Samet: Distance Browsing in Spatial Databases. ACM Trans. Database Syst. 24(2): 265-318(1999)
  3. Nikos Mamoulis, Dimitris Papadias: Integration of Spatial Join Algorithms for Processing Multiple Inputs. SIGMOD Conference 1999: 1-12
  4. Yannis Kotidis, Nick Roussopoulos: DynaMat: A Dynamic View Management System for Data Warehouses. SIGMOD Conference 1999: 371-382
  5. Botao Wang, Hiroyuki Horinokuchi, Kunihiko Kaneko, Akifumi Makinouchi: Parallel R-Tree Search Algorithm on DSVM. DASFAA 1999: 237-245
  6. Nick Roussopoulos: Materialized Views and Data Warehouses. SIGMOD Record 27(1): 21-26(1998)
  7. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  8. Yván J. García, Mario A. Lopez, Scott T. Leutenegger: On Optimal Node Splitting for R-trees. VLDB 1998: 334-344
  9. Yannis Kotidis, Nick Roussopoulos: An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees. SIGMOD Conference 1998: 249-258
  10. Scott T. Leutenegger, Mario A. Lopez: The Effect of Buffering on the Performance of R-Trees. ICDE 1998: 164-171
  11. Euripides G. M. Petrakis, Christos Faloutsos: Similarity Searching in Medical Image Databases. IEEE Trans. Knowl. Data Eng. 9(3): 435-447(1997)
  12. Jochen Van den Bercken, Bernhard Seeger, Peter Widmayer: A Generic Approach to Bulk Loading Multidimensional Index Structures. VLDB 1997: 406-415
  13. Nick Roussopoulos, Yannis Kotidis, Mema Roussopoulos: Cubetree: Organization of and Bulk Updates on the Data Cube. SIGMOD Conference 1997: 89-99
  14. Apostolos Papadopoulos, Yannis Manolopoulos: Performance of Nearest Neighbor Queries in R-Trees. ICDT 1997: 394-408
  15. Scott T. Leutenegger, J. M. Edgington, Mario A. Lopez: STR: A Simple and Efficient Algorithm for R-Tree Packing. ICDE 1997: 497-506
  16. Yannis Theodoridis, Timos K. Sellis: A Model for the Prediction of R-tree Performance. PODS 1996: 161-171
  17. Nick Koudas, Christos Faloutsos, Ibrahim Kamel: Declustering Spatial Databases on a Multi-Computer Architecture. EDBT 1996: 592-614
  18. Nick Roussopoulos, Chung-Min Chen, Stephen Kelley, Alex Delis, Yannis Papakonstantinou: The ADMS Project: View R Us. IEEE Data Eng. Bull. 18(2): 19-28(1995)
  19. Christos Faloutsos: Fast Searching by Content in Multimedia Databases. IEEE Data Eng. Bull. 18(4): 31-40(1995)
  20. Nick Roussopoulos, Stephen Kelley, Frédéic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79
  21. 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
  22. Max J. Egenhofer: Spatial SQL: A Query and Presentation Language. IEEE Trans. Knowl. Data Eng. 6(1): 86-95(1994)
  23. Maurício R. Mediano, Marco A. Casanova, Marcelo Dreux: V-Trees - A Storage Method for Long Vector Data. VLDB 1994: 321-330
  24. Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509
  25. Christos Faloutsos, Ibrahim Kamel: Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension. PODS 1994: 4-13
  26. Hongjun Lu, Beng Chin Ooi: Spatial Indexing: Past and Future. IEEE Data Eng. Bull. 16(3): 16-21(1993)
  27. Christos Faloutsos, Ibrahim Kamel: High Performance R-trees. IEEE Data Eng. Bull. 16(3): 28-33(1993)
  28. Alexander Brodsky, Joxan Jaffar, Michael J. Maher: Toward Practical Constraint Databases. VLDB 1993: 567-580
  29. Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith: The Sequoia 2000 Benchmark. SIGMOD Conference 1993: 2-11
  30. Max J. Egenhofer: What's Special about Spatial? Database Requirements for Vehicle Navigation in Geographic Space (Extended Abstract). SIGMOD Conference 1993: 398-402
  31. Ibrahim Kamel, Christos Faloutsos: Parallel R-trees. SIGMOD Conference 1992: 195-204
  32. Oliver Günther, Jeff Bilmes: Tree-Based Access Methods for Spatial Databases: Implementation and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 3(3): 342-356(1991)
  33. Curtis P. Kolovson, Michael Stonebraker: Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data. SIGMOD Conference 1991: 138-147
  34. Christos Faloutsos, Yi Rong: DOT: A Spatial Access Method Using Fractals. ICDE 1991: 152-159
  35. 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
  36. Christos Faloutsos, Shari Roseman: Fractals for Secondary Key Retrieval. PODS 1989: 247-252
  37. Oliver Günther: The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases. ICDE 1989: 598-605
  38. William I. Grosky, Peter Neo, Rajiv Mehrotra: A Pictorial Index Mechanism for Model-Based Matching. ICDE 1989: 180-187
  39. Diane Greene: An Implementation and Performance Analysis of Spatial Data Access Methods. ICDE 1989: 606-615
  40. Suh-Yin Lee, Man-Kwan Shan, Wei-Pang Yang: Similarity Retrieval of Iconic Images Based on 2D String Longest Common Subsequence. DASFAA 1989: 337-341
  41. Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371
  42. Nikos A. Lorentzos, Roger G. Johnson: An Extension of the Relational Model to Support Generic Intervals. EDBT 1988: 528-542
  43. Michael Stonebraker: The Design of the POSTGRES Storage System. VLDB 1987: 289-300
  44. Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518
  45. W. Bradley Rubenstein: A Database Design for Musical Information. SIGMOD Conference 1987: 479-490
  46. Christos Faloutsos, Timos K. Sellis, Nick Roussopoulos: Analysis of Object Oriented Spatial Access Methods. SIGMOD Conference 1987: 426-439
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:39:40 2009