NSJ: an efficient non-blocking spatial join algorithm

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: Mohamed F. Mokbel , Ming Lu , Walid G. Aref, Hash-Merge Join: A Non-blocking Join Algorithm for Producing Fast and Early Join Results, Proceedings of the 20th International Conference on Data Engineering, p.251, March 30-April 02, 2004
• 2: A Non-Blocking Parallel Spatial Join Algorithm, Proceedings of the 18th International Conference on Data Engineering, p.697, February 26-March 01, 2002
• 3: Peter J. Haas , Joseph M. Hellerstein, Ripple joins for online aggregation, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.287-298, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 4: Zachary G. Ives , Daniela Florescu , Marc Friedman , Alon Levy , Daniel S. Weld, An adaptive query execution system for data integration, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.299-310, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 5: Gang Luo , Curt J. Ellmann , Peter J. Haas , Jeffrey F. Naughton, A scalable hash ripple join algorithm, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564721]
• 6: Annita N. Wilschut , Peter M. G. Apers, Dataflow query execution in a parallel main-memory environment, Proceedings of the first international conference on Parallel and distributed information systems, p.68-77, December 1991, Miami, Florida, United States
• 7: T. Urhan and M. J. Franklin. XJoin: A reactively-scheduled pipelined join operator. In Proc. TKDE, 23(2):27--33, 2000.
• 8: Yufei Tao , Man Lung Yiu , Dimitris Papadias , Marios Hadjieleftheriou , Nikos Mamoulis, RPJ: producing fast join results on streams through rate-based optimization, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066200]
• 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.
• 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.
• 11: Data Redundancy and Duplicate Detection in Spatial Join Processing, Proceedings of the 16th International Conference on Data Engineering, p.535, February 28-March 03, 2000
• 12: Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.259-270, June 04-06, 1996, Montreal, Quebec, Canada
• 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: Donovan A. Schneider , David J. DeWitt, A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.110-121, June 1989, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Experimentation, Performance

Keywords:
BEA, DCFP, non-blocking, spatial join