Ziv Bar-Yossef

Publications

Disclaimer: In all instances below, the publishers own the copyright. A copy is made available here only for personal, non-commercial use. Please see the published version for more details on who owns the copyright and what restrictions apply. In many cases, the papers below are substantial extensions of the corresponding conference versions.

 

· Most recent

· Web

· Database

· Algorithms

· Complexity

· Other

· Theses

In reverse chronological order:

 

· Context-sensitive Query Auto-Completion

with Naama Kraus.

WWW 2011

[proceedings version]

 

· Estimating the ImpressionRank of Web Pages

with Maxim Gurevich.

WWW 2009

[proceedings version]

 

 

· Mining Search Engine Query Logs via Suggestion Sampling

with Maxim Gurevich.

VLDB 2008

[proceedings version]

 

 

· Local Approximation of PageRank and Reverse PageRank

with Li-Tal Mashiach.

CIKM 2008, SIGIR 2008 (Poster).

[full version] [proceedings version] [poster version]

 

 

· The Space Complexity of Processing XML Twig Queries over Indexed Documents

with Mirit Shalem.

ICDE 2008.

[full version] [proceedings version]

 

 

· Efficient Search Engine Measurements

with Maxim Gurevich.

WWW 2007.

[full version] [proceedings version] [slides]

    

 

· Do not Crawl in the DUST: Different URLs with Similar Text

with Idit Keidar and Uri Schonfeld.

TWEB (to appear), WWW 2007, WWW 2006 (Poster).

     [journal version] [proceedings version] [poster version] [slides]

 

 

· Cluster Ranking with an Application to Mining Mailbox Networks.

with Ido Guy, Ronny Lempel, Yoelle S. Maarek, and Vladimir Soroka.

KAIS Journal 2008.

ICDM 2006. Honorable mention for best application paper award.

[journal version] [proceedings version] [slides]

 

 

· Index Coding with Side Information

with Yitzhak (Tsahi) Birk, T. S. Jayram, and Tomer Kol.

FOCS 2006

[full version] [proceedings version]

 

 

· Random Sampling from a Search Engine’s Index

with Maxim Gurevich.

JACM 2008, WWW 2006. Best paper award.

     [journal version]  [proceedings version] [slides]

 

 

· RaWMS - Random Walk based Lightweight Membership Service for Wireless Ad Hoc Networks

with Roy Friedman and Gabriel Kliot.

TOCS 2008, MOBIHOC 2006

     [journal version] [proceedings version]

 

 

· Buffering in Query Evaluation over XML Streams

with Marcus Fontoura and Vanja Josifovski.

PODS 2005

     [proceedings version]  [slides]

 

 

· Focused Sampling: Computing Topical Web Statistics

with Tapas Kanungo and Robert Krauthgamer.

Technical Report, IBM TJ Watson Research Center RJ 10339, 2005.

     [report version]

 

 

· Approximating Edit Distance Efficiently 

     with T.S. Jayram, Robert Krauthgamer, and Ravi Kumar.

     FOCS 2004

     [proceedings version]  [slides]

 

 

· The Sketching Complexity of Pattern Matching  

     with T.S. Jayram, Robert Krauthgamer, and Ravi Kumar.

     RANDOM 2004

     [proceedings version]

 

 

· On the Memory Requirements of Evaluating XPath Queries over XML Streams 

     with Marcus Fontoura and Vanja Josifovski.

     JCSS 2007, PODS 2004

     [journal version]  [proceedings version]  [slides]

 

 

· Sic Transit Gloria Telae: Towards an Understanding of the Web's Decay 

     with Andrei Broder, Ravi Kumar, and Andrew Tomkins.

     WWW 2004

     [proceedings version]

 

 

· Exponential Separation of Quantum and Classical One-Way Communication Complexity

     with T.S. Jayram and Iordanis Kerenidis.

     SICOMP 2008, STOC 2004.

     [journal version]  [proceedings version]

 

 

· Sampling Lower Bounds via Information Theory

     STOC 2003

     [full version]  [proceedings version]  [slides]

 

 

· Information Statistics Approach to Data Stream and Communication Complexity

     with T.S. Jayram, Ravi Kumar, and D. Sivakumar.

     JCSS 2004, FOCS 2002.

     [journal version]  [proceedings version]  [slides]

 

 

· Counting Distinct Elements in a Data Stream

     with T.S. Jayram, Ravi Kumar, D. Sivakumar, and L. Trevisan.

     RANDOM 2002

     [proceedings version]

 

 

· Template Detection via Data Mining and its Applications

     with Sridhar Rajagopalan.

     WWW 2002

     [proceedings version]  [slides]

 

 

· Information Theory Methods in Communication Complexity

     with T.S. Jayram, Ravi Kumar, and D. Sivakumar.

     CCC 2002

     [full version]  [proceedings version]

 

 

· Streaming Computation of Combinatorial Objects

     with Omer Reingold, Ronen Shaltiel, and Luca Trevisan

     CCC 2002

     [full version]  [proceedings version]  [slides]

 

 

· Reductions in Streaming Algorithms, with an Application to Counting Triangles in Graphs

     with Ravi Kumar, and D. Sivakumar.

     SODA 2002

     [full version]  [proceedings version]  [slides]

 

 

· Incentive-Compatible Online Auctions for Digital Goods

     with Kris Hildrum, and Felix Wu.

     SODA 2002

     [proceedings version]

 

 

· Sampling Algorithms: Lower Bounds and Applications

     with Ravi Kumar, and D. Sivakumar.

     STOC 2001

     [full version]  [proceedings version]  [slides]

 

 

· Approximating Aggregate Queries about Web Pages via Random Walks

     with  Alexander Berg, Steve Chien, Jittat Fakcharoenphol, and Dror Weitz.

     VLDB 2000

     [proceedings version]  [slides]

 

 

· Deterministic Amplification of Space Bounded Probabilistic Algorithms

     with Oded Goldreich and Avi Wigderson.

     CCC 1999

     [proceedings version]  [slides]

 

 

· Querying Semantically Tagged Documents on the World-Wide Web

     with Yaron Kanza, Yakov Kogan, Werner Nutt, and Yehoshua Sagiv.

     NGITS 1999

     [proceedings version]

 

 

· Pointer Jumping Requires Concurrent Read

     with Noam Nisan.

     STOC 1997

     [full version]