Efficient techniques for range search queries on earth science data

Proceedings 14th International Conference on Scientific and Statistical Database Management - Trang 142-151
Qingmin Shi1, J.F. JaJa1
1Institute for Advanced Computer Studies, Department of Electrical and Computer Engineering, University of Maryland, College Park, MD, USA

Tóm tắt

We consider the problem of organizing large scale earth science raster data to efficiently handle queries for identifying regions whose parameters fall within certain range values specified by the queries. This problem seems to be critical to enabling basic data mining tasks such as determining associations between physical phenomena and spatial factors, detecting changes and trends, and content based retrieval. We assume that the input is too large to fit in internal memory and hence focus on data structures and algorithms that minimize the I/O bounds. A new data structure, called a tree-of-regions (ToR), is introduced and involves a combination of an R-tree and efficient representation of regions. It is shown that such a data structure enables the handling of range queries in an optimal I/O time, under certain reasonable assumptions. We also show that updates to the ToR can be handled efficiently. Experimental results for a variety of multi-valued earth science data illustrate the fast execution times of a wide range of queries, as predicted by our theoretical analysis.

Từ khóa

#Geoscience #Large-scale systems #Data mining #Information retrieval #Content based retrieval #Data structures #Computational modeling #Educational institutions #Organizing #Tree data structures

Tài liệu tham khảo

berchtold, 1996, The X-tree: An index structure for high-dimensional data, VLDB ‘96 Proceedings of 22nd International conference on Very Large Data Bases, 28

den bercken, 1997, A generic approach to bulk loading multidimensional index structures, VLDB '97 Proceedings of the 23rd International Conference on Very Large Data Bases, 406

ester, 1996, A density-based algorithm for discovering clusters in large spatial databases with noise, Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), 226

10.1145/280277.280279

guttman, 1984, R-trees: A dynamic index structure for spatial searching, SIGMOD Proceedings ACM SIGMOD International Conference on management of Data, 47, 10.1145/971697.602266

10.1145/170088.170403

kamel, 1994, Hilbert R-tree: An improved R-tree using fractals, Proceedings of the Twentieth International Conference on Very Large Databases, 500

10.1006/jcss.1996.0043

10.1109/ICDE.1997.582015

10.1145/318898.318900

10.1145/48529.48535

2000, Content-based search and data mining

10.1007/3-540-48518-X_20

arge, 1995, The buffer tree: A new technique for optimal 110-algorithms, Proc 4th International Workshop on Algorithms and Data Structures (WADS), 334, 10.1007/3-540-60220-8_74

10.1145/93597.98741

10.1145/303976.304010

1999, Goddard DAAC NOAA/NASA Pathfinder AVHRR Land (PAL)

10.1007/BFb0100987

0, Landsat thematic mapper data

sellis, 1987, The R+-tree: A dynamic index for multi-dimensional objects, Proceedings of the 13th Interntational conference on Very Large Data Bases, 507

10.1145/275487.275501

subramanian, 1995, The P-range tree: A new data structure for range searching in secondary memory, In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 378

white, 1996, Algorithms and strategies for similarity retrieval, Technical Report VCL-96–1 0 1

wang, 1997, STING: a statistical information grid approach to spatial data mining, Proceedings of the Twenty-third International Conference on Very Large Data Bases, 186

10.1007/3-540-45244-3_6

Thông tin
Thông tin xuất bản

Proceedings 14th International Conference on Scientific and Statistical Database Management

142-151

Thông tin tác giả