research-article

Spatial joins in main memory: implementation matters!

Authors:

Darius Šidlauskas,

Christian S. JensenAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 8, Issue 1

Pages 97 - 100

https://doi.org/10.14778/2735461.2735470

Published: 01 September 2014 Publication History

Get Access

Abstract

A recent PVLDB paper reports on experimental analyses of ten spatial join techniques in main memory. We build on this comprehensive study to raise awareness of the fact that empirical running time performance findings in main-memory settings are results of not only the algorithms and data structures employed, but also their implementation, which complicates the interpretation of the results.

In particular, we re-implement the worst performing technique without changing the underlying high-level algorithm, and we then offer evidence that the resulting re-implementation is capable of outperforming all the other techniques. This study demonstrates that in main memory, where no time-consuming I/O can mask variations in implementation, implementation details are very important; and it offers a concrete illustration of how it is difficult to make conclusions from empirical running time performance findings in main-memory settings about data structures and algorithms studied.

References

[1]

Spatial indexing at Cornell. http://www.cs.cornell.edu/bigreddata/spatial-indexing/. Accessed: 2014-07-23.

Google Scholar

[2]

S. Chen, C. S. Jensen, and D. Lin. A benchmark for evaluating moving object indexes. PVLDB, 1(2):1574--1585, 2008.

Digital Library

Google Scholar

[3]

J. Dittrich, L. Blunschi, and M. A. V. Salles. Indexing moving objects using short-lived throwaway indexes. In SSTD, pages 189--207, 2009.

Digital Library

Google Scholar

[4]

A. Guttman. R-trees: A dynamic index structure for spatial searching. In SIGMOD, pages 47--57, 1984.

Digital Library

Google Scholar

[5]

K. Kim, S. K. Cha, and K. Kwon. Optimizing multidimensional index trees for main memory access. In SIGMOD, pages 139--150, 2001.

Digital Library

Google Scholar

[6]

S. T. Leutenegger, M. A. Lopez, and J. Edgington. STR: A simple and efficient algorithm for R-tree packing. In ICDE, pages 497--506, 1997.

Digital Library

Google Scholar

[7]

B. Sowell, M. V. Salles, T. Cao, A. Demers, and J. Gehrke. An experimental analysis of iterated spatial joins in main memory. PVLDB, 6(14):1882--1893, 2013.

Digital Library

Google Scholar

[8]

D. Šidlauskas, S. Šaltenis, C. W. Christiansen, J. M. Johansen, and D. Šaulys. Trees or grids? Indexing moving objects in main memory. In GIS, pages 236--245, 2009.

Digital Library

Google Scholar

Cited By

View all

Koubarakis M(2022)Geospatial Interlinking with JedAI-spatialCompanion Proceedings of the Web Conference 202210.1145/3487553.3526093(499-500)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3487553.3526093
Amagata DTsuruoka SArai YHara T(2021)Feat-SKSJProceedings of the 29th International Conference on Advances in Geographic Information Systems10.1145/3474717.3483629(15-24)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3474717.3483629
Belussi AMigliorini SEldawy A(2020)Cost estimation of spatial join in spatialhadoopGeoinformatica10.1007/s10707-020-00414-x24:4(1021-1059)Online publication date: 5-Jul-2020
https://dl.acm.org/doi/10.1007/s10707-020-00414-x
Show More Cited By

Recommendations

Redesign the Memory Allocator for Non-Volatile Main Memory
Special Issue on Hardware and Algorithms for Learning On-a-chip and Special Issue on Alternative Computing Systems

The non-volatile memory (NVM) has the merits of byte-addressability, fast speed, persistency and low power consumption, which make it attractive to be used as main memory. Commonly, user process dynamically acquires memory through memory allocators. ...
A durable and energy efficient main memory using phase change memory technology
ISCA '09: Proceedings of the 36th annual international symposium on Computer architecture

Using nonvolatile memories in memory hierarchy has been investigated to reduce its energy consumption because nonvolatile memories consume zero leakage power in memory cells. One of the difficulties is, however, that the endurance of most nonvolatile ...
Power management of hybrid DRAM/PRAM-based main memory
DAC '11: Proceedings of the 48th Design Automation Conference

Hybrid main memory consisting of DRAM and non-volatile memory is attractive since the non-volatile memory can give the advantage of low standby power while DRAM provides high performance and better active power. In this work, we address the power ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 8, Issue 1

September 2014

100 pages

ISSN:2150-8097

Editors:
Chen Li
University of California, Irvine
,
Volker Markl
TU Berlin

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 September 2014

Published in PVLDB Volume 8, Issue 1

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
189
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Koubarakis M(2022)Geospatial Interlinking with JedAI-spatialCompanion Proceedings of the Web Conference 202210.1145/3487553.3526093(499-500)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3487553.3526093
Amagata DTsuruoka SArai YHara T(2021)Feat-SKSJProceedings of the 29th International Conference on Advances in Geographic Information Systems10.1145/3474717.3483629(15-24)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3474717.3483629
Belussi AMigliorini SEldawy A(2020)Cost estimation of spatial join in spatialhadoopGeoinformatica10.1007/s10707-020-00414-x24:4(1021-1059)Online publication date: 5-Jul-2020
https://dl.acm.org/doi/10.1007/s10707-020-00414-x
Li LTaniar D(2017)A Taxonomy for Distance-Based Spatial Join QueriesInternational Journal of Data Warehousing and Mining10.4018/IJDWM.201707010113:3(1-24)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.4018/IJDWM.2017070101
Sabek IMokbel M(2017)On Spatial Joins in MapReduceProceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3139958.3139967(1-10)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3139958.3139967
Sabek ICheung AElmore A(2017)Optimizing Spatial Queries in MapReduceProceedings of the 2017 ACM International Conference on Management of Data10.1145/3055167.3055179(28-30)Online publication date: 14-May-2017
https://dl.acm.org/doi/10.1145/3055167.3055179
Kriegel HSchubert EZimek A(2017)The (black) art of runtime evaluationKnowledge and Information Systems10.1007/s10115-016-1004-252:2(341-378)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s10115-016-1004-2
Abeywickrama TCheema MTaniar D(2016)k-nearest neighbors on road networksProceedings of the VLDB Endowment10.14778/2904121.29041259:6(492-503)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.14778/2904121.2904125
Tahboub RRompf TAli MNewsam SRenz MTrajcevski GRavada S(2016)On supporting compilation in spatial query enginesProceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2996913.2996945(1-4)Online publication date: 31-Oct-2016
https://dl.acm.org/doi/10.1145/2996913.2996945
Yu CBoyd J(2016)FB+-tree for Big Data ManagementBig Data Research10.1016/j.bdr.2015.11.0034:C(25-36)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1016/j.bdr.2015.11.003
Show More Cited By

View Options

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

Recommendations

Redesign the Memory Allocator for Non-Volatile Main Memory

A durable and energy efficient main memory using phase change memory technology

Power management of hybrid DRAM/PRAM-based main memory