An Efficient Multi-Dimensional Index for Cloud DataMan.ppt

1、An Efficient Multi-Dimensional Index for Cloud Data Management,Xiangyu Zhang Jing Ai Zhongyuan Wang Jiaheng Lu Xiaofeng Meng School of Information Renmin University of China,Outline,Motivation Query Answering on the Cloud Related Work EMINC: Index the Cloud Efficiently Node Bounding Extended Node Bo

2、unding Cost Estimation based Index Update Evaluation Conclusion & Future Work,Outline,Motivation Query Answering on the Cloud Related Work EMINC: Index the Cloud Efficiently Node Bounding Extended Node Bounding Cost Estimation based Index Update Evaluation Conclusion & Future Work,Motivation,Cloud s

3、ystems have been justified as brilliant for web search applications Simple structure, mostly key-value pairs Flexible, efficient for analytic work However, they are insufficient for complex data management needs No powerful language as SQL Hard to process complex queries Lack of efficient index stru

4、ctures,Distributed Cloud base?,BigTable,HBase,How to query on other attributes besides primary key?,Motivation,As part of our Cloud-based DBMS project, we aim to build efficient index structure on the Cloud.,Outline,Motivation Query Answering on the Cloud Related Work EMINC: Index the Cloud Efficien

5、tly Node Bounding Extended Node Bounding Cost Estimation based Index Update Evaluation Conclusion & Future Work,Query Answering in the Cloud,Fast locating of relevant slave nodes,Efficient lookup on each slave nodes,Outline,Motivation Query Answering on the Cloud Related Work EMINC: Index the Cloud

6、Efficiently Node Bounding Extended Node Bounding Cost Estimation based Index Update Evaluation Conclusion & Future Work,Related Work,S. Wu and K.-L. Wu, “An indexing framework for efficient retrieval on the cloud,” IEEE Data Eng. Bull., vol. 32, pp.7582, 2009.H. chih Yang and D. S. Parker, “Traverse

7、: Simplified indexing on large map-reduce-merge clusters,” in Proceedings of DASFAA 2009, Brisbane, Australia, April 2009, pp. 308322.M. K. Aguilera, W. Golab, and M. A. Shah, “A practical scalable distributed b-tree,” in Proceedings of VLDB08, Auckland, New Zealand, August 2008, pp. 598609.,Distrib

8、uted Database,Data slicing in DDBS Horizontal, vertical, etc. Slice based on conditions Check condition conflict on query processing Data distribution on the Cloud is different and could be very complex if expressed as set of conditions Condition check is too expensive,Outline,Motivation Query Answe

9、ring on the Cloud Related Work EMINC: Index the Cloud Efficiently Node Bounding Extended Node Bounding Cost Estimation based Index Update Evaluation Conclusion & Future Work,Outline,Motivation Query Answering on the Cloud Related Work EMINC: Index the Cloud Efficiently Node Bounding Extended Node Bo

10、unding Cost Estimation based Index Update Evaluation Conclusion & Future Work,EMINC: Node Bounding,Node cube of a table on a slave node Value range of table on this node,Node Cube: (1,1), (6,10),EMINC: Architecture,Each leaf node corresponds to one node cube,Use KD-Tree to maintain local index on sl

11、ave nodes,EMINC: Query Processing,Get query cube of the query and look up in the R-Tree to get relevant data nodes 1 Query Cube: (1,3),(2,4),Yes,No,Node Cube,Query Cube,Node Cube,Query Cube,Outline,Motivation Query Answering on the Cloud Related Work EMINC: Index the Cloud Efficiently Node Bounding

12、Extended Node Bounding Cost Estimation based Index Update Evaluation Conclusion & Future Work,EMINC: Extended Node Bounding,Problem with single bounding Bad performance for sparse node,Many queries will be mislead to this node,EMINC: Cube Cutting,Single Node Cube with Low Accuracy,Multiple Node Cube

13、 with High Accuracy,EMINC: Cube Methods,Random cutting,Equal cutting,Clustering-based cutting,Outline,Motivation Query Answering on the Cloud Related Work EMINC: Index the Cloud Efficiently Node Bounding Extended Node Bounding Cost Estimation based Index Update Evaluation Conclusion & Future Work,EM

14、INC: Index Update Strategy,Index update issues: Cubes may invalidate themselves after certain data update, thus need reconstruction Insertion invalidates cube Create a node cube containing new data For regular maintenance of index Cost estimation based update strategy,EMINC: Cost Estimation Strategy

15、,Cost of index update: Recalculate cubes on local node Transfer to master node and maintain R-Tree Query performance will be affected Benefit of index update: More accurate query directing, less waste,EMINC: Two Phase Method,After one update: Wait for a time period of deltaT deltaT expires, check if

16、 an update is needed Determin deltaT Check for update Assumption :,Number of queries to be processed,Total size of node cubes of this node,EMINC: Phase One,After pervious update: benefit = decrement-of-query/time* deltaT We enjoy the benefit of pervious update for deltaT time period cost = number-of

17、-queries missed Number of queries we could process if we use pervious update time to answer queries,EMINC: Phase Two,benefit cost = deltaT After deltaT expires, check if an update is needed. This check involves following: Record update frequency Expected benefit ratio Performance requirement We leav

18、e this as future work,Outline,Motivation Query Answering on the Cloud Related Work EMINC: Index the Cloud Efficiently Node Bounding Extended Node Bounding Cost Estimation based Index Update Evaluation Conclusion & Future Work,Evaluation,6 machines 1 as master node 5 slave nodes simulating 1001000 no

19、des Each machine had a 2.33GHz Intel Core2 Quad CPU, 4GB of main memory, and a 320G disk. Machines ran Ubuntu 9.04 Server OS.,Evaluation: Point Query,Evaluation: Range Query,Outline,Motivation Query Answering on the Cloud Related Work EMINC: Index the Cloud Efficiently Node Bounding Extended Node Bo

20、unding Cost Estimation based Index Update Evaluation Conclusion & Future Work,Conclusion,In this paper we presented a series of approaches on building efficient multi-dimensional index on Cloud platform. We developed the node bounding technique to reduce query processing cost on the cloud platform.

21、In order to maintain efficiency of the index, we proposed a cost estimation-based approach for index update.,Future Work,Complete cost estimation model Take replication of data into consideration Implement in Hbase to further verify performance,Thanks,Please visit our lab for more information: http:/