A Space-Time Efficient Algorithm for Constructing QC-Tree
QC-Tree is an effective data structure for constructing data cube,which makes a significant reduction in the cube size,while preserving its semantics. The original construction algorithm of QC-Tree performs not well because it does not begin the construction until all the temporary classes generated and sorted. The number of temporary classes is usually so huge,which leads to a huge memory requirement and poor sorting performance and thus quite a long time for constructing QC-Tree. In order to solve the problems,a new algorithm called ConstructTreeByBFS is proposed in this paper. ConstructTreeByBFS immediately constructs a corresponding QC-Tree branch once a temporary class is generated and then the temporary class is dropped. Without storing all of the temporary classes in memory,it significantly reduces the memory requirement during construction. In addition,for speeding up the construction,ConstructTreeByBFS searches the temporary classes in efficient iterative BFS way instead of inefficient recursive DFS way. An experimental study illustrates the space saving and time saving achieved by ConstructTreeByBFS algorithm. Finally,we discuss the plan for further improving the performance of QC-Tree by reducing storage size and speeding query answer in the future.
QC-Tree Temporary Class Recursive DFS Iterative BFS ConstructTreeByBFS
Yichen Li Jianqing Xi
School of Computer Science & Engineering,South China University of Technology,Guangzhou,510000,China
国际会议
香港
英文
76-80
2010-08-17（万方平台首次上网日期，不代表论文的发表时间）