dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Multikey Retrieval from K-d Trees and Quad-Trees.

D. A. Beckley, Martha W. Evens, V. K. Raman: Multikey Retrieval from K-d Trees and Quad-Trees. SIGMOD Conference 1985: 291-301
@inproceedings{DBLP:conf/sigmod/BeckleyER85,
  author    = {D. A. Beckley and
               Martha W. Evens and
               V. K. Raman},
  editor    = {Shamkant B. Navathe},
  title     = {Multikey Retrieval from K-d Trees and Quad-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     = {291-301},
  ee        = {http://doi.acm.org/10.1145/318898.318925},
  crossref  = {DBLP:conf/sigmod/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Associative file structures are potentiallv valuable for many database and artificial intelligence applications, but very little information is available to database designers trying to choose an appropriate file structure for a particular problem. This paper describes an experiment comparing the retrieval performance of K-d trees, quad-trees, and flat files, as measured by CPU time, wall clock time, and I/O operations. Five types of queries are used: exact match, partial match, range search, nearest neighbor, and best match. The database used in this study is a static medical database of half a million characters with the patient information removed. Results suggest that there is no one best type of file structure for all types of assoclatlve queries, quad trees dominated with some query classes, K-d trees with others.

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 ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 14(4)
Contents

Online Edition: ACM Digital Library


References

[1]
...
[2]
...
[3]
D. A. Beckley, Martha W. Evens, V. K. Raman: Empirical Comparison of Associative File Structures. FODO 1985: 407-414 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
...
[7]
Jon Louis Bentley: Decomposable Searching Problems. Inf. Process. Lett. 8(5): 244-251(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Jon Louis Bentley: Multidimensional Divide-and-Conquer. Commun. ACM 23(4): 214-229(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Alfonso F. Cardenas: Evaluation and Selection of File Organization - A Model and System. Commun. ACM 16(9): 540-548(1973) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Alfonso F. Cardenas, James P. Sagamang: Doubly-Chained Tree Data Base Organisation-Analysis and Design Strategies. Comput. J. 20(1): 15-26(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Jo-Mei Chang, King-sun Fu: A Dynamic Clustering Technique for Physical Database Design. SIGMOD Conference 1980: 188-199 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
...
[15]
Jo-Mei Chang, King-sun Fu: A Dynamic Clustering Technique for Physical Database Design. SIGMOD Conference 1980: 188-199 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Charles R. Dyer, Azriel Rosenfeld, Hanan Samet: Region Representation: Boundary Codes from Quadtrees. Commun. ACM 23(3): 171-179(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Raphael A. Finkel, Jon Louis Bentley: Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Inf. 4: 1-9(1974) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Jerome H. Friedman, Jon Louis Bentley, Raphael A. Finkel: An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Trans. Math. Softw. 3(3): 209-226(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
Irene Gargantini: An Effective Way to Represent Quadtrees. Commun. ACM 25(12): 905-910(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
...
[22]
Mark H. Overmars, Jan van Leeuwen: Dynamic Multi-Dimensional Data Structures Based on Quad- and K - D Trees. Acta Inf. 17: 267-285(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
Hanan Samet: Region Representation: Quadtrees from Boundary Codes. Commun. ACM 23(3): 163-170(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
Hanan Samet: Deletion in Two-Dimensional Quad Trees. Commun. ACM 23(12): 703-710(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
Hanan Samet: The Quadtree and Related Hierarchical Data Structures. ACM Comput. Surv. 16(2): 187-260(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
James B. Saxe, Jon Louis Bentley: Transforming Static Data Structures to Dynamic Structures (Abridged Version). FOCS 1979: 148-168 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[28]
...
[29]
...
[30]
Jan van Leeuwen, Mark H. Overmars: Stratified Balanced Search Trees. Acta Inf. 18: 345-359(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Tue Sep 18 00:24:59 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page