More Web Proxy on the site http://driver.im/

Article

NSJ: an efficient non-blocking spatial join algorithm

Authors:

Jose E. Córcoles,

Ning JingAuthors Info & Claims

GIS '06: Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems

Pages 235 - 242

https://doi.org/10.1145/1183471.1183510

Published: 10 November 2006 Publication History

Abstract

This paper introduces an efficient non-blocking spatial join (NSJ, for short) algorithm to deal with spatial objects from remote sources via underlying network. The objectives of NSJ are: (1) start reporting the first output join results as soon as possible, and (2) minimize the cost for output the remaining results. As some other previous non-blocking join algorithms, NSJ includes two stages: memory-join stage and disk-join stage The memory-join stage employs a join process as along as receiving spatial objects, and the disk-join stage is responsible for the uncompleted join process during the memory-join stage after all spatial objects are received completely. We propose a dynamic concurrent flush policy(DCFP) based on resident degree to process memory overflow, which makes join process in memory-join stage more efficiently. We also develop an optimal data access schedule algorithm based on BEA (Bond Energy Algorithm) to reduce redundant I/O and CPU cost in disk-join stage. Extensive experiments prove that our technique delivers result significantly more efficient than the previous methods.

References

[1]

M. F Mokbel, M. Lu, and W. G. Aref. Hash-merge Join: A non-blocking join algorithm for producing fast and early join results. In ICDE, pages 251--263, 2004.

Digital Library

[2]

G. Luo, J. F. Naughton, and C. Ellmann. A non-blocking parallel spatial join algorithm. In ICDE 2002, pages 697--705.

Digital Library

[3]

P. J. Haas and J. M. Hellerstein. Ripple Joins for Online Aggregation. In Proc. SIGMOD, pages 287--298, 1999.

Digital Library

[4]

Z. G. Ives, D. Florescu, M. Friedman, A. Y. Levy, and D S Weld. An Adaptive Query Execution System for Data Integration. In Proc. SIGMOD, pages 299--310, 1999.

Digital Library

[5]

G. Luo, C. J. Ellmann, P. J. Haas and J. F. Naughton. A Scalable Hash Ripple Join Algorithm. In Proc. SIGMOD, pages 40--51, 2002.

Digital Library

[6]

A. N. Wilschut and P. M. G. Apers. Dataflow Query Execution in a Parallel Main-Memory Environment. In Proc. PDIS, pages 68--77, 1991.

Digital Library

[7]

T. Urhan and M. J. Franklin. XJoin: A reactively-scheduled pipelined join operator. In Proc. TKDE, 23(2):27--33, 2000.

[8]

Y. Tao, M. Yiu and D. Papadias. RPJ: Producing Fast Join Results on Streams through Rate based Optimization. In Proc. SIGMOD, pages 371--382. 2005.

Digital Library

[9]

S. Viglas, J. F. Naughton and J. Burger. Maximizing the output rate of multi-way join queries over streaming information sources. In VLDB, pages 285--296, 2002.

Digital Library

[10]

J. P. Dittrich, B. Seeger, D. S. Taylor, and P. Widmayer. Progressive merge join: A generic and non-blocking sort-based join algorithm. In VLDB, pages 299--310, 2002.

Digital Library

[11]

J. Dittrich and B. Seeger. Data Redundancy and Duplicate Detection in Spatial Join Processing. In ICDE. 535--546, 2000.

Digital Library

[12]

J. M. Patel and D. J. DeWitt. Partition based spatial-merge join. In Proc. SIGMOD, pages 259--270. 1996.

Digital Library

[13]

X. P. Wang and L. M. Chao. Genetic Algorithm-Theory, application and implement. Xi'an JiaoTong university publication. 2004 the forth version.

[14]

J. McCirmick, P. J. Schweitzer and T. W. White(1972). Problem decomposition by a clustering technique. Op. Res, 20, 993--1009.

[15]

J. Xiao, Y. Zhang and X. Jia. Clustering non-uniform-sized spatial objects to reduce I/O cost for spatial-join processing. The Computer Journal, 2001, 44(5):384--397.

[16]

W. Xiong, W. Liao, F. Zhang, H. S. Chen and N. Jing. Genetic Optimization to the Refinement Step of Spatial Join Processing Journal of electron, 2006.

[17]

US Bureau of the Census. TIGER/Line Files. http://www.census.gov.

[18]

T. Urhan and M. J. Franklin. XJoin: Getting Fast Answers from Slow and Bursty Networks. University of Maryland Technical Report, CS-TR-3994., February, 1999.

[19]

D. A. Schneider and D. J. DeWitt. A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment. In SIGMOD, pages 110--121, 1989.

Digital Library

Cited By

Aly AAref WOuzzani MAli MHuang YGertz MRenz MSankaranarayanan J(2015)Spatial queries with k-nearest-neighbor and relational predicatesProceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2820783.2820815(1-10)Online publication date: 3-Nov-2015
https://dl.acm.org/doi/10.1145/2820783.2820815
Chen GLi GYang BTang XChen H(2008)Progressive Hash-Merge Join AlgorithmProceedings of the 2008 IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application - Volume 0210.1109/PACIIA.2008.234(117-121)Online publication date: 19-Dec-2008
https://dl.acm.org/doi/10.1109/PACIIA.2008.234
Chen GLi GYang BTang XChen H(2008)Fine-Grained Progressive Algorithm Based on HMJProceedings of the 2008 International Conference on Computer Science and Software Engineering - Volume 0410.1109/CSSE.2008.1008(589-592)Online publication date: 12-Dec-2008
https://dl.acm.org/doi/10.1109/CSSE.2008.1008

Index Terms

NSJ: an efficient non-blocking spatial join algorithm
1. Human-centered computing
  1. Visualization
    1. Visualization application domains
      1. Geographic visualization
2. Information systems
  1. Information systems applications
    1. Spatial-temporal systems

Recommendations

Efficient processing of spatial joins with DOT-based indexing

A spatial join is a query that searches for a set of object pairs satisfying a given spatial relationship from a database. It is one of the most costly queries, and thus requires an efficient processing algorithm that fully exploits the features of the ...
Grasping the gap between blocking and non-blocking transactional memories

Transactional memory (TM) is an inherently optimistic abstraction: it allows concurrent processes to execute sequences of shared-data accesses (transactions) speculatively, with an option of aborting them in the future. Early TM designs avoided using ...
Looking for efficient implementations of concurrent objects
PaCT'11: Proceedings of the 11th international conference on Parallel computing technologies

As introduced by Taubenfeld, a contention-sensitive implementation of a concurrent object is an implementation such that the overhead introduced by locking is eliminated in the common cases, i.e., when there is no contention or when the operations ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GIS '06: Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems

November 2006

264 pages

ISBN:1595935290

DOI:10.1145/1183471

General Chairs:
Rolf A. de By
ITC, The Netherlands
,
Silvia Nittel
University of Maine, USA

Copyright © 2006 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 November 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CIKM06

Sponsor:

CIKM06: Conference on Information and Knowledge Management

November 10 - 11, 2006

Virginia, Arlington, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
279
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Aly AAref WOuzzani MAli MHuang YGertz MRenz MSankaranarayanan J(2015)Spatial queries with k-nearest-neighbor and relational predicatesProceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2820783.2820815(1-10)Online publication date: 3-Nov-2015
https://dl.acm.org/doi/10.1145/2820783.2820815
Chen GLi GYang BTang XChen H(2008)Progressive Hash-Merge Join AlgorithmProceedings of the 2008 IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application - Volume 0210.1109/PACIIA.2008.234(117-121)Online publication date: 19-Dec-2008
https://dl.acm.org/doi/10.1109/PACIIA.2008.234
Chen GLi GYang BTang XChen H(2008)Fine-Grained Progressive Algorithm Based on HMJProceedings of the 2008 International Conference on Computer Science and Software Engineering - Volume 0410.1109/CSSE.2008.1008(589-592)Online publication date: 12-Dec-2008
https://dl.acm.org/doi/10.1109/CSSE.2008.1008

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten