Skip navigation
Skip navigation

Range queries in dynamic OLAP data cubes

Liang, Weifa; Wang, Hui; Orlowska, Maria

Description

A range query applies an aggregation operation (e.g., SUM) over all selected cells of an OLAP data cube where the selection is specified by providing ranges of values for numeric dimensions. Range sum queries on data cubes are a powerful analysis tool. Many applications domains requir that data cubes are updated often and the information provided by analysis tools are current or 'near current'. Existing techniques for range sum queries on data cubes, however, can incur update costs in the order...[Show more]

dc.contributor.authorLiang, Weifa
dc.contributor.authorWang, Hui
dc.contributor.authorOrlowska, Maria
dc.date.accessioned2015-12-13T23:21:06Z
dc.identifier.issn0169-023X
dc.identifier.urihttp://hdl.handle.net/1885/91023
dc.description.abstractA range query applies an aggregation operation (e.g., SUM) over all selected cells of an OLAP data cube where the selection is specified by providing ranges of values for numeric dimensions. Range sum queries on data cubes are a powerful analysis tool. Many applications domains requir that data cubes are updated often and the information provided by analysis tools are current or 'near current'. Existing techniques for range sum queries on data cubes, however, can incur update costs in the order of the size of the data cube. Since the size of a data cube is exponential in the number of its dimensions, rebuilding the entire data cube can be very costly and is not realistic. To cope with this dynamic data cube problem, a new approach has been introduced recently, which achieves constant time per range sum query while constraining each update cost within O(nd/2), where d is the number of dimensions of the data cube and n is the number of distinct values of the domain at each dimension. In this paper, we provide a new algorithm for the problem which requires O(n1/3) time for each range sum query and O(nd/3) time for each update. Our algorithm improves the update time by a factor of O(nd/6) in contrast to the current one for the problem O(nd/2). Like all existing techniques, our approach to answering range sum queries is also based on some precomputed auxiliary information (prefix sums) that is used to answer ad hoc queries at run time. Under both the product model and a new model introduced in this paper, the total cost for updates and ranges queries of the proposed algorithm is smallest compared with the cost by all known algorithms. Therefore our algorithm reduces the overall time complexity for range sum queries significantly.
dc.publisherElsevier
dc.sourceData and Knowledge Engineering
dc.subjectKeywords: Algorithms; Cellular arrays; Computational complexity; Constraint theory; Data structures; Decision support systems; Online searching; Query languages; Theorem proving; Data cube; Multidimensional database; Online analytical processing; Range sum query; U
dc.titleRange queries in dynamic OLAP data cubes
dc.typeJournal article
local.description.notesImported from ARIES
local.description.refereedYes
local.identifier.citationvolume34
dc.date.issued2000
local.identifier.absfor080708 - Records and Information Management (excl. Business Records and Information Management)
local.identifier.ariespublicationMigratedxPub21528
local.type.statusPublished Version
local.contributor.affiliationLiang, Weifa, College of Engineering and Computer Science, ANU
local.contributor.affiliationWang, Hui, Tianjin University
local.contributor.affiliationOrlowska, Maria, University of Queensland
local.description.embargo2037-12-31
local.bibliographicCitation.startpage21
local.bibliographicCitation.lastpage38
local.identifier.doi10.1016/S0169-023X(00)00007-0
dc.date.updated2015-12-12T09:05:30Z
local.identifier.scopusID2-s2.0-0033704234
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Liang_Range_queries_in_dynamic_OLAP_2000.pdf776.36 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator