research-article

Spatio-temporal join technique for disaster estimation in large-scale natural disaster

Authors:

Hideki Hayashi,

Akinori Asahara,

Natsuko Sugaya,

Hitoshi TomitaAuthors Info & Claims

IWGS '15: Proceedings of the 6th ACM SIGSPATIAL International Workshop on GeoStreaming

Pages 49 - 58

https://doi.org/10.1145/2833165.2833171

Published: 03 November 2015 Publication History

Abstract

When a large-scale natural disaster occurs, it is necessary to collect damage information within about 10 minutes so that disaster-relief operations and wide-area support (depending on the the scale of the natural disaster) can be initiated. A high-performance method for "spatio-temporal join" which joins time-series grid data (such as results of simulations of natural disasters like tsunamis and fire spreading after a large-scale earthquake) and time-series point data representing people flows is proposed and applied to estimate damage situations following a natural disaster. The results of a performance evaluation of the method show that the response time for joining 100,000 point data and 250,000 grid data is about 50 seconds. They also show that it is possible to apply the proposed method to a real environment in which it is necessary to join one-million point data and hundreds of thousands of grid data within 10 minutes.

References

[1]

Cabinet Office, Government of Japan, "Disaster management in Japan," http://www.bousai.go.jp/1info/pdf/saigaipamphlet_je.pdf

[2]

Center for Spatial Information Science, The University of Tokyo, Collaborative research, "Urban space information platform able to assimilate dynamic data". People Flow Project, http://pflow.csis.u-tokyo.ac.jp/?page_id=943

[3]

J. Allen, "Maintaining knowledge about temporal intervals," Communication of the ACM, vol. 26, pp. 832--843 (1983).

Digital Library

[4]

N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger, "The R* tree: an efficient and robust access method for points and rectangles," Proc.of ACM SIGMOD'90, pp. 322--332 (1990).

Digital Library

[5]

B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer, "An asymptotically optimal multiversion B-tree," VLDB Journal, vol. 5, no. 4, pp. 264--275 (1996).

Digital Library

[6]

S. Berchtold, C. Bohm, and H.-P. Kriegel, "The pyramid-technique: towards breaking the curse of dimensionality," Proc. of ACM SIGMOD'98, pp. 142--153 (2008).

Digital Library

[7]

T. Brinkhoff, H.-P. Kriegel, and B. Seeger, "Efficient processing of spatial joins using R-trees," Proc. of ACM SIGMOD'93, pp. 237--246 (1993).

Digital Library

[8]

V.P. Chakka, A. Everspaugh, and J.M. Patel, "Indexing large trajectory data sets with SETI," Proc. of CIDR (2003).

[9]

S. Chen, B.C. Ooi, K.-L. Tan, and M.A. Nascimento, "ST2B-tree: a self-tunable spatio-temporal B+-tree index for moving objects," Proc. of ACM SIGMOD'08, pp. 29--42 (2008).

Digital Library

[10]

E.F. Codd, "A relational model of data for large shared data banks," Communications of the ACM, vol. 13, issue 6, pp. 377--387 (1970).

Digital Library

[11]

J. Enderle, M. Hampel, and T. Seidl, "Joining interval data in relational databases," Proc of ACM SIGMOD'04, pp. 683--694 (2004).

Digital Library

[12]

O. Günther, "Efficient computation of spatial joins," Proc. of IEEE ICDE'93, pp. 50--59 (1993).

Digital Library

[13]

L. Harada, M. Nakano, M. Kitsuregawa, and M. Takagi, "Query processing for multi-attribute clustered records," Proc. of VLDB'90, pp. 59--70 (1990).

Digital Library

[14]

H. Hayashi, M. Tanizaki, A. Sato, K. Kimura, H. Kajiyama, and M. Irie, "Spatial search processing in embedded devices," Proc. of ACM GIS'09, pp. 516--519 (2009).

Digital Library

[15]

G.R. Hjaltason and H. Samet, "Speeding up construction of PMR quadtree-based spatial indexes," VLDB Journal, vol. 11, issue 2, pp. 109--137 (2002).

Digital Library

[16]

Y.-W. Huang, N. Jing, and E.A. Rundensteiner, "Spatial joins using R-trees: breadth-first traversal with global optimizations," Proc. of VLDB'97, pp. 396--405 (1997).

Digital Library

[17]

H. Jagadish, "Linear clustering objects with multiple attributes," Proc. of ACM SIGMOD'90, pp. 332--342 (1990).

Digital Library

[18]

H. Jagadish, B.C. Ooi, K.-L. Tan, C. Yu, and R. Zhang, "iDistance: an adaptive B+-tree based indexing method for nearest neighbor search," ACM Trans. Database Syst., vol. 30, no. 2, pp. 364--397 (2005).

Digital Library

[19]

E.H. Jacox and H. Samet, "Spatial join techniques," ACM Trans. Database Syst., vol. 32, issue 1, pp. 1--44 (2007).

Digital Library

[20]

C.S. Jensen, D. Lin, and B.C. Ooi, "Query and update efficient B+ tree based indexing of moving objects," Proc. of VLDB'04, pp. 768--779 (2004).

Digital Library

[21]

S.H. Jeong, N.W. Paton, A.A.A. Fernandes, and T. Griffiths, "An experimental performance evaluation of spatio-temporal join strategies," Transactions in GIS, vol. 9, issue 2, pp. 129--156 (2005).

[22]

S.-W. Kim, W.-S. Cho, M.-J. Lee, and K.-Y. Whang, "A new algorithm for processing joins using the multilevel grid file," Proc. of DASFAA'95, pp. 115--123 (1995).

Digital Library

[23]

M. Kitsuregawa, L. Harada, and M. Takagi, "Join strategies on kd-tree indexed relations," Proc of IEEE ICDE'89, pp. 85--93 (1989).

Digital Library

[24]

H.-P. Kriegel, M. Potke, and T. Seidl, "Managing intervals efficiently in object-relational databases," Proc of VLDB'00, pp. 407--418 (2000).

Digital Library

[25]

D. Lin, C.S. Jensen, B.C. Ooi, and S. Saltenis, "Efficient indexing of the historical, present, and future positions of moving objects," Proc of Int'l Conf. on Mobile Data Management (MDM'05), pp. 59--66 (2005).

Digital Library

[26]

K.C.K. Lee, B. Zheng, H. Li, and W.-C. Lee, "Approaching the skyline in z order," Proc of VLDB'07, pp. 279--290 (2007).

Digital Library

[27]

P. Mishra and M.H. Eich, "Join processing in relational databases," ACM Computing Surveys, vol. 24, issue 1, pp. 63--113 (1992).

Digital Library

[28]

M.F. Mokbel, T.M. Ghanem, and W.G. Aref, "Spatio-temporal access methods," IEEE Data Eng. Bull., vol. 26, no. 2, pp. 40--49 (2003).

[29]

L.-V. Nguyen-Dinh, W.G. Aref, and M.F. Mokbel, "Spatio-temporal access methods: part 2 (2003-2010)," IEEE Data Eng. Bull., vol. 33, no. 2, pp. 46--55 (2010).

[30]

S. Saltenis, C.S. Jensen, S. Leutenegger, and M. Lopez, "Indexing the positions of continuously moving objects," Proc of ACM SIGMOD'00, pp. 331--342 (2000).

Digital Library

[31]

J.-W. Song, K.-Y. Whang, Y.-K. Lee, M.-J. Lee, and S.-W. Kim, "Spatial join processing using corner transformation," IEEE Trans. Knowl. Data Eng., vol. 11, no. 4, pp. 688--695 (1999).

Digital Library

[32]

X. Song, Q. Zhang, Y. Sekimoto, T. Horanont, S. Ueyama, and R. Shibasaki, "Modeling and probabilistic reasoning of population evacuation during large-scale disaster," Proc. of ACM SIGKDD'13, pp. 1231--1239 (2013).

Digital Library

[33]

Y. Tao and D. Papadias, "MV3R-Tree: a spatio-temporal access method for timestamp and interval queries," Proc of VLDB'01, pp. 431--440 (2001).

Digital Library

[34]

Y. Theodoridis, M. Vazirgiannis, and T. Sellis, "Spatio-temporal indexing for large multimedia applications," Proc. of IEEE Conf. on Multimedia Computing and Systems (ICMCS'96), pp. 441--448 (1996).

Digital Library

[35]

M. Yiu, Y. Tao, and N. Mamoulis, "The Bdual-tree: indexing moving objects by space filling curves in the dual space," VLDB Journal, vol. 17, no. 3, pp. 379--400 (2008).

Digital Library

[36]

D. Zhang, V.J. Tsotras, and B. Seeger, "Efficient temporal join processing using indices," Proc of IEEE ICDE'02, pp. 103--113 (2002).

Digital Library

[37]

R. Zhang, J. Qi, M. Stradling, and J. Huang, "Towards a painless index for spatial objects," ACM Trans. Database Syst., vol. 39, no. 3, pp. 19:1--19:42 (2014).

Digital Library

Cited By

Li TXu J(2023)Block-Join: A Partition-Based Method for Processing Spatio-Temporal JoinsWeb and Big Data10.1007/978-3-031-25201-3_30(397-411)Online publication date: 10-Feb-2023
https://doi.org/10.1007/978-3-031-25201-3_30
Lee KSeo MLee RPark MLee S(2020)Efficient Processing of Spatio-Temporal Joins on IoT DataIEEE Access10.1109/ACCESS.2020.30012148(108371-108386)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3001214

Recommendations

Composition of simulation data for large-scale disaster estimation
EM-GIS '16: Proceedings of the Second ACM SIGSPATIALInternational Workshop on the Use of GIS in Emergency Management

When a large-scale natural disaster occurs, it is necessary to quickly collect damage information so that disaster-relief operations and wide-area support in accordance with the scale of the natural disaster can be initiated. Previously, we proposed a ...
Proposal of New Disaster Support System for Large-Scale Natural Disaster
NBIS '14: Proceedings of the 2014 17th International Conference on Network-Based Information Systems

This paper proposes New Disaster Support System at the time of large-scale natural disaster. This Disaster Support System consists of Relief Supplies Distribution Management System and IC Card Authorization Safety Confirmation System. Relief Supplies ...
Proposal of the Relief Supplies Support System at the Time of Large-Scale Natural Disaster
BWCCA '14: Proceedings of the 2014 Ninth International Conference on Broadband and Wireless Computing, Communication and Applications

The Great East Japan Earthquake caused catastrophic damage to Iwate Prefecture, Miyagi Prefecture, and Fukushima Prefecture. A lot of relief supplies were sent to these stricken areas from all over the country in case of the Great East Japan Earthquake. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

IWGS '15: Proceedings of the 6th ACM SIGSPATIAL International Workshop on GeoStreaming

November 2015

102 pages

ISBN:9781450339711

DOI:10.1145/2833165

Copyright © 2015 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

SIGSPATIAL: ACM Special Interest Group on Spatial Information

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

SIGSPATIAL'15

Sponsor:

SIGSPATIAL

SIGSPATIAL'15: 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 3 - 6, 2015

WA, Bellevue, USA

Acceptance Rates

Overall Acceptance Rate 7 of 9 submissions, 78%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
83
Total Downloads

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

Reflects downloads up to 08 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li TXu J(2023)Block-Join: A Partition-Based Method for Processing Spatio-Temporal JoinsWeb and Big Data10.1007/978-3-031-25201-3_30(397-411)Online publication date: 10-Feb-2023
https://doi.org/10.1007/978-3-031-25201-3_30
Lee KSeo MLee RPark MLee S(2020)Efficient Processing of Spatio-Temporal Joins on IoT DataIEEE Access10.1109/ACCESS.2020.30012148(108371-108386)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3001214

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.

Media

Figures

Other

Tables

View Table of Contents