Optimized union of non-disjoint distributed data sets

ABSTRACT

In a variety of applications, ranging from data integration to distributed query evaluation, there is a need to obtain sets of data items from several sources (peers) and compute their union. As these sets often contain common data items, avoiding the transmission of redundant information is essential for effective union computation. In this paper we define the notion of optimal union plans for non-disjoint data sets residing on distinct peers, and present efficient algorithms for computing and executing such optimal plans.

Our algorithms avoid redundant data transmission and optimally exploit the network bandwidth capabilities. A challenge in the design of optimal plans is the lack of a complete map of the distribution of the data items among peers. We analyze the information required for optimal planning and propose novel techniques to obtain compact, cheap to communicate, description of the data sources. We then exploit it for efficient union computation with reasonable accuracy. We demonstrate experimentally the superiority of our approach over the common naive union computation, showing it improves the performance by an order of magnitude.

REFERENCES

• 1: ADSL - Asymmetric Digital Subscriber Line. http://en.wikipedia.org/wiki/Adsl.
• 2: S. Abiteboul, I. Manolescu, N. Polyzotis, N. Preda, and C. Sun. Xml processing in dht networks. In ICDE '08, 2008.
• 3: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 4: Philip A. Bernstein , Nathan Goodman , Eugene Wong , Christopher L. Reeve , James B. Rothnie, Jr., Query processing in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.6 n.4, p.602-625, Dec. 1981 [doi>10.1145/319628.319650]
• 5: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 6: A. Broder and M. Mitzenmacher. Network applications of bloom filters: A survey. Internet Mathematics, 1(4):485--509, 2004.
• 7: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.327-336, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276781]
• 8: J. Byers, J. Considine, and M. Mitzenmacher. Fast approximate reconciliation of set differences. Technical report, 2002. Boston University Computer Science Tech. Rep. 2002--019.
• 9: John Byers , Jeffrey Considine , Michael Mitzenmacher , Stanislav Rost, Informed content delivery across adaptive overlay networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 10: Zhiyuan Chen , Nick Koudas , Flip Korn , S. Muthukrishnan, Selectively estimation for Boolean queries, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.216-225, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335225]
• 11: B. Cohen. Incentives build robustness in bittorrent. In Proc. Workshop on the Economics of Peer-to-Peer Systems, 2003.
• 12: Edith Cohen , Haim Kaplan, Summarizing data using bottom-k sketches, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281133]
• 13: Fan Deng , Davood Rafiei, Approximately detecting duplicates for streaming data using stable bloom filters, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142477]
• 14: The Piazza Peer Data Management System, IEEE Transactions on Knowledge and Data Engineering, v.16 n.7, p.787-798, July 2004 [doi>10.1109/TKDE.2004.1318562]
• 15: Ryan Huebsch , Minos Garofalakis , Joseph M. Hellerstein , Ion Stoica, Sharing aggregate computation for distributed queries, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247535]
• 16: Yuh-Jzer Joung , Chien-Tse Fang , Li-Wei Yang, Keyword Search in DHT-Based Peer-to-Peer Networks, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.339-348, June 06-10, 2005 [doi>10.1109/ICDCS.2005.44]
• 17: Donald Kossmann, The state of the art in distributed query processing, ACM Computing Surveys (CSUR), v.32 n.4, p.422-469, Dec. 2000 [doi>10.1145/371578.371598]
• 18: Lothar F. Mackert , Guy M. Lohman, R* Optimizer Validation and Performance Evaluation for Distributed Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.149-159, August 25-28, 1986
• 19: Amit Manjhi , Vladislav Shkapenyuk , Kedar Dhamdhere , Christopher Olston, Finding (Recently) Frequent Items in Distributed Data Streams, Proceedings of the 21st International Conference on Data Engineering, p.767-778, April 05-08, 2005 [doi>10.1109/ICDE.2005.68]
• 20: Petar Maymounkov , David Mazières, Kademlia: A Peer-to-Peer Information System Based on the XOR Metric, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.53-65, March 07-08, 2002
• 21: Sebastian Michel , Peter Triantafillou , Gerhard Weikum, KLEE: a framework for distributed top-k query algorithms, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 22: Tova Milo , Tal Zur , Elad Verbin, Boosting topic-based publish-subscribe systems with dynamic clustering, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247563]
• 23: Y. Minsky and A. Trachtenberg. Practical set reconciliation. Technical report, 2002. Dept. Elec. Comput. Eng., Boston Univ., Boston, MA, Tech. Rep. BU-ECE-2002-01.
• 24: Y. Minsky, A. Trachtenberg, and R. Zippel. Set reconciliation with nearly optimal communication complexity. In Proc. International Symposium on Information Theory, 2001.
• 25: Yannis Papakonstantinou , Serge Abiteboul , Hector Garcia-Molina, Object Fusion in Mediator Systems, Proceedings of the 22th International Conference on Very Large Data Bases, p.413-424, September 03-06, 1996
• 26: A. Sedeno-Noda, D. Alcaide, and C. Gonzalez-Martin. Network flow approaches to pre-emptive open-shop scheduling problems with time-windows. European Journal of Operational Research, 174(3):1501--1518, 2006.
• 27: G. Sivek, S. Sivek, J. Wolfe, and M. Zhivich. Webtorrent: a bittorrent extension for high availability servers. http://pdos.csail.mit.edu/6.824-2004/reports/jwolfe.pdf.
• 28: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 29: Nesime Tatbul , Uǧur Çetintemel , Stan Zdonik, Staying FIT: efficient load shedding techniques for distributed stream processing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 30: Aris Tsois , Timos Sellis, The generalized pre-grouping transformation: aggregate-query optimization in the presence of dependencies, Proceedings of the 29th international conference on Very large data bases, p.644-655, September 09-12, 2003, Berlin, Germany
• 31: Chuan Wu , Baochun Li, Optimal peer selection for minimum-delay peer-to-peer streaming with rateless codes, Proceedings of the ACM workshop on Advances in peer-to-peer multimedia streaming, November 11-11, 2005, Hilton, Singapore [doi>10.1145/1099384.1099394]
• 32: R. Xu and I. Wunsch. Survey of clustering algorithms. IEEE Transactions on Neural Networks, 16(3):645--678, 2005.
• 33: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]