Matthew Skala's academic publications

This only lists academic publications; see elsewhere on my site for popular articles, fiction, and so on. Starred entries are in venues where alphabetical ordering of authors is traditional. See also my page on DBLP, which is a less complete list but has some useful search features.

Pending journal submissions

Durocher, S.; Leblanc, A.; and Skala, M.* 2015. The Projection Median as a Weighted Average. Submitted to Journal of Computational Geometry October 2015.

Durocher, S.; Fraser, R.; Leblanc, A.; Morrison, J.; and Skala, M.* 2015. On Combinatorial Depth Measures. Submitted to International Journal of Computational Geometry and Applications September 2015.

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.

2016

Pagh, R.; Silvestri, F.; Sivertsen, J.; and Skala, M.* 2016. Approximate furthest neighbor with application to annulus query. Accepted to Information Systems.

Skala, M. 2016. Bit-vector search filtering with application to a kanji dictionary. Accepted to 9th International Conference on Similarity Search and Applications (SISAP 2016), Tokyo, Japan, October 24-26, 2016.

Skala, M. 2016. Astrological charts with horoscop and starfont. Accepted to 37th Annual Meeting of the TeX Users Group (TUG 2016), Toronto, Ontario, July 25-27, 2016. [Abstract] [Preprint]

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. [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] [home]

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] [home]

2008

Skala, M. A. 2008. Aspects of metric spaces in computation. PhD dissertation, University of Waterloo. [BiBTeX] [official deposit] [PDF] [LaTeX template]

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] [IEEE Xplore] [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] [IEEE Xplore] [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] [IEEE Xplore]

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] [home]

BiBTeX entries

@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",
}

@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."
}