HiPPIS: an online P2P system for efficient lookups on d-dimensional hierarchies

ABSTRACT

In this paper we describe HiPPIS, a system that enables efficient storage and on-line querying of multidimensional data organized into concept hierarchies and dispersed over a network. Our scheme utilizes an adaptive algorithm that automatically adjusts the level of indexing according to the granularity of the incoming queries, without assuming any prior knowledge of the workload. Efficient roll-up and drill-down operations take place in order to maximize the performance by minimizing query flooding. Extensive experimental evaluations show that, on top of the advantages that a distributed storage offers, our method answers the large majority of incoming queries, both point and aggregate ones, without flooding the network. At the same time, it manages to preserve the hierarchical nature of data. These characteristics are maintained even after sudden shifts in the workload.

REFERENCES

• 1: Karl Aberer , Philippe Cudré-Mauroux , Manfred Hauswirth, The chatty web: emergent semantics through gossiping, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775180]
• 2: K. Aberer, P. Cudre-Mauroux, M. Hauswirth, and T. V. Pelt. Gridvine:Building internet-scale semantic overlay networks. In International Semantic Web Conference, 2004.
• 3: APB-1 OLAP Benchmark. http://www.olapcouncil.org/.
• 4: Meeyoung Cha , Haewoon Kwak , Pablo Rodriguez , Yong-Yeol Ahn , Sue Moon, I tube, you tube, everybody tubes: analyzing the world's largest user generated content video system, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298309]
• 5: M. Ester, J. Kohlhammer, and P. Kriegel. The dc-tree: A fully dynamic index structure for data warehouses. In ICDE, 2000.
• 6: FreePastry. http://freepastry.rice.edu/freepastry.
• 7: Vijay Gopalakrishnan , Bujor Silaghi , Bobby Bhattacharjee , Pete Keleher, Adaptive Replication in Peer-to-Peer Systems, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.360-369, March 24-26, 2004
• 8: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843]
• 9: Ryan Huebsch , Joseph M. Hellerstein , Nick Lanham , Boon Thau Loo , Scott Shenker , Ion Stoica, Querying the internet with PIER, Proceedings of the 29th international conference on Very large data bases, p.321-332, September 09-12, 2003, Berlin, Germany
• 10: Verena Kantere , Dimitrios Tsoumakos , Timos Sellis , Nick Roussopoulos, GrouPeer: Dynamic clustering of P2P databases, Information Systems, v.34 n.1, p.62-86, March, 2009 [doi>10.1016/j.is.2008.04.002]
• 11: G. Koloniari and E. Pitoura. Content-based routing of path quieries in peer-to-peer systems. In EDBT, 2004.
• 12: Laks V. S. Lakshmanan , Jian Pei , Yan Zhao, QC-trees: an efficient summary structure for semantic OLAP, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872768]
• 13: B. Ooi, Y. Shu, K. Tan, and A. Zhou. PeerDB: A P2P-based System for Distributed Data Sharing. In ICDE, 2003.
• 14: T. Pitoura, N. Ntarmos, and P. Triantafillou. Replication, Load Balancing and Efficient Range Query Processing in DHTs. In EDBT, 2006.
• 15: Matei Ripeanu , Adriana Iamnitchi , Ian Foster, Mapping the Gnutella Network, IEEE Internet Computing, v.6 n.1, p.50-57, January 2002 [doi>10.1109/4236.978369]
• 16: Yannis Sismanis , Antonios Deligiannakis , Yannis Kotidis , Nick Roussopoulos, Hierarchical dwarfs for the rollup cube, Proceedings of the 6th ACM international workshop on Data warehousing and OLAP, November 07-07, 2003, New Orleans, Louisiana, USA [doi>10.1145/956060.956064]
• 17: Chunqiang Tang , Zhichen Xu , Sandhya Dwarkadas, Peer-to-peer information retrieval using self-organizing semantic overlay networks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863976]
• 18: W. Wang, H. Lu, J. Feng, and J. Yu. Condensed Cube: An Effective Approach to Reducing Data Cube Size. In ICDE, 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

General Terms:
Design, Performance

Keywords:
concept hierarchies, data warehousing, distributed hash table