Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Matthew D. Laws, Jocelyn Bliven, Kit Conklin, Elyes Laalai, Samuel McCauley, and Zach S. Sturdevant. SPIDER: Improved Succinct Rank and Select Performance. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{laws_et_al:LIPIcs.SEA.2024.21, author = {Laws, Matthew D. and Bliven, Jocelyn and Conklin, Kit and Laalai, Elyes and McCauley, Samuel and Sturdevant, Zach S.}, title = {{SPIDER: Improved Succinct Rank and Select Performance}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {21:1--21:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.21}, URN = {urn:nbn:de:0030-drops-203865}, doi = {10.4230/LIPIcs.SEA.2024.21}, annote = {Keywords: Rank and Select, Succinct Data Structures, Data Structres, Cache Performance, Predictions} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
William Kuszmaul and Zoe Xi. Towards an Analysis of Quadratic Probing. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 103:1-103:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kuszmaul_et_al:LIPIcs.ICALP.2024.103, author = {Kuszmaul, William and Xi, Zoe}, title = {{Towards an Analysis of Quadratic Probing}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {103:1--103: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.103}, URN = {urn:nbn:de:0030-drops-202463}, doi = {10.4230/LIPIcs.ICALP.2024.103}, annote = {Keywords: quadratic probing, hashing, open addressing, witness trees} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Tatsuya Yanagita, Sankardeep Chakraborty, Kunihiko Sadakane, and Srinivasa Rao Satti. Space-Efficient Data Structure for Posets with Applications. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{yanagita_et_al:LIPIcs.SWAT.2022.33, author = {Yanagita, Tatsuya and Chakraborty, Sankardeep and Sadakane, Kunihiko and Satti, Srinivasa Rao}, title = {{Space-Efficient Data Structure for Posets with Applications}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {33:1--33:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.33}, URN = {urn:nbn:de:0030-drops-161931}, doi = {10.4230/LIPIcs.SWAT.2022.33}, annote = {Keywords: Succinct Data Structures, Posets, Blockchain} }
Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)
Seungbum Jo, Wooyoung Park, and Srinivasa Rao Satti. Practical Implementation of Encoding Range Top-2 Queries. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{jo_et_al:LIPIcs.SEA.2021.10, author = {Jo, Seungbum and Park, Wooyoung and Satti, Srinivasa Rao}, title = {{Practical Implementation of Encoding Range Top-2 Queries}}, booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)}, pages = {10:1--10:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-185-6}, ISSN = {1868-8969}, year = {2021}, volume = {190}, editor = {Coudert, David and Natale, Emanuele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.10}, URN = {urn:nbn:de:0030-drops-137827}, doi = {10.4230/LIPIcs.SEA.2021.10}, annote = {Keywords: Range top-2 query, Range minimum query, Cartesian tree, Succinct encoding} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Kentaro Sumigawa, Sankardeep Chakraborty, Kunihiko Sadakane, and Srinivasa Rao Satti. Enumerating Range Modes. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{sumigawa_et_al:LIPIcs.ISAAC.2020.29, author = {Sumigawa, Kentaro and Chakraborty, Sankardeep and Sadakane, Kunihiko and Satti, Srinivasa Rao}, title = {{Enumerating Range Modes}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {29:1--29:16}, 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.29}, URN = {urn:nbn:de:0030-drops-133732}, doi = {10.4230/LIPIcs.ISAAC.2020.29}, annote = {Keywords: range mode, space-efficient data structure, enumeration algorithm} }
Published in: Dagstuhl Reports, Volume 8, Issue 7 (2019)
Jérémy Barbay, Johannes Fischer, Stefan Kratsch, and Srinivasa Rao Satti. Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281). In Dagstuhl Reports, Volume 8, Issue 7, pp. 44-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Article{barbay_et_al:DagRep.8.7.44, author = {Barbay, J\'{e}r\'{e}my and Fischer, Johannes and Kratsch, Stefan and Satti, Srinivasa Rao}, title = {{Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281)}}, pages = {44--61}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {8}, number = {7}, editor = {Barbay, J\'{e}r\'{e}my and Fischer, Johannes and Kratsch, Stefan and Satti, Srinivasa Rao}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.7.44}, URN = {urn:nbn:de:0030-drops-101724}, doi = {10.4230/DagRep.8.7.44}, annote = {Keywords: adaptive (analysis of) algorithms, compressed data structures, compressed indices, parameterized complexity} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Ran Ben Basat, Seungbum Jo, Srinivasa Rao Satti, and Shubham Ugare. Approximate Query Processing over Static Sets and Sliding Windows. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 54:1-54:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{benbasat_et_al:LIPIcs.ISAAC.2018.54, author = {Ben Basat, Ran and Jo, Seungbum and Satti, Srinivasa Rao and Ugare, Shubham}, title = {{Approximate Query Processing over Static Sets and Sliding Windows}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {54:1--54:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.54}, URN = {urn:nbn:de:0030-drops-100027}, doi = {10.4230/LIPIcs.ISAAC.2018.54}, annote = {Keywords: Streaming, Algorithms, Sliding window, Lower bounds} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Seungbum Jo and Srinivasa Rao Satti. Encoding Two-Dimensional Range Top-k Queries Revisited. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 69:1-69:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{jo_et_al:LIPIcs.ISAAC.2018.69, author = {Jo, Seungbum and Satti, Srinivasa Rao}, title = {{Encoding Two-Dimensional Range Top-k Queries Revisited}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {69:1--69:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.69}, URN = {urn:nbn:de:0030-drops-100179}, doi = {10.4230/LIPIcs.ISAAC.2018.69}, annote = {Keywords: Encoding model, top-k query, range minimum query} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Sankardeep Chakraborty, Anish Mukherjee, Venkatesh Raman, and Srinivasa Rao Satti. A Framework for In-place Graph Algorithms. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chakraborty_et_al:LIPIcs.ESA.2018.13, author = {Chakraborty, Sankardeep and Mukherjee, Anish and Raman, Venkatesh and Satti, Srinivasa Rao}, title = {{A Framework for In-place Graph Algorithms}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {13:1--13:16}, 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.13}, URN = {urn:nbn:de:0030-drops-94760}, doi = {10.4230/LIPIcs.ESA.2018.13}, annote = {Keywords: DFS, BFS, in-place algorithm, space-efficient graph algorithms, logspace} }
Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Jérémy Barbay, Carlos Ochoa, and Srinivasa Rao Satti. Synergistic Solutions on MultiSets. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{barbay_et_al:LIPIcs.CPM.2017.31, author = {Barbay, J\'{e}r\'{e}my and Ochoa, Carlos and Satti, Srinivasa Rao}, title = {{Synergistic Solutions on MultiSets}}, booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)}, pages = {31:1--31:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-039-2}, ISSN = {1868-8969}, year = {2017}, volume = {78}, editor = {K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.31}, URN = {urn:nbn:de:0030-drops-73441}, doi = {10.4230/LIPIcs.CPM.2017.31}, annote = {Keywords: deferred data structure, multivariate analysis, quick sort, select} }
Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Sankardeep Chakraborty, Venkatesh Raman, and Srinivasa Rao Satti. Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{chakraborty_et_al:LIPIcs.ISAAC.2016.22, author = {Chakraborty, Sankardeep and Raman, Venkatesh and Satti, Srinivasa Rao}, title = {{Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits}}, booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)}, pages = {22:1--22:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-026-2}, ISSN = {1868-8969}, year = {2016}, volume = {64}, editor = {Hong, Seok-Hee}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.22}, URN = {urn:nbn:de:0030-drops-67927}, doi = {10.4230/LIPIcs.ISAAC.2016.22}, annote = {Keywords: biconnectivity, st-number, chain decomposition, tree cover, space efficient algorithms, read-only memory} }
Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Seungbum Jo, Rahul Lingala, and Srinivasa Rao Satti. Encoding Two-Dimensional Range Top-k Queries. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{jo_et_al:LIPIcs.CPM.2016.3, author = {Jo, Seungbum and Lingala, Rahul and Satti, Srinivasa Rao}, title = {{Encoding Two-Dimensional Range Top-k Queries}}, booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)}, pages = {3:1--3:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-012-5}, ISSN = {1868-8969}, year = {2016}, volume = {54}, editor = {Grossi, Roberto and Lewenstein, Moshe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.3}, URN = {urn:nbn:de:0030-drops-60704}, doi = {10.4230/LIPIcs.CPM.2016.3}, annote = {Keywords: Encoding model, top-k query, range minimum query} }
Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Gonzalo Navarro, Rajeev Raman, and Srinivasa Rao Satti. Asymptotically Optimal Encodings for Range Selection. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 291-301, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{navarro_et_al:LIPIcs.FSTTCS.2014.291, author = {Navarro, Gonzalo and Raman, Rajeev and Satti, Srinivasa Rao}, title = {{Asymptotically Optimal Encodings for Range Selection}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {291--301}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-77-4}, ISSN = {1868-8969}, year = {2014}, volume = {29}, editor = {Raman, Venkatesh and Suresh, S. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.291}, URN = {urn:nbn:de:0030-drops-48502}, doi = {10.4230/LIPIcs.FSTTCS.2014.291}, annote = {Keywords: Data Structures, Order Statistics, Succinct Data Structures, Space-efficient Data Structures} }