Academic publications
I was active in academic research from 1998 to 2016. This page lists my publications from that time. Some appeared in later years or even have not yet appeared, as a result of the lengthy publication process.
My academic publications are also listed in the DBLP database; that is a less complete list but has some useful search features.
Author lists marked with an asterisk are in venues that standardize on alphabetical ordering of authors; all authors rank equally with no special status of "senior" or "first" author in such venues.
Pending journal submissions as of March 2019
Durocher, S.; Fraser, R.; Leblanc, A.; Morrison, J.; and Skala, M.* 2015. On Combinatorial Depth Measures. Accepted to International Journal of Computational Geometry and Applications October 2018.
Bose, P.; Durocher, S.; Mondal, D.; Peabody, M.; Skala, M.; and Wahid, M. A.* 2015. Local routing in convex subdivisions. Submitted to International Journal of Computational Geometry and Applications June 2015.
2017
Durocher, S.; Leblanc, A.; and Skala, M.* 2017. The Projection Median as a Weighted Average. Journal of Computational Geometry, 8(1):pp. 78-104. [BiBTeX] [Journal page]
Pagh, R.; Silvestri, F.; Sivertsen, J.; and Skala, M.* 2017. Approximate furthest neighbor with application to annulus query. Information Systems, 64:pp. 152-162. [BiBTeX] [Journal page] [arXiv]
2016
Skala, M. 2016. Bit-vector search filtering with application to a kanji dictionary. In 9th International Conference on Similarity Search and Applications (SISAP 2016), Tokyo, Japan, October 24-26, 2016. vol. 9939 of Lecture Notes in Computer Science, pp. 137-150. Springer. [BiBTeX] [Conference home] [Springer DOI]
Skala, M. 2016. Astrological charts with horoscop and starfont. TUGboat, 37(2):p. 182. Proceedings of the 37th Annual Meeting of the TeX Users Group (TUG 2016), Toronto, Ontario, July 25-27, 2016. [BiBTeX] [Journal PDF] [Journal contents] [Presentation slides] [Presentation video]
Durocher, S.; Shah, R.; Skala, M.; and Thankachan, S. V.* 2016. Linear-space data structures for range frequency queries on arrays and trees. Algorithmica, 74(1):pp. 344-366. [BiBTeX] [Springer DOI]
2015
Skala, M. 2015. A Structural Query System for Han Characters. International Journal of Asian Language Processing, 23(2):pp. 127-159. The journal has subsequently changed its numbering to make this Volume 25. [BiBTeX] [Publisher's PDF]
Durocher, S.; Gunderson, D. S.; Li, P. C.; and Skala, M.* 2015. Cycle-maximal triangle-free graphs. Discrete Mathematics, 338(2):pp. 274-290. [arXiv preprint] [Elsevier DOI]
Chan, T. M.; Durocher, S.; Skala, M.; and Wilkinson, B. T.* 2015. Linear-space data structures for range minority query in arrays. Algorithmica, 72(4):pp. 901-913. [Springer DOI]
Pagh, R.; Silvestri, F.; Sivertsen, J.; and Skala, M.* 2015. Approximate furthest neighbor in high dimensions. In 8th International Workshop on Similarity Search and Applications (SISAP 2015), Glasgow, Scotland, October 12-14, 2015. vol. 9371 of Lecture Notes in Computer Science, pp. 3-14. Springer. [BiBTeX] [Conference home] [Springer DOI]
Bose, P.; Durocher, S.; Mondal, D.; Skala, M.; and Wahid, M. A.* 2015. Local routing in convex subdivisions. In 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2015), Pec pod Sněžkou, Czech Republic, January 24-29, 2015, vol. 8939 of Lecture Notes in Computer Science, pp. 140-151. Springer. [BiBTeX]
2014
Durocher, S.; Fraser, R.; Leblanc, A.; Morrison, J.; and Skala, M.* 2014. On combinatorial depth measures. In 26th Canadian Conference on Computational Geometry (CCCG 2014), Halifax, Nova Scotia, August 11-13, 2014, pp. 198-205. [official PDF]
Skala, M. 2014. Cycle-maximal graphs of fixed girth. In 2014 Canadian Mathematical Society Summer Meeting, Winnipeg, Manitoba, June 6-9, 2014. [BiBTeX] [PDF abstract]
Durocher, S.; Fraser, R.; Gagie, T.; Mondal, D.; Skala, M.; and Thankachan, S.* 2014. Indexed geometric jumbled pattern matching. In 25th Annual Symposium on Combinatorial Pattern Matching (CPM 2014), Moscow, Russia, June 16-18, 2014, vol. 8486 of Lecture Notes in Computer Science, pp. 110-119. Springer. [BiBTeX] [Conference home]
Dorrigiv, R.; Durocher, S.; Farzan, A.; Fraser, R.; López-Ortiz, A.; Munro, J. I.; Salinger, A.; and Skala, M.* 2014. The Hausdorff core problem on simple polygons. Journal of Computational Geometry, 5(1):pp. 14-40. [BiBTeX] [official posting]
Durocher, S.; Leblanc, A.; Morrison, J.; and Skala, M.* 2014. Robust nonparametric simplification of polygonal chains. International Journal of Computational Geometry and Applications, 23(6):pp. 427-441. [BiBTeX] [World Scientific DOI] [arXiv preprint]
Skala, M. 2014. Tsukurimashou: a Japanese-language font meta-family. TUGboat, 34(3):pp. 269-278. Proceedings of the 34th Annual Meeting of the TeX Users Group (TUG 2013), Tokyo, Japan, October 23-26, 2013. [BiBTeX] [Journal PDF] [Journal contents] [Slides]
2013
Skala, M. 2013. Array range queries. In Conference on Space Efficient Data Structures, Streams and Algorithms (IanFest 66), Waterloo, Ontario, August 15-16, 2013, vol. 8066 of Lecture Notes in Computer Science, pp. 333-350. Springer. [BiBTeX] [Springer DOI] [PDF preprint] [Conference] Required notice: "The original publication is available at www.springerlink.com."
Durocher, S.; Shah, R.; Skala, M.; and Thankachan, S. V.* 2013. Top-k Color Queries On Tree Paths. In 20th String Processing and Information Retrieval Symposium (SPIRE 2013), Jerusalem, Israel, October 7-9, 2013, vol. 8214 of Lecture Notes in Computer Science, pp. 109-115. Springer. [BiBTeX] [Springer DOI] [PDF preprint] [Conference] Required notice: "The original publication is available at www.springerlink.com."
Durocher, S.; Shah, R.; Skala, M.; and Thankachan, S. V.* 2013. Linear-Space Data Structures for Range Frequency Queries on Arrays and Trees. In 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), Klosterneuberg, Austria, August 26-30 2013, vol. 8087 of Lecture Notes in Computer Science, pp. 325-336. Springer. [BiBTeX] [Springer DOI] [PDF preprint] [Program] Required notice: "The original publication is available at www.springerlink.com."
Barba, L.; Durocher, S.; Fraser, R.; Hurtado, F.; Mehrabi, S.; Mondal, D.; Morrison, J.; Skala, M.; and Wahid, M. A.* 2013. On k-enclosing objects in a coloured point set. In 25th Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Ontario, August 8-10, 2013, pp. 229-234. [BiBTeX] [official PDF of complete proceedings (warning, large!)] [unofficial PDF of just our paper] [Conference]
Durocher, S.; He, M.; Munro, J. I.; Nicholson, P. K.; and Skala, M.* 2013. Range majority in constant time and linear space. Information and Computation, 222(January 2013):pp. 169-179. [BiBTeX] [Elsevier DOI] [PDF preprint]
2012
Durocher, S.; Leblanc, A.; Morrison, J.; and Skala, M.* 2012. Robust non-parametric data approximation of pointsets via data reduction. In 23rd International Symposium on Algorithms and Computation (ISAAC 2012), Taipei, Taiwan, December 19-21, 2012, vol. 7676 of Lecture Notes in Computer Science, pp. 319-331. Springer. [BiBTeX] [Springer DOI] [PDF preprint] Required notice: "The original publication is available at www.springerlink.com."
Durocher, S.; Mehrabi, S.; Skala, M.; and Wahid, M. A.* 2012. The cover contact graph of discs touching a line. In 24th Canadian Conference on Computational Geometry (CCCG 2012), Charlottetown, P.E.I., August 8-10, 2012, pp. 67-72. [BiBTeX] [PDF (open access)]
Chan, T. M.; Durocher, S.; Skala, M.; and Wilkinson, B. T.* 2012. Linear-space data structures for range minority query in arrays. In 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012), Helsinki, Finland, July 4-6, 2012, vol. 7357 of Lecture Notes in Computer Science, pp. 295-306. Springer. [BiBTeX] [Springer DOI] [PDF preprint] Required notice: "The original publication is available at www.springerlink.com."
2011
Skala, M.; and Penn, G. 2011. Approximate Bit Vectors for Fast Unification. In 12th Meeting on Mathematics of Language (MOL 12), Nara, Japan, September 6-8, 2011, vol. 6878 of Lecture Notes in Computer Science, pp. 158-173. Springer. [BiBTeX] [Springer DOI] [PDF preprint] Required notice: "The original publication is available at www.springerlink.com."
Durocher, S.; Mehrabi, S.; Mondal, D.; and Skala, M.* 2011. Realizing site permutations. In 23rd Canadian Conference on Computational Geometry (CCCG 2011), Toronto, Ontario, August 10-12, 2011, pp. 355-360. [BiBTeX] [paper PDF] [slides PDF] [talk MP3]
Durocher, S.; He, M.; Munro, I.; Nicholson, P.; and Skala, M.* 2011. Range majority in constant time and linear space. In 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), Zürich, Switzerland, July 4-8, 2011, Proceedings, Part I, vol. 6755 of Lecture Notes in Computer Science, pp. 244-255. Springer. [BiBTeX] [Springer DOI] [PDF preprint] Required notice: "The original publication is available at www.springerlink.com."
Arroyuelo, D.; Claude, F.; Dorrigiv, R.; Durocher, S.; He, M.; López-Ortiz, A.; Munro, J. I.; Nicholson, P. K.; Salinger, A.; and Skala, M.* 2011. Untangled monotonic chains and adaptive range search. Theoretical Computer Science 412(32):pp. 4200-4211. [BiBTeX] [Elsevier DOI] [PDF preprint]
Ross, G.; DiMarco, C.; Afros, E.; Hovy, E.; Malton, A. J.; Malton, A.; and Skala, M. 2011. A health rhetorical model for authoring personalized mobile health information. In AAAI 2011 Spring Symposium on AI and Health Communication, Palo Alto, California, USA, March 21-23, 2011. Demo session.
2010
Munro, I.; Claude, F.; Nicholson, P. K.; and Skala, M. 2010. Efficient computation of large scale geographic data. In Thinking Ahead for a Strong Future (CRC 10th Anniversary conference), Toronto, Ontario, November 24–25, 2010. Canada Research Chairs Program. Poster.
Skala, M.; Krakovna, V.; Kramár, J.; and Penn, G. 2010. A generalized-zero-preserving method for compact encoding of concept lattices. In 48th Annual Meeting of the Association for Computational Linguistics (ACL 2010), Uppsala, Sweden, July 11-16, 2010, pp. 1512-1521. Association for Computational Linguistics. [Publisher's PDF] [BiBTeX]
2009
Arroyuelo, D.; Claude, F.; Dorrigiv, R.; Durocher, S.; He, M.; López-Ortiz, A.; Munro, J. I.; Nicholson, P. K.; Salinger, A.; and Skala, M. 2009.* Untangled monotonic chains and adaptive range search. In Dong, Y.; Du, D.-Z.; and Ibarra, O., eds., 20th International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, Hawaii, USA, December 16-18, 2009, vol. 5878 of Lecture Notes in Computer Science, pp. 203-212. Springer. [BiBTeX] [SpringerLink DOI] [PDF preprint] [PDF slides] Required notice: "The original publication is available at www.springerlink.com."
Dorrigiv, R.; Durocher, S.; Farzan, A.; Fraser, R.; López-Ortiz, A.; Munro, J. I.; Salinger, A.; and Skala, M.* Finding a Hausdorff core of a polygon: On convex polygon containment with bounded Hausdorff distance. In Dehne, F. K. H. A.; Gavrilova, M. L.; Sack, J.-R.; and Tóth, C. D., eds., 11th International Symposium on Algorithms and Data Structures (WADS 2009), Banff, Alberta, August 21-23, 2009, vol. 5664 of Lecture Notes in Computer Science, pp. 218-229. Springer. [BiBTeX] [SpringerLink DOI] [PDF preprint] Required notice: "The original publication is available at www.springerlink.com."
Skala, M. 2009. Counting distance permutations. Journal of Discrete Algorithms, 7(1):pp. 49-61. [BiBTeX] [Elsevier DOI] [PDF preprint]
Skala, M. 2009. Constraint satisfaction in string spaces. In BIRS 09w5124: Mathematics of String Spaces and Algorithmic Applications, Banff, Alberta, January 25-30, 2009. Banff International Research Station. [BiBTeX] [PDF slides]
2008
Skala, M. A. 2008. Aspects of metric spaces in computation. PhD dissertation, University of Waterloo. [BiBTeX] [official deposit] [PDF]
Skala, M.; Bonfield, B.; and Torpey, M. F. Feb. 15, 2008. Enforcing copyright. Library Journal, 133(3):p. 28. [BiBTeX] [online article] [Web]
Skala, M. 2008. On the complexity of reverse similarity search. In Chávez, E. and Navarro, G., eds., First International Workshop on Similarity Search and Applications (SISAP 2008), Cancun, Mexico, April 11-12, 2008, pp. 149-156. IEEE. [BiBTeX] [PDF slides] [references BiBTeX]
Skala, M. 2008. Counting distance permutations. In Chávez, E. and Navarro, G., eds., First International Workshop on Similarity Search and Applications (SISAP 2008), Cancun, Mexico, April 11-12, 2008, pp. 69-76. IEEE. [BiBTeX] [PDF slides] [references BiBTeX]
2005
Skala, M. 2005. Measuring the difficulty of distance-based indexing. In Consens, M. P. and Navarro, G., eds., Proceedings of the 12th International Conference on String Processing and Information Retrieval (SPIRE 2005), Buenos Aires, Argentina, November 2-4, 2005, vol. 3772 of Lecture Notes in Computer Science, pp. 103-114. Springer. [BiBTeX] [SpringerLink DOI] [PDF] [references BiBTeX] Required notice: "The original publication is available at www.springerlink.com."
Skala, M. 2005. Balancing the books with fiat goods. In OpenCity 2005, Winnipeg, Manitoba, August 17-19, 2005. University of Winnipeg. Invited talk by video. [BiBTeX] [Lulu video]
2001
Skala, M. A. 2001. Generation of graphs embedded on the torus. MSc thesis, University of Victoria. [BiBTeX] [official deposit] [PDF]
Skala, M. and Myrvold, W. 2001. Fast generation of graphs embedded on the torus. In 32nd Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Baton Rouge, Louisiana, USA, February 26-March 2, 2001. [BiBTeX]
1999
Goodenough, D. G.; Charlebois, D.; Bhogal, A. S.; Dyk, A.; and Skala, M. 1999. SEIDAM: A flexible and interoperable metadata-driven system for intelligent forest monitoring. In Stein, T. I., ed., Proceedings of the International Geoscience and Remote Sensing Symposium 1999 (IGARSS'99), Hamburg, Germany, June 28-July 2, 1999, vol. 2, pp. 1338-1341. IEEE. [BiBTeX]
1998
Skala, M. 1998. A limited-diffusion algorithm for blind substring search. In Proceedings of the 10th Annual Canadian Information Technology Security Symposium, Ottawa, Ontario, June 1-8, 1998, pp. 397-410. Communications Security Establishment. Winner of Best Student Paper award. [BiBTeX] [PDF] [gzipped Postscript]
BiBTeX entries
@article{JoCG2017,
author = "Stephane Durocher and Alexandre Leblanc and Matthew Skala",
title = "The Projection Median as a Weighted Average",
year = "2017",
journal = "Journal of Computational Geometry",
volume = "8",
number = "1",
pages = "78--104",
}
@article{InfSyst2017,
author = "Rasmus Pagh and Francesco Silvestri and Johan Sivertsen and
Matthew Skala",
title = "Approximate furthest neighbour with application to annulus
query",
year = "2017",
journal = "Information Systems",
volume = "64",
pages = "152--162",
}
@article{Algorithmica2016,
author = "Stephane Durocher and Rahul Shah and Matthew Skala and
Sharma V. Thankachan",
title = "Linear-Space Data Structures for Range Frequency Queries
on Arrays and Trees",
year = "2016",
journal = "Algorithmica",
volume = "74",
number = "1",
}
@inproceedings{SISAP2016,
title = "Bit-Vector Search Filtering with Application to a Kanji
Dictionary",
author = "Matthew Skala",
booktitle = "Ninth International Conference on Similarity Search and
Applications {(SISAP 2016)},
Tokyo, Japan,
October 24--26, 2016",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
volume = "9939",
pages = "137--150",
}
@article{TUG2016,
author = "Matthew Skala",
title = "Astrological charts with horoscop and starfont",
journal = "TUGboat",
volume = "37",
number = "2",
pages = "182",
note = "Proceedings of the 37th Annual Meeting of the {\TeX}
Users Group {(TUG 2016)},
Toronto, Ontario,
July 25--27, 2016.",
year = "2016",
}
@article{IJALP2015,
author = "Matthew Skala",
title = "A Structural Query System for {Han} Characters",
year = "2015",
journal = "International Journal of Asian Language Processing",
volume = "23",
number = "2",
pages = "127--159",
}
@inproceedings{SISAP2015,
title = "Approximate Furthest Neighbor in High Dimensions",
author = "Rasmus Pagh and Francesco Silvestri and Johan Sivertsen
and Matthew Skala",
booktitle = "Eighth International Conference on Similarity Search and
Applications {(SISAP 2015)},
Glasgow, Scotland,
October 12--14, 2015",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
volume = "9371",
pages = "3--14",
}
@article{Algorithmica2015,
author = "Timothy M. Chan and Stephane Durocher and Matthew Skala
and Bryan T. Wilkinson",
title = "Linear-Space Data Structures for Range Minority
Query in Arrays",
year = "2015",
journal = "Algorithmica",
volume = "72",
number = "4",
pages = "901--913",
}
@inproceedings{SOFSEM2015,
author = "Prosenjit Bose and Stephane Durocher and Debajyoti Mondal
and Matthew Skala and Mohammad Abdul Wahid",
title = "Local Routing in Convex Subdivisions",
year = "2015",
booktitle = "41st International Conference on Current
Trends in Theory and Practice of Computer Science {(SOFSEM
2015)},
{Pec pod Sn{\v{e}}{\v{z}}kou}, Czech Republic,
January 24--29, 2015",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
volume = "8939",
pages = "140--151",
}
@article{IJCGA2014,
title = "Robust nonparametric simplification of polygonal chains",
author = "Durocher, Stephane and Leblanc, Alexandre and
Morrison, Jason and Skala, Matthew",
journal = "International Journal of Computational Geometry and
Applications",
volume = "23",
number = "6",
pages = "427--441",
year = "2013",
}
@inproceedings{CMS2014,
title = "Cycle-Maximal Graphs of Fixed Girth",
author = "Matthew Skala",
booktitle = "2014 Canadian Mathematical Society Summer Meeting,
Winnipeg, Manitoba, June 6--9, 2014",
year = "2014",
}
@inproceedings{CPM2014,
title = "Indexed Geometric Jumbled Pattern Matching",
author = "Stephane Durocher and Robert Fraser and Travis Gagie
and Debajyoti Mondal and Matthew Skala and Sharma
Thankachan",
year = "2014",
booktitle = "25th Annual Symposium on Combinatorial
Pattern Matching {(CPM 2014)},
Moscow, Russia,
June 16--18, 2014",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
volume = "8486",
pages = "110--119",
}
@article{JoCG2014,
title = "The {H}ausdorff Core Problem on Simple Polygons",
author = "Reza Dorrigiv and Stephane Durocher and Arash Farzan and
Robert Fraser and Alejandro L{\'o}pez-Ortiz and
J. Ian Munro and Alejandro Salinger and Matthew Skala",
year = "2014",
volume = "5",
number = "1",
pages = "14--40",
}
@article{TUG2013,
author = "Matthew Skala",
title = "Tsukurimashou: a {Japanese}-language font meta-family",
journal = "TUGboat",
volume = "34",
number = "3",
pages = "269--278",
note = "Proceedings of the 34th Annual Meeting of the {\TeX}
Users Group {(TUG 2013)},
Tokyo, Japan,
October 23--26, 2013.",
year = "2014",
}
@inproceedings{SPIRE2013,
author = "Stephane Durocher and Rahul Shah and Matthew Skala and
Sharma V. Thankachan",
title = "Top-$k$ Color Queries On Tree Paths",
year = "2013",
booktitle = "20th String Processing and Information Retrieval Symposium
{(SPIRE 2013)},
Jerusalem, Israel,
October 7--9, 2013",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
volume = "8214",
pages = "109--115",
}
@inproceedings{MFCS2013,
author = "Stephane Durocher and Rahul Shah and Matthew Skala and
Sharma V. Thankachan",
title = "Linear-Space Data Structures for Range Frequency Queries
on Arrays and Trees",
booktitle = "38th International Symposium on Mathematical Foundations
of Computer Science {(MFCS 2013)},
Klosterneuberg, Austria,
August 26--30, 2013",
year = "2013",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
volume = "8087",
pages = "325--336",
}
@inproceedings{IanFest2013,
author = "Matthew Skala",
title = "Array Range Queries",
booktitle = "Conference on Space Efficient Data Structures, Streams,
and Algorithms {(IanFest 66)},
Waterloo, Ontario,
August 15--16, 2013",
year = "2013",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
volume = "8066",
pages = "333--350",
}
@inproceedings{CCCG2013,
author = "Luis Barba and Stephane Durocher and Robert Fraser and
Ferran Hurtado and Saeed Mehrabi and Debajyoti Mondal
and Jason Morrison and Matthew Skala and Mohammad Abdul
Wahid",
title = "On $k$-Enclosing Objects in a Coloured Point Set",
year = "2013",
booktitle = "25th Canadian Conference on Computational Geometry
{(CCCG 2013)},
Waterloo, Ontario,
August 8--10, 2013",
pages = "229--234",
}
@article{ICALP2011J,
title = "Range majority in constant time and linear space",
journal = "Information and Computation",
author = "Stephane Durocher and Meng He and J. Ian Munro and
Patrick K. Nicholson and Matthew Skala",
volume = "222",
pages = "169--179",
year = "2013",
number = "January 2013",
abstract = "Given an array $A$ of size $n$, we consider the problem
of answering range majority queries: given a query range $[i\ldots j]$
where $1\le i\le j\le n$, return the majority element of the subarray
$A[i\ldots j]$ if it exists. We describe a linear space data structure
that answers range majority queries in constant time. We further
generalize this problem by defining range $\alpha$-majority queries:
given a query range $[i\ldots j]$, return all the elements in the
subarray $A[i\ldots j]$ with frequency greater than $\alpha (j−i+1)$.
We prove an upper bound on the number of $\alpha$-majorities that can
exist in a subarray, assuming that query ranges are restricted to be
larger than a given threshold. Using this upper bound, we generalize
our range majority data structure to answer range $\alpha$-majority
queries in $O(\frac{1}{\alpha})$ time using $O(n \lg
(\frac{1}{\alpha}+1))$ space, for any fixed $\alpha\in (0,1)$.
This result is interesting since other similar range query problems
based on frequency have nearly logarithmic lower bounds on query time
when restricted to linear space.",
}
@inproceedings{ISAAC2012,
author = "Stephane Durocher and Alexandre Leblanc and Jason Morrison
and Matthew Skala",
title = "Robust Nonparametric Data Approximation of Point Sets
via Data Reduction",
booktitle = "23rd International Symposium on Algorithms and Computation
{(ISAAC 2012)},
Taipei, Taiwan,
December 19--21, 2012",
year = "2012",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
volume = "7676",
pages = "319--331",
}
@inproceedings{CCCG2012,
title = "The Cover Contact Graph of Discs Touching a Line",
author = "Stephane Durocher and Saeed Mehrabi and Matthew Skala and
Mohammad Abdul Wahid",
booktitle = "24th Canadian Conference on Computational Geometry
{(CCCG 2012)},
Charlottetown, Prince Edward Island,
August 8--10, 2012",
pages = "67--72",
year = "2012",
}
@inproceedings{SWAT2012,
author = "Timothy M. Chan and Stephane Durocher and Matthew Skala
and Bryan T. Wilkinson",
title = "Linear-Space Data Structures for Range Minority
Query in Arrays",
booktitle = "13th Scandinavian Symposium and Workshops on Algorithm Theory
{(SWAT 2012)},
Helsinki, Finland,
July 4--6, 2012",
year = "2012",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
volume = "7357",
pages = "295--306",
}
@inproceedings{MOL2011,
author = "Matthew Skala and Gerald Penn",
title = "Approximate Bit Vectors for Fast Unification",
booktitle = "The Mathematics of Language: 12th Biennial Conference
{(MOL 12)},
Nara, Japan,
September 6--8, 2011",
year = "2011",
series = "Lecture Notes in Artificial Intelligence",
publisher = "Springer",
volume = "6878",
pages = "158--173",
}
@inproceedings{CCCG2011,
title = "Realizing site permutations",
author = "Stephane Durocher and Saeed Mehrabi and
Debajyoti Mondal and Matthew Skala",
booktitle = "23rd Canadian Conference on Computational Geometry
(CCCG 2011),
Toronto, Ontario,
August 10--12, 2011",
pages = "355--360",
year = "2011",
abstract = "Given $n$ fixed sites on the plane, there are several ways to
determine a permutation of the sites as a function of a unit vector $u$
or a vantage point $v$. Given such a scheme and a permutation $\pi$,
we can ask whether there is any unit vector or vantage point for which
the permutation is $\pi$. We give linear-time algorithms for this
realization problem under three schemes for determining permutations:
sweeping a line across the sites in a direction $u$; expanding a
circle starting from a vantage point $v$; and sweeping a ray from $v$
to give a cyclic permutation.",
}
@inproceedings{ICALP2011,
title = "Range Majority in Constant Time and Linear Space",
author = "Stephane Durocher and Meng He and J. Ian Munro and
Patrick K. Nicholson and Matthew Skala",
booktitle = "38th International Colloquium on Automata, Languages,
and Programming ({ICALP} 2011),
Z{\"u}rich, Switzerland, July 4--8, 2011, Proceedings, Part I",
publisher = "Springer",
year = "2011",
volume = "6755",
editor = "Luca Aceto and Monika Henzinger and Jiri Sgall",
ISBN = "978-3-642-22005-0",
pages = "244--255",
series = "Lecture Notes in Computer Science",
URL = "http://dx.doi.org/10.1007/978-3-642-22006-7",
}
@article{TCS2011,
title = "Untangled monotonic chains and adaptive range search",
author = "Diego Arroyuelo and Francisco Claude and
Reza Dorrigiv and Stephane Durocher and
Meng He and Alejandro L{\'o}pez-Ortiz and
J. Ian Munro and Patrick K. Nicholson and
Alejandro Salinger and Matthew Skala",
journal = "Theoretical Computer Science",
volume = "412",
number = "32",
pages = "4200--4211",
year = "2011",
abstract = "
We present the first adaptive data structure for two-dimensional orthogonal
range search. Our data structure is adaptive in the sense that it gives
improved search performance for data that is better than the worst case
(Demaine et al., 2000); in this case, data with more inherent sortedness.\par
Given n points on the plane, the linear space data structure can answer range
queries in $O(\log n+k+m)$ time, where $m$ is the number of points in the
output and $k$ is the minimum number of monotonic chains into which the point
set can be decomposed, which is in the worst case. Our result matches the
worst-case performance of other optimal-time linear space data structures, or
surpasses them when $k=o(\sqrt{n})$. Our data structure can be made implicit,
requiring no extra space beyond that of the data points themselves (Munro and
Suwanda, 1980), in which case the query time becomes $O(k \log n+m)$. We also
present a novel algorithm of independent interest to decompose a point set into
a minimum number of untangled, similarly directed monotonic chains in
$O(k^2n+n\log n)$ time.",
}
@inproceedings{ACL2010,
author = "Matthew Skala and Victoria Krakovna and J{\'a}nos Kram{\'a}r
and Gerald Penn",
title = "A Generalized-Zero-Preserving Method for Compact Encoding
of Concept Lattices",
booktitle = "48th Annual Meeting of the Association for Computational
Linguistics {(ACL 2010)},
Uppsala, Sweden,
July 11--16, 2010",
year = "2010",
publisher = "Association for Computational Linguistics",
pages = "1512--1521",
url = "http://www.aclweb.org/anthology/P10-1153",
}
@inproceedings{ISAAC2009,
title = "Untangled Monotonic Chains and Adaptive Range Search",
author = "Diego Arroyuelo and Francisco Claude and
Reza Dorrigiv and Stephane Durocher and
Meng He and Alejandro L{\'o}pez-Ortiz and
J. Ian Munro and Patrick K. Nicholson and
Alejandro Salinger and Matthew Skala",
booktitle = "20th International Symposium on Algorithms and Computation
{(ISAAC 2009)},
Honolulu, Hawaii, USA,
December 16--18, 2009",
editor = "Yingfei Dong and Ding-Zhu Du and Oscar Ibarra",
publisher = "Springer",
year = "2009",
volume = "5878",
pages = "203--212",
series = "Lecture Notes in Computer Science",
url = "http://dx.doi.org/10.1007/978-3-642-10631-6_22",
isbn = "978-3-642-10630-9",
abstract = "We present the first adaptive data structure for
two-dim\-en\-sion\-al orthogonal range search. Our data structure is
adaptive in the sense that it gives improved search performance for
data with more inherent sortedness. Given $n$ points on the plane, the
linear-space data structure can answer range queries in
$O(\log{n}+k+m)$ time, where $m$ is the number of points in the output
and $k$ is the minimum number of monotonic chains into which the point
set can be decomposed, which is $O(\sqrt{n})$ in the worst case. Our
result matches the worst-case performance of other optimal-time
linear-space data structures, or surpasses them when $k=o(\sqrt{n})$.
Our data structure can also be made implicit, requiring no extra space
beyond that of the data points themselves, in which case the query
time becomes $O(k \log n + m)$. We present a novel algorithm of
independent interest to decompose a point set into a minimum number of
untangled, same-direction monotonic chains in $O(kn+n\log{n})$ time.",
}
@inproceedings{BIRS2009,
author = "Matthew Skala",
title = "Constraint satisfaction in string spaces",
booktitle = "BIRS 09w5124: Mathematics of String Spaces and
Algorithmic Applications, Banff, Alberta, January 25-30, 2009",
inactive_month = jan # "~30",
year = 2009,
organization = "Banff International Research Station",
abstract = "We discuss the complexity of a class of decision problems
derived from distance-based index data structures. Finding a point
that would be stored in a given leaf of a data structure, or proving
that no such point exists, may be polynomial-time or NP-complete
depending on the underlying metric space. This problem arises from
questions of security in robust hash or obfuscated recognition
applications. The problem is analysed for spaces of strings and
vectors with a variety of metrics: strings with Hamming distance; the
usual (Levenshtein) edit distance; an edit distance we introduce
called Superghost distance; arbitrary weighted tree metrics; and real
vectors with Minkowski $L_p$ metrics (of which the Euclidean distance
is a special case). We also summarize some results on distance
permutations and blind substring search.",
}
@article{JDA2009,
title = "Counting distance permutations",
journal = "Journal of Discrete Algorithms",
volume = "7",
number = "1",
pages = "49--61",
year = "2009",
issn = "1570-8667",
doi = "DOI: 10.1016/j.jda.2008.09.011",
url = "http://www.sciencedirect.com/science/article/B758J-4TJ1HMX-2/2/36229b1acdc3f1800f9cdcecda02cf06",
author = "Matthew Skala",
keywords = "Metric space",
keywords = "Nearest neighbour",
keywords = "Voronoi diagram",
keywords = "Distance permutation",
abstract = "Distance permutation indexes support fast proximity
searching in high-dimensional metric spaces. Given some fixed
reference sites, for each point in a database the index stores a
permutation naming the closest site, the second-closest, and so on.
We examine how many distinct permutations can occur as a function
of the number of sites and the size of the space. We give theoretical
results for tree metrics and vector spaces with L1, L2, and
L[infinity] metrics, improving on the previous best known storage
space in the vector case. We also give experimental results and
commentary on the number of distance permutations that actually
occur in a variety of vector, string, and document databases.",
}
@misc{WADS2009,
title = "Finding a {H}ausdorff Core of a Polygon: On Convex Polygon
Containment with Bounded {H}ausdorff Distance",
author = "Reza Dorrigiv and Stephane Durocher and Arash Farzan and
Robert Fraser and Alejandro L{\'o}pez-Ortiz and
J. Ian Munro and Alejandro Salinger and Matthew Skala",
booktitle = "11th International Symposium on Algorithms and Data
Structures {(WADS 2009)},
Banff, Alberta,
August 21--23, 2009",
publisher = "Springer",
year = "2009",
volume = "5664",
editor = "Frank K. H. A. Dehne and
Marina L. Gavrilova and
J{\"o}rg-R{\"u}diger Sack and
Csaba D. T{\'o}th",
ISBN = "978-3-642-03366-7",
pages = "218--229",
series = "Lecture Notes in Computer Science",
url = "http://dx.doi.org/10.1007/978-3-642-03367-4_20",
abstract = "Given a simple polygon $P$, we consider the problem of
finding a convex polygon $Q$ contained in $P$ that minimizes
$H(P,Q)$, where $H$ denotes the Hausdorff distance. We call
such a polygon $Q$ a {\em Hausdorff core} of $P$. We
describe polynomial-time approximations for both the
minimization and decision versions of the Hausdorff core
problem, and we provide an argument supporting the hardness
of the problem.",
}
}
@phdthesis{PhDThesis,
author = "Matthew Adam Skala",
title = "Aspects of Metric Spaces in Computation",
school = "University of Waterloo",
year = "2008",
abstract = "Metric spaces, which generalise the properties of
commonly-encountered physical and abstract spaces into a
mathematical framework, frequently occur in computer science
applications. Three major kinds of questions about metric
spaces are considered here: the intrinsic dimensionality of a
distribution, the maximum number of distance permutations,
and the difficulty of reverse similarity search. Intrinsic
dimensionality measures the tendency for points to be
equidistant, which is diagnostic of high-dimensional spaces.
Distance permutations describe the order in which a set of
fixed sites appears while moving away from a chosen point;
the number of distinct permutations determines the amount of
storage space required by some kinds of indexing data
structure. Reverse similarity search problems are constraint
satisfaction problems derived from distance-based index
structures. Their difficulty reveals details of the
structure of the space. Theoretical and experimental results
are given for these three questions in a wide range of metric
spaces, with commentary on the consequences for computer
science applications and additional related results where
appropriate.",
}
@article{LJ2008,
title = "Enforcing Copyright",
author = "Matthew Skala and Brett Bonfield and Mary Fran Torpey",
journal = "Library Journal",
month = feb # "~15,",
year = 2008,
volume = 133,
number = 3,
pages = 28,
}
@InProceedings{SISAP2008b,
title = "On the Complexity of Reverse Similarity Search",
author = "Matthew Skala",
booktitle = "First International Workshop on Similarity Search and
Applications {(SISAP 2008)},
Cancun, Mexico,
April 11--12, 2008",
publisher = "IEEE",
year = "2008",
editor = "Edgar Ch{\'a}vez and Gonzalo Navarro",
ISBN = "978-0-7695-3101-4",
pages = "149--156",
publisher = "IEEE Computer Society",
abstract = "Two decision problems are presented that arise from
reversing the operation of a distance-based indexing tree.
Whereas similarity search finds points in the tree given a
query point, reverse similarity search begins with a set of
constraints like those defining a leaf, and generates a
point meeting the constraints. These problems derive from
robust hashing, a technique used in similarity search and
security applications.
The problems are analysed for spaces of strings and vectors
with a variety of metrics: strings with Hamming distance;
the usual (Levenshtein) edit distance; an edit distance we
introduce called Superghost distance; arbitrary weighted
tree metrics; and real vectors with Minkowski $L_p$ metrics
(of which the Euclidean distance is a special case). They
are found to inhabit different complexity classes depending
on the metric. In particular, the reverse similarity
search problem derived from a VP- or GH-tree is NP-complete
for any $L_p$ metric except that it is in P for a GH-tree
with the Euclidean metric.",
}
@InProceedings{SISAP2008a,
title = "Counting Distance Permutations",
author = "Matthew Skala",
booktitle = "First International Workshop on Similarity Search and
Applications {(SISAP 2008)},
Cancun, Mexico,
April 11--12, 2008",
publisher = "IEEE",
year = "2008",
editor = "Edgar Ch{\'a}vez and Gonzalo Navarro",
ISBN = "978-0-7695-3101-4",
pages = "69--76",
publisher = "IEEE Computer Society",
abstract = "A distance permutation index supports fast proximity
searching in a high-dimensional metric space. Given some
fixed reference sites, for each point in a database the
index stores a permutation naming the closest site, the
second-closest, and so on. We examine how many distinct
permutations can occur as a function of the number of sites
and the size of the space. We give theoretical results for
tree metrics and vector spaces with $L_1$, $L_2$, and
$L_\infty$ metrics, improving on the previous best known
storage space in the vector case. We also give
experimental results and commentary on the number of
distance permutations that actually occur in a variety of
vector, string, and document spaces.",
}
@InProceedings{SPIRE2005,
title = "Measuring the Difficulty of Distance-Based Indexing",
author = "Matthew Skala",
booktitle = "Proceedings of the
12th International Conference on
String Processing and Information Retrieval
{(SPIRE 2005)},
{B}uenos {A}ires, {A}rgentina,
November 2--4, 2005",
publisher = "Springer",
year = "2005",
volume = "3772",
editor = "Mariano P. Consens and Gonzalo Navarro",
ISBN = "3-540-29740-5",
pages = "103--114",
series = "Lecture Notes in Computer Science",
abstract = "Data structures for similarity search are commonly
evaluated on data in vector spaces, but distance-based data structures are
also applicable to non-vector spaces with no natural concept of
dimensionality. The intrinsic dimensionality statistic of Ch{\'a}vez and
Navarro provides a way to compare the performance of similarity indexing and
search algorithms across different spaces, and predict the performance of
index data structures on non-vector spaces by relating them to equivalent
vector spaces. We characterise its asymptotic behaviour, and give
experimental results to calibrate these comparisons.",
}
@inproceedings{OpenCity2005,
author = "Matthew Skala",
title = "Balancing the Books with Fiat Goods",
booktitle = "OpenCity 2005, Winnipeg, Manitoba, August 17--19, 2005",
inactive_month = aug # "~19",
year = "2005",
organization = "University of Winnipeg",
note = "Invited talk by video."
}
@mastersthesis{MScThesis,
author = "Matthew Adam Skala",
title = "Generation of Graphs Embedded on the Torus",
school = "University of Victoria",
year = "2001",
}
@inproceedings{Southeastern2001,
author = "Matthew Skala and Wendy Myrvold",
title = "Fast Generation of Graphs Embedded on the Torus",
booktitle = "32nd {S}outheastern International Conference on
Combinatorics, Graph Theory, and Computing,
Baton Rouge, Louisiana, USA,
February 26--March 2, 2001",
inactive_month = feb # "~27",
year = "2001",
abstract = "A graph is planar if it can be drawn without any edges
crossing on the plane. Similarly, a graph is toroidal if it can
be drawn without any edges crossing on the torus, a surface shaped
like a doughnut and created by adding one handle to the plane. A
graph may be drawn on a surface in several distinct ways, called
embeddings. We describe and implement an algorithm to generate,
without duplication, all embeddings on the torus of graphs that are
not planar, up to a chosen number of vertices and edges. The
resulting lists of embeddings, as well as being of interest in
themselves, are useful in investigating torus obstructions, the
simplest graphs that are not toroidal.",
}
@inproceedings{IGARSS1999,
author = "Goodenough, D. G. and Charlebois, D. and Bhogal, A. S.
and Dyk, A. and Skala, M.",
title = "{SEIDAM}: A Flexible and Interoperable Metadata-Driven System
for Intelligent Forest Monitoring",
booktitle = "Proceedings of the
International Geoscience and Remote Sensing Symposium 1999
{(IGARSS'99)},
{H}amburg, {G}ermany,
June 28--July 2, 1999",
publisher = "IEEE",
year = "1999",
pages = "1338--1341",
volume = 2,
editor = "T. I. Stein",
ISBN = "0-7803-5207-6",
abstract = "The Advanced Forest Technologies Group at the Pacific
Forestry Centre is continuing to develop a System of Experts for Intelligent
Data Management (SEIDAM). SEIDAM manages large amounts of remotely sensed
and GIS data and processes information for intelligent forest management and
inventory updates. SEIDAM uses artificial intelligence (planning, case-based
reasoning, software agents and machine learning) with previously captured
domain expertise. SEIDAM uses a Prolog expert system shell called RESHELL.
In order to manage and process natural resource information, SEIDAM relies
on metadata that describes GIS data, field data and heterogeneous,
multi-temporal remotely sensed imagery. The authors discuss improvements to
SEIDAM. The system is presently composed of a multitude of software agents
that currently reside on a LAN. These agents are controlled by SEIDAM's main
expert system and are synchronous in nature. By redesigning the interfaces
between SEIDAM agents and the central system, SEIDAM will be able to operate
in a distributed asynchronous manner across the Internet by taking advantage
of new interchange protocols. For this initial implementation, the authors
are concentrating on a suite of agents for automated analysis of AirSAR and
AVIRIS data, beginning with the automated management of the hyperspectral
and AirSAR meta data",
}
@inproceedings{CSE1998,
author = "Matthew Skala",
title = "A Limited-Diffusion Algorithm for Blind Substring Search",
booktitle = "Proceedings of the
10th Annual {C}anadian Information Technology Security Symposium,
{O}ttawa, {O}ntario,
June 1--8, 1998",
year = "1998",
pages = "397--410",
organization = "Communications Security Establishment",
abstract = "Applications are described for ``blind substring search'',
where a program to search files for a substring is published without
revealing the substring. The ``limited diffusion'' approach proposed
in a previous article is described. Design criteria for a Boolean
function to be used in the limited diffusion algorithm are stated,
and a function meeting the criteria is proposed. An algorithm for
blind substring search is developed and discussed.",
note = "Winner of Best Student Paper award."
}
