Adaptive Pre-computed Partition Top Method for Range Top-k Queries in OLAP Data Cubes

Simple item page
dc.contributor.authorZheng Xuan LOHen_US
dc.contributor.authorTok Wang LINGen_US
dc.contributor.authorChuan Heng ANGen_US
dc.contributor.authorSin Yeung LEEen_US
dc.contributor.authorHua-Gang LIen_US
dc.date.accessioned2004-10-21T14:28:52Zen_US
dc.date.accessioned2017-01-23T06:59:37Z
dc.date.available2004-10-21T14:28:52Zen_US
dc.date.available2017-01-23T06:59:37Z
dc.date.issued2001-07-01T00:00:00Zen_US
dc.description.abstractA 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.en_US
dc.format.extent1415248 bytesen_US
dc.format.extent4078190 bytesen_US
dc.format.mimetypeapplication/pdfen_US
dc.format.mimetypeapplication/postscripten_US
dc.identifier.urihttps://dl.comp.nus.edu.sg/xmlui/handle/1900.100/1417en_US
dc.language.isoenen_US
dc.relation.ispartofseriesTRA7/01en_US
dc.titleAdaptive Pre-computed Partition Top Method for Range Top-k Queries in OLAP Data Cubesen_US
dc.typeTechnical Reporten_US
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
report.ps
Size:
3.89 MB
Format:
Postscript Files
Description:
Download
Thumbnail Image
Name:
report.pdf
Size:
1.35 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.52 KB
Format:
Plain Text
Description:
Download
Collections
Technical Reports