An adaptive range-query optimization technique with distributed replicas

Abstract

Replication is an approach often used to speed up the execution of queries submitted to a large dataset. A compile-time/run-time approach is presented for minimizing the response time of 2-dimensional range when a distributed replica of a dataset exists. The aim is to partition the query payload (and its range) into subsets and distribute those to the replica nodes in a way that minimizes a client’s response time. However, since query size and distribution characteristics of data (data dense/sparse regions) in varying ranges are not known a priori, performing efficient load balancing and parallel processing over the unpredictable workload is difficult. A technique based on the creation and manipulation of dynamic spatial indexes for query payload estimation in distributed queries was proposed. The effectiveness of this technique was demonstrated on queries for analysis of archived earthquake-generated seismic data records.

Keywords

distributed systems / load balancing / range query / query optimization

References

[1] TanenbaumA S, van SteenMDistributed systems: Principles and paradigms prentice hall upper saddle river [M], 20062nd ed.704

[2] ChenC M, ChengC T. Replication and retrieval strategies of multidimensional data on parallel disks [C]. CIKM’ 03 Proceedings of the Twelfth International Conference on Information and Knowledge Management, 2003, New York, NY, USA, ACM Press: 32-39

[3] ChervenakA, DeelmanE, FosterI, GuyL, HoschekW, IamnitchiA, KesselmanC, KunsztP, RipeanuM, SchwartzkopfB, StockingerH, StockingerK, TierneyB. Giggle: A framework for constructing scalable replica location supercomputing [C]. ACM/IEEE 2002 Conference, 2002, Baltimore, USA, IEEE Computer Society Press: 1-17

[4] GanesanP, BawaM, Garcia-MolinaH. Online balancing of range-partitioned data with applications to peer-to-peer systemsvery large database (VLDB) [C]. Proceedings fo the 30th International Conference on Very Large Data Bases, 2004, Toronto, Canada, Morgan Kaufmam: 444-455

[5] WengL, CatalyurekU, KurcT, AgrawalG, SaltzJ. Servicing range queries on multidimensional datasets with partial replicas IEEE international symposium on cluster computing and the grid [C]. CCGrid 2005, 2005, Cardiff, UK, IEEE: 726-733

[6] BeynonM, ChangC, CatalyurekU, KurcT, SussmanA, AndradeH, FerreiraR, SaltzJ. Processing large-scale multi-dimensional data in parallel and distributed environments [J]. Parallel Computing-Parallel Data-Intensive Algorithms and Applications, 2002, 28(5): 827-859

[7] DewittD, GrayJ. Parallel database systems: The future of high performance database systems [J]. ACM Communications, 1992, 35(6): 85-98

[8] ChakkaV P, EverspaughA, PatelJ M. Indexing large trajectory data sets with SETI [C]. Conference on Innovative Data Systems Research (CIDR-2003), 2003, CA, USA, VLDB: 281-291

[9] MaurouxC P, WuE, MaddenS. TrajStore: An adaptive storage system for very large trajectory data sets [C]. IEEE 26th International Conference on Data Engineering (ICDE), 2010, Long Beach, CA, IEEE Press: 109-120

[10] JoelB M, SaltzJ H. Scalability analysis of declustering methods for multidimensional range queries [J]. IEEE Transactions on Knowledge and Data Engineering, 1998, 10(2): 310-327

[11] BentleyJ L. Multidimensional binary search trees used for associative searching [J]. Communications of the ACM, 1975, 18(9): 509-517

[12] FilhoY S. Avarage case analysis of region search in balanced k-d trees [J]. Information Processing Letters, 1979, 8(5): 219-223

[13] TanenbaumA SModern operating systems [M], 2008, New Jersey, USA, Pearson Prentice Hall

[14] SayarA, PierceM, FoxGDeveloping GIS visualization web services for geophysical applications [C], 2005, Turkey, ISPRS Spatial Data Mining Workshop Ankara

[15] SayarA, PierceM, FoxG-CharlesGrid technology for maximizing collaborative decision management and support: Advancing effective virtual organizations [M], 2009, Bedfordshire, UK, IGI Global-Information Science Reference: 360-368

[16] AydinG, SayarA, GadgilH, AktasM S, FoxG C, KoS, BulutH, PierceM E. Building and applying geographical information systems grids [J]. Concurrency and Computation: Practice and Experience, 2008, 20(14): 1653-1695

[17] VRETANOS P A. Web Feature Service Implementation Specification [EB/OL]. 2002-11-02.

[18] BEAUJARDIERE J. OGC Web Map Service Interface [EB/OL]. Open GIS Consortium Inc. (OGC), 2006-03-15.