Distinct value estimation on peer-to-peer networks

ABSTRACT

Peer-to-Peer networks have become very popular on the Internet, with millions of peers all over the world sharing large volumes of data. In the assistive healthcare sector, it is likely that P2P networks will develop that interconnect and allow the controlled sharing of patient databases of various hospitals, clinics, and research laboratories. However, the sheer scale of these networks has made it difficult to gather statistics that could be used for building new features. In this paper, we present a technique to obtain estimations of the number of distinct values matching a query on the network. We evaluate the technique experimentally and provide a set of results that demonstrate its effectiveness, as well as its flexibility in supporting a variety of queries and applications.

REFERENCES

• 1: Surajit Chaudhuri , Gautam Das , Utkarsh Srivastava, Effective use of block-level sampling in statistics estimation, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007602]
• 2: Arai, B., Das, G., Gunopulos, D., and Kalogeraki, V. Approximating Aggregation Queries in Peer-to-Peer Networks. ICDE 2006 (April 3--8, Atlanta, GA, 2006)
• 3: Ziv Bar-Yossef , Maxim Gurevich, Random sampling from a search engine's index, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135833]
• 4: Moses Charikar , Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Towards estimation error guarantees for distinct values, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.268-279, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335230]
• 5: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 6: Java Universal Network/Graph Framework (JUNG) Website. http://jung.sourceforge.net.
• 7: Metropolis, N., Rosenbluth A, Rosenbluth, M., Teller, A., and Teller, E., Equations of state calculations by fast computing machines. J. of Chemical Physics, 21:1087--1091, 1953.
• 8: W. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):97--109, 1970.
• 9: M. Ripeanu, [15] Peer-to-Peer Architecture Case Study: Gnutella Network, Proceedings of the First International Conference on Peer-to-Peer Computing (P2P'01), p.99, August 27-29, 2001
• 10: Gnutella Development website: rfc-gnutella.sourceforge.net
• 11: Daniel Stutzbach , Reza Rejaie , Nick Duffield , Subhabrata Sen , Walter Willinger, On unbiased sampling for unstructured peer-to-peer networks, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177084]
• 12: Baset, S. A., and Schulzrinne, H. An analysis of the Skype peer-to-peer Internet telephony protocol. Technical Report CUCS-039-04, Computer Science Department, Columbia University, September 2004.
• 13: KazaA website: kazaa.com
• 14: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Random sampling for histogram construction: how much is enough?, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.436-447, June 01-04, 1998, Seattle, Washington, United States
• 15: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Lynne Stokes, Sampling-Based Estimation of the Number of Distinct Values of an Attribute, Proceedings of the 21th International Conference on Very Large Data Bases, p.311-322, September 11-15, 1995
• 16: Tsoumakos, D., and Roussopoulos, N. - A Comparison of Peer-to-Peer Search Methods In Proceedings of the Sixth International Workshop on Web and Databases, San Diego, California (June 12--13, 2003)
• 17: Stephanos Androutsellis-Theotokis , Diomidis Spinellis, A survey of peer-to-peer content distribution technologies, ACM Computing Surveys (CSUR), v.36 n.4, p.335-371, December 2004 [doi>10.1145/1041680.1041681]
• 18: Ziv Bar-Yossef , Alexander Berg , Steve Chien , Jittat Fakcharoenphol , Dror Weitz, Approximating Aggregate Queries about Web Pages via Random Walks, Proceedings of the 26th International Conference on Very Large Data Bases, p.535-544, September 10-14, 2000
• 19: Valerie King , Jared Saia, Choosing a random peer, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011786]
• 20: David Kempe , Alin Dobra , Johannes Gehrke, Gossip-Based Computation of Aggregate Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.482, October 11-14, 2003
• 21: Prasanna Ganesan , Mayank Bawa , Hector Garcia-Molina, Online balancing of range-partitioned data with applications to peer-to-peer systems, Proceedings of the Thirtieth international conference on Very large data bases, p.444-455, August 31-September 03, 2004, Toronto, Canada
• 22: Wen-Chi Hou , Gultekin Ozsoyoglu , Erdogan Dogdu, Error-constrained COUNT query evaluation in relational databases, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.278-287, May 29-31, 1991, Denver, Colorado, United States
• 23: Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Statistical estimators for relational algebra expressions, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.276-287, March 1988, Austin, Texas, United States [doi>10.1145/308386.308455]
• 24: Christos Gkantsidis , Milena Mihail , Amin Saberi, Random walks in peer-to-peer networks: algorithms and evaluation, Performance Evaluation, v.63 n.3, p.241-263, March 2006 [doi>10.1016/j.peva.2005.01.002]
• 25: Asad Awan , Ronaldo A. Ferreira , Suresh Jagannathan , Ananth Grama, Distributed Uniform Sampling in Unstructured Peer-to-Peer Networks, Proceedings of the 39th Annual Hawaii International Conference on System Sciences, p.223.3, January 04-07, 2006 [doi>10.1109/HICSS.2006.126]
• 26: Nikos Ntarmos , Peter Triantafillou , Gerhard Weikum, Counting at Large: Efficient Cardinality Estimation in Internet-Scale Data Networks, Proceedings of the 22nd International Conference on Data Engineering, p.40, April 03-07, 2006 [doi>10.1109/ICDE.2006.44]
• 27: L. Goodman. On the estimation of the number of classes in a population. Annals of Math. Stat., 20:572--579, 1949.
• 28: K. Burnham and W. Overton. Robust estimation of population size when capture probabilities vary among animals. Ecology, 60:927--936, 1979.
• 29: Shlosser A. On estimation of the size of the dictionary of a long text on the basis of a sample. Engrg. Cybernetics, 19:97--102, 1981.
• 30: Zipf, G. E. Human Behavior and the Principle of Least Effort. Addison-Wesley Press, Inc., 1949.
• 31: Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider, Practical selectivity estimation through adaptive sampling, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.1-11, May 23-26, 1990, Atlantic City, New Jersey, United States
• 32: Peter J. Haas , Arun N. Swami, Sequential sampling procedures for query size estimation, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.341-350, June 02-05, 1992, San Diego, California, United States
• 33: Ming Zhong , Kai Shen, Random walk based node sampling in self-organizing networks, ACM SIGOPS Operating Systems Review, v.40 n.3, July 2006 [doi>10.1145/1151374.1151386]
• 34: Le Fessant, F., Handurukande, S., Kermarrec, A.-M., and Massoulié, L. Clustering in Peer-to-Peer File Sharing Workloads. 3rd Intl. Workshop on Peer-to-Peer Systems IPTPS 2004
• 35: Brian Babcock , Surajit Chaudhuri , Gautam Das, Dynamic sample selection for approximate query processing, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872822]
• 36: Surajit Chaudhuri , Gautam Das , Mayur Datar , Rajeev Motwani , Vivek R. Narasayya, Overcoming Limitations of Sampling for Aggregation Queries, Proceedings of the 17th International Conference on Data Engineering, p.534-542, April 02-06, 2001

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Experimentation, Performance, Reliability

Keywords:
assistive healthcare, peer-to-peer networks