Article

Free access

Multikey retrieval from K-d trees and QUAD-trees

Authors:

D. A. Beckley,

M. W. Evens,

V. K. RamanAuthors Info & Claims

SIGMOD '85: Proceedings of the 1985 ACM SIGMOD international conference on Management of data

Pages 291 - 301

https://doi.org/10.1145/318898.318925

Published: 01 May 1985 Publication History

PDF eReader

References

[1]

Banks, G, Caplan, L R, and Hier, D B 1983 The Michael Reese Hospital Stroke Registry - A Mrcrocomputer-Implemented Data Base 7th Annual Symposium 0" Computer Applications~ Medical Care IEEE Computer Society 124-727-

Google Scholar

[2]

Beckley, D A, Evens, M W, and Raman. V K 1984 An Experiment With Balanced and Unbalanced K-D Trees for Associative Retrieval 0th Int Computer Software and Applications Conf Gceedings IEEE Computer Society IEEE Catalog NO 84CH2096-6 256-262

Google Scholar

[3]

Beckley, D A, Evers, M W, and Raman, V h 1985 Empirical Comparison of Assoclatlve File Structures International Conference on Foundations of Data Organization Kyo to, Japan May, -85(to be published)

Google Scholar

[4]

Bentley, J L 1975 Multidimensional Binary Search lrees Used for Associative Searching Communications of the ACM Vol 18, No 9 509-517

Digital Library

Google Scholar

[5]

Bentley, J L 1979 Multidimensional Binary Search Trees Used in Database Applications IEEE Transartions on Software Englneerlng Vol SE-5, No 4 333340

Google Scholar

[6]

Bentley, J L and Friedman, J H 1978 Fast Algorithms for Constructing Minimal Spanning Trees in Coordinate Spaces IEEE Transactions on Computers Vol C-27, ho 2 97-105

Google Scholar

[7]

Bentley, J L 1979 Decomposable Searching Problems Information Processing Letters Vol 8, No 5 244-251

Google Scholar

[8]

Bentley, J L and Friedman, J H 1979 Data Structures for Range Searching Computing Surveys Vol 11, No 4 397-409

Digital Library

Google Scholar

[9]

Bentley, J L 1980 Multrdimensional Divideand-Conquer Communications of the ACM Vol --- 23. No 4 214-229

Digital Library

Google Scholar

[10]

Cardenas, A F 1973 Evaluation and Selection of File Organization - A Model and Sys tern Communlcatlons of the ACM --- Vol 16, No 9 540-548

Digital Library

Google Scholar

[11]

Cardenas, AF 1975 Analysis and Performance of Inverted Data Base Structures Communications of the 4CM Vol 10, No -- 5 253-263

Digital Library

Google Scholar

[12]

Cardenas, A F, Sagamang, J P 1977 Doubly- Chained Tree Data Base Organization - Analysis and Design Strategies The Computer Journal Vol 20, No 1 15-26

Google Scholar

[13]

Chang, J M andFu, KS 1978 Dynamic Clustering Techniques for Physical Database Des lgn TR-EE 78-49, Paue University

Google Scholar

[14]

Chang, J M and Fu, K S 1979 Extended K-D A- IEEE Compu 79CH1515-6C 39-43 Tree Data Base Organization A Dynamic p*l+*- Attribute Clustering Method 3rd T-c F-, Software and Applications Conf ter Society IEEE Proceedings Catalog No

Google Scholar

[15]

Chang, J M andFu, KS 1980 A Dynamic Clustering Terhnrone for Physical Database Des ien ACM-SIGMOD 1900- International Conference 0" Management of Data Association -- for Computing Machinery ACM Order No 472800

Digital Library

Google Scholar

[16]

Comer, D 1979 The Ubiquitous B-tree Computing Surveys Vol. 11, No 2 121-137

Digital Library

Google Scholar

[17]

Dyer, C R, Rosenfeld, A, and Samet, H 1980 Region Representation Boundary Codes from Quadtrees Communlcatlons of the ACM Vol 23, No 3 171-179

Digital Library

Google Scholar

[18]

Flnkel, R A and Bentley, 3 L 1974 A Data Structure for Retrieval on Composite Keys Acta Informatrca Vol 4 l-9

Google Scholar

[19]

Frledman, J H, Bentley, J L, and Flnkel, RA 1977 An Algorithm for FindIng Best ACM Vol Matches IIY Logarithmic Expected Time Transactions on Mathematical Software 3, No 3 209-226

Digital Library

Google Scholar

[20]

Gargantlni, I 1982 An Effectrve Represent Quadtrees Communications ACM - Vol 25, No 12 905-910

Digital Library

Google Scholar

[21]

Lum, V Y, Ling, H, and Senko, M E Analysis of a Complex Data Management ACCeSS Method by Simulation Modeling AFIPS Proceedin@ of Fall Joint Computer Conference --- AFIPS Press, Arlington, Va Vol 37 211-222

Digital Library

Google Scholar

[22]

Overmars, M H and Van Leeuwen, Jan 1982 Dynamic Multi-Dimensional Data Structures Based on Quad- and K-d Trees Acta Informatlca Vol 17 267-285

Google Scholar

[23]

RobInson, J T 1981 The K-D-B-Tree A Search Structure for Large Multidlmenslonal Dynamic Indexes 4CM-SIGMOD 1981 International Conference 0" Management of Data Association -- for Computing Machinery

Digital Library

Google Scholar

[24]

Samet, H 1980 Region Representation Quadtrees from Boundary Codes Communications of the ACM Vol --- 23, No 3 163-170

Digital Library

Google Scholar

[25]

Samet, H 1980 Deletion In Two-Dlmenslonal Quad Trees Communications of the ACM Vol 23. No 12 703-710 ---

Digital Library

Google Scholar

[26]

Samet, H 1984 The Quadtree and Related Hierarchical Data Structures Surveys Vol 16, No 2 187-260 Computing

Digital Library

Google Scholar

[27]

Saxe, J B and Bentley, J L 1979 Transforming Static Data Str&tures to Dynamic Structures - 20th Annual IEEE S~~POSUUII Proc on Foundations of GumScGe Catalog No 79CHlRl-2 148-168 IEEE

Google Scholar

[28]

Snedecor, G W and Cochran, W G 1980 Statistical Methods 7th ed The Iowa State University Press Ames, Iowa

Google Scholar

[29]

Vandendorpe, J 1980 A Crash Tolerant B-tree Data Structure for - - - Data Base Retrieval Systems Ph D T&ils, -- Illinois Jnstitute of Technology

Digital Library

Google Scholar

[30]

Van Leeuwen, J and Overmars, M H 1983 Stratified Balanced Search Trees Acta Informatica Vol 18 345-359

Google Scholar

Cited By

View all

Xuan KZhao GTaniar DSafar MSrinivasan B(2011)Voronoi-based multi-level range search in mobile navigationMultimedia Tools and Applications10.1007/s11042-010-0498-y53:2(459-479)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1007/s11042-010-0498-y
Xuan KZhao GTaniar DSafar MSrinivasan B(2011)Constrained range search query processing on road networksConcurrency and Computation: Practice & Experience10.1002/cpe.165123:5(491-504)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1002/cpe.1651
Xuan KTaniar DSafar MSrinivasan BPardede ETaniar DAwan I(2010)Time constrained range search queries over moving objects in road networksProceedings of the 8th International Conference on Advances in Mobile Computing and Multimedia10.1145/1971519.1971573(329-336)Online publication date: 8-Nov-2010
https://dl.acm.org/doi/10.1145/1971519.1971573
Show More Cited By

Index Terms

Recommendations

Rank-Balanced Trees

Since the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But the ...
Deletion in two-dimensional quad trees

An algorithm for deletion in two-dimensional quad trees that handles the problem in a manner analogous to deletion in binary search trees is presented. The algorithm is compared with a proposed method for deletion which reinserts all of the nodes in the ...
Quad-kd trees

We introduce the quad-kd tree: a general purpose and hierarchical data structure for the storage of multidimensional points. Quad-kd trees include point quad trees and kd trees as particular cases and therefore they could constitute a general framework ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGMOD '85: Proceedings of the 1985 ACM SIGMOD international conference on Management of data

May 1985

66 pages

ISBN:0897911601

DOI:10.1145/318898

Chairmen:
Shamkant B. Navathe
Univ. of Florida, Gainesville
,
Al Dale
Univ. of Texas

ACM SIGMOD Record Volume 14, Issue 4
May 1985
423 pages
ISSN:0163-5808
DOI:10.1145/971699
Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1985

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD '85

Sponsor:

SIGMOD

SIGMOD '85: Management of data

Texas, Austin, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
945
Total Downloads

Downloads (Last 12 months)88
Downloads (Last 6 weeks)20

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Xuan KZhao GTaniar DSafar MSrinivasan B(2011)Voronoi-based multi-level range search in mobile navigationMultimedia Tools and Applications10.1007/s11042-010-0498-y53:2(459-479)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1007/s11042-010-0498-y
Xuan KZhao GTaniar DSafar MSrinivasan B(2011)Constrained range search query processing on road networksConcurrency and Computation: Practice & Experience10.1002/cpe.165123:5(491-504)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1002/cpe.1651
Xuan KTaniar DSafar MSrinivasan BPardede ETaniar DAwan I(2010)Time constrained range search queries over moving objects in road networksProceedings of the 8th International Conference on Advances in Mobile Computing and Multimedia10.1145/1971519.1971573(329-336)Online publication date: 8-Nov-2010
https://dl.acm.org/doi/10.1145/1971519.1971573
Xuan KZhao GTaniar DSrinivasan BSafar MGavrilova M(2009)Network Voronoi Diagram Based Range SearchProceedings of the 2009 International Conference on Advanced Information Networking and Applications10.1109/AINA.2009.82(741-748)Online publication date: 26-May-2009
https://dl.acm.org/doi/10.1109/AINA.2009.82
Hibino SRundensteiner E(1998)Processing incremental multidimensional range queries in a direct manipulation visual query environmentProceedings 14th International Conference on Data Engineering10.1109/ICDE.1998.655808(458-465)Online publication date: 1998
https://doi.org/10.1109/ICDE.1998.655808
Hibino SRundensteiner EAigrain PHall WLittle TBove V(1997)MMVISProceedings of the fourth ACM international conference on Multimedia10.1145/244130.244149(75-86)Online publication date: 1-Feb-1997
https://dl.acm.org/doi/10.1145/244130.244149
Jain VShneiderman B(1994)Data structures for dynamic queriesProceedings of the workshop on Advanced visual interfaces10.1145/192309.192313(1-11)Online publication date: 1-Jun-1994
https://dl.acm.org/doi/10.1145/192309.192313
Samet HWebber R(1989)A comparison of the space requirements of multi-dimensional quadtree-based file structuresThe Visual Computer10.1007/BF019991025:6(349-359)Online publication date: Nov-1989
https://doi.org/10.1007/BF01999102
Eastman C(1987)File organizations & incrementally specified queriesProceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval10.1145/42005.42030(217-222)Online publication date: 1-Nov-1987
https://dl.acm.org/doi/10.1145/42005.42030
Samaddar RSamaddar SKim TBhattacharyya D(2010)Hierarchical Data Structures for Accessing Spatial DataSignal Processing and Multimedia10.1007/978-3-642-17641-8_32(267-274)Online publication date: 2010
https://doi.org/10.1007/978-3-642-17641-8_32

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Rank-Balanced Trees

Deletion in two-dimensional quad trees

Quad-kd trees