Search Results

Documents authored by Jones, Chris

Found 2 Possible Name Variants:

Jones, Chris

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.16
Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs

Authors: Tommaso d'Orsi, Chris Jones, Jake Ruotolo, Salil Vadhan, and Jiyu Zhang

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
Whether or not the Sparsest Cut problem admits an efficient O(1)-approximation algorithm is a fundamental algorithmic question with connections to geometry and the Unique Games Conjecture. Revisiting spectral algorithms for Sparsest Cut, we present a novel, simple algorithm that combines eigenspace enumeration with a new algorithm for the Cut Improvement problem. The runtime of our algorithm is parametrized by a quantity that we call the solution dimension SD_ε(G): the smallest k such that the subspace spanned by the first k Laplacian eigenvectors contains all but ε fraction of a sparsest cut. Our algorithm matches the guarantees of prior methods based on the threshold-rank paradigm, while also extending beyond them. To illustrate this, we study its performance on low degree Cayley graphs over Abelian groups - canonical examples of graphs with poor expansion properties. We prove that low degree Abelian Cayley graphs have small solution dimension, yielding an algorithm that computes a (1+ε)-approximation to the uniform Sparsest Cut of a degree-d Cayley graph over an Abelian group of size n in time n^O(1) ⋅ exp{(d/ε)^O(d)}. Along the way to bounding the solution dimension of Abelian Cayley graphs, we analyze their sparse cuts and spectra, proving that the collection of O(1)-approximate sparsest cuts has an ε-net of size exp{(d/ε)^O(d)} and that the multiplicity of λ₂ is bounded by 2^O(d). The latter bound is tight and improves on a previous bound of 2^O(d²) by Lee and Makarychev.
Cite as

Tommaso d'Orsi, Chris Jones, Jake Ruotolo, Salil Vadhan, and Jiyu Zhang. Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dorsi_et_al:LIPIcs.APPROX/RANDOM.2025.16,
  author =	{d'Orsi, Tommaso and Jones, Chris and Ruotolo, Jake and Vadhan, Salil and Zhang, Jiyu},
  title =	{{Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.16},
  URN =		{urn:nbn:de:0030-drops-243827},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.16},
  annote =	{Keywords: Sparsest Cut, Spectral Graph Theory, Cayley Graphs, Approximation Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.102
Fourier Analysis of Iterative Algorithms

Authors: Chris Jones and Lucas Pesenti

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study a general class of nonlinear iterative algorithms which includes power iteration, belief propagation and approximate message passing, and many forms of gradient descent. When the input is a random matrix with i.i.d. entries, we use Boolean Fourier analysis to analyze these algorithms as low-degree polynomials in the entries of the input matrix. Each symmetrized Fourier character represents all monomials with a certain shape as specified by a small graph, which we call a Fourier diagram. We prove fundamental asymptotic properties of the Fourier diagrams: over the randomness of the input, all diagrams with cycles are negligible; the tree-shaped diagrams form a basis of asymptotically independent Gaussian vectors; and, when restricted to the trees, iterative algorithms exactly follow an idealized Gaussian dynamic. We use this to prove a state evolution formula, giving a "complete" asymptotic description of the algorithm’s trajectory. The restriction to tree-shaped monomials mirrors the assumption of the cavity method, a 40-year-old non-rigorous technique in statistical physics which has served as one of the most important techniques in the field. We demonstrate how to implement cavity method derivations by 1) restricting the iteration to its tree approximation, and 2) observing that heuristic cavity method-type arguments hold rigorously on the simplified iteration. Our proofs use combinatorial arguments similar to the trace method from random matrix theory. Finally, we push the diagram analysis to a number of iterations that scales with the dimension n of the input matrix, proving that the tree approximation still holds for a simple variant of power iteration all the way up to n^{Ω(1)} iterations.
Cite as

Chris Jones and Lucas Pesenti. Fourier Analysis of Iterative Algorithms. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 102:1-102:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jones_et_al:LIPIcs.ICALP.2025.102,
  author =	{Jones, Chris and Pesenti, Lucas},
  title =	{{Fourier Analysis of Iterative Algorithms}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{102:1--102:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.102},
  URN =		{urn:nbn:de:0030-drops-234791},
  doi =		{10.4230/LIPIcs.ICALP.2025.102},
  annote =	{Keywords: Iterative Algorithms, Message-passing Algorithms, Random Matrix Theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.40
Exact Completeness of LP Hierarchies for Linear Codes

Authors: Leonardo Nagami Coregliano, Fernando Granha Jeronimo, and Chris Jones

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Determining the maximum size A₂(n,d) of a binary code of blocklength n and distance d remains an elusive open question even when restricted to the important class of linear codes. Recently, two linear programming hierarchies extending Delsarte’s LP were independently proposed to upper bound A₂^{Lin}(n,d) (the analogue of A₂(n,d) for linear codes). One of these hierarchies, by the authors, was shown to be approximately complete in the sense that the hierarchy converges to A₂^{Lin}(n,d) as the level grows beyond n². Despite some structural similarities, not even approximate completeness was known for the other hierarchy by Loyfer and Linial. In this work, we prove that both hierarchies recover the exact value of A₂^{Lin}(n,d) at level n. We also prove that at this level the polytope of Loyfer and Linial is integral. Even though these hierarchies seem less powerful than general hierarchies such as Sum-of-Squares, we show that they have enough structure to yield exact completeness via pseudoprobabilities.
Cite as

Leonardo Nagami Coregliano, Fernando Granha Jeronimo, and Chris Jones. Exact Completeness of LP Hierarchies for Linear Codes. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{coregliano_et_al:LIPIcs.ITCS.2023.40,
  author =	{Coregliano, Leonardo Nagami and Jeronimo, Fernando Granha and Jones, Chris},
  title =	{{Exact Completeness of LP Hierarchies for Linear Codes}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.40},
  URN =		{urn:nbn:de:0030-drops-175433},
  doi =		{10.4230/LIPIcs.ITCS.2023.40},
  annote =	{Keywords: LP bound, linear codes, Delsarte’s LP, combinatorial polytopes, pseudoexpectation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.77
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses

Authors: Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, and Jonathan Shi

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We study random constraint satisfaction problems (CSPs) at large clause density. We relate the structure of near-optimal solutions for any Boolean Max-CSP to that for an associated spin glass on the hypercube, using the Guerra-Toninelli interpolation from statistical physics. The noise stability polynomial of the CSP’s predicate is, up to a constant, the mixture polynomial of the associated spin glass. We show two main consequences: 1) We prove that the maximum fraction of constraints that can be satisfied in a random Max-CSP at large clause density is determined by the ground state energy density of the corresponding spin glass. Since the latter value can be computed with the Parisi formula [Parisi, 1980; Talagrand, 2006; Auffinger and Chen, 2017], we provide numerical values for some popular CSPs. 2) We prove that a Max-CSP at large clause density possesses generalized versions of the overlap gap property if and only if the same holds for the corresponding spin glass. We transfer results from [Huang and Sellke, 2021] to obstruct algorithms with overlap concentration on a large class of Max-CSPs. This immediately includes local classical and local quantum algorithms [Chou et al., 2022].
Cite as

Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, and Jonathan Shi. Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 77:1-77:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jones_et_al:LIPIcs.ITCS.2023.77,
  author =	{Jones, Chris and Marwaha, Kunal and Sandhu, Juspreet Singh and Shi, Jonathan},
  title =	{{Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{77:1--77:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.77},
  URN =		{urn:nbn:de:0030-drops-175804},
  doi =		{10.4230/LIPIcs.ITCS.2023.77},
  annote =	{Keywords: spin glass, overlap gap property, constraint satisfaction problem, Guerra-Toninelli interpolation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.51
A Complete Linear Programming Hierarchy for Linear Codes

Authors: Leonardo Nagami Coregliano, Fernando Granha Jeronimo, and Chris Jones

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
A longstanding open problem in coding theory is to determine the best (asymptotic) rate R₂(δ) of binary codes with minimum constant (relative) distance δ. An existential lower bound was given by Gilbert and Varshamov in the 1950s. On the impossibility side, in the 1970s McEliece, Rodemich, Rumsey and Welch (MRRW) proved an upper bound by analyzing Delsarte’s linear programs. To date these results remain the best known lower and upper bounds on R₂(δ) with no improvement even for the important class of linear codes. Asymptotically, these bounds differ by an exponential factor in the blocklength. In this work, we introduce a new hierarchy of linear programs (LPs) that converges to the true size A^{Lin}₂(n,d) of an optimum linear binary code (in fact, over any finite field) of a given blocklength n and distance d. This hierarchy has several notable features: 1) It is a natural generalization of the Delsarte LPs used in the first MRRW bound. 2) It is a hierarchy of linear programs rather than semi-definite programs potentially making it more amenable to theoretical analysis. 3) It is complete in the sense that the optimum code size can be retrieved from level O(n²). 4) It provides an answer in the form of a hierarchy (in larger dimensional spaces) to the question of how to cut Delsarte’s LP polytopes to approximate the true size of linear codes. We obtain our hierarchy by generalizing the Krawtchouk polynomials and MacWilliams inequalities to a suitable "higher-order" version taking into account interactions of 𝓁 words. Our method also generalizes to translation schemes under mild assumptions.
Cite as

Leonardo Nagami Coregliano, Fernando Granha Jeronimo, and Chris Jones. A Complete Linear Programming Hierarchy for Linear Codes. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 51:1-51:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{coregliano_et_al:LIPIcs.ITCS.2022.51,
  author =	{Coregliano, Leonardo Nagami and Jeronimo, Fernando Granha and Jones, Chris},
  title =	{{A Complete Linear Programming Hierarchy for Linear Codes}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{51:1--51:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.51},
  URN =		{urn:nbn:de:0030-drops-156474},
  doi =		{10.4230/LIPIcs.ITCS.2022.51},
  annote =	{Keywords: Coding theory, code bounds, convex programming, linear programming hierarchy}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.89
Almost-Orthogonal Bases for Inner Product Polynomials

Authors: Chris Jones and Aaron Potechin

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
In this paper, we consider low-degree polynomials of inner products between a collection of random vectors. We give an almost orthogonal basis for this vector space of polynomials when the random vectors are Gaussian, spherical, or Boolean. In all three cases, our basis admits an interesting combinatorial description based on the topology of the underlying graph of inner products. We also analyze the expected value of the product of two polynomials in our basis. In all three cases, we show that this expected value can be expressed in terms of collections of matchings on the underlying graph of inner products. In the Gaussian and Boolean cases, we show that this expected value is always non-negative. In the spherical case, we show that this expected value can be negative but we conjecture that if the underlying graph of inner products is planar then this expected value will always be non-negative.
Cite as

Chris Jones and Aaron Potechin. Almost-Orthogonal Bases for Inner Product Polynomials. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 89:1-89:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{jones_et_al:LIPIcs.ITCS.2022.89,
  author =	{Jones, Chris and Potechin, Aaron},
  title =	{{Almost-Orthogonal Bases for Inner Product Polynomials}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{89:1--89:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.89},
  URN =		{urn:nbn:de:0030-drops-156853},
  doi =		{10.4230/LIPIcs.ITCS.2022.89},
  annote =	{Keywords: Orthogonal polynomials, Fourier analysis, combinatorics}
}

Jones, Christopher B.

Document
DOI: 10.4230/LIPIcs.GIScience.2025.12
Large Multi-Modal Model Cartographic Map Comprehension for Textual Locality Georeferencing

Authors: Kalana Wijegunarathna, Kristin Stock, and Christopher B. Jones

Published in: LIPIcs, Volume 346, 13th International Conference on Geographic Information Science (GIScience 2025)

Abstract
Millions of biological sample records collected in the last few centuries archived in natural history collections are un-georeferenced. Georeferencing complex locality descriptions associated with these collection samples is a highly labour-intensive task collection agencies struggle with. None of the existing automated methods exploit maps that are an essential tool for georeferencing complex relations. We present preliminary experiments and results of a novel method that exploits multi-modal capabilities of recent Large Multi-Modal Models (LMM). This method enables the model to visually contextualize spatial relations it reads in the locality description. We use a grid-based approach to adapt these auto-regressive models for this task in a zero-shot setting. Our experiments conducted on a small manually annotated dataset show impressive results for our approach (∼1 km Average distance error) compared to uni-modal georeferencing with Large Language Models and existing georeferencing tools. The paper also discusses the findings of the experiments in light of an LMM’s ability to comprehend fine-grained maps. Motivated by these results, a practical framework is proposed to integrate this method into a georeferencing workflow.
Cite as

Kalana Wijegunarathna, Kristin Stock, and Christopher B. Jones. Large Multi-Modal Model Cartographic Map Comprehension for Textual Locality Georeferencing. In 13th International Conference on Geographic Information Science (GIScience 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 346, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wijegunarathna_et_al:LIPIcs.GIScience.2025.12,
  author =	{Wijegunarathna, Kalana and Stock, Kristin and Jones, Christopher B.},
  title =	{{Large Multi-Modal Model Cartographic Map Comprehension for Textual Locality Georeferencing}},
  booktitle =	{13th International Conference on Geographic Information Science (GIScience 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-378-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{346},
  editor =	{Sila-Nowicka, Katarzyna and Moore, Antoni and O'Sullivan, David and Adams, Benjamin and Gahegan, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2025.12},
  URN =		{urn:nbn:de:0030-drops-238412},
  doi =		{10.4230/LIPIcs.GIScience.2025.12},
  annote =	{Keywords: Large Multi-Modal Models, Large Language Models, LLM, Georeferencing, Natural History collections}
}
Document
DOI: 10.4230/LIPIcs.COSIT.2022.1
What Do You Mean You're in Trafalgar Square? Comparing Distance Thresholds for Geospatial Prepositions

Authors: Niloofar Aflaki, Kristin Stock, Christopher B. Jones, Hans Guesgen, Jeremy Morley, and Yukio Fukuzawa

Published in: LIPIcs, Volume 240, 15th International Conference on Spatial Information Theory (COSIT 2022)

Abstract
Natural language location descriptions frequently describe object locations relative to other objects (the house near the river). Geospatial prepositions (e.g.near) are a key element of these descriptions, and the distances associated with proximity, adjacency and topological prepositions are thought to depend on the context of a specific scene. When referring to the context, we include consideration of properties of the relatum such as its feature type, size and associated image schema. In this paper, we extract spatial descriptions from the Google search engine for nine prepositions across three locations, compare their acceptance thresholds (the distances at which different prepositions are acceptable), and study variations in different contexts using cumulative graphs and scatter plots. Our results show that adjacency prepositions next to and adjacent to are used for a large range of distances, in contrast to beside; and that topological prepositions in, at and on can all be used to indicate proximity as well as containment and collocation. We also found that reference object image schema influences the selection of geospatial prepositions such as near and in.
Cite as

Niloofar Aflaki, Kristin Stock, Christopher B. Jones, Hans Guesgen, Jeremy Morley, and Yukio Fukuzawa. What Do You Mean You're in Trafalgar Square? Comparing Distance Thresholds for Geospatial Prepositions. In 15th International Conference on Spatial Information Theory (COSIT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 240, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{aflaki_et_al:LIPIcs.COSIT.2022.1,
  author =	{Aflaki, Niloofar and Stock, Kristin and Jones, Christopher B. and Guesgen, Hans and Morley, Jeremy and Fukuzawa, Yukio},
  title =	{{What Do You Mean You're in Trafalgar Square? Comparing Distance Thresholds for Geospatial Prepositions}},
  booktitle =	{15th International Conference on Spatial Information Theory (COSIT 2022)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-257-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{240},
  editor =	{Ishikawa, Toru and Fabrikant, Sara Irina and Winter, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2022.1},
  URN =		{urn:nbn:de:0030-drops-168865},
  doi =		{10.4230/LIPIcs.COSIT.2022.1},
  annote =	{Keywords: contextual factors, spatial descriptions, acceptance model, spatial template, applicability model, geospatial prepositions}
}
Document
DOI: 10.4230/LIPIcs.COSIT.2022.4
Predicting Distance and Direction from Text Locality Descriptions for Biological Specimen Collections

Authors: Ruoxuan Liao, Pragyan P. Das, Christopher B. Jones, Niloofar Aflaki, and Kristin Stock

Published in: LIPIcs, Volume 240, 15th International Conference on Spatial Information Theory (COSIT 2022)

Abstract
A considerable proportion of records that describe biological specimens (flora, soil, invertebrates), and especially those that were collected decades ago, are not attached to corresponding geographical coordinates, but rather have their location described only through textual descriptions (e.g. North Canterbury, Selwyn River near bridge on Springston-Leeston Rd). Without geographical coordinates, millions of records stored in museum collections around the world cannot be mapped. We present a method for predicting the distance and direction associated with human language location descriptions which focuses on the interpretation of geospatial prepositions and the way in which they modify the location represented by an associated reference place name (e.g. near the Manawatu River). We study eight distance-oriented prepositions and eight direction-oriented prepositions and use machine learning regression to predict distance or direction, relative to the reference place name, from a collection of training data. The results show that, compared with a simple baseline, our model improved distance predictions by up to 60% and direction predictions by up to 31%.
Cite as

Ruoxuan Liao, Pragyan P. Das, Christopher B. Jones, Niloofar Aflaki, and Kristin Stock. Predicting Distance and Direction from Text Locality Descriptions for Biological Specimen Collections. In 15th International Conference on Spatial Information Theory (COSIT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 240, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{liao_et_al:LIPIcs.COSIT.2022.4,
  author =	{Liao, Ruoxuan and Das, Pragyan P. and Jones, Christopher B. and Aflaki, Niloofar and Stock, Kristin},
  title =	{{Predicting Distance and Direction from Text Locality Descriptions for Biological Specimen Collections}},
  booktitle =	{15th International Conference on Spatial Information Theory (COSIT 2022)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-257-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{240},
  editor =	{Ishikawa, Toru and Fabrikant, Sara Irina and Winter, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2022.4},
  URN =		{urn:nbn:de:0030-drops-168892},
  doi =		{10.4230/LIPIcs.COSIT.2022.4},
  annote =	{Keywords: geospatial prepositions, biological specimen collections, georeferencing, natural language processing, locative expressions, locality descriptions, geoparsing, geocoding, geographic information retrieval, regression, machine learning}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.COSIT.2019.11
Detecting the Geospatialness of Prepositions from Natural Language Text (Short Paper)

Authors: Mansi Radke, Prarthana Das, Kristin Stock, and Christopher B. Jones

Published in: LIPIcs, Volume 142, 14th International Conference on Spatial Information Theory (COSIT 2019)

Abstract
There is increasing interest in detecting the presence of geospatial locative expressions that include spatial relation terms such as near or within <some distance>. Being able to do so provides a foundation for interpreting relative descriptions of location and for building corpora that facilitate the development of methods for spatial relation extraction and interpretation. Here we evaluate the use of a spatial role labelling procedure to distinguish geospatial uses of prepositions from other spatial and non-spatial uses and experiment with the use of additional machine learning features to improve the quality of detection of geospatial prepositions. An annotated corpus of nearly 2000 instances of preposition usage was created for training and testing the classifiers.
Cite as

Mansi Radke, Prarthana Das, Kristin Stock, and Christopher B. Jones. Detecting the Geospatialness of Prepositions from Natural Language Text (Short Paper). In 14th International Conference on Spatial Information Theory (COSIT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 142, pp. 11:1-11:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{radke_et_al:LIPIcs.COSIT.2019.11,
  author =	{Radke, Mansi and Das, Prarthana and Stock, Kristin and Jones, Christopher B.},
  title =	{{Detecting the Geospatialness of Prepositions from Natural Language Text}},
  booktitle =	{14th International Conference on Spatial Information Theory (COSIT 2019)},
  pages =	{11:1--11:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-115-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{142},
  editor =	{Timpf, Sabine and Schlieder, Christoph and Kattenbeck, Markus and Ludwig, Bernd and Stewart, Kathleen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2019.11},
  URN =		{urn:nbn:de:0030-drops-111033},
  doi =		{10.4230/LIPIcs.COSIT.2019.11},
  annote =	{Keywords: spatial language, natural language processing, geospatial language}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.34
Mapping Wildlife Species Distribution With Social Media: Augmenting Text Classification With Species Names (Short Paper)

Authors: Shelan S. Jeawak, Christopher B. Jones, and Steven Schockaert

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
Social media has considerable potential as a source of passive citizen science observations of the natural environment, including wildlife monitoring. Here we compare and combine two main strategies for using social media postings to predict species distributions: (i) identifying postings that explicitly mention the target species name and (ii) using a text classifier that exploits all tags to construct a model of the locations where the species occurs. We find that the first strategy has high precision but suffers from low recall, with the second strategy achieving a better overall performance. We furthermore show that even better performance is achieved with a meta classifier that combines data on the presence or absence of species name tags with the predictions from the text classifier.
Cite as

Shelan S. Jeawak, Christopher B. Jones, and Steven Schockaert. Mapping Wildlife Species Distribution With Social Media: Augmenting Text Classification With Species Names (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 34:1-34:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jeawak_et_al:LIPIcs.GISCIENCE.2018.34,
  author =	{Jeawak, Shelan S. and Jones, Christopher B. and Schockaert, Steven},
  title =	{{Mapping Wildlife Species Distribution With Social Media: Augmenting Text Classification With Species Names}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{34:1--34:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.34},
  URN =		{urn:nbn:de:0030-drops-93626},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.34},
  annote =	{Keywords: Social media, Text mining, Volunteered Geographic Information, Ecology}
}
Document
DOI: 10.4230/LIPIcs.COSIT.2017.21
Using Flickr for Characterizing the Environment: An Exploratory Analysis

Authors: Shelan S. Jeawak, Christopher B. Jones, and Steven Schockaert

Published in: LIPIcs, Volume 86, 13th International Conference on Spatial Information Theory (COSIT 2017)

Abstract
The photo-sharing website Flickr has become a valuable informal information source in disciplines such as geography and ecology. Some ecologists, for instance, have been manually analysing Flickr to obtain information that is more up-to-date than what is found in traditional sources. While several previous works have shown the potential of Flickr tags for characterizing places, it remains unclear to what extent such tags can be used to derive scientifically useful information for ecologists in an automated way. To obtain a clearer picture about the kinds of environmental features that can be modelled using Flickr tags, we consider the problem of predicting scenicness, species distribution, land cover, and several climate related features. Our focus is on comparing the predictive power of Flickr tags with that of structured data from more traditional sources. We find that, broadly speaking, Flickr tags perform comparably to the considered structured data sources, being sometimes better and sometimes worse. Most importantly, we find that combining Flickr tags with structured data sources consistently, and sometimes substantially, improves the results. This suggests that Flickr indeed provides information that is complementary to traditional sources.
Cite as

Shelan S. Jeawak, Christopher B. Jones, and Steven Schockaert. Using Flickr for Characterizing the Environment: An Exploratory Analysis. In 13th International Conference on Spatial Information Theory (COSIT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 86, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jeawak_et_al:LIPIcs.COSIT.2017.21,
  author =	{Jeawak, Shelan S. and Jones, Christopher B. and Schockaert, Steven},
  title =	{{Using Flickr for Characterizing the Environment: An Exploratory Analysis}},
  booktitle =	{13th International Conference on Spatial Information Theory (COSIT 2017)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-043-9},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{86},
  editor =	{Clementini, Eliseo and Donnelly, Maureen and Yuan, May and Kray, Christian and Fogliaroni, Paolo and Ballatore, Andrea},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2017.21},
  URN =		{urn:nbn:de:0030-drops-77523},
  doi =		{10.4230/LIPIcs.COSIT.2017.21},
  annote =	{Keywords: Social media, Volunteered Geographic Information, Ecology}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact