EDBT/ICDT 2009 Joint Conference

Electronic Conference Proceedings

• Welcome
• Full Program
• ICDT Sessions
  • Invited Talks
  • Research Track
    • Inconsistency and Repairs
    • Data Exchange
    • Data Structures and Algorithms
    • Uncertain Databases
    • XML
    • Querying
    • Business Processes
    • Streams, Data Mining, Complexity
    • Provenance
• ICDT Papers
• EDBT Sessions
• EDBT Papers
• Author Index
• Workshops

Efficient Data Structures for Range-Aggregate Queries on Trees

Authors

• Hao Yuan (Purdue University, USA)
• Mikhail J. Atallah (Purdue University, USA)

Abstract

Graph-theoretic aggregation problems have been considered both in OLAP (grid graph) and XML (tree). This paper gives new results for MIN aggregation in a tree, where we want the MIN in a query subtree consisting of the nodes reachable from a node u along paths of length <=k (u and k are query parameters). The same problem is well solved when the aggregation is SUM rather than MIN, but the solutions rely on additive inverses for the "+" operator, and they fail for the MIN aggregation which is the topic of this paper. For the directed (rooted tree) case, we give an O(n) space, constant query time solution. For the undirected case, the space complexity is O(n log n) and the query time is O(log n).

Session

ICDT Research Session 3: Data Structures and Algorithms (Monday, March 23, 16:00—17:30)