Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Kento Iseri, Tomohiro I, Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, and Ayumi Shinohara. Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 89:1-89:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{iseri_et_al:LIPIcs.ICALP.2024.89, author = {Iseri, Kento and I, Tomohiro and Hendrian, Diptarama and K\"{o}ppl, Dominik and Yoshinaka, Ryo and Shinohara, Ayumi}, title = {{Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {89:1--89:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.89}, URN = {urn:nbn:de:0030-drops-202324}, doi = {10.4230/LIPIcs.ICALP.2024.89}, annote = {Keywords: Index for parameterized pattern matching, Parameterized Burrows-Wheeler Transform, Online construction} }
Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)
Philip Bille, Yakov Nekrich, and Solon P. Pissis. Size-Constrained Weighted Ancestors with Applications. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bille_et_al:LIPIcs.SWAT.2024.14, author = {Bille, Philip and Nekrich, Yakov and Pissis, Solon P.}, title = {{Size-Constrained Weighted Ancestors with Applications}}, booktitle = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, pages = {14:1--14:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-318-8}, ISSN = {1868-8969}, year = {2024}, volume = {294}, editor = {Bodlaender, Hans L.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.14}, URN = {urn:nbn:de:0030-drops-200544}, doi = {10.4230/LIPIcs.SWAT.2024.14}, annote = {Keywords: weighted ancestors, string indexing, data structures} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Rathish Das, John Iacono, and Yakov Nekrich. External-Memory Dictionaries with Worst-Case Update Cost. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{das_et_al:LIPIcs.ISAAC.2022.21, author = {Das, Rathish and Iacono, John and Nekrich, Yakov}, title = {{External-Memory Dictionaries with Worst-Case Update Cost}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {21:1--21:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.21}, URN = {urn:nbn:de:0030-drops-173060}, doi = {10.4230/LIPIcs.ISAAC.2022.21}, annote = {Keywords: Data Structures, External Memory, Buffer Tree} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Meng He, J. Ian Munro, Yakov Nekrich, Sebastian Wild, and Kaiyu Wu. Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{he_et_al:LIPIcs.ISAAC.2020.25, author = {He, Meng and Munro, J. Ian and Nekrich, Yakov and Wild, Sebastian and Wu, Kaiyu}, title = {{Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {25:1--25:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.25}, URN = {urn:nbn:de:0030-drops-133693}, doi = {10.4230/LIPIcs.ISAAC.2020.25}, annote = {Keywords: succinct data structures, distance oracles, ordinal tree, level order, breadth-first order, interval graphs, proper interval graphs, succinct graph representation} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Younan Gao, Meng He, and Yakov Nekrich. Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{gao_et_al:LIPIcs.ESA.2020.54, author = {Gao, Younan and He, Meng and Nekrich, Yakov}, title = {{Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {54:1--54:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.54}, URN = {urn:nbn:de:0030-drops-129202}, doi = {10.4230/LIPIcs.ESA.2020.54}, annote = {Keywords: orthogonal range search, geometric data structures, orthogonal range reporting, orthogonal range successor, sorted range reporting, text indexing, word RAM} }
Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
J. Ian Munro, Gonzalo Navarro, and Yakov Nekrich. Text Indexing and Searching in Sublinear Time. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{munro_et_al:LIPIcs.CPM.2020.24, author = {Munro, J. Ian and Navarro, Gonzalo and Nekrich, Yakov}, title = {{Text Indexing and Searching in Sublinear Time}}, booktitle = {31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)}, pages = {24:1--24:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-149-8}, ISSN = {1868-8969}, year = {2020}, volume = {161}, editor = {G{\o}rtz, Inge Li and Weimann, Oren}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.24}, URN = {urn:nbn:de:0030-drops-121497}, doi = {10.4230/LIPIcs.CPM.2020.24}, annote = {Keywords: data structures, string indexes} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Timothy M. Chan, Qizheng He, and Yakov Nekrich. Further Results on Colored Range Searching. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chan_et_al:LIPIcs.SoCG.2020.28, author = {Chan, Timothy M. and He, Qizheng and Nekrich, Yakov}, title = {{Further Results on Colored Range Searching}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {28:1--28:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.28}, URN = {urn:nbn:de:0030-drops-121868}, doi = {10.4230/LIPIcs.SoCG.2020.28}, annote = {Keywords: Range searching, geometric data structures, randomized incremental construction, random sampling, word RAM} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Yakov Nekrich. Four-Dimensional Dominance Range Reporting in Linear Space. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 59:1-59:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{nekrich:LIPIcs.SoCG.2020.59, author = {Nekrich, Yakov}, title = {{Four-Dimensional Dominance Range Reporting in Linear Space}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {59:1--59:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.59}, URN = {urn:nbn:de:0030-drops-122170}, doi = {10.4230/LIPIcs.SoCG.2020.59}, annote = {Keywords: Range searching, geometric data structures, word RAM} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Hicham El-Zein, Meng He, J. Ian Munro, Yakov Nekrich, and Bryce Sandlund. On Approximate Range Mode and Range Selection. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{elzein_et_al:LIPIcs.ISAAC.2019.57, author = {El-Zein, Hicham and He, Meng and Munro, J. Ian and Nekrich, Yakov and Sandlund, Bryce}, title = {{On Approximate Range Mode and Range Selection}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {57:1--57:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.57}, URN = {urn:nbn:de:0030-drops-115531}, doi = {10.4230/LIPIcs.ISAAC.2019.57}, annote = {Keywords: data structures, approximate range query, range mode, range median} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
J. Ian Munro and Yakov Nekrich. Dynamic Planar Point Location in External Memory. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{munro_et_al:LIPIcs.SoCG.2019.52, author = {Munro, J. Ian and Nekrich, Yakov}, title = {{Dynamic Planar Point Location in External Memory}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {52:1--52:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.52}, URN = {urn:nbn:de:0030-drops-104566}, doi = {10.4230/LIPIcs.SoCG.2019.52}, annote = {Keywords: Data Structures, Dynamic Data Structures, Planar Point Location, External Memory} }
Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)
Arnab Ganguly, J. Ian Munro, Yakov Nekrich, Rahul Shah, and Sharma V. Thankachan. Categorical Range Reporting with Frequencies. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ganguly_et_al:LIPIcs.ICDT.2019.9, author = {Ganguly, Arnab and Munro, J. Ian and Nekrich, Yakov and Shah, Rahul and Thankachan, Sharma V.}, title = {{Categorical Range Reporting with Frequencies}}, booktitle = {22nd International Conference on Database Theory (ICDT 2019)}, pages = {9:1--9:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-101-6}, ISSN = {1868-8969}, year = {2019}, volume = {127}, editor = {Barcelo, Pablo and Calautti, Marco}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.9}, URN = {urn:nbn:de:0030-drops-103115}, doi = {10.4230/LIPIcs.ICDT.2019.9}, annote = {Keywords: Data Structures, Range Reporting, Range Counting, Categorical Range Reporting, Orthogonal Range Query} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Mordecai Golin, John Iacono, Stefan Langerman, J. Ian Munro, and Yakov Nekrich. Dynamic Trees with Almost-Optimal Access Cost. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{golin_et_al:LIPIcs.ESA.2018.38, author = {Golin, Mordecai and Iacono, John and Langerman, Stefan and Munro, J. Ian and Nekrich, Yakov}, title = {{Dynamic Trees with Almost-Optimal Access Cost}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {38:1--38:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.38}, URN = {urn:nbn:de:0030-drops-95017}, doi = {10.4230/LIPIcs.ESA.2018.38}, annote = {Keywords: Data Structures, Binary Search Trees, Adaptive Alphabetic Coding} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Timothy M. Chan, Yakov Nekrich, Saladi Rahul, and Konstantinos Tsakalidis. Orthogonal Point Location and Rectangle Stabbing Queries in 3-d. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chan_et_al:LIPIcs.ICALP.2018.31, author = {Chan, Timothy M. and Nekrich, Yakov and Rahul, Saladi and Tsakalidis, Konstantinos}, title = {{Orthogonal Point Location and Rectangle Stabbing Queries in 3-d}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {31:1--31:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.31}, URN = {urn:nbn:de:0030-drops-90352}, doi = {10.4230/LIPIcs.ICALP.2018.31}, annote = {Keywords: geometric data structures, orthogonal point location, rectangle stabbing, pointer machines, I/O model, word RAM model} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Hicham El-Zein, J. Ian Munro, and Yakov Nekrich. Succinct Dynamic One-Dimensional Point Reporting. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 17:1-17:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{elzein_et_al:LIPIcs.SWAT.2018.17, author = {El-Zein, Hicham and Munro, J. Ian and Nekrich, Yakov}, title = {{Succinct Dynamic One-Dimensional Point Reporting}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {17:1--17:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.17}, URN = {urn:nbn:de:0030-drops-88438}, doi = {10.4230/LIPIcs.SWAT.2018.17}, annote = {Keywords: Succinct Data Structures, Range Searching, Computational Geometry} }
Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Hicham El-Zein, J. Ian Munro, and Yakov Nekrich. Succinct Color Searching in One Dimension. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 30:1-30:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{elzein_et_al:LIPIcs.ISAAC.2017.30, author = {El-Zein, Hicham and Munro, J. Ian and Nekrich, Yakov}, title = {{Succinct Color Searching in One Dimension}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {30:1--30:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.30}, URN = {urn:nbn:de:0030-drops-82096}, doi = {10.4230/LIPIcs.ISAAC.2017.30}, annote = {Keywords: Succinct Data Structures, Range Searching, Computational Geometry} }
Feedback for Dagstuhl Publishing