Publications

Listed in approximate reverse chronological order of first appearence

Succint 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, 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, 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, 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, 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, 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 Proceedings of the 28th Symposium on Combinatorial Pattern Matching, 2017. [draft of full version]

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, 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, 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 Proceedings of the 36th Conference on Foundations of Software Technology and Theoretical Computer Science, 2016. [draft of full version,slides]

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, 2016. [draft of full version]

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, 2016.

Subsequence Automata with Failure Transitions.
Philip Bille, Inge Li Gørtz, and Frederik Rye Skjoldjensen.
In Journal of Discrete Algorithms, 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, 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, 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, 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 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, to appear.
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, 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), 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]