## Matthew Skala's 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. For my more recent activities, see my Web sites at North Coast Synthesis (electronic musical instruments); Edifying Fellowship (tarot and astrology); and Ansuz (personal).

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. Efﬁcient 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." }