2020 [ nach oben ]

• 
  Fogel, Sharon; Averbuch-Elor, Hadar; Cohen, Sarel; Mazor, Shai; Litman, RoeeScrabbleGAN: Semi-Supervised Varying Length Handwritten Text Generation. Conference on Computer Vision and Pattern Recognition (CVPR) 2020: 4323-4332
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Optical character recognition (OCR) systems performance have improved significantly in the deep learning era. This is especially true for handwritten text recognition (HTR), where each author has a unique style, unlike printed text, where the variation is smaller by design. That said, deep learning based HTR is limited, as in every other task, by the number of training examples. Gathering data is a challenging and costly task, and even more so, the labeling task that follows, of which we focus here. One possible approach to reduce the burden of data annotation is semi-supervised learning. Semi supervised methods use, in addition to labeled data, some unlabeled samples to improve performance, compared to fully supervised ones. Consequently, such methods may adapt to unseen images during test time. We present ScrabbleGAN, a semi-supervised approach to synthesize handwritten text images that are versatile both in style and lexicon. ScrabbleGAN relies on a novel generative model which can generate images of words with an arbitrary length. We show how to operate our approach in a semi-supervised manner, enjoying the aforementioned benefits such as performance boost over state of the art supervised HTR. Furthermore, our generator can manipulate the resulting text style. This allows us to change, for instance, whether the text is cursive, or how thin is the pen stroke.
  @inproceedings{fogel2020scrabblegan, abstract = {Optical character recognition (OCR) systems performance have improved significantly in the deep learning era. This is especially true for handwritten text recognition (HTR), where each author has a unique style, unlike printed text, where the variation is smaller by design. That said, deep learning based HTR is limited, as in every other task, by the number of training examples. Gathering data is a challenging and costly task, and even more so, the labeling task that follows, of which we focus here. One possible approach to reduce the burden of data annotation is semi-supervised learning. Semi supervised methods use, in addition to labeled data, some unlabeled samples to improve performance, compared to fully supervised ones. Consequently, such methods may adapt to unseen images during test time. We present ScrabbleGAN, a semi-supervised approach to synthesize handwritten text images that are versatile both in style and lexicon. ScrabbleGAN relies on a novel generative model which can generate images of words with an arbitrary length. We show how to operate our approach in a semi-supervised manner, enjoying the aforementioned benefits such as performance boost over state of the art supervised HTR. Furthermore, our generator can manipulate the resulting text style. This allows us to change, for instance, whether the text is cursive, or how thin is the pen stroke.}, author = {Fogel, Sharon and Averbuch-Elor, Hadar and Cohen, Sarel and Mazor, Shai and Litman, Roee}, booktitle = {Conference on Computer Vision and Pattern Recognition (CVPR)}, keywords = {sarelcohen sys:relevantfor:ae shaimazor roeelitman cvpr sharonfogel hadaraverbuch-elor year2020}, pages = {4323-4332}, title = {ScrabbleGAN: Semi-Supervised Varying Length Handwritten Text Generation}, year = 2020 }
• 
  Chechik, Shiri; Cohen, SarelDistance sensitivity oracles with subcubic preprocessing time and fast query time. Symposium Theory of Computing (STOC) 2020: 1375-1388
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We present the first distance sensitivity oracle (DSO) with subcubic preprocessing time and poly-logarithmic query time for directed graphs with integer weights in the range \([−M,M]\). Weimann and Yuster [FOCS 10] presented a distance sensitivity oracle for a single vertex/edge failure with subcubic preprocessing time of \(\mathcal{O(Mn^\omega+1− \alpha})\) and subquadratic query time of \(\tilde{\mathcal{O(n^{1+\alpha})\), where \(\alpha\) is any parameter in \([0,1]\), \(n\) is the number of vertices, \(m\) is the number of edges, the \(\tilde{\mathcal{O(·)\) notation hides poly-logarithmic factors in \(n\) and \(\omega<2.373\) is the matrix multiplication exponent.Later, Grandoni and Vassilevska Williams [FOCS 12] substantially improved the query time to sublinear in \(n\). In particular, they presented a distance sensitivity oracle for a single vertex/edge failure with \(\tilde{\mathcal{O}}\)\( (Mn^\omega +1/2}\) \(+ Mn^\omega+\alpha(4−\omega)})\) preprocessing time and \(\tilde{\mathcal{O(n^{1−\alpha})\) query time. Despite the substantial improvement in the query time, it still remains polynomial in the size of the graph, which may be undesirable in many settings where the graph is of large scale. A natural question is whether one can hope for a distance sensitivity oracle with subcubic preprocessing time and very fast query time (of poly-logarithmic in \(n\)). In this paper we answer this question affirmatively by presenting a distance sensitive oracle supporting a single vertex/edge failure in subcubic \(\tilde{\mathcal{O(Mn^{2.873})\) preprocessing time for \(\omega=2.373\), \(\tilde{\mathcal{O(n^{2.5})\) space and near optimal query time of \(\tilde{\mathcal{O(1)\). For comparison, with the same \(\tilde{\mathcal{O(Mn^{2.873})\) preprocessing time the DSO of Grandoni and Vassilevska Williams has \(\tilde{\mathcal{O(n^{0.693})\) query time. In fact, the best query time their algorithm can obtain is \(\tilde{\mathcal{O(Mn^{0.385})\) (with \(\tilde{\mathcal{O(Mn^3)\) preprocessing time).
  @inproceedings{chechik2020distance, abstract = {We present the first distance sensitivity oracle (DSO) with subcubic preprocessing time and poly-logarithmic query time for directed graphs with integer weights in the range \([−M,M]\). Weimann and Yuster [FOCS 10] presented a distance sensitivity oracle for a single vertex/edge failure with subcubic preprocessing time of \(\mathcal{O}(Mn^{\omega+1− \alpha})\) and subquadratic query time of \(\tilde{\mathcal{O}}(n^{1+\alpha})\), where \(\alpha\) is any parameter in \([0,1]\), \(n\) is the number of vertices, \(m\) is the number of edges, the \(\tilde{\mathcal{O}}(·)\) notation hides poly-logarithmic factors in \(n\) and \(\omega<2.373\) is the matrix multiplication exponent.Later, Grandoni and Vassilevska Williams [FOCS 12] substantially improved the query time to sublinear in \(n\). In particular, they presented a distance sensitivity oracle for a single vertex/edge failure with \(\tilde{\mathcal{O}}\)\( (Mn^{\omega +1/2}\) \(+ Mn^{\omega+\alpha(4−\omega)})\) preprocessing time and \(\tilde{\mathcal{O}}(n^{1−\alpha})\) query time. Despite the substantial improvement in the query time, it still remains polynomial in the size of the graph, which may be undesirable in many settings where the graph is of large scale. A natural question is whether one can hope for a distance sensitivity oracle with subcubic preprocessing time and very fast query time (of poly-logarithmic in \(n\)). In this paper we answer this question affirmatively by presenting a distance sensitive oracle supporting a single vertex/edge failure in subcubic \(\tilde{\mathcal{O}}(Mn^{2.873})\) preprocessing time for \(\omega=2.373\), \(\tilde{\mathcal{O}}(n^{2.5})\) space and near optimal query time of \(\tilde{\mathcal{O}}(1)\). For comparison, with the same \(\tilde{\mathcal{O}}(Mn^{2.873})\) preprocessing time the DSO of Grandoni and Vassilevska Williams has \(\tilde{\mathcal{O}}(n^{0.693})\) query time. In fact, the best query time their algorithm can obtain is \(\tilde{\mathcal{O}}(Mn^{0.385})\) (with \(\tilde{\mathcal{O}}(Mn^3)\) preprocessing time).}, author = {Chechik, Shiri and Cohen, Sarel}, booktitle = {Symposium Theory of Computing (STOC)}, keywords = {sarelcohen sys:relevantfor:ae stoc shirichechik year2020}, pages = {1375-1388}, title = {Distance sensitivity oracles with subcubic preprocessing time and fast query time}, year = 2020 }

2019 [ nach oben ]

• 
  Alon, Noga; Chechik, Shiri; Cohen, SarelDeterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles. International Colloquium on Automata, Languages and Programming (ICALP) 2019: 12:1-12:14
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  In this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the randomized algorithms. For the replacement paths problem, let \(G = (V,E)\) be a directed unweighted graph with \(n\) vertices and m edges and let \(P\) be a shortest path from \(s\) to \(t\) in \(G\). The replacement paths problem is to find for every edge \(e\) in \(P\) the shortest path from \(s\) to \(t\) avoiding \(e\). Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of \(\mathcal{O(m \sqrt{n})\). Here we provide the first deterministic algorithm for this problem, with the same \(\mathcal{O(m \sqrt{n})\) time. Due to matching conditional lower bounds of Williams et al. [FOCS 2010], our deterministic combinatorial algorithm for the replacement paths problem is optimal up to polylogarithmic factors (unless the long standing bound of \(\mathcal{O(mn)\) for the combinatorial boolean matrix multiplication can be improved). This also implies a deterministic algorithm for the second simple shortest path problem in \(\mathcal{O(m \sqrt{n})\) time, and a deterministic algorithm for the \(k\)-simple shortest paths problem in \(\mathcal{O(k m sqrt{n})\) time (for any integer constant \(k > 0\)). For the problem of distance sensitivity oracles, let \(G = (V,E)\) be a directed graph with real-edge weights. An \(f\)-Sensitivity Distance Oracle (\(f\)-DSO) gets as input the graph \(G=(V,E)\) and a parameter \(f\), preprocesses it into a data-structure, such that given a query \((s,t,F)\) with \(s,t \in V\) and \(F \subseteq E \cup V\), \(|F| <=f\) being a set of at most \(f\) edges or vertices (failures), the query algorithm efficiently computes the distance from \(s\) to \(t\) in the graph \(G \setminus F\) (i.e., the distance from \(s\) to \(t\) in the graph \(G\) after removing from it the failing edges and vertices \(F\)). For weighted graphs with real edge weights, Weimann and Yuster [FOCS 2010] presented several randomized \(f\)-DSOs. In particular, they presented a combinatorial \(f\)-DSO with \(\mathcal{O(mn^{4-\alpha})\) preprocessing time and subquadratic \(\mathcal{O(n^2-2(1-\alpha)/f})\) query time, giving a tradeoff between preprocessing and query time for every value of \(0 < \alpha < 1\). We derandomize this result and present a combinatorial deterministic \(f\)-DSO with the same asymptotic preprocessing and query time.
  @inproceedings{alon2019deterministic, abstract = {In this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the randomized algorithms. For the replacement paths problem, let \(G = (V,E)\) be a directed unweighted graph with \(n\) vertices and m edges and let \(P\) be a shortest path from \(s\) to \(t\) in \(G\). The replacement paths problem is to find for every edge \(e\) in \(P\) the shortest path from \(s\) to \(t\) avoiding \(e\). Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of \(\mathcal{O}(m \sqrt{n})\). Here we provide the first deterministic algorithm for this problem, with the same \(\mathcal{O}(m \sqrt{n})\) time. Due to matching conditional lower bounds of Williams et al. [FOCS 2010], our deterministic combinatorial algorithm for the replacement paths problem is optimal up to polylogarithmic factors (unless the long standing bound of \(\mathcal{O}(mn)\) for the combinatorial boolean matrix multiplication can be improved). This also implies a deterministic algorithm for the second simple shortest path problem in \(\mathcal{O}(m \sqrt{n})\) time, and a deterministic algorithm for the \(k\)-simple shortest paths problem in \(\mathcal{O}(k m sqrt{n})\) time (for any integer constant \(k > 0\)). For the problem of distance sensitivity oracles, let \(G = (V,E)\) be a directed graph with real-edge weights. An \(f\)-Sensitivity Distance Oracle (\(f\)-DSO) gets as input the graph \(G=(V,E)\) and a parameter \(f\), preprocesses it into a data-structure, such that given a query \((s,t,F)\) with \(s,t \in V\) and \(F \subseteq E \cup V\), \(|F| <=f\) being a set of at most \(f\) edges or vertices (failures), the query algorithm efficiently computes the distance from \(s\) to \(t\) in the graph \(G \setminus F\) (i.e., the distance from \(s\) to \(t\) in the graph \(G\) after removing from it the failing edges and vertices \(F\)). For weighted graphs with real edge weights, Weimann and Yuster [FOCS 2010] presented several randomized \(f\)-DSOs. In particular, they presented a combinatorial \(f\)-DSO with \(\mathcal{O}(mn^{4-\alpha})\) preprocessing time and subquadratic \(\mathcal{O}(n^{2-2(1-\alpha)/f})\) query time, giving a tradeoff between preprocessing and query time for every value of \(0 < \alpha < 1\). We derandomize this result and present a combinatorial deterministic \(f\)-DSO with the same asymptotic preprocessing and query time.}, author = {Alon, Noga and Chechik, Shiri and Cohen, Sarel}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {sarelcohen sys:relevantfor:ae shirichechik year2019 nogaalon icalp}, pages = {12:1-12:14}, title = {Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles}, year = 2019 }
• 
  Chechik, Shiri; Cohen, SarelNear Optimal Algorithms For The Single Source Replacement Paths Problem. Symposium on Discrete Algorithms (SODA) 2019: 2090-2109
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  The Single Source Replacement Paths (SSRP) problem is as follows; Given a graph \(G = (V, E)\), a source vertex \(s\) and a shortest paths tree \(T_s\) rooted in \(s\), output for every vertex \(t \in V\) and for every edge \(e\) in \(T_s\) the length of the shortest path from \(s\) to \(t\) avoiding \(e\). We present near optimal upper bounds, by providing \(\tilde{\mathcal{O(m \sqrt{n} + n^2) \) time randomized combinatorial algorithm for unweighted undirected graphs, and matching conditional lower bounds for the SSRP problem.
  @inproceedings{chechik2019optimal, abstract = {The Single Source Replacement Paths (SSRP) problem is as follows; Given a graph \(G = (V, E)\), a source vertex \(s\) and a shortest paths tree \(T_s\) rooted in \(s\), output for every vertex \(t \in V\) and for every edge \(e\) in \(T_s\) the length of the shortest path from \(s\) to \(t\) avoiding \(e\). We present near optimal upper bounds, by providing \(\tilde{\mathcal{O}}(m \sqrt{n} + n^2) \) time randomized combinatorial algorithm for unweighted undirected graphs, and matching conditional lower bounds for the SSRP problem.}, author = {Chechik, Shiri and Cohen, Sarel}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {sarelcohen sys:relevantfor:ae shirichechik year2019 soda}, pages = {2090-2109}, title = {Near Optimal Algorithms For The Single Source Replacement Paths Problem}, year = 2019 }

2018 [ nach oben ]

• 
  Azar, Yossi; Cohen, SarelAn improved algorithm for online machine minimization. Operations Research Letters 2018: 128-133
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
   
  The online machine minimization problem seeks to design a preemptive scheduling algorithm on multiple machines — each job \(j\) arrives at its release time \(r_j\), has to be processed for \(p_j\) time units, and must be completed by its deadline \(d_j\). The goal is to minimize the number of machines the algorithm uses. We improve the \(\mathcal{O(\log m)\)-competitive algorithm by Chen, Megow and Schewior (SODA 2016) and provide an \(\mathcal{O(\frac{\log m\log \log m})\)-competitive algorithm.
  @article{azar2018improved, abstract = {The online machine minimization problem seeks to design a preemptive scheduling algorithm on multiple machines — each job \(j\) arrives at its release time \(r_j\), has to be processed for \(p_j\) time units, and must be completed by its deadline \(d_j\). The goal is to minimize the number of machines the algorithm uses. We improve the \(\mathcal{O}(\log m)\)-competitive algorithm by Chen, Megow and Schewior (SODA 2016) and provide an \(\mathcal{O}(\frac{\log m}{\log \log m})\)-competitive algorithm.}, author = {Azar, Yossi and Cohen, Sarel}, journal = {Operations Research Letters}, keywords = {sarelcohen sys:relevantfor:ae year2018 yossiazar orl}, pages = {128-133}, title = {An improved algorithm for online machine minimization}, year = 2018 }
• 
  Arar, Moab; Chechik, Shiri; Cohen, Sarel; Stein, Cliff; Wajc, DavidDynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms. International Colloquium on Automata, Languages and Programming (ICALP) 2018: 7:1-7:16
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic "approximately-maximal" fractional matching algorithms. Applying this reduction to the recent fractional matching algorithm of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result for the integral problem. Specifically, our main result is a randomized fully-dynamic \((2+\varepsilon)\)-approximate integral matching algorithm with small polylog worst-case update time. For the \((2+\varepsilon)\)-approximation regime only a fractional fully-dynamic \((2+\varepsilon)\)-matching algorithm with worst-case polylog update time was previously known, due to Bhattacharya et al. (SODA 2017). Our algorithm is the first algorithm that maintains approximate matchings with worst-case update time better than polynomial, for any constant approximation ratio. As a consequence, we also obtain the first constant-approximate worst-case polylogarithmic update time maximum weight matching algorithm.
  @inproceedings{arar2018dynamic, abstract = {We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic "approximately-maximal" fractional matching algorithms. Applying this reduction to the recent fractional matching algorithm of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result for the integral problem. Specifically, our main result is a randomized fully-dynamic \((2+\varepsilon)\)-approximate integral matching algorithm with small polylog worst-case update time. For the \((2+\varepsilon)\)-approximation regime only a fractional fully-dynamic \((2+\varepsilon)\)-matching algorithm with worst-case polylog update time was previously known, due to Bhattacharya et al. (SODA 2017). Our algorithm is the first algorithm that maintains approximate matchings with worst-case update time better than polynomial, for any constant approximation ratio. As a consequence, we also obtain the first constant-approximate worst-case polylogarithmic update time maximum weight matching algorithm.}, author = {Arar, Moab and Chechik, Shiri and Cohen, Sarel and Stein, Cliff and Wajc, David}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {sarelcohen sys:relevantfor:ae shirichechik davidwajc year2018 moabarar icalp cliffstein}, pages = {7:1-7:16}, title = {Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms}, year = 2018 }

2017 [ nach oben ]

• 
  Chechik, Shiri; Cohen, Sarel; Fiat, Amos; Kaplan, Haim\( (1 + \varepsilon)\)-Approximate \(f\)-Sensitive Distance Oracles. Symposium on Discrete Algorithms (SODA) 2017: 1479-1496
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  An \(f\)-Sensitive Distance Oracle with stretch a preprocesses a graph \( G(V, E) \) and produces a small data structure that is used to answer subsequent queries. A query is a triple consisting of a set \( F \subset E \) of at most \(f\) edges, and vertices \(s\) and \(t\). The oracle answers a query \( (F,s.,t) \) by returning a value \(d\) which is equal to the length of some path between \(s\) and \(t\) in the graph \(G \setminus F\) (the graph obtained from \(G\) by discarding all edges in \(F\)). Moreover, d is at most a times the length of the shortest path between \(s\) and \(t\) in \(G \setminus F\). The oracle can also construct a path between \(s\) and \(t\) in \(G \setminus F\) of length \(d\). To the best of our knowledge we give the first nontrivial f-sensitive distance oracle with fast query time and small stretch capable of handling multiple edge failures. Specifically, for any \( \mathcal{O(\frac{\log n\log \log n ) \) and a fixed \( \varepsilon > 0 \) our oracle answers queries \( (F,s,t) \) in time \( \mathcal{O(l) \) with \( (1 + \varepsilon) \) stretch using a data structure of size \( n^2+ \mathcal{O(1) \) For comparison, the naive alternative requires \( m^f n^2 \) space for sublinear query time.
  @inproceedings{chechik2017varepsilonapproximate, abstract = {An \(f\)-Sensitive Distance Oracle with stretch a preprocesses a graph \( G(V, E) \) and produces a small data structure that is used to answer subsequent queries. A query is a triple consisting of a set \( F \subset E \) of at most \(f\) edges, and vertices \(s\) and \(t\). The oracle answers a query \( (F,s.,t) \) by returning a value \(d\) which is equal to the length of some path between \(s\) and \(t\) in the graph \(G \setminus F\) (the graph obtained from \(G\) by discarding all edges in \(F\)). Moreover, d is at most a times the length of the shortest path between \(s\) and \(t\) in \(G \setminus F\). The oracle can also construct a path between \(s\) and \(t\) in \(G \setminus F\) of length \(d\). To the best of our knowledge we give the first nontrivial f-sensitive distance oracle with fast query time and small stretch capable of handling multiple edge failures. Specifically, for any \( \mathcal{O}(\frac{\log n}{\log \log n} ) \) and a fixed \( \varepsilon > 0 \) our oracle answers queries \( (F,s,t) \) in time \( \mathcal{O}(l) \) with \( (1 + \varepsilon) \) stretch using a data structure of size \( n^{2+ \mathcal{O}(1)} \) For comparison, the naive alternative requires \( m^f n^2 \) space for sublinear query time.}, author = {Chechik, Shiri and Cohen, Sarel and Fiat, Amos and Kaplan, Haim}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {sarelcohen amosfiat sys:relevantfor:ae haimkaplan shirichechik year2017 soda}, pages = {1479-1496}, title = {\( (1 + \varepsilon)\)-Approximate \(f\)-Sensitive Distance Oracles}, year = 2017 }

2015 [ nach oben ]

• 
  Cohen, Sarel; Fiat, Amos; Hershcovitch, Moshik; Haim, KaplanMinimal indices for predecessor search. Information and Computation 2015: 12-30
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We give a new predecessor data structure which improves upon the index size of the Pǎtraşcu–Thorup data structures, reducing the index size from \( \mathcal{O(n w^{4/5}) \) bits to \( \mathcal{O(n \log w) \) bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra \( \mathcal{O(\log w) \) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of \( \mathcal{O(n \log w) \) bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree \(w \log w \) (compared to \(w ^{1/5}\) of a fusion tree node). To construct these indices we device highly efficient bit selectors which, we believe, are of independent interest.
  @article{cohen2015minimal, abstract = {We give a new predecessor data structure which improves upon the index size of the Pǎtraşcu–Thorup data structures, reducing the index size from \( \mathcal{O}(n w^{4/5}) \) bits to \( \mathcal{O}(n \log w) \) bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra \( \mathcal{O}(\log w) \) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of \( \mathcal{O}(n \log w) \) bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree \(w \log w \) (compared to \(w ^{1/5}\) of a fusion tree node). To construct these indices we device highly efficient bit selectors which, we believe, are of independent interest.}, author = {Cohen, Sarel and Fiat, Amos and Hershcovitch, Moshik and Haim, Kaplan}, journal = {Information and Computation}, keywords = {sarelcohen amosfiat sys:relevantfor:ae haimkaplan moshikhershcovitch year2015 ic}, pages = {12-30}, title = {Minimal indices for predecessor search}, year = 2015 }

2013 [ nach oben ]

• 
  Cohen, Sarel; Fiat, Amos; Hershcovitch, Moshik; Kaplan, HaimMinimal Indices for Successor Search - (Extended Abstract).Mathematical Foundations of Computer Science (MFCS) 2013: 278-289
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We give a new successor data structure which improves upon the index size of the Pǎtraşcu-Thorup data structures, reducing the index size from \( \mathcal{O(n w^4/5 \) bits to \( \mathcal{O(n \log w) \) bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra \( \mathcal{O(n \log w) \) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of \( \mathcal{O(n \log w) \) bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree \( w / \log w \) (compared to the \( w^1/5 \) out-degree of fusion tree based indices). To construct such high efficiency single word indices we device highly efficient bit selectors which, we believe, are of independent interest.
  @inproceedings{cohen2013minimal, abstract = {We give a new successor data structure which improves upon the index size of the Pǎtraşcu-Thorup data structures, reducing the index size from \( \mathcal{O}(n w^{4/5} \) bits to \( \mathcal{O}(n \log w) \) bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra \( \mathcal{O}(n \log w) \) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of \( \mathcal{O}(n \log w) \) bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree \( w / \log w \) (compared to the \( w^{1/5} \) out-degree of fusion tree based indices). To construct such high efficiency single word indices we device highly efficient bit selectors which, we believe, are of independent interest.}, author = {Cohen, Sarel and Fiat, Amos and Hershcovitch, Moshik and Kaplan, Haim}, booktitle = {Mathematical Foundations of Computer Science (MFCS)}, keywords = {sarelcohen amosfiat sys:relevantfor:ae haimkaplan moshikhershcovitch mfcs year2013}, pages = {278-289}, title = {Minimal Indices for Successor Search - (Extended Abstract).}, year = 2013 }