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.
Type de document :
Communication dans un congrès
SPIRE 2018 - International Symposium on String Processing and Information Retrieval, Oct 2018, Lima, Peru. 11147, pp.74-87, 2018, Lecture Notes in Computer Science. 〈10.1007/978-3-030-00479-8_7〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01964719
Contributeur : Marie-France Sagot <>
Soumis le : dimanche 23 décembre 2018 - 12:55:03
Dernière modification le : lundi 21 janvier 2019 - 10:42:11

Lien texte intégral

Identifiants

Collections

Citation

Philip Bille, Mikko Berggreen Ettienne, Roberto Grossi, Inge Li Gørtz, Eva Rotenberg. Compressed Communication Complexity of Longest Common Prefixes. SPIRE 2018 - International Symposium on String Processing and Information Retrieval, Oct 2018, Lima, Peru. 11147, pp.74-87, 2018, Lecture Notes in Computer Science. 〈10.1007/978-3-030-00479-8_7〉. 〈hal-01964719〉

Partager

Métriques

Consultations de la notice

10