Compressed Communication Complexity of Longest Common Prefixes

Philip Bille, Mikko Berggreen Ettienne, Roberto Grossi, Inge Li Gørtz, Eva Rotenberg

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

46 Downloads (Pure)

Abstract

We consider the communication complexity of fundamental longest common prefix $$({{\mathrm{\textsc {Lcp}}}})$$ problems. In the simplest version, two parties, Alice and Bob, each hold a string, A and B, and we want to determine the length of their longest common prefix $$\ell ={{\mathrm{\textsc {Lcp}}}}(A,B)$$ using as few rounds and bits of communication as possible. We show that if the longest common prefix of A and B is compressible, then we can significantly reduce the number of rounds compared to the optimal uncompressed protocol, while achieving the same (or fewer) bits of communication. Namely, if the longest common prefix has an LZ77 parse of z phrases, only $$O(\lg z)$$ rounds and $$O(\lg \ell )$$ total communication is necessary. We extend the result to the natural case when Bob holds a set of strings $$B_1, \ldots , B_k$$ , and the goal is to find the length of the maximal longest prefix shared by A and any of $$B_1, \ldots , B_k$$ . Here, we give a protocol with $$O(\log z)$$ rounds and $$O(\lg z \lg k + \lg \ell )$$ total communication. We present our result in the public-coin model of computation but by a standard technique our results generalize to the private-coin model. Furthermore, if we view the input strings as integers the problems are the greater-than problem and the predecessor problem.
Original languageEnglish
Title of host publicationString Processing and Information Retrieval
PublisherSpringer
Publication date2018
Pages74-87
ISBN (Print)9783030004798
DOIs
Publication statusPublished - 2018
Event25th International Symposium on String Processing and Information Retrieval - Lima, Peru
Duration: 9 Oct 201811 Oct 2018

Conference

Conference25th International Symposium on String Processing and Information Retrieval
CountryPeru
CityLima
Period09/10/201811/10/2018
SeriesLecture Notes in Computer Science
Volume11147
ISSN0302-9743

Keywords

  • Communication complexity
  • LZ77
  • Compression Upper bound
  • Output sensitive
  • Longest common prefix
  • Predecessor

Cite this

Bille, P., Berggreen Ettienne, M., Grossi, R., Gørtz, I. L., & Rotenberg, E. (2018). Compressed Communication Complexity of Longest Common Prefixes. In String Processing and Information Retrieval (pp. 74-87). Springer. Lecture Notes in Computer Science, Vol.. 11147 https://doi.org/10.1007/978-3-030-00479-8_7
Bille, Philip ; Berggreen Ettienne, Mikko ; Grossi, Roberto ; Gørtz, Inge Li ; Rotenberg, Eva. / Compressed Communication Complexity of Longest Common Prefixes. String Processing and Information Retrieval. Springer, 2018. pp. 74-87 (Lecture Notes in Computer Science, Vol. 11147).
@inproceedings{b0d1703939a1471b88d924a5c3ab75f6,
title = "Compressed Communication Complexity of Longest Common Prefixes",
abstract = "We consider the communication complexity of fundamental longest common prefix $$({{\mathrm{\textsc {Lcp}}}})$$ problems. In the simplest version, two parties, Alice and Bob, each hold a string, A and B, and we want to determine the length of their longest common prefix $$\ell ={{\mathrm{\textsc {Lcp}}}}(A,B)$$ using as few rounds and bits of communication as possible. We show that if the longest common prefix of A and B is compressible, then we can significantly reduce the number of rounds compared to the optimal uncompressed protocol, while achieving the same (or fewer) bits of communication. Namely, if the longest common prefix has an LZ77 parse of z phrases, only $$O(\lg z)$$ rounds and $$O(\lg \ell )$$ total communication is necessary. We extend the result to the natural case when Bob holds a set of strings $$B_1, \ldots , B_k$$ , and the goal is to find the length of the maximal longest prefix shared by A and any of $$B_1, \ldots , B_k$$ . Here, we give a protocol with $$O(\log z)$$ rounds and $$O(\lg z \lg k + \lg \ell )$$ total communication. We present our result in the public-coin model of computation but by a standard technique our results generalize to the private-coin model. Furthermore, if we view the input strings as integers the problems are the greater-than problem and the predecessor problem.",
keywords = "Communication complexity, LZ77, Compression Upper bound, Output sensitive , Longest common prefix, Predecessor",
author = "Philip Bille and {Berggreen Ettienne}, Mikko and Roberto Grossi and G{\o}rtz, {Inge Li} and Eva Rotenberg",
year = "2018",
doi = "10.1007/978-3-030-00479-8_7",
language = "English",
isbn = "9783030004798",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "74--87",
booktitle = "String Processing and Information Retrieval",

}

Bille, P, Berggreen Ettienne, M, Grossi, R, Gørtz, IL & Rotenberg, E 2018, Compressed Communication Complexity of Longest Common Prefixes. in String Processing and Information Retrieval. Springer, Lecture Notes in Computer Science, vol. 11147, pp. 74-87, 25th International Symposium on String Processing and Information Retrieval, Lima, Peru, 09/10/2018. https://doi.org/10.1007/978-3-030-00479-8_7

Compressed Communication Complexity of Longest Common Prefixes. / Bille, Philip; Berggreen Ettienne, Mikko; Grossi, Roberto; Gørtz, Inge Li; Rotenberg, Eva.

String Processing and Information Retrieval. Springer, 2018. p. 74-87 (Lecture Notes in Computer Science, Vol. 11147).

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

TY - GEN

T1 - Compressed Communication Complexity of Longest Common Prefixes

AU - Bille, Philip

AU - Berggreen Ettienne, Mikko

AU - Grossi, Roberto

AU - Gørtz, Inge Li

AU - Rotenberg, Eva

PY - 2018

Y1 - 2018

N2 - We consider the communication complexity of fundamental longest common prefix $$({{\mathrm{\textsc {Lcp}}}})$$ problems. In the simplest version, two parties, Alice and Bob, each hold a string, A and B, and we want to determine the length of their longest common prefix $$\ell ={{\mathrm{\textsc {Lcp}}}}(A,B)$$ using as few rounds and bits of communication as possible. We show that if the longest common prefix of A and B is compressible, then we can significantly reduce the number of rounds compared to the optimal uncompressed protocol, while achieving the same (or fewer) bits of communication. Namely, if the longest common prefix has an LZ77 parse of z phrases, only $$O(\lg z)$$ rounds and $$O(\lg \ell )$$ total communication is necessary. We extend the result to the natural case when Bob holds a set of strings $$B_1, \ldots , B_k$$ , and the goal is to find the length of the maximal longest prefix shared by A and any of $$B_1, \ldots , B_k$$ . Here, we give a protocol with $$O(\log z)$$ rounds and $$O(\lg z \lg k + \lg \ell )$$ total communication. We present our result in the public-coin model of computation but by a standard technique our results generalize to the private-coin model. Furthermore, if we view the input strings as integers the problems are the greater-than problem and the predecessor problem.

AB - We consider the communication complexity of fundamental longest common prefix $$({{\mathrm{\textsc {Lcp}}}})$$ problems. In the simplest version, two parties, Alice and Bob, each hold a string, A and B, and we want to determine the length of their longest common prefix $$\ell ={{\mathrm{\textsc {Lcp}}}}(A,B)$$ using as few rounds and bits of communication as possible. We show that if the longest common prefix of A and B is compressible, then we can significantly reduce the number of rounds compared to the optimal uncompressed protocol, while achieving the same (or fewer) bits of communication. Namely, if the longest common prefix has an LZ77 parse of z phrases, only $$O(\lg z)$$ rounds and $$O(\lg \ell )$$ total communication is necessary. We extend the result to the natural case when Bob holds a set of strings $$B_1, \ldots , B_k$$ , and the goal is to find the length of the maximal longest prefix shared by A and any of $$B_1, \ldots , B_k$$ . Here, we give a protocol with $$O(\log z)$$ rounds and $$O(\lg z \lg k + \lg \ell )$$ total communication. We present our result in the public-coin model of computation but by a standard technique our results generalize to the private-coin model. Furthermore, if we view the input strings as integers the problems are the greater-than problem and the predecessor problem.

KW - Communication complexity

KW - LZ77

KW - Compression Upper bound

KW - Output sensitive

KW - Longest common prefix

KW - Predecessor

U2 - 10.1007/978-3-030-00479-8_7

DO - 10.1007/978-3-030-00479-8_7

M3 - Article in proceedings

SN - 9783030004798

T3 - Lecture Notes in Computer Science

SP - 74

EP - 87

BT - String Processing and Information Retrieval

PB - Springer

ER -

Bille P, Berggreen Ettienne M, Grossi R, Gørtz IL, Rotenberg E. Compressed Communication Complexity of Longest Common Prefixes. In String Processing and Information Retrieval. Springer. 2018. p. 74-87. (Lecture Notes in Computer Science, Vol. 11147). https://doi.org/10.1007/978-3-030-00479-8_7