The BANG File: A New Kind of Grid File.

@inproceedings{DBLP:conf/sigmod/Freeston87,
  author    = {Michael Freeston},
  editor    = {Umeshwar Dayal and
               Irving L. Traiger},
  title     = {The BANG File: A New Kind of Grid File},
  booktitle = {Proceedings of the Association for Computing Machinery Special
               Interest Group on Management of Data 1987 Annual Conference,
               San Francisco, California, May 27-29, 1987},
  publisher = {ACM Press},
  year      = {1987},
  pages     = {260-269},
  ee        = {http://doi.acm.org/10.1145/38713.38743, db/conf/sigmod/Freeston87.html},
  crossref  = {DBLP:conf/sigmod/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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

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

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod7592 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[BENT79a]

Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979)

[BENT79b]

Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979)

[BOCC85]

Jorge B. Bocca: EDUCE: A Marriage of Convenience: Prolog and a Relational DBMS. SLP 1986: 36-45

[BURK83a]

Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89

[FAGI79]

Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979)

[FREE86]

...

[GARD83]

...

[HINR85]

Klaus Hinrichs: Implementation of the Grid File: Design Concepts and Experience. BIT 25(4): 569-592(1985)

[LEE80]

D. T. Lee, C. K. Wong: Quintary Trees: A File Structure for Multidimensional Database Systems. ACM Trans. Database Syst. 5(3): 339-353(1980)

[NIEV81]

Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multi-Key File Structure. ECI 1981: 236-251

[OUKS83]

Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105

[OTOO85]

Ekow J. Otoo: A Multidimensional Digital Hashing Scheme for Files With Composite Keys. SIGMOD Conference 1985: 214-229

[OZKA85]

Esen A. Ozkarahan, Aris M. Ouksel: Dynamic and Order Preserving Data Partitioning for Database Machines. VLDB 1985: 358-368

[ROBI81]

John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18

[WALL86]

...

Referenced by

1. Kothuri Venkata Ravi Kanth, Ambuj K. Singh: Optimal Dynamic Range Searching in Non-replicating Index Structures. ICDT 1999: 257-276
2. Dimitris G. Kapopoulos, Michael Hatzopoulos: The G^r_Tree: The Use of Active Regions in G-Trees. ADBIS 1999: 141-155
3. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
4. Kothuri Venkata Ravi Kanth, Divyakant Agrawal, Ambuj K. Singh: Dimensionality Reduction for Similarity Searching in Dynamic Databases. SIGMOD Conference 1998: 166-176
5. Andreas Henrich: The LSD^h-Tree: An Access Structure for Feature Vectors. ICDE 1998: 362-369
6. Junping Sun, William I. Grosky: Dynamic Maintenance of Multidimensional Range Data Partitioning for Parallel Data Processing. DOLAP 1998: 72-79
7. Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: Using Extended Feature Objects for Partial Similarity Retrieval. VLDB J. 6(4): 333-348(1997)
8. Jong-Hak Lee, Young-Koo Lee, Kyu-Young Whang, Il-Yeol Song: A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations. VLDB 1997: 416-425
9. Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer: An Asymptotically Optimal Multiversion B-Tree. VLDB J. 5(4): 264-275(1996)
10. Jochen Van den Bercken, Bernhard Seeger: Query Processing Techniques for Multiversion Access Methods. VLDB 1996: 168-179
11. Yannis Theodoridis, Timos K. Sellis: A Model for the Prediction of R-tree Performance. PODS 1996: 161-171
12. Nick Koudas, Christos Faloutsos, Ibrahim Kamel: Declustering Spatial Databases on a Multi-Computer Architecture. EDBT 1996: 592-614
13. Thomas A. Mück, Manfred J. Schauer: Optimizing Sort Order Query Execution in Balanced and Nested Grid Files. IEEE Trans. Knowl. Data Eng. 7(2): 246-260(1995)
14. Christos Faloutsos: Fast Searching by Content in Multimedia Databases. IEEE Data Eng. Bull. 18(4): 31-40(1995)
15. Michael Freeston: A General Solution of the n-dimensional B-tree Problem. SIGMOD Conference 1995: 80-91
16. Sang-Wook Kim, Wan-Sup Cho, Min-Jae Lee, Kyu-Young Whang: A New Algorithm for Processing Joins Using the Multilevel Grid File. DASFAA 1995: 115-123
17. Kyu-Young Whang, Sang-Wook Kim, Gio Wiederhold: Dynamic Maintenance of Data Distribution for Selectivity Estimation. VLDB J. 3(1): 29-51(1994)
18. Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994)
19. Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: The Glue-Nail Deductive Database System: Design, Implementation, and Evaluation. VLDB J. 3(2): 123-160(1994)
20. Akhil Kumar: G-Tree: A New Data Structure for Organizing Multidimensional Data. IEEE Trans. Knowl. Data Eng. 6(2): 341-347(1994)
21. Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509
22. Thomas Brinkhoff, Hans-Peter Kriegel: The Impact of Global Clustering on Spatial Database Systems. VLDB 1994: 168-179
23. 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
24. Hongjun Lu, Beng Chin Ooi: Spatial Indexing: Past and Future. IEEE Data Eng. Bull. 16(3): 16-21(1993)
25. Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: Design and Implementation of the Glue-Nail Database System. SIGMOD Conference 1993: 147-156
26. 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
27. Ludger Becker, Klaus Hinrichs, Ulrich Finke: A New Algorithm for Computing Joins with Grid Files. ICDE 1993: 190-197
28. Thomas A. Mück: The DiNG - A Parallel Multiattribute File System for Deductive Database Machines. DASFAA 1993: 115-122
29. Shashi Shekhar, Toneluh Andrew Yang: MoBiLe Files and Efficient Processing of Path Queries on Scientific Data. ICDE 1992: 78-85
30. Bruno Becker, Hans-Werner Six, Peter Widmayer: Spatial Priority Search: An Access Technique for Scaleless Maps. SIGMOD Conference 1991: 128-137
31. Aris M. Ouksel, Otto Mayer: The Nested Interpolation Based Grid File. MFDBS 1991: 173-187
32. Doron Rotem: Spatial Join Indices. ICDE 1991: 500-509
33. Oliver Günther, Hartmut Noltemeier: Spatial Database Indices for Large Extended Objects. ICDE 1991: 520-526
34. Carol Small, Alexandra Poulovassilis: An Overview of PFL. DBPL 1991: 96-110
35. Jorge B. Bocca: MegaLog - A platform for developing Knowledge Base Management Systems. DASFAA 1991: 374-380
36. David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. 15(4): 625-658(1990)
37. Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601
38. Lilian Harada, Miyuki Nakano, Masaru Kitsuregawa, Mikio Takagi: Query Processing for Multi-Attribute Clustered Records. VLDB 1990: 59-70
39. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The R-File: An Efficient Access Structure for Proximity Queries. ICDE 1990: 372-379
40. Jorge B. Bocca: Compilation of Logic Programs to Implement Very Large Knowledge Base Systems - A Case Study: Educe*. ICDE 1990: 361-369
41. Jaideep Srivastava, Jack S. Eddy Tan, Vincent Y. Lum: TBSAM: An Access Method for Efficient Processing of Statistical Queries. IEEE Trans. Knowl. Data Eng. 1(4): 414-423(1989)
42. Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53
43. David B. Lomet, Betty Salzberg: A Robust Multi-Attribute Search Structure. ICDE 1989: 296-304
44. Michel de Rougemont: Fixed-point semantics and the representation of algorithms on large data. VLDB 1988: 264-272
45. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Twin Grid Files: Space Optimizing Access Schemes. SIGMOD Conference 1988: 183-190
46. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The Twin Grid File: A Nearly Space Optimal Index Structure. EDBT 1988: 352-363