Yossi Matias - Publication List

For copies of recent papers listed below, see Recent Papers.

    Refereed Conference Papers

  1. A Video Scrambling Technique Based on Space Filling Curves, Y. Matias and A. Shamir, Proceedings of Advances in Cryptology-CRYPTO'87, Springer LNCS 293, Santa Barbara, CA, August 1987, pp. 398-417.
  2. Simple and efficient election algorithms for anonymous networks Y. Afek and Y. Matias, Proceedings of the Third International Workshop on Distributed Algorithms (WDAG), Springer LNCS 392, pp. 183-194, Nice, France, September 1989.
  3. On Parallel Hashing and Integer Sorting, Y. Matias and U. Vishkin, Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP), Springer LNCS 443, Warwick, England, July 1990, pp. 729--743.
  4. Fast Hashing on a PRAM - Designing by Expectation, J. Gil and Y. Matias, Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, CA, January 1991, pp. 271-280.
  5. Converting High Probability into Nearly-Constant Time - with Applications to Parallel Hashing, Y. Matias and U. Vishkin, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC), New Orleans, LA, May 1991, pp. 307-316.
  6. Towards a Theory of Nearly Constant Time Parallel Algorithms, J. Gil, Y. Matias and U. Vishkin, Proceedings of the 32nd IEEE Annual Symposium on Foundation of Computer Science (FOCS), San Juan, Puerto Rico, October 1991, pp. 698-710.
  7. A Simple Randomized Sieve Algorithm for the Closest-Pair Problem, S. Khuller and Y. Matias, Proceedings of the Third Canadian Conference on Computational Geometry (CCCG), Vancouver, Canada (August 1991), pp. 34-37.
  8. Efficient Randomized Dictionary-Matching Algorithms, A. Amir, M. Farach and Y. Matias, Proceedings of the Third Symposium on Combinatorial Pattern Matching (CPM), Tucson, AZ, April 1992, pp. 259-272.
  9. Leaders election without a conflict resolution rule---fast and efficient randomized simulations among CRCW PRAMs, J. Gil and Y. Matias, Proceedings of the First Latin American Informatics Symposium, Springer LNCS 583, Sao Paulo, Brazil (April 1992), pp. 204-218.
  10. A Neural Model for a Randomized Frequency-Spatial Transformation, Y. Matias and E. Ruppin, Computation and Neural Systems, F. H. Eeckman and J. M. Bower (editors), Kluwer Academic, 1993, pp. 449-454, A collection from papers presented in the First Annual Computation and Neural Systems Meeting, San Francisco, CA (July, 1992).
  11. Polynomial Hash Functions Are Reliable, M. Dietzfelbinger, J. Gil, Y. Matias and N. Pippenger, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, Springer LNCS 623 (ICALP), Vienna, Austria, July 1992, pp. 235-246.
  12. Randomized Range-Maxima in Nearly-Constant Parallel Time, O. Berkman, Y. Matias and U. Vishkin, Proceedings of the Third Annual International Symposium on Algorithms and Computation, Nagoya, Japan (December 1992), pp. 135-144.
  13. Dynamic Generation of Discrete Random Variates, Y. Matias, J.S. Vitter and W.C. Ni, Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Austin, TX, January 1993, pp. 361-370.
  14. Approximate Parallel Prefix Computation and Its Applications, M. T. Goodrich, Y. Matias and U. Vishkin, Proceedings of the Seventh International Parallel Processing Symposium (IPPS), Newport Beach, CA, April 1993, pp. 318-325.
  15. Triply-Logarithmic Upper and Lower Bounds for Minimum, Range Minima, and Related Problems with Integer Inputs (WADS), O. Berkman, Y. Matias and P.L. Ragde, Proceedings of the Workshop on Algorithms and Data Structures, Montreal, Canada, August 1993, pp. 175-187.
  16. Semi-Dynamic Closest-Pair Algorithms, Y. Matias, Proceedings of the Fifth Canadian Conference on Computational Geometry (CCCG), Waterloo, Canada, August 1993, pp. 264-271.
  17. Approximate Data Structures with Applications, Y. Matias, J.S. Vitter and N.E. Young, Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington, Virginia, January 1994, pp. 187-194.
  18. Optimal Parallel Approximation Algorithms for Prefix Sums and Integer Sorting, M. T. Goodrich, Y. Matias and U. Vishkin, Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington, Virginia, January 1994, pp. 241-250.
  19. The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms, P.B. Gibbons, Y. Matias and V. Ramachandran, Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington, VA, January 1994, pp. 638-648.
  20. An Optical Simulation of Shared Memory, L. A. Goldberg, Y. Matias and S. Rao, Proceedings of the Sixth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), Cape May, New Jersey, June 1994, pp. 257-267.
  21. Efficient Low-Contention Parallel Algorithms, P.B. Gibbons, Y. Matias and V. Ramachandran, Proceedings of the 6th ACM Symposium on Parallel Algorithms and Architectures (SPAA), Cape May, NJ, June 1994, pp. 236-247.
  22. Simple Fast Parallel Hashing (ICALP), J. Gil and Y. Matias, Proceedings of the 21st International Colloquium on Automata, Languages and Programming, Springer LNCS 820, Jerusalem, Israel, July 1994, pp. 239-250.
  23. On the power of randomization for the Common PRAM, O. Berkman, P.B. Gibbons and Y. Matias, Proceedings of the third Israel Symposium on Theory of Computing and Systems (ISTCS), Tel Aviv, Israel, January, 1995, pp. 229-240.
  24. Fast Parallel Algorithms for Minimum and Related Problems with Small Integer Inputs, O. Berkman and Y. Matias, Proceedings of the Ninth International Parallel Processing Symposium (IPPS), Santa Barbara, CA, April 1995, pp. 203-207.
  25. A Note on Reducing Parallel Model Simulations to Integer Sorting, Y. Matias and U. Vishkin, Proceedings of the Ninth International Parallel Processing Symposium (IPPS), Santa Barbara, CA, April 1995, pp. 208-212.
  26. Fast, Efficient Mutual and Self Simulations for Shared Memory and Reconfigurable Mesh, Y. Matias and A. Schuster, Proceedings of the Seventh IEEE Symposium on Parallel and Distributed Processing (SPDP), pp. 239-246, San Antonio, TX, October 1995.
  27. Provably Efficient Scheduling for Languages with Fine-Grained Parallelism, G.E. Blelloch, P.B. Gibbons and Y. Matias, Proceedings of the 7th ACM Symposium on Parallel Algorithms and Architectures (SPAA), Santa Barbara, CA, July 1995, pp. 1-12.
  28. Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors, G.E. Blelloch, P.B. Gibbons, Y. Matias and M. Zagha, Proceedings of the 7th ACM Symposium on Parallel Algorithms and Architectures (SPAA), Santa Barbara, CA, July 1995, pp. 84-94.
  29. The Space Complexity of Approximating the Frequency Moments, N. Alon, Y. Matias and M. Szegedy, Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), pp. 20-29, May, 1996.
  30. Bifocal Sampling for Skew-Resistant Join Size Estimation, S. Ganguly, P.B. Gibbons, Y. Matias and A. Silberschatz, Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data (SIGMOD), Montreal, Canada, June 1996, pp. 271-281.
  31. Modeling Skewed Distributions using Multifractals and the `80-20 Law', C. Faloutsos, Y. Matias and A. Silberschatz, Proceedings of the 22nd International Conference on Very Large Databases (VLDB), Mumbai, India, September, 1996.
  32. The Queue-Read Queue-Write Asynchronous PRAM Model, P.B. Gibbons, Y. Matias and V. Ramachandran, Proceedings of the 2nd International Euro-Par Conference, Lyon, France, August 1996, Vol. II, pp. 279-292, Lecture Notes in Computer Science, Vol. 1124, Springer, Berlin.
  33. How to Make Personalized Web Browsing Simple, Secure, and Anonymous, E. Gabber, P.B. Gibbons, Y. Matias and A. Mayer, Lecture Notes in Computer Science, Proceedings of Financial Cryptography '97 (FC), Anguilla, February 1997.
  34. Can A Shared-Memory Model Serve as a Bridging Model for Parallel Computation?, P.B. Gibbons, Y. Matias and V. Ramachandran, Proceedings of the 9th ACM Symposium on Parallel Algorithms and Architectures (SPAA), Newport, RI, June 1997, pp. 72-83.
  35. Modeling Parallel Bandwidth: Local vs. Global Restrictions, M. Adler, P.B. Gibbons, Y. Matias and V. Ramachandran, Proceedings of the 9th ACM Symposium on Parallel Algorithms and Architectures (SPAA), Newport, RI, June 1997, pp. 94-105.
  36. Space-Efficient Scheduling of Parallelism with Synchronization Variables, G.E. Blelloch, P.B. Gibbons, Y. Matias and G. J. Narlikar, Proceedings of the 9th ACM Symposium on Parallel Algorithms and Architectures (SPAA), Newport, RI, June 1997, pp. 12-23.
  37. Fast Incremental Maintenance of Approximate Histograms, P.B. Gibbons, Y. Matias and V. Poosala, Proceedings of the 23rd International Conference on Very Large Databases (VLDB), Athens, Greece, August 1997, pp. 466-475.
  38. Lightweight Security Primitives for E-Commerce, Y. Matias, A. Mayer and A. Silberschatz, USENIX Symposium on Internet Technologies and Systems, December 1997, 95-102.
  39. Curbing Junk E-Mail via Secure Classification, E. Gabber, M. Jakobsson, Y. Matias, and A. Mayer, Financial Cryptography, February 1998, 198-213.
  40. New Sampling-based summary statistics for improving approximate query answers, P.B. Gibbons and Y. Matias, SIGMOD'98.
  41. Wavelet-Based Histograms for Selectivity Estimation, Y. Matias, J.S. Vitter, and M. Wang, SIGMOD'98.
  42. On Secure and Pseudonymous Client-Relationships with Multiple Servers, D. Bleichenbacher, E. Gabber, P.B. Gibbons, Y. Matias and A. Mayer, 3rd USENIX Workshop on Electronic Commerce, August/September 1998, pp. 99-108.
  43. Augmenting suffix trees with applications, Y. Matias, S. Muthukrishnan, S.C. Sahinalp and J. Ziv, Sixth Annual European Symposium on Algorithms (ESA), August, 1998, pp. 67-78.
  44. The effect of flexible parsing for dynamic dictionary based data compression, Y. Matias, N. Rajpoot and S.C. Sahinalp, Data Compression Conference (DCC), March 1999.
  45. Round-like behavior in multiple disks on a bus. R. Barve, P.B. Gibbons, B.K. Hillyer, Y. Matias, E. Shriver, and J.S. Vitter. Sixth Workshop on I/O in Parallel and Distributed Systems (IOPADS), May, 1999.
  46. Modeling and optimizing I/O throughput of multiple disks on a bus. R. Barve, E. Shriver, P.B. Gibbons, B.K. Hillyer, Y. Matias, and J.S. Vitter. 1999 ACM Conference on the Measurement and Modeling of Computer Systems (SIGMETRICS), May 1999.
  47. Tracking join and self-join sizes in limited storage. N. Alon, P.B. Gibbons, Y. Matias, and M. Szegedy. Eighteenth ACM Symposium on Principles of Database Systems (PODS), May 1999.
  48. Efficient bundle sorting. Y. Matias, E. Segal and J.S. Vitter. Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2000.
  49. Context-based Space Filling Curves. R. Dafner, D. Cohen-Or, and Y. Matias. Eurographics 2000
  50. Dynamic maintenance of wavelet-based Histograms. Y. Matias, J. Vitter, and M. Wang. The 26th International Conference on Very Large Databases (VLDB), 2000.
  51. Placing search in context: the concept revisited. L. Finkelstein, E. Gabrilovich, Y. Matias, E. Rivlin, Z. Solan, G. Wolfman, E. Ruppin, The Tenth International World Wide Web Conference (WWW10), 406-414, May 2001.
  52. Online subpath profiling. D. Oren, Y. Matias, M. Sagiv. International Conference on Compiler Construction (CC2002), 78-94, April 2002.
  53. Spectral Bloom Filters. S. Cohen, Y. Matias. SIGMOD'03.
  54. Efficient pebbling for list traversal synopses. Y. Matias, E. Porat. ICALP'03.
  55. Adaptive probing and communication in sensor networks. I. Ragoler, Y. Matias, N. Aviram. The 3rd International Conference on Ad-Hoc Networks & Wireless (AdHoc-Now}, July 2004.
  56. Fractional xSketch synopses for XML databases, N. Drukh, M. Garofalakis, Y. Matias, N. Polyzotis. The Second International XML Database Symposium , (SXym 2004).
  57. Optimal workload-based weighted wavelet synopses, Y. Matias, D. Urieli. Tenth International Conference Database Theory, (ICDT 2005).
  58. Delayed dictionary compression for packet networks, Y. Matias, R. Refua. IEEE INFOCOM 2005.

    Journal Papers

  1. Elections in anonymous networks, Y. Afek and Y. Matias, Information and Computation, 113:2 (September 1994), pp. 113-330.
  2. On Parallel Hashing and Integer Sorting, Y. Matias and U. Vishkin, Journal of Algorithms, 12:4 (December 1991), pp. 573-606.
  3. Fast and Efficient Simulations among CRCW PRAMs, J. Gil and Y. Matias, Journal of Parallel and Distributed Computing, 23:2 (November 1994), pp. 135-148.
  4. Randomized Range-Maxima in Nearly-Constant Parallel Time, O. Berkman, Y. Matias and U. Vishkin, Computational Complexity, 2 (1992), pp. 350-373.
  5. Triply-Logarithmic Upper and Lower Bounds for Minimum, Range Minima, and Related Problems with Integer Inputs, O. Berkman, Y. Matias and P.L. Ragde, Journal of Algorithms, 28(2) (August 1998) pp. 197-215.
  6. Designing Algorithms by Expectations, J. Gil and Y. Matias, Information Processing Letters, 51:1 (July 1994), pp. 31-34.
  7. An Optical Simulation of Shared Memory, L. A. Goldberg, Y. Matias and S. Rao, SIAM J. Computing, to appear.
  8. A Simple Randomized Sieve Algorithm for the Closest-Pair Problem, S. Khuller and Y. Matias, Information and Computation, 118:1 (April 1995), pp. 34-37.
  9. Fast Parallel Algorithms for Minimum and Related Problems with Small Integer Inputs, O. Berkman and Y. Matias, Parallel Processing Letters, 5(2):223-230, 1995.
  10. Fast, Efficient Mutual and Self Simulations for Shared Memory and Reconfigurable Mesh, Y. Matias and A. Schuster, Parallel Algorithms and Applications, special issue on Algorithms for Enhanced Mesh Architectures, 8:195-221, 1996.
  11. An Effective Load Balancing Policy for Geometric Decaying Algorithms, J. Gil and Y. Matias, Journal of Parallel and Distributed Computing, 36(2):185-188, August 1996.
  12. Frequency-Spatial Transformation: A Proposal for Parsimonious Intra-Cortical Communication, R. Levi, E. Ruppin, Y. Matias and J. Reggia, International Journal of Neural Systems, 7(5): 591-598, 1996.
  13. Shuffling Biological Sequences, D. Kandel, Y. Matias, R. Unger and P. Winkler, Discrete Applied Mathematics, special issue on Computational Molecular Biology, 71: (1-3) 171-185, Dec. 5 1996.
  14. Simple Fast Parallel Hashing by Oblivious Execution, J. Gil and Y. Matias, SIAM Journal on Computing, 27(5):1348-1375, 1998.
  15. Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors, G.E. Blelloch, P.B. Gibbons, Y. Matias and M. Zagha, IEEE Transactions on Parallel and Distributed Systems, 8(9):943-958, September 1997.
  16. Efficient low-contention parallel algorithms, P.B. Gibbons, Y. Matias and V. Ramachandran, Journal of Computer and System Sciences, special issue devoted to select papers from SPAA '94, 53:3 (1996), pp. 417-442.
  17. The Queue-Read Queue-Write Asynchronous PRAM Model, P.B. Gibbons, Y. Matias and V. Ramachandran, Theoretical Computer Science, special issue devoted to select papers from Euro-Par '96, 196 (1998), pp. 3-29.
  18. The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms, P.B. Gibbons, Y. Matias and V. Ramachandran, SIAM Journal on Computing, 28(2): 733-769, 1998.
  19. Modeling parallel bandwidth: local vs. global restrictions, M. Adler, P.B. Gibbons, Y. Matias, V. Ramachandran, Algorithmica, special issue on Coarse Grained Parallel Algorithms, to appear.
  20. The Space Complexity of Approximating the Frequency Moments, N. Alon, Y. Matias and M. Szegedy, Journal of Computer and System Sciences, special issue of STOC'96, to appear.
  21. Provably Efficient Scheduling for Languages with Fine-Grained Parallelism, G.E. Blelloch, P.B. Gibbons and Y. Matias, Journal of the ACM, to appear.
  22. Can A Shared-Memory Model Serve as a Bridging Model for Parallel Computation?, P. B. Gibbons, Y. Matias and V. Ramachandran, Theory of Computing Systems, special issue devoted to select papers from SPAA '97, to appear.
  23. Synopsis Data Structures for Massive Data Sets, P. B. Gibbons and Y. Matias, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, special issue on external memory algorithms and visualization, to appear.
  24. Consistent yet anonymous Web access with LPWA, E. Gabber, P.B. Gibbons, D.M. Kristol, Y. Matias and A. Mayer, Communication of the ACM, special section on Internet Privacy, 42(2), pp. 42-47, February 1999.
  25. On secure and pseudonymous client relationships with multiple servers, E. Gabber, P.B. Gibbons, D.M. Kristol, Y. Matias, A. Mayer, ACM Transactions on Information and System Security, Volume 2, pp. 390-415, Issue 4 (1999)
  26. Scheduling Space-Sharing for Internet Advertising, M. Adler, P.B. Gibbons and Y. Matias, Journal of Scheduling, Vol 5, pp. 103-119, 2002.
  27. Implementation and experimental evaluation of flexible parsing for dynamic dictionary based data compression, Y. Matias, N. Rajpoot, S.C. Sahinalp, Journal on Experimental Algorithms (JEA), special issue of selected papers from WAE'98 (invited paper).
  28. Context-based Space Filling Curves, R. Dafner, D. Cohen-Or, Y. Matias, Computer Graphics Forum, 19(3), (2000) 209-217.
  29. Tracking join and self-join sizes in limited storage, N. Alon, P.B. Gibbons, Y. Matias, M. Szegedy, Journal of Computer and System Sciences (JCSS), special issue of selected papers from PODS'99, 64(3), (2002) 719-747 (invited paper).
  30. Placing search in context: the concept revisited, L. Finkelstein, E. Gabrilovich, Y. Matias, E. Rivlin, Z. Solan, G. Wolfman, E. Ruppin, ACM Transactions on Information Systems (TOIS), 20(1), (2002) 116-131 (invited paper)
  31. Fast Incremental Maintenance of Approximate Histograms, P.B. Gibbons, Y. Matias and V. Poosala, ACM Transactions on Database Systems (TODS), 27(3) (2002) 261-298.
  32. Dynamic generation of discrete random variates, Y. Matias, J.S. Vitter and W.-C. Ni, Theory of Computing Systems (TCS), 36(4) (2003) 329-374.

    Other Papers

  1. Workshop on Parallel Algorithms: From Solving Combinatorial Problems to Solving Grand Challenge Problems, J. Flanagan, Y. Matias and V.L. Ramachandran, Eds., November 1993, DIMACS Technical Report 93-90.
  2. A survey of query processing techniques with recommendations for the Teradata Database System, P.B. Gibbons, Y. Matias et al. (with Bell Labs-Teradata Working Group), AT&T Teradata Technical Report, 1995.
  3. Rolling a Dice with Varying Biases, Y. Matias, Manuscript, July 1992.
  4. Performance Evaluation of Approximate Priority Queues, Y. Matias, S.C. Sahinalp and N.E. Young, Presented at DIMACS Fifth Implementation Challenge: Priority Queues, Dictionaries, and Point Sets, organized by David Johnson and Cathy McGeoch, October, 1996.
  5. Optimal parsing for dictionary based data compression, Y. Matias and S.C. Sahinalp, Bell Laboratories technical report, Murray Hill, NJ, June 1997.
  6. Implementation and experimental evaluation of flexible parsing for dynamic dictionary based data compression, Y. Matias, N. Rajpoot and S.C. Sahinalp, 2nd Workshop on Algorithm Engineering (WAE), August, 1998.
  7. Parallel Algorithms Column: On the Search for Suitable Models, SIGACT News, 28(3):21-29, September 1997.
  8. Approximate Iceberg Queries. Y. Matias and E. Segal. Technical Report, Tel Aviv University, December 1998.
  9. AQUA Project White Paper, P.B. Gibbons, Y. Matias, V. Poosala, Technical Report, Bell Laboratories, Murray Hill, New Jersey, December 1997.
  10. AQUA: System and techniques for approximate query answering, P.B. Gibbons, V. Poosala, S. Acharya, Y. Bartal, Y. Matias, S. Muthukrishnan, S. Ramaswamy, T. Suel, Technical Report, Bell Laboratories, Murray Hill, New Jersey, February 1998.
  11. Implementation and experimental evaluation of flexible parsing for dynamic dictionary based data compression, Y. Matias, N. Rajpoot, S.C. Sahinalp, 2nd Workshop on Algorithm Engineering, (WAE), August, 1998. Invited to the JEA special issue of the workshop.
  12. Modeling and optimizing I/O throughput of multiple disks on a bus, R. Barve, E. Shriver, P.B. Gibbons, B. Hillyer, Y. Matias, J.S. Vitter, ACM Conference on the Measurement and Modeling of Computer Systems (SIGMETRICS), 264--265, 1998.
  13. Report to the Federal Trade Commission of the Ad-Hoc Working Group on Unsolicited Commercial Email, D. Mulligan et al. Center for Democracy and Technology, July 1998 (available at http://www.cdt.org/spam).
  14. P3P Guiding Principles, L.F. Cranor et al., W3C Note NOTE-P3P10-principles-19980721, Part of the Platform for Privacy Preferences Project, July 1998 (available at http://www.w3.org/TR/NOTE-P3P10-principles).
  15. Synopsis data structures for massive data sets (summary), P.B. Gibbons, Y. Matias, Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), S909-S910, January, 1999.
  16. On the optimality of parsing in dynamic dictionary based data compression (summary), Y. Matias, S.C. Sahinalp, Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), S943-S944, January, 1999.
  17. Selecting estimation procedures and bounds for approximate answering of aggregation queries, P.B. Gibbons, Y. Matias, Technical report, Bell Laboratories, Murray Hill, New Jersey, 1999.
  18. On the temporal HZY compression scheme (summary), Z. Cohen, Y. Matias, S. Muthukrishnan, S.C. Sahinalp, J. Ziv, Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), S185-S186, January, 2000.
  19. Workload-based wavelet synopses, Y. Matias, L. Portman. Technical Report, Tel Aviv University, 2003.
  20. τ-Synopses: a system for run-time management of remote synopses, Y. Matias, L. Portman. International conference on Extending Database Technology (EDBT), Software Demo, 865-867, March 2004.
  21. τ-Synopses: a system for run-time management of remote synopses, Y. Matias, L. Portman. International Conference on Data Engineering, (ICDE), Software Demo, 964-865, April 2004.
  22. Optimal Wavelet synopses for range-sum queries, Y. Matias, D. Urieli. Technical report, Tel Aviv University, February, 2004.

    Theses

  1. A Video Scrambling Technique Based on Space Filling Curves, Y. Matias, MSc Thesis, The Weizmann Institute of Science, Israel, 1987.
  2. Highly Parallel Randomized Algorithmics, Y. Matias, PhD Thesis, Tel Aviv University, Israel, 1992.

    Patents

  1. A video scrambling apparatus and method based on space filling curves, Y. Matias and A. Shamir, U.S. Patent 4,910,772 (1990).
  2. A video scrambling apparatus and method based on space filling curves, Y. Matias and A. Shamir, U.S. Patent 5,058,158 (1991).
  3. Method for implementing approximate data structures using operations on machine words, Y. Matias, J.S. Vitter and N.E. Young, U.S. Patent 5,519,840 (1996).
  4. Method for maintaining information in a database used to generate high biased histograms using a probability function, counter and threshold values, P.B. Gibbons, Y. Matias, and A. Witkowski, U.S. Patent 5,689,696 (1997).
  5. Method and apparatus for data compression and decompression, Y. Matias and S.C. Sahinalp, U.S. Patent 5,703,581 (1997).
  6. Method for skew resistant join size estimation, S. Ganguly, P.B. Gibbons, Y. Matias, and A. Silberschatz, U.S. Patent 5,721,896 (1998).
  7. Method for characterizing information in data sets using multifractals, C. Faloutsos, Y. Matias, and A. Silberschatz, U.S. Patent 5,758,338 (1998).
  8. Method and means for scheduling parallel processors, G.E. Blelloch, P.B. Gibbons, and Y. Matias, U.S. Patent 5,768,594 (1998).
  9. Incremental maintenance of an approximate histogram in a database system, P.B. Gibbons, Y. Matias, V. Poosala, and A. Witkowski, U.S. Patent 5,870,752 (1999).
  10. Method of accessing data using approximate data structures, Y. Matias, U.S. Patent 5,923,837 (1999).
  11. Apparatus and method for approximating frequency moments, N. Alon, Y. Matias, and M. Szegedy, U.S. Patent 5,950,185 (1999).
  12. System and method for providing anonymous personalized browsing by a proxy system in a network, E. Gabber, P.B. Gibbons, Y. Matias, A. Mayer, U.S. Patent 5,961,593 (1999).
  13. System and method for scheduling and controlling delivery of advertising in a communications network, M. Adler, P.B. Gibbons, Y. Matias, U.S. patent 6,009,409 (1999).
  14. Maintaining a random sample of a relation in a database in the presence of updates to the relation, P.B. Gibbons, Y. Matias, V. Poosala, U.S. patent 6,012,064 (1999).
  15. System and method for modeling and optimizing I/O throughput of multiple disks on a bus, R.D. Barve, P.B. Gibbons, B.K. Hillyer, Y. Matias, E. Shriver, J.S. Vitter, U.S. patent 6,260,108 (2001).
  16. Method of accessing data using approximate data structures by relaxing the operations that define same, Y. Matias, U.S. patent 6,269,363 (2001).
  17. System and method for modeling and optimizing I/O throughput of multiple disks on a bus, R.D. Barve, P.B. Gibbons, B.K. Hillyer, Y. Matias, E. Shriver, J.S. Vitter, U.S. patent 6,301,640 (2001).
  18. Methods and apparatus for scheduling parallel processors, G.E. Blelloch, P.B. Gibbons, Y. Matias, G.J. Narlikar, U.S. patent 6,434,590 (2002).
  19. Efficient bundle sorting, Y. Matias, E. Segal, U.S. patent 6,519,593 (2003).
  20. System and method for secure classification of electronic mail, E. Gabber, B.M. Jakobsson, Y. Matias, A.J. Mayer, U.S. patent 6,574,658 (2003).
  21. System and method for providing anonymous remailing and filtering of electronic mail, E. Gabber, P.B. Gibbons, D.M. Kristol, Y. Matias, A.J. Mayer, U.S. patent 6,591,291 (2003).
  22. Simplified secure shared key establishment and data delivery protocols for electronic commerce, Y. Matias, A.J. Mayer, A. Silberschatz, U.S. patent 6,681,017 (2004).


For copies of recent papers listed above, see Recent Papers.

Return to Yossi Matias home page

matias+www@math.tau.ac.il
Last updated December, 1998