Philip Bille

According to our database, Philip Bille authored at least 87 papers between 2004 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Gapped String Indexing in Subquadratic Space and Sublinear Query Time.

Philip Bille, Inge Li Gørtz, Moshe Lewenstein, Solon P. Pissis, Eva Rotenberg, Teresa Anna Steiner

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Sparse Regular Expression Matching.

Philip Bille, Inge Li Gørtz

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

String Indexing with Compressed Patterns.

Philip Bille, Inge Li Gørtz, Teresa Anna Steiner

ACM Trans. Algorithms, October, 2023

Random Access in Persistent Strings and Segment Selection.

Philip Bille, Inge Li Gørtz

Theory Comput. Syst., August, 2023

Gapped Indexing for Consecutive Occurrences.

Philip Bille, Inge Li Gørtz, Max Rishøj Pedersen, Teresa Anna Steiner

Algorithmica, April, 2023

Size-constrained Weighted Ancestors with Applications.

Philip Bille, Yakov Nekrich, Solon P. Pissis

CoRR, 2023

Rank and Select on Degenerate Strings.

Philip Bille, Inge Li Gørtz, Tord Stordalen

CoRR, 2023

Faster Compression of Deterministic Finite Automata.

Philip Bille, Inge Li Gørtz, Max Rishøj Pedersen

CoRR, 2023

Hierarchical Relative Lempel-Ziv Compression.

Philip Bille, Inge Li Gørtz, Simon J. Puglisi, Simon R. Tarnow

Proceedings of the 21st International Symposium on Experimental Algorithms, 2023

Sliding Window String Indexing in Streams.

Philip Bille, Johannes Fischer, Inge Li Gørtz, Max Rishøj Pedersen, Tord Joakim Stordalen

Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching, 2023

2022

Partial sums on the ultra-wide word RAM.

Philip Bille, Inge Li Gørtz, Frederik Rye Skjoldjensen

Theor. Comput. Sci., 2022

String indexing for top-<i>k</i> close consecutive occurrences.

Philip Bille, Inge Li Gørtz, Max Rishøj Pedersen, Eva Rotenberg, Teresa Anna Steiner

Theor. Comput. Sci., 2022

From regular expression matching to parsing.

Philip Bille, Inge Li Gørtz

Acta Informatica, 2022

Predecessor on the Ultra-Wide Word RAM.

Philip Bille, Inge Li Gørtz, Tord Stordalen

Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

The Complexity of the Co-occurrence Problem.

Philip Bille, Inge Li Gørtz, Tord Stordalen

Proceedings of the String Processing and Information Retrieval, 2022

The Fine-Grained Complexity of Episode Matching.

Philip Bille, Inge Li Gørtz, Shay Mozes, Teresa Anna Steiner, Oren Weimann

Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching, 2022

2021

A Conditional Lower Bound for Episode Matching.

Philip Bille, Inge Li Gørtz, Shay Mozes, Teresa Anna Steiner, Oren Weimann

CoRR, 2021

Top Tree Compression of Tries.

Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, Gad M. Landau, Oren Weimann

Algorithmica, 2021

2020

Editorial: Special Issue on Data Compression Algorithms and Their Applications.

Philip Bille

Algorithms, 2020

Random Access in Persistent Strings.

Philip Bille, Inge Li Gørtz

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Space Efficient Construction of Lyndon Arrays in Linear Time.

Philip Bille, Jonas Ellert, Johannes Fischer, Inge Li Gørtz, Florian Kurpicz, J. Ian Munro, Eva Rotenberg

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

String Indexing for Top-k Close Consecutive Occurrences.

Philip Bille, Inge Li Gørtz, Max Rishøj Pedersen, Eva Rotenberg, Teresa Anna Steiner

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

Decompressing Lempel-Ziv Compressed Text.

Philip Bille, Mikko Berggren Ettienne, Travis Gagie, Inge Li Gørtz, Nicola Prezza

Proceedings of the Data Compression Conference, 2020

2019

Mergeable Dictionaries With Shifts.

Philip Bille, Mikko Berggren Ettienne, Inge Li Gørtz

CoRR, 2019

2018

Time-space trade-offs for Lempel-Ziv compressed indexing.

Philip Bille, Mikko Berggren Ettienne, Inge Li Gørtz, Hjalte Wedel Vildhøj

Theor. Comput. Sci., 2018

Finger Search in Grammar-Compressed Strings.

Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording, Inge Li Gørtz

Theory Comput. Syst., 2018

A separation between RLSLPs and LZ77.

Philip Bille, Travis Gagie, Inge Li Gørtz, Nicola Prezza

J. Discrete Algorithms, 2018

Fast Lempel-Ziv Decompression in Linear Space.

Philip Bille, Mikko Berggren Ettienne, Travis Gagie, Inge Li Gørtz, Nicola Prezza

CoRR, 2018

Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation.

Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording, Inge Li Gørtz, Frederik Rye Skjoldjensen, Hjalte Wedel Vildhøj, Søren Vind

Algorithmica, 2018

Compressed Communication Complexity of Longest Common Prefixes.

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

Proceedings of the String Processing and Information Retrieval, 2018

2017

Subsequence automata with default transitions.

Philip Bille, Inge Li Gørtz, Frederik Rye Skjoldjensen

J. Discrete Algorithms, 2017

Fingerprints in compressed strings.

Philip Bille, Inge Li Gørtz, Patrick Hagge Cording, Benjamin Sach, Hjalte Wedel Vildhøj, Søren Vind

J. Comput. Syst. Sci., 2017

A Separation Between Run-Length SLPs and LZ77.

Philip Bille, Travis Gagie, Inge Li Gørtz, Nicola Prezza

CoRR, 2017

Practical and Effective Re-Pair Compression.

Philip Bille, Inge Li Gørtz, Nicola Prezza

CoRR, 2017

Compressed Subsequence Matching and Packed Tree Coloring.

Philip Bille, Patrick Hagge Cording, Inge Li Gørtz

Algorithmica, 2017

Tight Bounds for Top Tree Compression.

Philip Bille, Finn Fernstrøm, Inge Li Gørtz

Proceedings of the String Processing and Information Retrieval, 2017

Succinct Partial Sums and Fenwick Trees.

Philip Bille, Anders Roy Christiansen, Nicola Prezza, Frederik Rye Skjoldjensen

Proceedings of the String Processing and Information Retrieval, 2017

Immersive Algorithms: Better Visualization with Less Information.

Philip Bille, Inge Li Gørtz

Proceedings of the 2017 ACM Conference on Innovation and Technology in Computer Science Education, 2017

Fast Dynamic Arrays.

Philip Bille, Anders Roy Christiansen, Mikko Berggren Ettienne, Inge Li Gørtz

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Space-Efficient Re-Pair Compression.

Philip Bille, Inge Li Gørtz, Nicola Prezza

Proceedings of the 2017 Data Compression Conference, 2017

Deterministic Indexing for Packed Strings.

Philip Bille, Inge Li Gørtz, Frederik Rye Skjoldjensen

Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

Lempel-Ziv Compression in a Sliding Window.

Philip Bille, Patrick Hagge Cording, Johannes Fischer, Inge Li Gørtz

Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

2016

Longest common extensions in trees.

Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, Gad M. Landau, Oren Weimann

Theor. Comput. Sci., 2016

Sparse Text Indexing in Small Space.

Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj

ACM Trans. Algorithms, 2016

Computation over Compressed Structured Data (Dagstuhl Seminar 16431).

Philip Bille, Markus Lohrey, Sebastian Maneth, Gonzalo Navarro

Dagstuhl Reports, 2016

Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation.

Philip Bille, Patrick Hagge Cording, Inge Li Gørtz, Frederik Rye Skjoldjensen, Hjalte Wedel Vildhøj, Søren Vind

Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

Boxed Permutation Pattern Matching.

Mika Amit, Philip Bille, Patrick Hagge Cording, Inge Li Gørtz, Hjalte Wedel Vildhøj

Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

2015

On Regular Expression Matching and Deterministic Finite Automata.

Philip Bille

Tiny Trans. Comput. Sci., 2015

Random Access to Grammar-Compressed Strings and Trees.

Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, Oren Weimann

SIAM J. Comput., 2015

Tree compression with top trees.

Philip Bille, Inge Li Gørtz, Gad M. Landau, Oren Weimann

Inf. Comput., 2015

Dynamic Relative Compression.

Philip Bille, Patrick Hagge Cording, Inge Li Gørtz, Frederik Rye Skjoldjensen, Hjalte Wedel Vildhøj, Søren Vind

CoRR, 2015

Finger Search, Random Access, and Longest Common Extensions in Grammar-Compressed Strings.

Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording, Inge Li Gørtz

CoRR, 2015

Compressed Data Structures for Range Searching.

Philip Bille, Inge Li Gørtz, Søren Vind

Proceedings of the Language and Automata Theory and Applications, 2015

Longest Common Extensions in Sublinear Space.

Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen, Moshe Lewenstein, Hjalte Wedel Vildhøj

Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

2014

Compact q-gram profiling of compressed strings.

Philip Bille, Patrick Hagge Cording, Inge Li Gørtz

Theor. Comput. Sci., 2014

Towards optimal packed string matching.

Oren Ben-Kiki, Philip Bille, Dany Breslauer, Leszek Gasieniec, Roberto Grossi, Oren Weimann

Theor. Comput. Sci., 2014

String Indexing for Patterns with Wildcards.

Philip Bille, Inge Li Gørtz, Hjalte Wedel Vildhøj, Søren Vind

Theory Comput. Syst., 2014

Time-space trade-offs for longest common extensions.

Philip Bille, Inge Li Gørtz, Benjamin Sach, Hjalte Wedel Vildhøj

J. Discrete Algorithms, 2014

Longest Common Extensions in Trees.

Philip Bille, Inge Li Gørtz, Gad M. Landau, Oren Weimann

CoRR, 2014

Compact Subsequence Matching and Packed Tree Coloring.

Philip Bille, Patrick Hagge Cording, Inge Li Gørtz

CoRR, 2014

Substring Range Reporting.

Philip Bille, Inge Li Gørtz

Algorithmica, 2014

Indexing Motion Detection Data for Surveillance Video.

Søren Vind, Philip Bille, Inge Li Gørtz

Proceedings of the 2014 IEEE International Symposium on Multimedia, 2014

2013

Sparse Suffix Tree Construction in Small Space.

Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

String matching with variable length gaps.

Philip Bille, Inge Li Gørtz, Hjalte Wedel Vildhøj, David Kofoed Wind

Theor. Comput. Sci., 2012

Faster Approximate String Matching for Short Patterns.

Philip Bille

Theory Comput. Syst., 2012

Sparse Suffix Tree Construction with Small Space

Philip Bille, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj

CoRR, 2012

Fast Arc-Annotated Subsequence Matching in Linear Space.

Philip Bille, Inge Li Gørtz

Algorithmica, 2012

Fast and Cache-Oblivious Dynamic Programming with Local Dependencies.

Philip Bille, Morten Stöckel

Proceedings of the Language and Automata Theory and Applications, 2012

Longest Common Extensions via Fingerprinting.

Philip Bille, Inge Li Gørtz, Jesper Kristensen

Proceedings of the Language and Automata Theory and Applications, 2012

2011

The tree inclusion problem: In linear space and faster.

Philip Bille, Inge Li Gørtz

ACM Trans. Algorithms, 2011

Fast searching in packed strings.

Philip Bille

J. Discrete Algorithms, 2011

Random Access to grammar-Compressed Strings.

Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, Oren Weimann

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Optimal Packed String Matching.

Oren Ben-Kiki, Philip Bille, Dany Breslauer, Leszek Gasieniec, Roberto Grossi, Oren Weimann

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

2010

Random Access to Grammar Compressed Strings

Philip Bille, Gad M. Landau, Oren Weimann

CoRR, 2010

Regular Expression Matching with Multi-Strings and Intervals.

Philip Bille, Mikkel Thorup

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

Improved approximate string matching and regular expression matching on Ziv-Lempel compressed texts.

Philip Bille, Rolf Fagerberg, Inge Li Gørtz

ACM Trans. Algorithms, 2009

Matching subsequences in trees.

Philip Bille, Inge Li Gørtz

J. Discrete Algorithms, 2009

Faster Regular Expression Matching.

Philip Bille, Mikkel Thorup

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008

Fast and compact regular expression matching.

Philip Bille, Martin Farach-Colton

Theor. Comput. Sci., 2008

2007

Pattern Matching in Trees and Strings

Philip Bille

CoRR, 2007

Fast Evaluation of Union-Intersection Expressions.

Philip Bille, Anna Pagh, Rasmus Pagh

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

2006

Matching 2D Shapes using their Symmetry Sets.

Arjan Kuijper, Ole Fogh Olsen, Philip Bille, Peter J. Giblin

Proceedings of the 18th International Conference on Pattern Recognition (ICPR 2006), 2006

New Algorithms for Regular Expression Matching.

Philip Bille

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

A survey on tree edit distance and related problems.

Philip Bille

Theor. Comput. Sci., 2005

Labeling Schemes for Small Distances in Trees.

Stephen Alstrup, Philip Bille, Theis Rauhe

SIAM J. Discret. Math., 2005

The Tree Inclusion Problem: In Optimal Space and Faster.

Philip Bille, Inge Li Gørtz

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004

From a 2D Shape to a String Structure Using the Symmetry Set.

Arjan Kuijper, Ole Fogh Olsen, Peter J. Giblin, Philip Bille, Mads Nielsen

Proceedings of the Computer Vision, 2004