Algorithms for massive data sets
Parallel computation
Data compression, data structures and algorithms
Internet privacy and spam control
Miscellaneous
Systems and software demos

Please see copyright notice below.

See my publication list for full citations of these papers, and for a listing of papers prior to 1996.

Algorithms for massive data sets: synopsis data structures, data synopses, data streams, approximate query processing, streaming data analysis

• Calibration and profile based synopses error estimation and synopses reconciliation (with Y. Matia), ICDE, 2007.
• Trends in High Performance Analytics, SIGMOD'06.
• LTS: The List Traversal Synopsis System, (with M. Furman, and E. Porat), Software Demo, NGITS'06.
• τ-xSynopses - a system for run-time management of XML synopses, (with N. Drukh, Y. Matia, and L. Portman), Software Demo, NGITS'06.
• Data streams and data synopses for massive data sets (invited talk), ECML-PKDD, 2005
• Synopses reconciliation via calibration in the τ-synopses system (with Y. Matia and L. Portman), Software Demo, EDBT'06.
• The design and architecture of the τ-synopses system (with N. Drukh and L. Portman), Industrial & Application, EDBT'06.
• Efficient control flow profiling using hardware counters (with B. Litvin, M. Sagiv, O. Etzion, S. Goldenberg), 2005.
• On the optimality of the greedy heuristic in wavelet synopses for range queries (with D. Urieli), TR-TAU, 2005.
• Improved implementation of the max-error optimized wavelet synopses (with D. Urieli), TR-TAU, 2005.
• Optimal workload-based wavelet synopses (with D. Urieli), ICDT'05. Full version, Theoretical Computer Science, Special issue for ICDT'05.
• τ-xSynopses - a system for run-time management of XML synopses (with N. Drukh and L. Portman), TR-TAU, 2005.
• The design and architecture of the τ-synopses system (with N. Drukh and L. Portman), TR-TAU, 2004.
• Fractional xSketch synopses for XML databases, (with N. Drukh, M. Garofalakis, N. Polyzotis), XSym'04.
• Adaptive probing and communication in sensor networks (with I. Ragoler and N. Aviram). AdHoc Now'04.
• Spectral Bloom Filters (with S. Cohen), SIGMOD'03. Full version in TR-TAU, 2003.
• The list-traversal synopsis (LTS) system - implementation, animation, and program rollback support (with M. Furman, E. Porat ). TR-TAU, 2004 (revised, 2006).
• Efficient pebbling for list traversal synopses with application to program rollback (with E. Porat), ICALP'03. Full version.
• Workload-based wavelet synopses (with L. Portman), TR-TAU, 2003 (revised, 2005).
• τ-Synopses: a system for run-time management of remote synopses (with L. Portman), Software Demo, EDBT'04. Also, Software Demo in ICDE'04.
• Online subpath profiling (with D. Oren and M. Sagiv), CC2002.
• Wavelet-based histograms for selectivity estimation: a systematic study (with C. Barillon and M. Wang), TR-TAU, 2001.
• Placing search in context: the concept revisited (with L. Finkelstein, E. Gabrilovich, E. Rivlin, Z. Solan, G. Wolfman, and E. Ruppin), WWW10. Full version in TOIS.
• Dynamic maintenance of wavelet-based Histograms (with J. Vitter and M. Wang), VLDB 2000.
• Efficient bundle sorting (with E. Segal and J.S. Vitter), SODA 2000. Full version
• Tracking join and self-join sizes in limited storage (with N. Alon, P.B. Gibbons, and M. Szegedy), PODS'99. Full version in JCSS (2002), special issue for PODS'99.
• Synopsis data structures for massive data sets (with P.B. Gibbons), External Memory Algorithms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, 1999. A two-page synopsis in SODA'99.
• Approximate iceberg queries (with E. Segal), TR-TAU, 1998.
• Wavelet-based histograms for selectivity estimation (with J.S. Vitter and M. Wang), SIGMOD'98.
• New Sampling-based summary statistics for improving approximate query answers (with P.B. Gibbons). SIGMOD'98.
• AQUA: System and techniques for approximate query answering (with S. Acharya, Y. Bartal, P.B. Gibbons, S. Muthukrishnan, V. Poosala, S. Ramaswamy and T. Suel), Bell Labs TR 1998.
• The AQUA project white paper (with P.B. Gibbons and V. Poosala), Bell Labs TR 1997.
• Fast incremental maintenance of approximate histograms (with P.B. Gibbons and V. Poosala), VLDB'97. Journal version in TODS.
• Modeling skewed distributions using multifractals and the '80-20 law' (with C. Faloutsos and A. Silberschatz), VLDB'96.
• Bifocal sampling for skew-resistant join size estimation (with S. Ganguly, P.B. Gibbons and A. Silberschatz), SIGMOD'96.
• Performance evaluation of approximate priority queues (with S.C. Sahinalp and N.E. Young), DIMACS Implementation Challenge, Oct 1996. (This is a followup to Approximate data structures with applications.)
• The space complexity of approximating the frequency moments (with N. Alon and M. Szegedy), STOC'96. Full version in JCSS, special issue for STOC'96. [Gödel prize citation]

Parallel computation: parallel models, parallel algorithms, parallel scheduling

• Modeling and optimizing I/O throughput of multiple disks on a bus (with R. Barve, E. Shriver, P.B. Gibbons, B. Hillyer, and J.S. Vitter). SIGMETRICS'99. See also a short abstract presented at SIGMETRICS'98.
• Round-like behavior in multiple disks on a bus (with R. Barve, P.B. Gibbons, B.K. Hillyer, E. Shriver, and J.S. Vitter). IOPADS'99.
• Parallel algorithms column: On the search for suitable models, SIGACT News, Sept. '97.
• Space-efficient scheduling of parallelism with synchronization Variables (with G.E. Blelloch, P.B. Gibbons and G.J. Narlikar), SPAA'97.
• Can a shared-memory model serve as a bridging model for parallel computation? (with P.B. Gibbons and V. Ramachandran), SPAA'97. Full version in Theory of Computing Systems, special issue on SPAA'97.
• Modeling parallel bandwidth: local vs. global restrictions (with M. Adler, P.B. Gibbons and V. Ramachandran), SPAA'97. Full version in Algorithmica, special issue on coarse grained parallel algorithms
• The Queue-Read Queue-Write Asynchronous PRAM Model (with P.B. Gibbons and V. Ramachandran), Euro-Par'96. Full version in special issue of TCS.

• Provably Efficient Scheduling for Languages with Fine-Grained Parallelism (with G.E. Blelloch and P.B. Gibbons), JACM(1998) (preliminary version in SPAA'95).
• The Queue-Read Queue-Write PRAM model: Accounting for contention in parallel algorithms (with P.B. Gibbons and V. Ramachandran), SICOMP(1997) (preliminary version in SODA'94). [SIAM page]
• Efficient low-contention parallel algorithms (with P.B. Gibbons and V. Ramachandran), JCSS(1996) (preliminary version in SPAA'94).
• Fast, efficient mutual and self simulations for shared memory and reconfigurable mesh (with A. Schuster), Parallel Algorithms and Applications, special issue on Algorithms for Enhanced Mesh Architectures, 8:195-221, 1996 (preliminary version in SPDP'95).
• An effective load balancing policy for geometric decaying algorithms (with J. Gil), Journal of Parallel and Distributed Computing, 36(2):185-188, August 1996.
• Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs (with O. Berkman and P.L. Ragde), Journal of Algorithms, 23(2) (August 1998) pp. 197-215. (preliminary version in WADS'93).
• An Optical simulation of shared memory (with L.A. Goldberg and S. Rao), SICOMP(1997) (preliminary version in SPAA'94).
• Simple fast parallel hashing by oblivious execution (with J. Gil), SICOMP(1997) (preliminary version in SODA'91+ICALP'94). [SIAM page]
• Accounting for memory bank contention and delay in high-bandwidth multiprocessors (with G.E. Blelloch, P.B. Gibbons and M. Zagha), IEEE-TPDS(1997) (preliminary version in SPAA'95).

Data compression, data structures and algorithms

• Delayed dictionary compression for packet networks, (with R. Refua), INFOCOM'05.
• Improved compression latency trade-off through delayed-dictionary compression, (with R. Refua), Software Demo, INFOCOM'05.
• Context-based Space Filling Curves (with R. Dafner and D. Cohen-Or), Eurographics2000.
• On the Temporal HZY Compression Scheme (with Z. Cohen, S. Muthukrishnan, S.C. Sahinalp and J. Ziv), SODA'00.
• The effect of flexible parsing for dynamic dictionary based data compression (with N. Rajpoot and S.C. Sahinalp), Data Compression Conference (DCC), 1999.
• On the optimality of parsing in dynamic dictionary based data compression (with S.C. Sahinalp). A two-page summary in SODA'99.
• Implementation and experimental evaluation of flexible parsing for dynamic dictionary based data compression (with N. Rajpoot and S.C. Sahinalp), Second Workshop on Algorithm Engineering (WAE), August, 1998.
• Augmenting suffix trees with applications (with S. Muthukrishnan, S.C. Sahinalp and J. Ziv), Sixth Annual European Symposium on Algorithms (ESA), August, 1998.
• The FKS perfect hashing scheme, TAU Data Structures lecture notes, 1997.
• Performance evaluation of approximate priority queues (with S.C. Sahinalp and N.E. Young), DIMACS Implementation Challenge, Oct 1996. (This is a followup to Approximate data structures with applications.)
  
  
• [See also relevant papers in the other sections]

• Dynamic generation of discrete random variates (with J.S. Vitter and W.C. Ni), TOCS 36(4) (2003) 329-358 (preliminary version in SODA'93).

Internet privacy and spam control

• Consistent yet anonymous Web access with LPWA (with E. Gabber, P.B. Gibbons, D.M. Kristol, and A. Mayer), Communication of the ACM, special section on Internet Privacy, February 1999.
• On Secure and pseudonymous client-relationships with multiple servers (with E. Gabber, P.B. Gibbons, D.M. Kristol and A. Mayer), ACM TISSEC.
• Design and implementation of the Lucent Personalized Web Assistant (LPWA) (with D.M. Kristol, E. Gabber, P.B. Gibbons, and A. Mayer), Bell Labs TR 1998.
• Curbing junk e-mail via secure classification (with E. Gabber, M. Jakobsson, and A. Mayer), Financial Cryptography, 1998.
• How to make personalized web browsing simple, secure, and anonymous (with E. Gabber, P.B. Gibbons and A. Mayer), Financial Cryptography '97.
• On Secure and pseudonymous client-relationships with multiple servers (with D. Bleichenbacher, E. Gabber, P.B. Gibbons and A. Mayer), Proceedings of 3rd USENIX Workshop on Electronic Commerce, August/September, 1998.
• Lightweight security primitives for e-commerce (with A. Mayer and A. Silberschatz), Proceedings USENIX Symposium on Internet Technologies and Systems 1997.
• SPAM: Report to the Federal Trade Commission of the Ad-Hoc Working Group on Unsolicited Commercial Email, (with D. Mulligan et al.), Center for Democracy and Technology, July 1998.
• P3P Guiding Principles, (with L.F. Cranor et al.), W3C Note NOTE-P3P10-principles-19980721, Part of the Platform for Privacy Preferences Project, July 1998.

Miscellaneous

• Shuffling Biological Sequences (with D. Kandel, R. Unger and P. Winkler), Discrete Applied Mathematics, special issue on Computational Molecular Biology, 1997.
• Scheduling space-sharing for internet advertising (with M. Adler and P.B. Gibbons), Journal of Scheduling.
• Frequency-spatial transformation: a proposal for parsimonious intra-cortical communication (with R. Levi, E. Ruppin, and J. Reggia), International Journal of Neural Systems, 7(5): 591-598, 1996.

Systems and software demos

• LTS: The List Traversal Synopsis System, (with M. Furman, and E. Porat), Software Demo, NGITS'06.
• τ-xSynopses - a system for run-time management of XML synopses, (with N. Drukh, Y. Matia, and L. Portman), Software Demo, NGITS'06.
• Synopses reconciliation via calibration in the τ-synopses system (with Y. Matia and L. Portman), Software Demo, EDBT'06.
• The design and architecture of the τ-synopses system (with N. Drukh and L. Portman), Industrial & Application, EDBT'06.
• Improved compression latency trade-off through delayed-dictionary compression, (with R. Refua), Software Demo, INFOCOM'05.
• τ-Synopses - a system for run-time management of XML synopses (with N. Drukh and L. Portman), TR-TAU, 2005.
• The design and architecture of the τ-synopses system (with N. Drukh and L. Portman), TR-TAU, 2004.
• τ-Synopses: a system for run-time management of remote synopses (with L. Portman), Software Demo, EDBT'04. Also, Software Demo in ICDE'04.
• The list-traversal synopsis (LTS) system (with M. Furman, E. Porat ). TR-TAU, 2004.
• Design and implementation of the Lucent Personalized Web Assistant (LPWA) (with D.M. Kristol, E. Gabber, P.B. Gibbons, and A. Mayer), Bell Labs TR 1998
• AQUA: System and techniques for approximate query answering (with S. Acharya, Y. Bartal, P.B. Gibbons, S. Muthukrishnan, V. Poosala, S. Ramaswamy and T. Suel), Bell Labs TR 1998.
• The AQUA project white paper (with P.B. Gibbons and V. Poosala), Bell Labs TR 1997.

Copyright Notice: Since most of these papers are published, the copyright has been transferred to the respective publishing houses. Therefore, the papers cannot be duplicated for commercial purposes. The following is ACM's copyright notice. The other publishers have similar ones.

Copyright © 199x by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.