Publications

Listed in approximate reverse chronological order of first appearence

Popcorning: Repurposing Write-Optimization Buffers for Faster Queries.
Peyman Afshani, Michael A. Bender, Philip Bille, Alex Conway, Martin Farach-Colton, Jeremy Fineman, Michael T. Goodrich, Inge Li Gørtz, John Iacono, Rob Johnson, Hanna Komlós, William Kuszmaul, Rose Silver, Robert Tarjan, Simon Rumle Tarnow, and Renfei Zhou.
In Proceedings of the 46th Symposium on Principles of Database Systems, 2027.

Average-Case Optimal Encodings and Efficient Worst-Case Indices for Element Distinctness Queries.
Philip Bille, Johannes Fischer, Inge Li Gørtz, and Filippo Lari.
In Proceedings of the 33rd International Symposium on String Processing and Information Retrieval, 2026. [draft of full version]

k2-octopus: An adaptive data structure for binary matrices.
Philip Bille, Gabriel Carmona, and Inge Li Gørtz.
In Proceedings of the 33rd International Symposium on String Processing and Information Retrieval, 2026.

Tighter Bounds for Wheeler Determinization.
Philip Bille, Inge Li Gørtz, Máximo Pérez López, and Simon Rumle Tarnow.
In Proceedings of the 33rd International Symposium on String Processing and Information Retrieval, 2026. [draft of full version]

Data Stream Algorithms Unplugged.
Philip Bille and Inge Li Gørtz.
In Proceedings of the 8th Conference on Creative Mathematical Sciences Communication, 2026.

The Local/Global Disk Problem: How to Use Shared High-Bandwidth Storage Economically.
Michael A. Bender, Philip Bille, Martin Farach-Colton, Jeremy Fineman, Inge Li Gørtz, Michael Goodrich, Hanna Komlós, Bradley C. Kuszmaul, William Kuszmaul, Rose Silver, Todd Veldhuisen, and Renfei Zhou.
In Proceedings of the 38th Symposium on Parallelism in Algorithms and Architectures, 2026.
Outstanding Paper Award.

From Relative Compression to Hierarchical Compression.
Philip Bille, Inge Li Gørtz, and Máximo Pérez López.
In Proceedings of the 24th Symposium on Experimental Algorithms, 2026.

Compact Data Structures for Collections of Sets.
Jarno N. Alanko, Philip Bille, Inge Li Gørtz, Gonzalo Navarro, and Simon J. Puglisi.
In Proceedings of the From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday, 2025.

Differentially Private Substring and Document Counting.
Giulia Bernardini, Philip Bille, Inge Li Gørtz, and Teresa Anna Steiner.
In Proceedings of the 44th Symposium on Principles of Database Systems, 2025. [draft of full version]
Best Newcomer Award, SIGMOD Research Highlight Award 2026, and highlight talk at CPM 2026.

Text Indexing for Simple Regular Expressions.
Hideo Bannai, Philip Bille, Inge Li Gørtz, Gad M. Landau, Gonzalo Navarro, Teresa Anna Steiner, and Simon Rumle Tarnow.
In Proceedings of the 36th Symposium on Combinatorial Pattern Matching, 2025.

Succinct Data Structures for Segments.
Philip Bille, Inge Li Gørtz, and Simon Rumle Tarnow.
In Proceedings of the 36th Symposium on Combinatorial Pattern Matching, 2025. [draft of full version]

Compressed Dictionary Matching on Run-Length Encoded Strings.
Philip Bille, Inge Li Gørtz, Simon J. Puglisi, and Simon Rumle Tarnow.
In Algorithmica, special issue on CPM 2025, volume 88(50), 2026.
Conference version:
Compressed Dictionary Matching on Run-Length Encoded Strings.
Philip Bille, Inge Li Gørtz, Simon J. Puglisi, and Simon Rumle Tarnow.
In Proceedings of the 36th Symposium on Combinatorial Pattern Matching, 2025.

Toward Greener Matrix Operations by Lossless Compressed Formats.
Francesco Tosoni, Philip Bille, Valerio Brunacci, Alessio De Angelis, Paolo Ferragina, and Giovanni Manzini.
In IEEE Access, volume 13, pages 56756-56779, 2025.

Dynamic Range Minimum Queries on the Ultra-Wide Word RAM.
Philip Bille, Inge Li Gørtz, Máximo Pérez López, and Tord Stordalen.
In Information and Computation, 2026.
Conference version:
Dynamic Range Minimum Queries on the Ultra-Wide Word RAM.
Philip Bille, Inge Li Gørtz, Máximo Pérez López, and Tord Stordalen.
In Proceedings of the 50th International Conference on Current Trends in Theory and Practice of Computer Science, 2025.

Fast Practical Compression of Deterministic Finite Automata.
Philip Bille, Inge Li Gørtz, and Max Rishøj Pedersen.
In Proceedings of the 50th International Conference on Current Trends in Theory and Practice of Computer Science, 2025. [draft of full version]

Faster Sliding Window String Indexing in Streams.
Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, and Simon Rumle Tarnow.
In Proceedings of the 35th Symposium on Combinatorial Pattern Matching, 2024.

Tight Bounds for Compressing Substring Samples.
Philip Bille, Christian Mikkelsen Fuglsang, and Inge Li Gørtz.
In Proceedings of the 35th Symposium on Combinatorial Pattern Matching, 2024.

Size-constrained Weighted Ancestors with Applications.
Philip Bille, Yakov Nekrich, and Solon P. Pissis.
In Proceedings of the 19th Scandinavian Workshop and Symposium on Algorithms, 2024. [draft of full version]

Snake in Optimal Space and Time.
Philip Bille, Martin Farach-Colton, Inge Li Gørtz, and Ivor van der Hoog.
In Proceedings of the 12th International Conference on Fun with Algorithms, 2024. [slides]

Rank and Select on Degenerate Strings.
Philip Bille, Inge Li Gørtz, and Tord Stordalen.
In Proceedings of the 34th Data Compression Conference, 2024. [draft of full version]

Gapped String Indexing in Subquadratic Space and Sublinear Query Time.
Philip Bille, Inge Li Gørtz, Moshe Lewenstein, Solon P. Pissis, Eva Rotenberg, and Teresa Anna Steiner.
In Proceedings of the 41st Symposium on Theoretical Aspects of Computer Science, 2024. [draft of full version,slides]
Highlight talk at CPM 2024.

Sparse Regular Expression Matching.
Philip Bille and Inge Li Gørtz.
In Proceedings of the 35th Symposium on Discrete Algorithms, 2024. [draft of full version]

Hierarchical Relative Lempel-Ziv Compression.
Philip Bille, Inge Li Gørtz, Simon J. Puglisi, and Simon Rumle Tarnow.
In Proceedings of the 21st Symposium on Experimental Algorithms, 2023.

Sliding Window String Indexing in Streams.
Philip Bille, Johannes Fischer, Inge Li Gørtz, Max Rishøj Pedersen, and Tord Stordalen.
In Proceedings of the 34th Symposium on Combinatorial Pattern Matching, 2023. [draft of full version]

The Complexity of the Co-Occurrence Problem.
Philip Bille, Inge Li Gørtz, and Tord Stordalen.
In Proceedings of the 29th International Symposium on String Processing and Information Retrieval, 2022. [draft of full version]

Predecessor on the Ultra-Wide Word RAM.
Philip Bille, Inge Li Gørtz, and Tord Stordalen.
In Algorithmica, volume 86(5), pages 1578-1599, 2024.
Conference version:
Predecessor on the Ultra-Wide Word RAM.
Philip Bille, Inge Li Gørtz, and Tord Stordalen.
In Proceedings of the 18th Scandinavian Workshop and Symposium on Algorithms, 2022.

The Fine-Grained Complexity of Episode Matching.
Philip Bille, Inge Li Gørtz, Shay Mozes, Teresa Anna Steiner, and Oren Weimann.
In Proceedings of the 33rd Symposium on Combinatorial Pattern Matching, 2022.

Gapped Indexing for Consecutive Occurrences.
Philip Bille, Inge Li Gørtz, Max Rishøj Pedersen, and Teresa Anna Steiner.
In Algorithmica, volume 85(4), pages 879-901, 2023.
Conference version:
Gapped Indexing for Consecutive Occurrences.
Philip Bille, Inge Li Gørtz, Max Rishøj Pedersen, and Teresa Anna Steiner.
In Proceedings of the 40th Symposium on Combinatorial Pattern Matching, 2021.

String Indexing for Top-k Close Consecutive Occurrences.
Philip Bille, Inge Li Gørtz, Max Rishøj Pedersen, Eva Rotenberg, and Teresa Anna Steiner.
In Theoretical Computer Science, volume 927, pages 133-147, 2023.
Conference version:
String Indexing for Top-k Close Consecutive Occurrences.
Philip Bille, Inge Li Gørtz, Max Rishøj Pedersen, Eva Rotenberg, and Teresa Anna Steiner.
In Proceedings of the 32nd Conference on Foundations of Software Technology and Theoretical Computer Science, 2020.

Random Access in Persistent Strings and Segment Selection.
Philip Bille and Inge Li Gørtz.
In Theory of Computing Systems, volume 67, pages 694-713, 2022.
Conference version:
Random Access in Persistent Strings.
Philip Bille and Inge Li Gørtz.
In Proceedings of the 31st International Symposium on Algorithms and Computation, 2020. [slides]

Partial Sums on the Ultra-Wide Word RAM.
Philip Bille, Inge Li Gørtz, and Frederik Rye Skjoldjensen.
In Theoretical Computer Science, volume 905, pages 99-105, 2022.
Conference version:
Partial Sums on the Ultra-Wide Word RAM.
Philip Bille, Inge Li Gørtz, and Frederik Rye Skjoldjensen.
In Proceedings of the 16th Theory and Applications of Models of Computation, 2020. [slides]

Space Efficient Construction of Lyndon Arrays in Linear Time.
Philip Bille, Jonas Ellert, Johannes Fischer, Inge Li Gørtz, Florian Kurpicz, J. Ian Munro, and Eva Rotenberg.
In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020. [draft of full version]

Decompressing Lempel-Ziv Compressed Text.
Philip Bille, Mikko Berggren Ettienne, Travis Gagie, Inge Li Gørtz, and Nicola Prezza.
In Proceedings of the 31st Data Compression Conference, 2020. [draft of full version]

String Indexing with Compressed Patterns.
Philip Bille, Inge Li Gørtz, and Teresa Anna Steiner.
In ACM Transactions on Algorithms, volume 19(4), 2023.
Conference version:
String Indexing with Compressed Patterns.
Philip Bille, Inge Li Gørtz, and Teresa Anna Steiner.
In Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science, 2020.

Top Tree Compression of Tries.
Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, Gad M. Landau, and Oren Weimann.
In Algorithmica, volume 83(12), pages 3602-3628, 2021.
Conference version:
Top Tree Compression of Tries.
Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, Gad M. Landau, and Oren Weimann.
In Proceedings of the 30th International Symposium on Algorithms and Computation, pages 4:1-4:18, 2019.

From Regular Expression Matching to Parsing.
Philip Bille and Inge Li Gørtz.
In Acta Informatica, volume 59(6), pages 709-724, 2022.
Conference version:
From Regular Expression Matching to Parsing.
Philip Bille and Inge Li Gørtz.
In Proceedings of the 44th Symposium on Mathematical Foundations of Computer Science, pages 71:1-71:14, 2019. [slides]

Compressed Communication Complexity of Longest Common Prefixes.
Philip Bille, Mikko Berggren Ettienne, Roberto Grossi, Inge Li Gørtz, and Eva Rotenberg.
In Proceedings of the 25th International Symposium on String Processing and Information Retrieval, pages 74-87, 2018. [draft of full version,slides]

A Separation Between RLSLPs and LZ77.
Philip Bille, Travis Gagie, Inge Li Gørtz, and Nicola Prezza.
In Journal of Discrete Algorithms, volume 50, pages 36-39, 2018.

Succinct Partial Sums and Fenwick Trees.
Philip Bille, Anders Roy Christiansen, Nicola Prezza, and Frederik Rye Skjoldjensen.
In Proceedings of the 24th International Symposium on String Processing and Information Retrieval, pages 91-96, 2017. [draft of full version]

Tight Bounds for Top Tree Compression.
Philip Bille, Finn Fernstrøm, and Inge Li Gørtz.
In Proceedings of the 24th International Symposium on String Processing and Information Retrieval, pages 97-102, 2017.

Fast Dynamic Arrays.
Philip Bille, Anders Roy Christiansen, Mikko Berggren Ettienne, and Inge Li Gørtz.
In Proceedings of the 24th European Symposium on Algorithms, pages 16:1-16:17, 2017.

Immersive Algorithms: Better Visualization with Less Information.
Philip Bille and Inge Li Gørtz.
In Proceedings of the 22nd Innovation and Technology in Computer Science Education, pages 80-81, 2017. [slides]

Lempel-Ziv Compression in a Sliding Window.
Philip Bille, Patrick Hagge Cording, Johannes Fischer, and Inge Li Gørtz.
In Proceedings of the 28th Symposium on Combinatorial Pattern Matching, pages 15:1-15:11, 2017.

Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing.
Philip Bille, Mikko Berggren Ettienne, Inge Li Gørtz, and Hjalte Wedel Vildhøj.
In Theoretical Computer Science, volume 713, pages 66-77, 2018.
Conference version:
Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing.
Philip Bille, Mikko Berggren Ettienne, Inge Li Gørtz, and Hjalte Wedel Vildhøj.
In Proceedings of the 28th Symposium on Combinatorial Pattern Matching, pages 16:1-16:17, 2017.

Deterministic Indexing for Packed Strings.
Philip Bille, Inge Li Gørtz, and Frederik Rye Skjoldjensen.
In Proceedings of the 28th Symposium on Combinatorial Pattern Matching, pages 6:1-6:11, 2017. [draft of full version]

Space-Efficient Re-Pair Compression.
Philip Bille, Inge Li Gørtz, and Nicola Prezza.
In Proceedings of the 26th Data Compression Conference, pages 171-180, 2017. [draft of full version]

Finger Search in Grammar-Compressed Strings.
Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording, and Inge Li Gørtz.
In Theory of Computing Systems, volume 62(8), pages 1715-1735, 2018.
Conference version:
Finger Search in Grammar-Compressed Strings.
Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording, and Inge Li Gørtz.
In Proceedings of the 36th Conference on Foundations of Software Technology and Theoretical Computer Science, pages 36:1-36:16, 2016. [slides]

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, and Søren Vind.
In Algorithmica, volume 80(11), pages 3207-3224, 2018.
Conference version:
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, and Søren Vind.
In Proceedings of the 27th International Symposium on Algorithms and Computation, pages 18:1-18:13, 2016.

Boxed Permutation Pattern Matching.
Mika Amit, Philip Bille, Patrick Hagge Cording, Inge Li Gørtz, and Hjalte Wedel Vildhøj.
In Proceedings of the 27th Symposium on Combinatorial Pattern Matching, pages 20:1-20:11, 2016.

Subsequence Automata with Failure Transitions.
Philip Bille, Inge Li Gørtz, and Frederik Rye Skjoldjensen.
In Journal of Discrete Algorithms, pages 48-55, 2017.
Conference version:
Subsequence Automata with Failure Transitions.
Philip Bille, Inge Li Gørtz, and Frederik Rye Skjoldjensen.
In Proceedings of the 42nd International Conference on Current Trends in Theory and Practice of Computer Science, pages 208-216, 2016.

Longest Common Extensions in Sublinear Space.
Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen, Moshe Lewenstein, and Hjalte Wedel Vildhøj.
In Proceedings of the 26th Symposium on Combinatorial Pattern Matching, pages 65-76, 2015. [draft of full version]

Longest Common Extensions in Trees.
Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, Gad M. Landau, and Oren Weimann.
In Theoretical Computer Science, volume 638, pages 98-107, 2016.
Pattern Matching, Text Data Structures and Compression — Special issue in honor of the 60th birthday of Amihood Amir.
Conference version:
Longest Common Extensions in Trees.
Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, Gad M. Landau, and Oren Weimann.
In Proceedings of the 26th Symposium on Combinatorial Pattern Matching, pages 52-64, 2015.

On Regular Expression Matching and Deterministic Finite Automata.
Philip Bille.
In Tiny Transactions on Computer Science, volume 3, 2015.

Compressed Data Structures for Range Reporting.
Philip Bille, Inge Li Gørtz, and Søren Vind.
In Proceedings of the 9th International Conference on Language and Automata Theory and Applications, pages 577-586, 2015.

Indexing Motion Detection Data for Surveillance Video.
Søren Vind, Philip Bille, and Inge Li Gørtz.
In Proceedings of the 14th International Symposium on Multimedia, pages 24-27, 2014.

Compressed Subsequence Matching and Packed Tree Coloring.
Philip Bille, Patrick Hagge Cording, and Inge Li Gørtz.
In Algorithmica, volume 77(2), pages 336-348, 2017.
Conference version:
Compressed Subsequence Matching and Packed Tree Coloring.
Philip Bille, Patrick Hagge Cording, and Inge Li Gørtz.
In Proceedings of the 25th Symposium on Combinatorial Pattern Matching, pages 40-49, 2014.

Fingerprints in Compressed Strings.
Philip Bille, Patrick Hagge Cording, Inge Li Gørtz, Benjamin Sach, Hjalte Wedel Vildhøj, and Søren Vind.
In Journal of Computer and System Sciences, volume 86, pages 171-180, 2017.
Conference version:
Fingerprints in Compressed Strings.
Philip Bille, Patrick Hagge Cording, Inge Li Gørtz, Benjamin Sach, Hjalte Wedel Vildhøj, and Søren Vind.
In Proceedings of the 13th Algorithms and Data Structures Symposium, pages 146-157, 2013.

Tree Compression with Top Trees.
Philip Bille, Inge Li Gørtz, Gad M. Landau, and Oren Weimann.
In Information and Computation, special issue on ICALP 2013, volume 243, pages 166-177, 2015.
Conference version:
Tree Compression with Top Trees.
Philip Bille, Inge Li Gørtz, Gad M. Landau, and Oren Weimann.
In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming, pages 160-171, 2013. [slides]

Sparse Text Indexing in Small Space.
Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, and Hjalte Wedel Vildhøj.
In ACM Transactions on Algorithms, volume 12(3), pages 39:1-39:19, 2016.
Conference version:
Sparse Suffix Tree Construction with Small Space.
Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, and Hjalte Wedel Vildhøj.
In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming, pages 148-159, 2013.

Compact q-Gram Profiling of Compressed Strings.
Philip Bille, Patrick Hagge Cording, and Inge Li Gørtz.
In Theoretical Computer Science, volume 550, pages 51-58, 2014.
Conference version:
Compact q-Gram Profiling of Compressed Strings.
Philip Bille, Patrick Hagge Cording, and Inge Li Gørtz.
In Proceedings of the 24th Symposium on Combinatorial Pattern Matching, pages 62-73, 2013.

String Indexing for Patterns with Wildcards.
Philip Bille, Inge Li Gørtz, Hjalte Wedel Vildhøj, and Søren Vind.
In Theory of Computing Systems, volume 55(1), pages 41-60, 2014.
Conference version:
String Indexing for Patterns with Wildcards.
Philip Bille, Inge Li Gørtz, Hjalte Wedel Vildhøj, and Søren Vind.
In Proceedings of the 13th Scandinavian Workshop and Symposium on Algorithms, pages 283-294, 2012.

Time-Space Trade-Offs for Longest Common Extensions.
Philip Bille, Inge Li Gørtz, Benjamin Sach, and Hjalte Wedel Vildhøj.
In Journal of Discrete Algorithms, special issue on CPM 2012, volume 25, pages 42-50, 2014.
Conference version:
Time-Space Trade-Offs for Longest Common Extensions.
Philip Bille, Inge Li Gørtz, Benjamin Sach, and Hjalte Wedel Vildhøj.
In Proceedings of the 23rd Symposium on Combinatorial Pattern Matching, pages 293-305, 2012.

Fast and Cache-Oblivious Dynamic Programming with Local Dependencies.
Philip Bille and Morten Stöckel.
In Proceedings of the 6th International Conference on Language and Automata Theory and Applications, pages 131-142, 2012.

Longest Common Extensions via Fingerprinting.
Philip Bille, Inge Li Gørtz, and Jesper Kristensen.
In Proceedings of the 6th International Conference on Language and Automata Theory and Applications, pages 119-130, 2012.

Towards Optimal Packed String Matching.
Oren Ben-Kiki, Philip Bille, Dany Breslauer, Leszek Gąsieniec, Roberto Grossi, and Oren Weimann.
In Theoretical Computer Science, volume 525, pages 111-129, 2014.
Advances in Stringology - Special issue dedicated to Professor Gad M. Landau, on the occasion of his 60th birthday.
Conference version:
Optimal Packed String Matching.
Oren Ben-Kiki, Philip Bille, Dany Breslauer, Leszek Gąsieniec, Roberto Grossi, and Oren Weimann.
In Proceedings of the 31st Conference on Foundations of Software Technology and Theoretical Computer Science, pages 423-432, 2011.

Substring Range Reporting.
Philip Bille and Inge Li Gørtz.
In Algorithmica, volume 69(2), pages 384-396, 2014.
Conference version:
Substring Range Reporting.
Philip Bille and Inge Li Gørtz.
In Proceedings of the 22nd Symposium on Combinatorial Pattern Matching, pages 299-308, 2011. [slides]

Random Access to Grammar-Compressed Strings and Trees.
Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, and Oren Weimann.
In SIAM Journal of Computation, volume 44(3), pages 513-539, 2015.
Conference version:
Random Access to Grammar-Compressed Strings.
Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, and Oren Weimann.
In Proceedings of the 22nd Symposium on Discrete Algorithms, pages 373-389, 2011. [slides]

String Matching with Variable Length Gaps.
Philip Bille, Inge Li Gørtz, Hjalte Wedel Vildhøj, and David Kofoed Wind.
In Theoretical Computer Science, volume 443, pages 25-34, 2012.
Conference version:
String Matching with Variable Length Gaps.
Philip Bille, Inge Li Gørtz, Hjalte Wedel Vildhøj, and David Kofoed Wind.
In Proceedings of the 17th International Symposium on String Processing and Information Retrieval, pages 385-394, 2010.

Fast Arc-Annotated Subsequence Matching in Linear Space.
Philip Bille and Inge Li Gørtz.
In Algorithmica, volume 62(1-2), pages 209-223, 2012.
Conference version:
Fast Arc-Annotated Subsequence Matching in Linear Space.
Philip Bille and Inge Li Gørtz.
In Proceedings of the 36th International Conference on Current Trends in Theory and Practice of Computer Science, pages 188-199, 2010.

Regular Expression Matching with Multi-Strings and Intervals.
Philip Bille and Mikkel Thorup.
In Proceedings of the 21st Symposium on Discrete Algorithms, pages 1297-1308, 2010. [slides]
Also USPTO patent 20110153641.

Faster Regular Expression Matching.
Philip Bille and Mikkel Thorup.
In Proceedings of the 36th International Colloquium on Automata, Languages, and Programming, pages 171-182, 2009. [slides]

Fast Searching in Packed Strings.
Philip Bille.
In Journal of Discrete Algorithms, special issue on CPM 2009, volume 9(1), pages 49-56, 2011.
Conference version:
Fast Searching in Packed Strings.
Philip Bille.
In Proceedings of the 20th Symposium on Combinatorial Pattern Matching, pages 116-126, 2009. [slides]

Faster Approximate String Matching for Short Patterns.
Philip Bille.
In Theory of Computing Systems, volume 50(3), pages 492-515, 2012.
First appeared as Arxiv preprint in 2008.

Fast Evaluation of Union-Intersection Expressions.
Philip Bille, Anna Pagh, and Rasmus Pagh.
In Proceedings of the 18th International Symposium on Algorithms and Computation, pages 739-750, 2007. [draft of full version,slides]

Pattern Matching in Trees and Strings.
Philip Bille.
PhD dissertation, IT University of Copenhagen, 2007. [slides]

Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts.
Philip Bille, Rolf Fagerberg, and Inge Li Gørtz.
In ACM Transactions on Algorithms, volume 6(1), pages 1-14, 2009.
Conference version:
Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts.
Philip Bille, Rolf Fagerberg, and Inge Li Gørtz.
In Proceedings of the 18th Symposium on Combinatorial Pattern Matching, pages 52-62, 2007. [slides]

Matching 2D Shapes using their Symmetry Sets.
Arjan Kuijper, Ole Fogh Olsen, Peter Giblin, and Philip Bille.
In Proceedings of the 18th International Conference of Pattern Recognition, pages 179-182, 2006.

New Algorithms for Regular Expression Matching.
Philip Bille.
In Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming, pages 643-654, 2006. [draft of full version,slides]

Matching Subsequences in Trees.
Philip Bille and Inge Li Gørtz.
In Journal of Discrete Algorithms, special issue on CIAC 2006, volume 7(3), pages 306-314, 2009.
Conference version:
Matching Subsequences in Trees.
Philip Bille and Inge Li Gørtz.
In Proceedings of the 6th International Conference on Algorithms and Complexity, pages 248-259, 2006. [slides]

Fast and Compact Regular Expression Matching.
Philip Bille and Martin Farach-Colton.
In Theoretical Computer Science, volume 409(3), pages 486-496, 2008.
First appeared as Arxiv preprint in 2005.

The Tree Inclusion Problem: In Linear Space and Faster.
Philip Bille and Inge Li Gørtz.
In ACM Transactions on Algorithms, volume 7(3), pages 1-47, 2011.
Conference version:
The Tree Inclusion Problem: In Optimal Space and Faster.
Philip Bille and Inge Li Gørtz.
In Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming, pages 66-77, 2005. [slides]

From a 2D Shape to a String Structure using the Symmetry Set.
Arjan Kuijper, Ole Fogh Olsen, Peter Giblin, Philip Bille, and Mads Nielsen.
In Proceedings of the 8th European Conference on Computer Vision, pages 313-325, 2004.

A Survey on Tree Edit Distance and Related Problems.
Philip Bille.
In Theoretical Computer Science, volume 337(1-3), pages 217-239, 2005.
First appeared as IT University of Copenhagen technical report in 2003.

Labeling Schemes for Short Distances in Trees.
Stephen Alstrup, Philip Bille, and Theis Rauhe.
In SIAM Journal of Discrete Mathematics, volume 19(2), pages 448-462, 2005.
Conference version:
Labeling Schemes for Short Distances in Trees.
Stephen Alstrup, Philip Bille, and Theis Rauhe.
In Proceedings of the 14th Symposium on Discrete Algorithms, pages 689-698, 2003. [slides]