MINING SPATIO-TEMPORAL INFORMATION SYSTEMS THE KLUWER INTERNATIONAL SERIES IN ENGINEERING AND COMPUTER SCIENCE MINING SP ATIO-TEMPORAL INFORMATION SYSTEMS edited by Roy Ladner Kevin Shaw Naval Research Laboratory Stennis Space Center, MS USA. Mahdi Abdelguerfi Computer Science Department University o/New Orleans, LA USA. SPRINGER SCIENCE+BUSINESS MEDIA, LLC Library of Congress Cataloging-in-Publication Data Ladner, Roy. Mining spatio-temporal information systems!Roy Ladner, Kevin Shaw, Mahdi Abdelguerfi. p.cm. - (Kiuwer international series in engineering and computer science; SECS 699) Includes bibliographical references and index. ISBN 978-1-4613-5416-1 ISBN 978-1-4615-1149-6 (eBook) DOI 10.1007/978-1-4615-1149-6 1. Data mining. 2. Temporal databases. 3. Geographic information systems. 4. Database management. I. Shaw, Kevin. II. Abdelguerfi, Mahdi III. Title. IV. Series QA 76.9.D343 L33 2002 06.3-dc10 2002072142 Copyright© 2002 by Springer Science+Business Media New York Originally published by K1uwer Academic Publishers in 2002 Softcover reprint ofthe hardcover 1st edition 2002 Ali rights reserved. No part ofthis work may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, microfilming, recording, or otherwise, without the written permission from the Publisher, with the exception of any material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser ofthe work. Printed on acid-free paper. CONTENTS PREFACE ...................................................................................................... ix CHAPTER 1 : SPATIO-TEMPORAL DATA MINING AND KNOWLEDGE DISCOVERY: ISSUES OVERVIEW by Roy Ladner and Frederick Petry ............................................................... 1 1. INTRODUCTION .................................................................................. 1 2. BACKGROUND .................................................................................... 2 2.1 DATA MINING ............................................................................ 2 2.2 SPATIAL DATA MINING ........................................................... 3 2.3 GIDB DATA MINING ............................................................... ..4 2.3.1 DATA MINING EFFORT ATNRL DMAP ....................... .4 2.3.2 GEOSPAT IAL INFORMATION DATABASE (GIDBTM) .. 5 3. DATA ..................................................................................................... 7 3.1 VECTOR DATA -NIMA ............................................................. 7 3.2 MISCELLANEOUS DATA REPOSITORIES ............................. 9 3.3 OCEANOGRAPHIC DATA ....................................................... 10 3.4 MODEL OUTPUT ...................................................................... 10 3.5 OBSERVATIONAL DATA-ARGUS SITES ........................... 11 3.6 2.5DAND3DDATA .................................................................. 11 4. DATA ISSUES .................................................................................... 11 4.1 SPATIO-TEMPORAL DATA ISSUES ...................................... 12 4.2 DATA SOURCE ISSUES ........................................................... 15 4.2.1 NIMA DATA ...................................................................... 15 4.2.2 MODEL OUTPUT .............................................................. 16 4.2.3 OBSERVATION DATA .................................................... 17 5. CONCLUSIONS .................................................................................. 17 CHAPTER 2 : INDEXING OF OBJECTS ON THE MOVE by Simonas Saltenis and Christian S. Jensen .............................................. .21 1. INTRODUCTION ................................................................................ 21 2. PROBLEM STATEMENT AND RELATED WORK ........................ 23 2.1 PROBLEM STATEMENT .......................................................... 23 2.2 PREVIOUS WORK .................................................................... 25 3. THE TPR-TREE .................................................................................. 26 3.1 INDEX STRUCTURE AND TIME-PARAMETERIZED BOUNDING RECTANGLES .................................................................. 26 3.2 HEURISTICS FOR TREE ORGANIZATION ........................... 28 3.3 INDEXING APPROACHES RELATED TO THE TPR-TREE.29 4. THE REXP_TREE ................................................................................. .30 4.1 REPRESENTATION OF POINTS AND BOUNDING RECTANGLES ........................................................................................ 30 4.2 ONE-DIMENSIONAL OPTIMAL TIME-PARAMETERIZED BOUNDING RECTANGLES .................................................................. 30 4.3 MULTI-DIMENSIONAL TIME-PARAMETERIZED BOUNDING RECTANGLES .................................................................. 32 4.4 REMOVAL OF EXPIRED ENTRIES ....................................... .35 5. SUMMARY OF PERFORMANCE EXPERIMENTS ....................... .38 6. CONCLUSIONS .................................................................................. 39 CHAPTER 3 : EFFICIENT STORAGE OF LARGE VOLUME SPATIAL AND TEMPORAL POINT-DATA IN AN OBJECT-ORIENTED DATABASE by David Olivier, Roy Ladner, Frank McCreedy, Ruth Wilson .................. .43 1. INTRODUCTION ................................................................................ 43 2. THE GIDB SySTEM ........................................................................... 45 3. THE PROBLEM DOMAIN ................................................................. 45 4. AN OBJECT-ORIENTED SOLUTION ............................................. .46 5. REQUIREMENTS ............................................................................... 48 6. TOWARDS A SOLUTION ................................................................. 48 7. THE DESIGN ...................................................................................... 49 8. A FLEXIBLE FRAMEWORK ............................................................ 52 9. SAMPLE APPLICATIONS ................................................................. 55 10. EVALUATION .................................................................................... 56 11. FUTURE DEVELOPMENTS .............................................................. 58 12. CONCLUSIONS .................................................................................. 59 CHAPTER 4 : A TYPOLOGY OF SPATIOTEMPORALINFORMATION QUERIES by May Yuan and John McIntosh ................................................................. 63 1. INTRODUCTION ................................................................................ 63 2. SPATIOTEMPORAL INFORMATION FOR THE DYNAMIC WORLD ........................................................................................................ 65 3. A TYPOLOGY OF SPATIOTEMPORAL QUERIES ........................ 67 3.1 ATTRIBUTE QUERY ................................................................ 67 3.2 THREE SPATIAL QUERY TYPES ........................................... 68 3.3 THREE TEMPORAL QUERY TYPES ...................................... 70 3.4 FOUR SPATIOTEMPORAL QUERY TYPES .......................... 72 4. CONCLUSIONS .................................................................................. 78 CHAPTER 5 : VISUAL QUERY OF TIME-DEPENDENT 3D WEATHER IN A GLOBAL GEOSPA TIAL ENVIRONMENT by William Ribarsky, Nickolas Faust, Zachary Wartell, Christopher Shaw, and Justin Jang ............................................................................................. 83 1. INTRODUCTION ................................................................................ 83 2. 40 DATA MODEL FOR THE VISUAL EARTH .............................. 84 2.1 RELEVANTWORK ................................................................... 85 2.2 THE DYNAMIC DATA MODEL .............................................. 87 2.3 SYSTEM ORGANIZATION ...................................................... 90 3. SCALABLE, HIERARCHICAL 3D DATA STRUCTURE ............... 92 3.1 THE DATA STRUCTURE ......................................................... 92 3.2 RESULTS FOR ACQUIRING AND VISUALIZING TIME- DEPENDENT DATA ............................................................................... 96 4. INTERACTIVE, ACCURATE VISUALIZATION OF NON- UNIFORM DATA ...................................................................................... 10 0 CHAPTER 6 : STQL - A SPA TIO-TEMPORAL QUERY LANGUAGE by Martin Erwig and Markus Schneider .................................................... 10 5 1. INTRODUCTION .............................................................................. 10 5 2. RELATED WORK ............................................................................. 107 3. THE DATA MODEL ......................................................................... 109 3.1 MOVINGOBJECTS ................................................................. II0 3.2 TEMPORAL LIFTING ............................................................. 110 3.3 SPATIO-TEMPORAL PREDICATES AND DEVELOPMENTS ........................................................................... 111 4. QUERYING WITH SPATIO-TEMPORAL OPERATIONS ............ 113 4.1 DESIGN ASPECTS AND APPLICATION SCENARIOS ....... 114 4.2 TEMPORAL SELECTIONS ..................................................... 115 4.3 PROJECTIONS TO SPACE AND TIME ................................. 115 4.4 AGGREGATIONS .................................................................... 116 4.5 TEMPORALLY LIFTED OPERATIONS ................................ 117 4.6 QUERYING DEVELOPMENTS IN STQL .............................. 118 4.6.1 MOTIVATION ................................................................. 119 4.6.2 QUERyING ...................................................................... 120 5. VISUAL QUERYING ....................................................................... 123 6. CONCLUSIONS ................................................................................ 124 CHAPTER 7: TRIPOD: A SPATIO-HISTORICAL OBJECT DATABASE SYSTEM by Tony Griffiths, Alvaro A.A. Fernandes, Norman W Paton, Seung-Hyun Jeong, Nassima Djafri, Keith T. Mason, Eo Huang, Mike Worboys .......... .127 1. INTRODUCTION .............................................................................. 128 2. CASE STUDY: UK NATIONAL LAND USE DATABASE ........... 129 3. THE TRIPOD OBJECT MODEL. ..................................................... 130 3.1 SPATIAL LITERALS ............................................................... 131 3.2 TIMESTAMP LITERALS ........................................................ 133 3.3 HISTORIES ............................................................................... 134 4. ARCHITECTURE .............................................................................. 136 4.1 THE LANGUAGE BINDINGS ................................................ 138 4.2 QUERY PROCESSING ............................................................ 139 4.2.1 LOGICAL OPTIMIZATION ........................................... 140 4.2.2 PHYSICAL OPTIMIZATION AND QUERY EVALUATION .................................................................................. 141 5. RELATED WORK ............................................................................. 145 6. CONCLUSIONS ................................................................................ 146 CHAPTER 8: SPATIO-TEMPORAL SUBGROUP DISCOVERY by Willi K16sgen and Michael May ............................................................ 149 1. INTRODUCTION : SPATIAL SUBGROUP MINING ..................... 149 2. APPLICATION EXAMPLE ............................................................. 152 3. REPRESENTATION OF SPATIO-TEMPORAL DATA AND OF SPATIAL SUBGROUPS ........................................................................... 154 3.1 REPRESENTATION OF SPATIAL DATA ............................. 154 3.2 REPRESENTATION OF SPATIO-TEMPORAL DATA ........ 156 3.3 REPRESENTATION OF SPATIAL SUBGROUPS ................ 157 3.4 REPRESENTATION OF SPATIAL SUBGROUPS IN QUERY LANGUAGES ........................................................................................ 159 4. SPATIO-TEMPORAL ANALYSES ................................................ 160 4.1 ANALYSES .............................................................................. 160 4.2 STATISTICAL METHODS ...................................................... 162 5. DATABASE INTEGRATION .............. ,. ........................................... 164 6. CONCLUSIONS AND FUTURE WORK ......................................... 166 Preface This edited manuscript is composed of chapters from leading experts in the field of Spatial-Temporal Information Systems. The manuscript brings together a coherent body of recent knowledge relating STIS data modeling, design, implementation and STIS in knowledge discovery. In particular, the reader is exposed to the latest techniques for the practical design of STIS, essential for complex query processing. The book is organized into four general sections. The first section serves as a general overview of the field. Chapter 1, "Spatio-Temporal Data Mining and Knowledge Discovery: Issues Overview," presents a survey of spatio-temporal data mining emphasizing the issues that the practitioner must deal with due to the special characteristics of this type of data. The efficient storage of spatio-temporal data can be quite helpful to the knowledge discovery process. The second section addresses this topic through three chapters in which the authors deal with this aspect of the mining process by discussing indexing techniques and data structures that aid the storage and retrieval of spatial and temporal data. Chapter 2, "Indexing of Objects on the Move," presents data indexing techniques that index on object positions described by linear functions of time. In chapter 3, "Efficient Storage of Large Volume Spatial and Temporal Point-Data in an Object Oriented Database," the authors describe the data structures particularly suited to the storage of temporal and spatial data. x The third broad section of this work covers spatio-temporal query issues. The authors discuss the fundamentals of spatio-temporal queries and develop a classification for such queries in Chapter 4, "A Typology of Spatiotemporal Information Queries." In Chapter 5, the authors deal with the querying of spatio-temporal data from an interactive visual perspective with a chapter titled, "Visual Query of Time-Dependent 3D Weather in a Global Geospatial Environment." The authors provide insight on how to handle a continuous stream of large-scale, time-dependent data. The authors in Chapter 6 present aspects of a spatio-temporal query language that allows query and retrieval of moving objects in a work entitled "STQL: A Spatio Temporal Query Language." The final section covers different aspects of specific systems. In Chapter 7, "Tripod: A Spatio-Historical Object Database System," the authors describe a spatio-historical object database system. In it the authors show how they maintain knowledge about entities that change over time. The authors in the final chapter, "Spatio-Temporal Subgroup Discovery," detail a subgroup mining system that provides causal analyses and interactive visualizations. The body of coherent work brought together by this manuscript describes first-hand experiences with Spatial-Temporal Information System design and development. We expect that this manuscript will appeal to a wide audience, ranging from the beginning student to experienced practitioners. The CD-ROM accompanying this manuscript includes a colored version of this manuscript's figures.