Campus Event Calendar
Event Entry
What and Who
Counting at Large (Efficient Scalable Counting in Internet-Scale Data Networks)
Peter Triantafillou
University of Patras
Informatik-Kolloquium
AG 1, AG 2, AG 3, AG 4, AG 5
Expert Audience
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 8 July 2005
16:00
-- Not specified --
45 - FR 6.2
HS 001
Saarbrücken
Abstract
The realization of the next-generation killer applications largely
depends on our ability to build the foundations for the efficient
deployment and access of internet-scale infomation systems. Frequently,
counting in general, and estimating the cardinality of (multi)sets in
particular, is highly desirable for a large variety of applications.
Examples of such applications include optimizing query access plans,
ensuring robustness and high availability of data and services, and
evaluating the significance of various data items with respect to an
information need. The key constraints that any acceptable solution must
satisfy are the following: (i) scalability: millions of nodes may need
to add elements to a (multi)set, which dictates that a large number of
nodes need help with the counting chores; (ii) efficiency, which
seemingly contradicts the scalability goal: the number of nodes that
need be contacted for counting purposes must be small in order to enjoy
small latency and bandwidth requirements; (iii) access and storage load
balancing: counting and related overhead chores should be distributed
fairly to the nodes of the network; (iv) tunable, robust (in the
presence of dynamics and failures) and highly accurate estimation of the
cardinality; (v) simplicity and ease of integration: special,
solution-specific indexing structures should be avoided. In this talk,
first our efforts towards creating a highly-distributed, scalable,
efficient (multi)set-cardinality counter will be presented.
Subsequently, we will show how to use our solution to build and maintain
histograms which have been a basic foundational block for query
optimization for centralized DBs, facilitating their porting into the
realm of internet-scale data networks.
depends on our ability to build the foundations for the efficient
deployment and access of internet-scale infomation systems. Frequently,
counting in general, and estimating the cardinality of (multi)sets in
particular, is highly desirable for a large variety of applications.
Examples of such applications include optimizing query access plans,
ensuring robustness and high availability of data and services, and
evaluating the significance of various data items with respect to an
information need. The key constraints that any acceptable solution must
satisfy are the following: (i) scalability: millions of nodes may need
to add elements to a (multi)set, which dictates that a large number of
nodes need help with the counting chores; (ii) efficiency, which
seemingly contradicts the scalability goal: the number of nodes that
need be contacted for counting purposes must be small in order to enjoy
small latency and bandwidth requirements; (iii) access and storage load
balancing: counting and related overhead chores should be distributed
fairly to the nodes of the network; (iv) tunable, robust (in the
presence of dynamics and failures) and highly accurate estimation of the
cardinality; (v) simplicity and ease of integration: special,
solution-specific indexing structures should be avoided. In this talk,
first our efforts towards creating a highly-distributed, scalable,
efficient (multi)set-cardinality counter will be presented.
Subsequently, we will show how to use our solution to build and maintain
histograms which have been a basic foundational block for query
optimization for centralized DBs, facilitating their porting into the
realm of internet-scale data networks.
Contact
Gerhard Weikum
500
--email hidden
passcode not visible
logged in users only
Petra Schaaf, 06/06/2005 12:55 -- Created document.