ACM SIGMOD Anthology ACM SIGMOD dblp.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, db/conf/sigmod/BeckleyER85.html},
  crossref  = {DBLP:conf/sigmod/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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

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

Referenced by

  1. Stacie Hibino, Elke A. Rundensteiner: Processing Incremental Multidimensional Range Queries in a Direct Manipulation Visual Query. ICDE 1998: 458-465
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:42 2009