BISC: BISC Seminar, April 19, 2001: Ron Fagin

From: masoud nikravesh (nikraves@eecs.berkeley.edu)
Date: Sat Apr 21 2001 - 15:17:58 MET DST

  • Next message: H. Mark Hubey: "ICCIT2001"

    *********************************************************************
    Berkeley Initiative in Soft Computing (BISC)
    *********************************************************************

    Optimal Aggregation Algorithms for Middleware

    BISC Seminar
    Ron Fagin
    Manager of the Foundations of Computer Science Group
    IBM, Almaden Research Center

    Thursday, 19 April 2001
    380 Soda Hall
    4:00-5:15 pm

    Abstract:

    Assume that each object in a database has m grades, or scores, one for
    each of m attributes. For example, an object can have a color grade,
    that tells how red it is,
    and a shape grade, that tells how round it is. The objects are given in
    m sorted lists (where the ith list is sorted according to the ith
    attribute). Our goal is to find the
    top k objects according to a monotone aggregation function, while
    minimizing access to the lists. The problem arises in several contexts.
    In particular, the speaker
    originally considered it for the purpose of combining fuzzy information
    in a multimedia database system.

    We define a very strong notion of optimality, which we call "instance
    optimality". An algorithm is instance optimal if, up to a constant
    factor, its performance is as
    good as every other (correct) algorithm. We give an elegant and
    remarkably simple algorithm that is instance optimal for our problem
    (under some natural
    restrictions).

    This research, which is joint with Amnon Lotem and Moni Naor, won the
    Best Paper Award for the 2001 ACM Symposium on Principles on Database
    Systems.
    The talk will be completely self-contained.

    Biography of speaker:
    Ronald Fagin is manager of the Foundations of Computer Science group at
    the IBM Almaden Research Center in San Jose, California. He received his
    B.A. degree
    in mathematics from Dartmouth College in 1967 and his Ph.D. in
    mathematics, with his thesis in finite model theory, from the University
    of California at Berkeley in
    1973. Much of his research has focused on applications of logic to
    computer science. He has published around 100 papers, and has coauthored
    a book on
    "Reasoning about Knowledge". He is a Fellow of the Institute of
    Electrical and Electronic Engineers, and a Fellow of the Association for
    Computing Machinery.

    --------------------------------------------------------------------
    If you ever want to remove yourself from this mailing list,
    you can send mail to <Majordomo@EECS.Berkeley.EDU> with the following
    command in the body of your email message:
    unsubscribe bisc-group
    or from another account,
    unsubscribe bisc-group <your_email_adress>

    ############################################################################
    This message was posted through the fuzzy mailing list.
    (1) To subscribe to this mailing list, send a message body of
    "SUB FUZZY-MAIL myFirstName mySurname" to listproc@dbai.tuwien.ac.at
    (2) To unsubscribe from this mailing list, send a message body of
    "UNSUB FUZZY-MAIL" or "UNSUB FUZZY-MAIL yoursubscription@email.address.com"
    to listproc@dbai.tuwien.ac.at
    (3) To reach the human who maintains the list, send mail to
    fuzzy-owner@dbai.tuwien.ac.at
    (4) WWW access and other information on Fuzzy Sets and Logic see
    http://www.dbai.tuwien.ac.at/ftp/mlowner/fuzzy-mail.info
    (5) WWW archive: http://www.dbai.tuwien.ac.at/marchives/fuzzy-mail/index.html



    This archive was generated by hypermail 2b30 : Sat Apr 21 2001 - 15:22:14 MET DST