Browsing by Author "Chuan Heng ANG"

Now showing 1 - 3 of 3
  • No Thumbnail Available
    Item
    Adaptive Pre-computed Partition Top Method for Range Top-k Queries in OLAP Data Cubes
    (2001-07-01T00:00:00Z) Zheng Xuan LOH; Tok Wang LING; Chuan Heng ANG; Sin Yeung LEE; Hua-Gang LI
    A range top-k query finds the top-k maximum values over all selected cells of an On-Line Analytical Processing (OLAP) data cube where the selection is specified by providing ranges of contiguous values for each dimension. The naive method answers a range query by accessing every individual cell in the data cube. Therefore, the naive method is very costly and is exponentially proportional to the number of dimensions of the data cube. Here, we propose a new method for handling the range top-k queries efficiently, termed the Adaptive Pre-computed Partition Top method (APPT). This method partitions the given data cube and stores r pre-computed maximum values with the corresponding locations over partitioned sub-blocks. Furthermore, an area termed overflow array stores additional maximum values for sub-block, which requires more than r maximum values for some range queries. By pre-storing the additional maximum values in the overflow array, the response time for the subsequent queries with the similar ranges will be significantly reduced. The experiment results exhibit vast improvement in terms of the response time of our APPT method as compared to the naive method. Our method promises an average update cost of (1+t) total disk accesses, where t is the average number of IO blocks in the overflow array for each sub-block. This method, which is equipped with intelligence and self- learning capability, is able to maintain the value of t below 0.5. Moreover, the APPT method can be efficiently applied on uniform and non-uniform data distributions in both dense and sparse OLAP data cubes.
  • No Thumbnail Available
    Item
    Bitmap R-trees
    (1999-05-01T00:00:00Z) Chuan Heng ANG; Tuck Choy TAN
    Bitmap R-tree is a variant of R-tree in which bitmaps are used for the description of the internal and the external regions of the objects in addition to the use of minimum bounding rectangles. The proposed scheme increases the chance of trivial acceptance and rejection of data objects, and reduces unnecessary disk accesses in query processing. It has been shown that with the bitmaps as filters, the reference to the object data file can be cut down by as much as 60%.
  • No Thumbnail Available
    Item
    Filtered Linear Hashing
    (1999-05-01T00:00:00Z) Chuan Heng ANG; Tuck Choy TAN
    Filtered linear hashing is a combination of linear hashing and filtered hashing. It expands the file gracefully as linear hashing, and organizes the overflow buckets with the use of a filter buffer to ensure that any bucket can be retrieved in one disk access. At a load factor of 0.7, the cost of file creation is reduced by 15% as opposed to linear hashing, with higher cost saving for larger load factors.