Article

Free access

Speeding up bulk-loading of quadtrees

Authors:

Gísli R. Hjaltason,

Hanan Samet,

Yoram J. SussmannAuthors Info & Claims

GIS '97: Proceedings of the 5th ACM international workshop on Advances in geographic information systems

Pages 50 - 53

https://doi.org/10.1145/267825.267839

Published: 01 November 1997 Publication History

PDF eReader

References

[1]

T. Brinkhoff, H. E Kriegel, and B. Seeger. Efficient processing of spatial joins using R-trees. In Proceedings of the 1993 A CM SIGMOD International Conference, pages 237-246, Washington, DC, May 1993.

Digital Library

Google Scholar

[2]

Bureau of the Census. 7iger/Lineprecensusfiles. Washington, DC, 1989.

Google Scholar

[3]

C. Esperan~a and H. Samet. An overview of the SAND spatial database system. Communications of the ACM, to appear 1997.

Google Scholar

[4]

I. Gargantini. An effective way to represent quadtrees. Communications of the A CM, 25(12):905-910, December 1982.

Digital Library

Google Scholar

[5]

O. Gtinther. Efficient computation of spatial joins. InProceedings of the 9th IEEE International Conference on Data Engineering, pages 50-59, Vienna, Austria, April 1993.

Digital Library

Google Scholar

[6]

E. G. Hoel and H. Samet. Benehmarking spatial join operations with spatial output. In U. Dayal, P. M. D. Gray, and S. Nishio, editors, Proceedings of the 21st International Conference on Very Large Data Bases, pages 606--618, Zurich, September 1995.

Digital Library

Google Scholar

[7]

I. Kamel and C. Faloutsos. On packing R-trees. Second International Conference on Information and Knowledge Management (CIKM), pages 490--499, November 1993.

Digital Library

Google Scholar

[8]

M. Lindenbaumand H. Samet. A probabilistie analysis oftriebased sorting of large collections of line segments. Computer Science Department TR-3455, University of Maryland, College Park, MD, April 1995.

Google Scholar

[9]

R. C. Nelson and H. Samet. A population analysis for hierarchical data structures. In Proceedingsofthe SIGMOD Conference, pages 270--277, San Francisco, May 1987.

Digital Library

Google Scholar

[10]

Oracle Corporation. Advances in relational database technology for spatial data management. Oracle spatial data option technical white paper, September 1996.

Google Scholar

[11]

H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1990.

Digital Library

Google Scholar

Cited By

View all

Elshrif MIsufaj KMokbel MRenz MSarwat M(2022)Network-less trajectory imputationProceedings of the 30th International Conference on Advances in Geographic Information Systems10.1145/3557915.3560942(1-10)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1145/3557915.3560942
Roumelis GFevgas AVassilakopoulos MCorral ABozanis PManolopoulos Y(2019)Bulk-loading and bulk-insertion algorithms for $$\hbox {xBR}^{+}\hbox {-trees}$$ xBR + -trees in Solid State DrivesComputing10.1007/s00607-019-00709-4Online publication date: 12-Mar-2019
https://doi.org/10.1007/s00607-019-00709-4
Roumelis GVassilakopoulos MCorral AManolopoulos Y(2016)Bulk-Loading xBR $$^+$$ -treesModel and Data Engineering10.1007/978-3-319-45547-1_5(57-71)Online publication date: 7-Sep-2016
https://doi.org/10.1007/978-3-319-45547-1_5
Show More Cited By

Index Terms

Speeding up bulk-loading of quadtrees
1. Information systems
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Bulk-loading the ND-tree in non-ordered discrete data spaces
DASFAA'08: Proceedings of the 13th international conference on Database systems for advanced applications

Applications demanding multidimensional index structures for performing efficient similarity queries often involve a large amount of data. The conventional tuple-loading approach to building such an index structure for a large data set is inefficient. ...
Efficient Bulk-Loading of Gridfiles

This paper considers the problem of bulk-loading large data sets for the gridfile multiattribute indexing technique. We propose a rectilinear partitioning algorithm that heuristically seeks to minimize the size of the gridfile needed to ensure no bucket ...
Bulk-Loading an Index for Temporally Overlaying Spatio-Textual Trajectories
BigSpatial '17: Proceedings of the 6th ACM SIGSPATIAL Workshop on Analytics for Big Geospatial Data

The IR-With-Identifiers (IRWI) tree, proposed by Issa and Damiani, indexes temporally overlaying spatio-textual trajectories and allows for efficiently answering sequenced spatio-textual range queries. We investigate the efficiency of constructing such ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GIS '97: Proceedings of the 5th ACM international workshop on Advances in geographic information systems

November 1997

78 pages

ISBN:1581130171

DOI:10.1145/267825

Editors:
Niki Pissinou
Univ. of Southwestern Louisiana, Lafayette
,
Kia Makki
Univ. of Nevada, Las Vegas
,
Patrick Bergougnoux
Univ. of Toulouse, France
,
Robert Laurini
INSA, France, and Univ. of Lyon, France

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 November 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

CIKM97

Sponsor:

CIKM97: Sixth International Conference on Information and Knowledge Management

November 10 - 14, 1997

Nevada, Las Vegas, USA

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
370
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)14

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Elshrif MIsufaj KMokbel MRenz MSarwat M(2022)Network-less trajectory imputationProceedings of the 30th International Conference on Advances in Geographic Information Systems10.1145/3557915.3560942(1-10)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1145/3557915.3560942
Roumelis GFevgas AVassilakopoulos MCorral ABozanis PManolopoulos Y(2019)Bulk-loading and bulk-insertion algorithms for $$\hbox {xBR}^{+}\hbox {-trees}$$ xBR + -trees in Solid State DrivesComputing10.1007/s00607-019-00709-4Online publication date: 12-Mar-2019
https://doi.org/10.1007/s00607-019-00709-4
Roumelis GVassilakopoulos MCorral AManolopoulos Y(2016)Bulk-Loading xBR $$^+$$ -treesModel and Data Engineering10.1007/978-3-319-45547-1_5(57-71)Online publication date: 7-Sep-2016
https://doi.org/10.1007/978-3-319-45547-1_5
Haverkort HToma L(2016)Quadtrees and Morton IndexingEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_585(1637-1642)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_585
Haverkort HToma L(2015)Quadtrees and Morton IndexingEncyclopedia of Algorithms10.1007/978-3-642-27848-8_585-1(1-7)Online publication date: 14-Jul-2015
https://doi.org/10.1007/978-3-642-27848-8_585-1
Haverkort HMcGranaghan MToma L(2013)An Edge Quadtree for External MemoryExperimental Algorithms10.1007/978-3-642-38527-8_12(115-126)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38527-8_12
Rafiei DHu C(2006)Bulk loading a linear hash fileProceedings of the 8th international conference on Data Warehousing and Knowledge Discovery10.1007/11823728_3(23-32)Online publication date: 4-Sep-2006
https://dl.acm.org/doi/10.1007/11823728_3
Ghanem TShah RMokbel MAref WVitter J(2004)Bulk Operations for Space-Partitioning TreesProceedings of the 20th International Conference on Data Engineering10.5555/977401.978122Online publication date: 30-Mar-2004
https://dl.acm.org/doi/10.5555/977401.978122
Vasaitis VNanopoulos ABozanis P(2004)Merging R-treesProceedings. 16th International Conference on Scientific and Statistical Database Management, 2004.10.1109/SSDM.2004.1311206(141-150)Online publication date: 2004
https://doi.org/10.1109/SSDM.2004.1311206
Kim TLi K(2003)A distance-based packing method for high dimensional dataProceedings of the 14th Australasian database conference - Volume 1710.5555/820085.820115(135-144)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.5555/820085.820115
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

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

Bulk-loading the ND-tree in non-ordered discrete data spaces

Efficient Bulk-Loading of Gridfiles

Bulk-Loading an Index for Temporally Overlaying Spatio-Textual Trajectories