Efficient data structures for range-aggregate queries on trees

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).

REFERENCES

• 1: P. Agarwal and J. Erickson. Geometric range searching and its relatives. Advances in Discrete and Computational Geometry, volume 23 of Contemporary Mathematics, 1--56. American Mathematical Society Press, Providence, RI, 1999.
• 2: M. J. Atallah, Y. Cho, and A. Kundu. Efficient data authentication in an environment of untrusted third-party distributors. In Proceedings of the 24th International Conference on Data Engineering, ICDE 2008, April 7--12, 2008, Cancún, México, pages 696--704, 2008.
• 3: A. M. Ben-Amram. The Euler path to static level-ancestors. Unpublished manuscript.
• 4: Michael A. Bender , Martin Farach-Colton, The LCA Problem Revisited, Proceedings of the 4th Latin American Symposium on Theoretical Informatics, p.88-94, April 10-14, 2000
• 5: Michael A. Bender , Martín Farach-Colton, The level ancestor problem simplified, Theoretical Computer Science, v.321 n.1, p.5-12, June 16, 2004 [doi>10.1016/j.tcs.2003.05.002]
• 6: F. Bengtsson and J. Chen. Space-efficient range-sum queries in OLAP. In Y. Kambayashi, M. K. Mohania, and W. Wöß, editors, DaWaK, volume 3181 of Lecture Notes in Computer Science, pages 87--96. Springer, 2004.
• 7: Omer Berkman , Uzi Vishkin, Finding level-ancestors in trees, Journal of Computer and System Sciences, v.48 n.2, p.214-230, April 1994 [doi>10.1016/S0022-0000(05)80002-9]
• 8: B. Chazelle, Computing On A Free Tree Via Complexity-Preserving Mappings, Proceedings of the 25th Annual Symposium onFoundations of Computer Science, 1984, p.358-368, October 24-26, 1984 [doi>10.1109/SFCS.1984.715936]
• 9: Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
• 10: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 11: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 12: Ching-Tien Ho , Rakesh Agrawal , Nimrod Megiddo , Ramakrishnan Srikant, Range queries in OLAP data cubes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.73-88, May 11-15, 1997, Tucson, Arizona, United States
• 13: Raghav Kaushik , Philip Bohannon , Jeffrey F Naughton , Henry F Korth, Covering indexes for branching path queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564707]
• 14: J. Komlos, Linear Verification For Spanning Trees, Proceedings of the 25th Annual Symposium onFoundations of Computer Science, 1984, p.201-206, October 24-26, 1984 [doi>10.1109/SFCS.1984.715916]
• 15: Ashish Kundu , Bertino Elisa, Secure Dissemination of XML Content Using Structure-based Routing, Proceedings of the 10th IEEE International Enterprise Distributed Object Computing Conference, p.153-164, October 16-20, 2006 [doi>10.1109/EDOC.2006.46]
• 16: Hua-Gang Li , Tok Wang Ling , Sin Yeung Lee, Range-Max/Min Query in OLAP Data Cube, Proceedings of the 11th International Conference on Database and Expert Systems Applications, p.467-476, September 04-08, 2000
• 17: Weifa Liang , Hui Wang , Maria E. Orlowska, Range queries in dynamic OLAP data cubes, Data & Knowledge Engineering, v.34 n.1, p.21-38, July 2000 [doi>10.1016/S0169-023X(00)00007-0]
• 18: Seth Pettie, An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.155, November 16-19, 2002
• 19: Chung Keung Poon, Orthogonal Range Queries in OLAP, Proceedings of the 8th International Conference on Database Theory, p.361-374, January 04-06, 2001
• 20: R. E. Tarjan. Sensitivity analysis of minimum spanning trees and shortest path trees. Inf. Process. Lett., 14(1):30--33, 1982.
• 21: Hao Yuan , Mikhail J. Atallah, Efficient Distributed Third-Party Data Authentication for Tree Hierarchies, Proceedings of the 2008 The 28th International Conference on Distributed Computing Systems, p.184-193, June 17-20, 2008 [doi>10.1109/ICDCS.2008.53]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms

Keywords:
query answering, range aggregation