IBM®
Skip to main content
    United States [change]    Terms of use
  
 
 
    Home    Products    Services & solutions    Support & downloads    My account    
IBM Research

(none)

Activity Report


This is the non-confidential version of the report.

  Activity Report, July - December 2005
clear image

Highlights

 OLAP Over Uncertain and Imprecise Data
The OLAP paradigm, which is very useful in analyzing structured/unstructured information in large-scale business applications, does not provide support for uncertainty and imprecision in the data. Doug Burdick, Prasad M. Deshpande, T.S. Jayram, Raghu Ramakrishnan and Shivakumar Vaithyanathan addressed two significant challenges in this context: (a) the uncertainty associated with measures derived from text and (b) the imprecision associated with dimension attributes. Two key requirements were postulated for any OLAP-based solution to this problem: (i) the answers must be consistent at different levels of the dimension hierarchy, and (ii) the answers must be faithful to the underlying input data. These requirements were formalized and an allocation-based framework was proposed to satisfy consistency and faithfulness. A key aspect is the identification of correlation-preserving criteria that guides the choice of appropriate allocation policies. The resulting solution can be mapped to an extended database that generalizes the standard star schema used in OLAP. Efficient algorithms that operate on the extended database were designed for standard aggregation operators of OLAP; the complexity analysis showed that they are comparable to those used in conventional OLAP. A paper describing these results was presented at the 31st International Conference on Very Large Databases (VLDB 2005).

Scalable Leader Election
One of the challenges in designing peer-to-peer systems is robustness to various failures, especially when the number of peers is extremely large. Although peer-to-peer systems have been well-studied, there has been relatively little formal work on robust scalable systems. Valerie King, Jared Saia, Vishal Sanwalani and Erik Vee address this issue by designing a new leader election protocol in which the total communication for each is only polylogarithmic in the number of participants. The protocol is designed to sustain nodes that behave adversarially (up to 1/3 of the nodes). A paper describing these results was accepted to the Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006).

Improved Lower Bounds for Embeddings into L_1
In recent years, low distortion embeddings of finite metric spaces into L_1 have become a powerful tool in an algorithm designer's arsenal. Such embeddings are extremely useful in different contexts, such as Combinatorial Optimization and Data Analysis. Robert Krauthgamer and Yuval Rabani (Technion) simplifies and improved upon recent lower bounds on the minimum distortion of embedding certain finite metric spaces into L_1. In particular, they show that for n-point metric spaces of negative type that require a distortion of Omega(loglog n) for such an embedding, implying the same lower bound on the integrality gap of a well-known semidefinite programming relaxation for the Sparsest-Cut problem. This result builds upon and improves the recent lower bound of Khot and Vishnoi [STOC 2005]. A second result simplifies and improves a very recent lower bound of Khot and Naor [FOCS 2005] and shows that embedding into L_1 the Edit Distance on length m strings requires a distortion of Omega(log m). A paper describing these results was accepted to the Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006).

Awards and Honors

 R. Fagin, P. Kolaitis, L. Popa, and W.-C. Tan (UC Santa Cruz) won a 2004 IBM Pat Goldberg Memorial Best Paper Award for the paper "Composing schema mappings: Second-order dependencies to the rescue", which appeared in the Proceedings of the 2004 PODS conference.

R. Fagin, P. G. Kolaitis, and L. Popa, earned a 2005 Research Division Accomplishment for Science, titled "Foundations of Schema Mappings", December 2005.

P. G. Kolaitis, elected ACM Fellow in December 2005 for contributions to logic in computer science.

R. Krauthgamer and Uriel Feige (Microsoft Research and Weizmann Institute), were awarded a SIAM Outstanding Paper Prize for the paper "A polylogarithmic approximation of the minimum bisection", July 2005.

R. Krauthgamer, 1st Plateau Invention Achievement Award, October 2005.

N. Megiddo, 13th Plateau Invention Achievement Award, July 2005.

Publications and Conferences

M. Ajtai. A Non-linear Time Lower Bound for Boolean Branching Programs. Theory of Computing (ToC), Vol. 1 (2005), pp. 149-176.

L. E. Bertossi, J. Chomicki, P. Godfrey, P. G. Kolaitis, A. Thomo, C. Zuzarte. Exchange, integration, and consistency of data: Report on the ARISE/NISR Workshop, SIGMOD Record, 34(7), 2005, pp. 87-90.

J. Chuzhoy, S. Guha, E. Halperin, S. Khanna, G. Kortsarz, R. Krauthgamer, and J. Naor. Asymmetric k-center is log*n-hard to Approximate. Journal of the ACM (JACM), 52(4):538-551, 2005.

A. Durand, M. Hermann, P. G. Kolaitis. "Subtractive reductions and complete problems for counting complexity classes". Theoretical Computer Science (TCS), 340, 2005, pp. 496-513.

R. Fagin, P. Kolaitis, R. Kumar, J. Novak, D. Sivakumar, and A. Tomkins. Efficient Implementation of Large-Scale Multi-Structural Databases, In Proc. of the 31st Very Large Data Bases Conference (VLDB '05), pp. 958-969.

D. de Farias and N. Megiddo, Combining Expert Advice in Reactive Environments, EU PASCAL Workshop on Principled methods of trading exploration and exploitation, July 2005, London, U.K.

K. Jain, A. Mehta, K. Talwar, V. Vazirani. A Simple Characterization for Truth-Revealing Single-Item Auctions. In Proc. 1st Workshop on Internet and Network Economics (WINE 2005), December 2005.

S. Kapoor, A. Mehta, V. Vazirani. An Auction-Based Market Equilibrium Algorithm for a Production Model. In Proc. 1st Workshop on Internet and Network Economics (WINE 2005), December 2005.

S. Khot, R. Lipton, E. Markakis, A. Mehta. Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions. In Proc. 1st Workshop on Internet and Network Economics (WINE 2005), December 2005.

M. Kolountzakis, E. Markakis, A. Mehta. The Spectrum of Symmetric Boolean Functions (Learning Symmetric k-Juntas in time n^{o(k)}). In Proc. of Workshop on Interface Between Harmonic Analysis and Number Theory, Marseille, October 2005.

R. Krauthgamer, J. R. Lee, M. Mendel and A. Naor. Measured descent: A new embedding method for finite metrics. Geometric and Functional Analysis (GAFA), 15(4):839-858, 2005.

V. Markl, N. Megiddo, M. Kutsch, T.M. Tran, P. Haas, and U. Srivastava, Consistently Estimating the Selectivity of Conjuncts of Predicates. In Proc. of the 31st International Conference on Very Large Databases (VLDB 2005).

N. Megiddo, Y. Xu, and B. Zhu, (Eds.), Algorithmic Applications in Management, First International Conference, AAIM 2005. Xian, China, June 22-25, Proceedings Springer 2005.

A. Mehta, A. Saberi, U. Vazirani, V. Vazirani. Adwords and Generalized Online Matching. In Proc. of the 46th IEEE Symposium on the Foundations of Computer Science (FOCS 2005), Oct 2005.

Patents

R. Fagin, J. B. Lotspiech, N. Megiddo, D. Naor, S. Naor, Method for assigning encryption keys, Issued as Patent 6947563 in US, 9/20/2005.

J. L. Hellerstein, J. S. Thathachar and I. Rish., Method and system for recognizing end-user transactions, Issued as Patent 6925452 in US, 8/2/2005.

K. McCurley and N. Megiddo, Efficient retrieval of uniform resource locators, Issued as Patent 6957224 in US, 10/18/2005.

N. Megiddo and D. Modha, Method and program product for maintaining security of publicly distributed information, Issued as Patent 6947557 in US, 9/20/2005.

Invited Talks

  • M. Ajtai
    "The role of lattices in complexity theory and cryptography",
    Bay Area Theory Symposium (BATS), Stanford, Palo Alto, CA, November 2005.
  • R. Fagin
    "Optimal aggregation algorithms for middleware"
    Shannon Lecture, Stanford, 10/20/05, organized by the IEEE Computer Society of Santa Clara Valley.
  • P. Kolaitis
    "Constraint Satisfaction, Complexity, and Logic"
    Invited Tutorial, Logic Colloquium 2005, Association for Symbolic Logic European Summer Meeting, Athens, Greece, August 2005.
    "Inductive Definability and Finite-Variable Logics: From Logic to Computer Science"
    Invited Talk, Fifth Panhellenic Logic Symposium (PLS 2005), Athens, Greece, July 2005.

Presentations and Seminars
  • R. Krauthgamer
    "On L_1-embeddings of the edit distance"
    UC Berkeley, August 2005.
    "Approximating Edit Distance Efficiently",
    UC Bekeley, Berkeley, CA, September 2005.
    "Improved Integrality Ratio for Sparsest-Cut"
    INFORMS Annual Meeting (sponsored session), November 2005.
  • A. Mehta
    "Adwords and Generalized Online Matching"
    Theory Seminar, University of Wisconsin, Madison, August 2005.
    Theory Seminar, UC Santa Cruz, December 2005.

Committee Work
  • N. Megiddo
    Invited sole organizer of the Workshop on Game Theory and Computer Science, The Game Theory Center, SUNY, Stony Brook, July 2005.
    Program Committee member, Workshop on Internet & Network Economics(WINE 2005), Hong Kong, December 2005.

Editorships

External Positions

Personnel

 Short-Term Visitors
  • Yuval Rabani (Oct 10-Oct 21, 2005)

Organization
  • Phokion Kolaitis (Senior Manager) CS Principles and Methodologies
  • David Gibson (On Leave at the Content & Knowledge Management Department
  • Sridhar Rajagopalan (On Leave at the Content & Management Department)
  • Ron Fagin, Manager, Foundations of Computer Science
  • Miki Ajtai
  • T. S. Jayram
  • Robert Krauthgamer
  • Nimrod Megiddo
  • Aranyak Mehta
  • Erik Vee

Transitions (in chronological order)
  • David Gibson and Sridhar Rajagopalan are on leave to work in the Content and Knowledge Management Department at ARC.
  • Ravi Kumar moved to Yahoo! Research Labs in July 2005.
  • D. Sivakumar moved to Google in July 2005.
  • Jasmine Novak moved to Yahoo! Research Labs in August 2005.
  • Aranyak Mehta, a graduate of Georgia Institute of Technology, joined the department as a postdoc in September 2005.
  • Rene Henthorn left the department in December 2005, transferring to the Almaden HR department as an administrative assistant to Kenneth Daney.

    About IBM    Privacy    Contact