Quintary Trees: A File Structure for Multidimensional Database Systems.

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

@article{DBLP:journals/tods/LeeW80,
  author    = {D. T. Lee and
               C. K. Wong},
  title     = {Quintary Trees: A File Structure for Multidimensional Database
               Systems},
  journal   = {ACM Trans. Database Syst.},
  volume    = {5},
  number    = {3},
  year      = {1980},
  pages     = {339-353},
  ee        = {http://doi.acm.org/10.1145/320613.320618, db/journals/tods/LeeW80.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

In this paper we present a file structure designed for a database system in which four types of retrieval requests (queries) are allowed: exact match, partial match, range, and partial range queries. For a file of N records, each of k keys, the worst-case running times of our search algorithms are bounded above, respectively, by O(k + log N), O(t + 3^k-s(s + log N)), O(t + (log N)^k), and O(t + 3^k-s(log N)^s) where s is the number of keys specified in a partial match (or range) query and t is the number of records retrieved by the query. The file structure can be built in O(N(log N)^k/(k - 1)!) time and requires similar storage; by a slight modification, both of these requirements can be reduced to O(N(log N)^k-1/(k - 1)!). We also sketch outlines for inserting and deleting records that require O(k + (log N)^k) time, on the average. This structure achieves faster response time than previously known structures (for many of the queries) at the cost of extra storage.

Copyright © 1980 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" 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/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" 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 DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

BibTeX

References

[1]: Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
[2]: ...
[3]: Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979) BibTeX
[4]: Jon Louis Bentley, Hermann A. Maurer: Efficient Worst-Case Data Structures for Range Searching. Acta Inf. 13: 155-168(1980) BibTeX
[5]: ...
[6]: Alfonso F. Cardenas, James P. Sagamang: Doubly-Chained Tree Data Base Organisation-Analysis and Design Strategies. Comput. J. 20(1): 15-26(1977) BibTeX
[7]: ...
[8]: ...
[9]: Rangasami L. Kashyap, S. K. C. Subas, S. Bing Yao: Analysis of the Multiple-Attribute-Tree Data-Base Organization. IEEE Trans. Software Eng. 3(6): 451-467(1977) BibTeX
[10]: Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
BibTeX
[11]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[12]: D. T. Lee, C. K. Wong: Worst-Case Analysis for Region and Partial Region Searches in Multidimensional Binary Search Trees and Balanced Quad Trees. Acta Inf. 9: 23-29(1977) BibTeX
[13]: ...
[14]: George S. Lueker: A Data Structure for Orthogonal Range Queries. FOCS 1978: 28-34 BibTeX
[15]: Louis Monier: Combinatorial Solutions of Multidimensional Divide-and-Conquer Recurrences. J. Algorithms 1(1): 60-74(1980) BibTeX
[16]: ...

Referenced by

Spyros Sioutas, Athanasios K. Tsakalidis, John Tsaknakis, Bill Vassiliadis: An Index Structure for the Support of Partial and Exact Match Queries in Database Systems. ADBIS (Short Papers) 1999: 24-30
Guido Moerkotte, Peter C. Lockemann: Reactive Consistency Control In Deductive Databases. ACM Trans. Database Syst. 16(4): 670-702(1991)
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269
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)
Dan E. Willard: Efficient Processing of Relational Calculus Expressions Using Range Query Theory. SIGMOD Conference 1984: 164-175
Andrew U. Frank: Application of DBMS to Land Information Systems. VLDB 1981: 448-453

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]