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

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, streaming algorithms, approximate query processing

• Efficient control flow profiling using hardware counters, (with B. Litvin, M. Sagiv, O. Etzion, S. Goldenberg), 2005.
• Improved implementation of the max-error optimized wavelet synopses, (with D. Urieli), TR-TAU, 2005.
• Optimal wavelet synopses for range-sum queries, (with D. Urieli), TR-TAU, July, 2004.
• Optimal workload-based wavelet synopses, (with D. Urieli), TR-TAU, 2004. ICDT'05.
• 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.
• The List-Traversal Synopsis (LTS) system, (with M. Furman, E. Porat ). TR-TAU, 2004.
• Efficient pebbling for list traversal synopses (with E. Porat), ICALP'03. Full version.
• Workload-based Wavelet Synopses (with L. Portman), TR-TAU, 2003.
• τ-Synopses: a system for run-time management of remote synopses (with L. Portman), Software Demo, ICDE'04 & 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.
• Approximate iceberg queries (with E. Segal).
• Efficient bundle sorting (with E. Segal and J.S. Vitter), SODA 2000.
• 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), To appear in DIMACS Series in Discrete Mathematics and Theoretical Computer Science. A two-page synopsis will also appear in SODA'99.
• Wavelet-based histograms for selectivity estimation (with J.S. Vitter and M. Wang), SIGMOD'98. [1.64M; also compressed, 424K and gzip'ed, 295K].
• 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. (gzipped). Journal version to appear in TODS (pdf).
• 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 STOC'96 Special Issue.

Parallel computation: models, algorithms, 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 to appear 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 to appear 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 to appear 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 appeared 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.
• 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.)
• Scheduling space-sharing for internet advertising (with M. Adler and P.B. Gibbons), Journal of Scheduling, to appear.
• Shuffling Biological Sequences [1.56M; also compressed, 520K and gzip'ed, 316K] (with D. Kandel, R. Unger and P. Winkler), Discrete Applied Mathematics, special issue on Computational Molecular Biology, 1997.
  
  
• [See also relevant papers in the other sections]

• Dynamic generation of discrete random variates (with J.S. Vitter and W.C. Ni), Bell Labs TR 1997 (preliminary version in SODA'93).

Internet privacy and spam control

• Consistent yet anonymous Web access with LPWA [1.13M; also compressed, 143K and gzip'ed, 91K] (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) [2.27M; also compressed, 194K and gzip'ed, 126K] (with D.M. Kristol, E. Gabber, P.B. Gibbons, and A. Mayer).
• 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 [1.82M; also compressed, 179K and gzip'ed, 109K] (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, (D. Mulligan et al.), Center for Democracy and Technology, July 1998.
• P3P Guiding Principles, (L.F. Cranor et al.), W3C Note NOTE-P3P10-principles-19980721, Part of the Platform for Privacy Preferences Project, July 1998.

Miscellaneous

• 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.

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.