TRAPP Project

Tradeoff in Replication Precision and Performance


Stanford University Database Group



About the TRAPP Project

The TRAPP team is investigating techniques for trading off precision for performance in replicated data environments. There are fundamental limits on the performance of replicated data environments when exact consistency and exact pr ecision are necessary. However, performance gains can often be achieved if precision requirements can be relaxed. In practice, unbounded imprecision is often introduced in order to achieve better performance. The goal of the TRAPP project is to investigat e techniques to permit controlled and explicit relaxation of data precision in exchange for improved performance.

Our past work focused on an approximate data caching architecture that permits fine-grained control of the precision-performance tradeoff for numerical data in data caching environments. We are currently working on applying these techniques and oth ers to more complex data such as Web pages.

For a more detailed description of our work and a more complete discussion of our plans for future work, please see our papers.

People

  • Chris Olston
  • Jennifer Widom
  • Brian Babcock
  • Tomas Feder
  • Yu-Shan Fung
  • Keith Ito
  • Jing Jiang
  • Boon Thau Loo
  • Rajeev Motwani
  • Liadan O'Callaghan
  • Rina Panigrahy

    Demos

    Click     HERE for a Java demonstration of our best-effort cache synchronization algorithm.
    Click HERE for a Java demonstration of our adaptive precision setting algorithm.

    Our Papers

    C. Olston, J. Jiang, and J. Widom.     Adaptive Filters for Continuous Queries over Distributed Data Streams. To appear:SIGMOD 2003.

    B. Babcock and C. Olston. Distributed Top-K Monitoring. To appear:SIGMOD 2003.

    C. Olston and J. Widom. Best-Effort Cache Synchronization with Source Cooperation. ACM SIGMOD 2002 International Conference on Management of Data, Madison, Wisconsin, June 2002, pp. 73 -84.

    C. Olston, B. T. Loo and J. Widom. Adaptive Precision Setting for Cached Approximate Values. ACM SIGMOD 2001 International Conference on Management of Data, Santa Barbara , California, May 2001, pp. 355-366.

    C. Olston and J. Widom. Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data. Twenty-Sixth International Conference on Very Large Data Bases (VLDB 2 000), Cairo, Egypt, September 2000, pp. 144-155.

    T. Feder, R. Motwani, L. O'Callaghan, C. Olston and R. Panigrahy. Computing Shortest Paths with Uncertainty. To appear: Twentieth International Symposium on Theoretical Aspects of Computer Science (STACS), February 2003.

    T. Feder, R. Motwani, R. Panigrahy, C. Olston and J. Widom. Computing the Median with Uncertainty. 32nd ACM Symposium on Theory of Computing (STOC 2000), Portland, Oregon, May 2000. Also to appear in: SIAM Journal on Computing.

    Other Papers based on TRAPP

    S. Khanna and W. Tan. On Computing Functions with Uncertainty. PODS 2001. University of Pennsylvania: [Abstract], [PS.GZ] , [PDF].