6 Search Results for "Zhao, Yu"

Document
Short Paper
DOI: 10.4230/LIPIcs.GIScience.2023.28
GeoQAMap - Geographic Question Answering with Maps Leveraging LLM and Open Knowledge Base (Short Paper)

Authors: Yu Feng, Linfang Ding, and Guohui Xiao

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
GeoQA (Geographic Question Answering) is an emerging research field in GIScience, aimed at answering geographic questions in natural language. However, developing systems that seamlessly integrate structured geospatial data with unstructured natural language queries remains challenging. Recent advancements in Large Language Models (LLMs) have facilitated the application of natural language processing in various tasks. To achieve this goal, this study introduces GeoQAMap, a system that first translates natural language questions into SPARQL queries, then retrieves geospatial information from Wikidata, and finally generates interactive maps as visual answers. The system exhibits great potential for integration with other geospatial data sources such as OpenStreetMap and CityGML, enabling complicated geographic question answering involving further spatial operations.
Cite as

Yu Feng, Linfang Ding, and Guohui Xiao. GeoQAMap - Geographic Question Answering with Maps Leveraging LLM and Open Knowledge Base (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 28:1-28:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.GIScience.2023.28,
  author =	{Feng, Yu and Ding, Linfang and Xiao, Guohui},
  title =	{{GeoQAMap - Geographic Question Answering with Maps Leveraging LLM and Open Knowledge Base}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{28:1--28:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.28},
  URN =		{urn:nbn:de:0030-drops-189233},
  doi =		{10.4230/LIPIcs.GIScience.2023.28},
  annote =	{Keywords: Geographic Question Answering, Large Language Models, SPARQL, Knowledge Base, Wikidata}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GIScience.2023.36
Characterizing Urban Expansion Processes Using Dynamic Spatial Models – a European Application (Short Paper)

Authors: Alex Hagen-Zanker, Jingyan Yu, Naratip Santitissadeekorn, and Susan Hughes

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
Characterisation of the urban expansion processes using time series of binary urban/non-urban land cover data is complex due to the need to account for the initial configuration and the rate of urban expansion over the analysed period. Failure to account for these factors makes the interpretation of landscape metrics for compactness, fragmentation, or clumpiness problematic and the comparison between geographical areas and time periods contentious. This paper presents an approach for characterisation using spatio-dynamic modelling which is data-centred using a process based model, Bayesian optimization, cluster identification, and maximum likelihood classification. An application of the approach across 652 functional urban areas in Europe (1975-2014) demonstrates the consistency of the approach and its ability to identify spatial and temporal trends in urban expansion processes.
Cite as

Alex Hagen-Zanker, Jingyan Yu, Naratip Santitissadeekorn, and Susan Hughes. Characterizing Urban Expansion Processes Using Dynamic Spatial Models – a European Application (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 36:1-36:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hagenzanker_et_al:LIPIcs.GIScience.2023.36,
  author =	{Hagen-Zanker, Alex and Yu, Jingyan and Santitissadeekorn, Naratip and Hughes, Susan},
  title =	{{Characterizing Urban Expansion Processes Using Dynamic Spatial Models – a European Application}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{36:1--36:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.36},
  URN =		{urn:nbn:de:0030-drops-189312},
  doi =		{10.4230/LIPIcs.GIScience.2023.36},
  annote =	{Keywords: Urban expansion, morphology, spatio-temporal dynamics, simulation, compactness}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.52
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs

Authors: Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
For a directed graph G with n vertices and a start vertex u_start, we wish to (approximately) sample an L-step random walk over G starting from u_start with minimum space using an algorithm that only makes few passes over the edges of the graph. This problem found many applications, for instance, in approximating the PageRank of a webpage. If only a single pass is allowed, the space complexity of this problem was shown to be Θ̃(n ⋅ L). Prior to our work, a better space complexity was only known with Õ(√L) passes. We essentially settle the space complexity of this random walk simulation problem for two-pass streaming algorithms, showing that it is Θ̃(n ⋅ √L), by giving almost matching upper and lower bounds. Our lower bound argument extends to every constant number of passes p, and shows that any p-pass algorithm for this problem uses Ω̃(n ⋅ L^{1/p}) space. In addition, we show a similar Θ̃(n ⋅ √L) bound on the space complexity of any algorithm (with any number of passes) for the related problem of sampling an L-step random walk from every vertex in the graph.
Cite as

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu. Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 52:1-52:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2021.52,
  author =	{Chen, Lijie and Kol, Gillat and Paramonov, Dmitry and Saxena, Raghuvansh R. and Song, Zhao and Yu, Huacheng},
  title =	{{Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{52:1--52:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.52},
  URN =		{urn:nbn:de:0030-drops-141218},
  doi =		{10.4230/LIPIcs.ICALP.2021.52},
  annote =	{Keywords: streaming algorithms, random walk sampling}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.54
On Closeness to k-Wise Uniformity

Authors: Ryan O'Donnell and Yu Zhao

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

Abstract
A probability distribution over {-1, 1}^n is (epsilon, k)-wise uniform if, roughly, it is epsilon-close to the uniform distribution when restricted to any k coordinates. We consider the problem of how far an (epsilon, k)-wise uniform distribution can be from any globally k-wise uniform distribution. We show that every (epsilon, k)-wise uniform distribution is O(n^{k/2}epsilon)-close to a k-wise uniform distribution in total variation distance. In addition, we show that this bound is optimal for all even k: we find an (epsilon, k)-wise uniform distribution that is Omega(n^{k/2}epsilon)-far from any k-wise uniform distribution in total variation distance. For k=1, we get a better upper bound of O(epsilon), which is also optimal. One application of our closeness result is to the sample complexity of testing whether a distribution is k-wise uniform or delta-far from k-wise uniform. We give an upper bound of O(n^{k}/delta^2) (or O(log n/delta^2) when k = 1) on the required samples. We show an improved upper bound of O~(n^{k/2}/delta^2) for the special case of testing fully uniform vs. delta-far from k-wise uniform. Finally, we complement this with a matching lower bound of Omega(n/delta^2) when k = 2. Our results improve upon the best known bounds from [Alon et al., 2007], and have simpler proofs.
Cite as

Ryan O'Donnell and Yu Zhao. On Closeness to k-Wise Uniformity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 54:1-54:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{odonnell_et_al:LIPIcs.APPROX-RANDOM.2018.54,
  author =	{O'Donnell, Ryan and Zhao, Yu},
  title =	{{On Closeness to k-Wise Uniformity}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{54:1--54:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.54},
  URN =		{urn:nbn:de:0030-drops-94581},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.54},
  annote =	{Keywords: k-wise independence, property testing, Fourier analysis, Boolean function}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.29
Some Lower Bounds in Dynamic Networks with Oblivious Adversaries

Authors: Irvan Jahja, Haifeng Yu, and Yuda Zhao

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
This paper considers several closely-related problems in synchronous dynamic networks with oblivious adversaries, and proves novel Omega(d + poly(m)) lower bounds on their time complexity (in rounds). Here d is the dynamic diameter of the dynamic network and m is the total number of nodes. Before this work, the only known lower bounds on these problems under oblivious adversaries were the trivial Omega(d) lower bounds. Our novel lower bounds are hence the first non-trivial lower bounds and also the first lower bounds with a poly(m) term. Our proof relies on a novel reduction from a certain two-party communication complexity problem. Our central proof technique is unique in the sense that we consider the communication complexity with a special leaker. The leaker helps Alice and Bob in the two-party problem, by disclosing to Alice and Bob certain "non-critical" information about the problem instance that they are solving.
Cite as

Irvan Jahja, Haifeng Yu, and Yuda Zhao. Some Lower Bounds in Dynamic Networks with Oblivious Adversaries. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jahja_et_al:LIPIcs.DISC.2017.29,
  author =	{Jahja, Irvan and Yu, Haifeng and Zhao, Yuda},
  title =	{{Some Lower Bounds in Dynamic Networks with Oblivious Adversaries}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.29},
  URN =		{urn:nbn:de:0030-drops-79690},
  doi =		{10.4230/LIPIcs.DISC.2017.29},
  annote =	{Keywords: dynamic networks, oblivious adversary, adaptive adversary, lower bounds, communication complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.24
Polynomial Bounds for Decoupling, with Applications

Authors: Ryan O'Donnell and Yu Zhao

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
Let f(x) = f(x_1, ..., x_n) = sum_{|S|<=k} a_S prod_{i in S} x_i be an n-variate real multilinear polynomial of degree at most k, where S subseteq [n] = {1, 2, ..., n}. For its one-block decoupled version, vf(y,z) = sum_{abs(S)<=k} a_S sum_{i in S}} y_i prod_{j in S\{i}} z_j, we show tail-bound comparisons of the form Pr(abs(vf)(y,z)) > C_k t} <= D_k Pr(abs(f(x)) > t). Our constants C_k, D_k are significantly better than those known for "full decoupling". For example, when x, y, z are independent Gaussians we obtain C_k = D_k = O(k); when x, by, z are +/-1 random variables we obtain C_k = O(k^2), D_k = k^{O(k)}. By contrast, for full decoupling only C_k = D_k = k^{O(k)} is known in these settings. We describe consequences of these results for query complexity (related to conjectures of Aaronson and Ambainis) and for analysis of Boolean functions (including an optimal sharpening of the DFKO Inequality).
Cite as

Ryan O'Donnell and Yu Zhao. Polynomial Bounds for Decoupling, with Applications. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{odonnell_et_al:LIPIcs.CCC.2016.24,
  author =	{O'Donnell, Ryan and Zhao, Yu},
  title =	{{Polynomial Bounds for Decoupling, with Applications}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.24},
  URN =		{urn:nbn:de:0030-drops-58520},
  doi =		{10.4230/LIPIcs.CCC.2016.24},
  annote =	{Keywords: Decoupling, Query Complexity, Fourier Analysis, Boolean Functions}
}
  • Refine by Author
  • 2 O'Donnell, Ryan
  • 2 Zhao, Yu
  • 1 Chen, Lijie
  • 1 Ding, Linfang
  • 1 Feng, Yu
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Cartography
  • 1 Applied computing → Environmental sciences
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 1 Boolean Functions
  • 1 Boolean function
  • 1 Decoupling
  • 1 Fourier Analysis
  • 1 Fourier analysis
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2023
  • 1 2016
  • 1 2017
  • 1 2018
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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