2D TSA-tree: A Wavelet-Based Approach to Improve the Efficiency of Multi-Level Spatial Data Mining Cyrus Shahabi, Seokkyung Chung, Maytham Safar, and George Hajj   View Paper (PDF)   Return to Index Structures for SSDBM Abstract Due to the large amount of the collected scientific data, it is becoming increasingly difficult for scientists to comprehend and interpret the available data. Moreover, typical queries on these data sets are in the nature of identifying (or visualizing) trends and surprises at a selected sub-region in multiple levels of abstraction rather than identifying information about a specific data point. In this paper, we propose a versatile wavelet-based data structure, 2D TSA-tree (stands or Trend and Surprise Abstractions Tree), to enable efficient multi-level trend detection on spatial data at different levels. We showhow2D TSA-tree can be utilized efficiently or sub-region selections. Moreover, 2D TSA-tree can be utilized to precompute the reconstruction error and retrieval time of a data subset in advance in order to allow the user to trade off accuracy for response time (or vice versa) at the query time. Finally, when the storage space is limited, our 2D Optimal TSA-tree saves on storage by storing only a specific optimal subset of the tree. To demonstrate the effectiveness of our proposed methods, we evaluated our 2D TSA-tree using real and synthetic data. Our results show that our method out performed other methods (DFT and SVD) in terms of accuracy, complexity and scalability. DiSC'02 © 2003 Association for Computing Machinery