30 Search Results for "Wang, Te-Li"

Document
Position
DOI: 10.4230/TGDK.2.1.2
Grounding Stream Reasoning Research

Authors: Pieter Bonte, Jean-Paul Calbimonte, Daniel de Leng, Daniele Dell'Aglio, Emanuele Della Valle, Thomas Eiter, Federico Giannini, Fredrik Heintz, Konstantin Schekotihin, Danh Le-Phuoc, Alessandra Mileo, Patrik Schneider, Riccardo Tommasini, Jacopo Urbani, and Giacomo Ziffer

Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1

Abstract
In the last decade, there has been a growing interest in applying AI technologies to implement complex data analytics over data streams. To this end, researchers in various fields have been organising a yearly event called the "Stream Reasoning Workshop" to share perspectives, challenges, and experiences around this topic. In this paper, the previous organisers of the workshops and other community members provide a summary of the main research results that have been discussed during the first six editions of the event. These results can be categorised into four main research areas: The first is concerned with the technological challenges related to handling large data streams. The second area aims at adapting and extending existing semantic technologies to data streams. The third and fourth areas focus on how to implement reasoning techniques, either considering deductive or inductive techniques, to extract new and valuable knowledge from the data in the stream. This summary is written not only to provide a crystallisation of the field, but also to point out distinctive traits of the stream reasoning community. Moreover, it also provides a foundation for future research by enumerating a list of use cases and open challenges, to stimulate others to join this exciting research area.
Cite as

Pieter Bonte, Jean-Paul Calbimonte, Daniel de Leng, Daniele Dell'Aglio, Emanuele Della Valle, Thomas Eiter, Federico Giannini, Fredrik Heintz, Konstantin Schekotihin, Danh Le-Phuoc, Alessandra Mileo, Patrik Schneider, Riccardo Tommasini, Jacopo Urbani, and Giacomo Ziffer. Grounding Stream Reasoning Research. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 2:1-2:47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{bonte_et_al:TGDK.2.1.2,
  author =	{Bonte, Pieter and Calbimonte, Jean-Paul and de Leng, Daniel and Dell'Aglio, Daniele and Della Valle, Emanuele and Eiter, Thomas and Giannini, Federico and Heintz, Fredrik and Schekotihin, Konstantin and Le-Phuoc, Danh and Mileo, Alessandra and Schneider, Patrik and Tommasini, Riccardo and Urbani, Jacopo and Ziffer, Giacomo},
  title =	{{Grounding Stream Reasoning Research}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{2:1--2:47},
  ISSN =	{2942-7517},
  year =	{2024},
  volume =	{2},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.2},
  URN =		{urn:nbn:de:0030-drops-198597},
  doi =		{10.4230/TGDK.2.1.2},
  annote =	{Keywords: Stream Reasoning, Stream Processing, RDF streams, Streaming Linked Data, Continuous query processing, Temporal Logics, High-performance computing, Databases}
}
Document
Position
DOI: 10.4230/TGDK.2.1.5
Standardizing Knowledge Engineering Practices with a Reference Architecture

Authors: Bradley P. Allen and Filip Ilievski

Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1

Abstract
Knowledge engineering is the process of creating and maintaining knowledge-producing systems. Throughout the history of computer science and AI, knowledge engineering workflows have been widely used given the importance of high-quality knowledge for reliable intelligent agents. Meanwhile, the scope of knowledge engineering, as apparent from its target tasks and use cases, has been shifting, together with its paradigms such as expert systems, semantic web, and language modeling. The intended use cases and supported user requirements between these paradigms have not been analyzed globally, as new paradigms often satisfy prior pain points while possibly introducing new ones. The recent abstraction of systemic patterns into a boxology provides an opening for aligning the requirements and use cases of knowledge engineering with the systems, components, and software that can satisfy them best, however, this direction has not been explored to date. This paper proposes a vision of harmonizing the best practices in the field of knowledge engineering by leveraging the software engineering methodology of creating reference architectures. We describe how a reference architecture can be iteratively designed and implemented to associate user needs with recurring systemic patterns, building on top of existing knowledge engineering workflows and boxologies. We provide a six-step roadmap that can enable the development of such an architecture, consisting of scope definition, selection of information sources, architectural analysis, synthesis of an architecture based on the information source analysis, evaluation through instantiation, and, ultimately, instantiation into a concrete software architecture. We provide an initial design and outcome of the definition of architectural scope, selection of information sources, and analysis. As the remaining steps of design, evaluation, and instantiation of the architecture are largely use-case specific, we provide a detailed description of their procedures and point to relevant examples. We expect that following through on this vision will lead to well-grounded reference architectures for knowledge engineering, will advance the ongoing initiatives of organizing the neurosymbolic knowledge engineering space, and will build new links to the software architectures and data science communities.
Cite as

Bradley P. Allen and Filip Ilievski. Standardizing Knowledge Engineering Practices with a Reference Architecture. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{allen_et_al:TGDK.2.1.5,
  author =	{Allen, Bradley P. and Ilievski, Filip},
  title =	{{Standardizing Knowledge Engineering Practices with a Reference Architecture}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{5:1--5:23},
  ISSN =	{2942-7517},
  year =	{2024},
  volume =	{2},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.5},
  URN =		{urn:nbn:de:0030-drops-198623},
  doi =		{10.4230/TGDK.2.1.5},
  annote =	{Keywords: knowledge engineering, knowledge graphs, quality attributes, software architectures, sociotechnical systems}
}
Document
Survey
DOI: 10.4230/TGDK.1.1.7
Rule Learning over Knowledge Graphs: A Review

Authors: Hong Wu, Zhe Wang, Kewen Wang, Pouya Ghiasnezhad Omran, and Jiangmeng Li

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
Compared to black-box neural networks, logic rules express explicit knowledge, can provide human-understandable explanations for reasoning processes, and have found their wide application in knowledge graphs and other downstream tasks. As extracting rules manually from large knowledge graphs is labour-intensive and often infeasible, automated rule learning has recently attracted significant interest, and a number of approaches to rule learning for knowledge graphs have been proposed. This survey aims to provide a review of approaches and a classification of state-of-the-art systems for learning first-order logic rules over knowledge graphs. A comparative analysis of various approaches to rule learning is conducted based on rule language biases, underlying methods, and evaluation metrics. The approaches we consider include inductive logic programming (ILP)-based, statistical path generalisation, and neuro-symbolic methods. Moreover, we highlight important and promising application scenarios of rule learning, such as rule-based knowledge graph completion, fact checking, and applications in other research areas.
Cite as

Hong Wu, Zhe Wang, Kewen Wang, Pouya Ghiasnezhad Omran, and Jiangmeng Li. Rule Learning over Knowledge Graphs: A Review. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{wu_et_al:TGDK.1.1.7,
  author =	{Wu, Hong and Wang, Zhe and Wang, Kewen and Omran, Pouya Ghiasnezhad and Li, Jiangmeng},
  title =	{{Rule Learning over Knowledge Graphs: A Review}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{7:1--7:23},
  ISSN =	{2942-7517},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.7},
  URN =		{urn:nbn:de:0030-drops-194813},
  doi =		{10.4230/TGDK.1.1.7},
  annote =	{Keywords: Rule learning, Knowledge graphs, Link prediction}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GIScience.2023.52
Impacts of Catchments Derived from Fine-Grained Mobility Data on Spatial Accessibility (Short Paper)

Authors: Alexander Michels, Jinwoo Park, Bo Li, Jeon-Young Kang, and Shaowen Wang

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

Abstract
Spatial accessibility is a powerful tool for understanding how access to important services and resources varies across space. While spatial accessibility methods traditionally rely on origin-destination matrices between centroids of administrative zones, recent work has examined creating polygonal catchments - areas within a travel-time threshold - from point-based fine-grained mobility data. In this paper, we investigate the difference between the convex hull and alpha shape algorithms for determining catchment areas and how this affects the results of spatial accessibility analyses. Our analysis shows that the choice of how we define a catchment produces differences in the measured accessibility which correlate with social vulnerability. These findings highlight the importance of evaluating and communicating minor methodological choices in spatial accessibility analyses.
Cite as

Alexander Michels, Jinwoo Park, Bo Li, Jeon-Young Kang, and Shaowen Wang. Impacts of Catchments Derived from Fine-Grained Mobility Data on Spatial Accessibility (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 52:1-52:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{michels_et_al:LIPIcs.GIScience.2023.52,
  author =	{Michels, Alexander and Park, Jinwoo and Li, Bo and Kang, Jeon-Young and Wang, Shaowen},
  title =	{{Impacts of Catchments Derived from Fine-Grained Mobility Data on Spatial Accessibility}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{52:1--52: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.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.52},
  URN =		{urn:nbn:de:0030-drops-189470},
  doi =		{10.4230/LIPIcs.GIScience.2023.52},
  annote =	{Keywords: Spatial accessibility, alpha shape, convex hull, cyberGIS, social vulnerability}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.32
Approximation Algorithm for Norm Multiway Cut

Authors: Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, and Liren Shan

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph G into k parts so as to separate k given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced 𝓁_p-norm Multiway Cut, a generalization of the problem, in which the goal is to minimize the 𝓁_p norm of the edge boundaries of k parts. We provide an O(log^{1/2} nlog^{1/2+1/p} k) approximation algorithm for this problem, improving upon the approximation guarantee of O(log^{3/2} n log^{1/2} k) due to Chandrasekaran and Wang. We also introduce and study Norm Multiway Cut, a further generalization of Multiway Cut. We assume that we are given access to an oracle, which answers certain queries about the norm. We present an O(log^{1/2} n log^{7/2} k) approximation algorithm with a weaker oracle and an O(log^{1/2} n log^{5/2} k) approximation algorithm with a stronger oracle. Additionally, we show that without any oracle access, there is no n^{1/4-ε} approximation algorithm for every ε > 0 assuming the Hypergraph Dense-vs-Random Conjecture.
Cite as

Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, and Liren Shan. Approximation Algorithm for Norm Multiway Cut. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{carlson_et_al:LIPIcs.ESA.2023.32,
  author =	{Carlson, Charlie and Jafarov, Jafar and Makarychev, Konstantin and Makarychev, Yury and Shan, Liren},
  title =	{{Approximation Algorithm for Norm Multiway Cut}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.32},
  URN =		{urn:nbn:de:0030-drops-186854},
  doi =		{10.4230/LIPIcs.ESA.2023.32},
  annote =	{Keywords: Multiway cut, Approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.64
Improved Quantum Boosting

Authors: Adam Izdebski and Ronald de Wolf

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Boosting is a general method to convert a weak learner (which generates hypotheses that are just slightly better than random) into a strong learner (which generates hypotheses that are much better than random). Recently, Arunachalam and Maity [Srinivasan Arunachalam and Reevu Maity, 2020] gave the first quantum improvement for boosting, by combining Freund and Schapire’s AdaBoost algorithm with a quantum algorithm for approximate counting. Their booster is faster than classical boosting as a function of the VC-dimension of the weak learner’s hypothesis class, but worse as a function of the quality of the weak learner. In this paper we give a substantially faster and simpler quantum boosting algorithm, based on Servedio’s SmoothBoost algorithm [Servedio, 2003].
Cite as

Adam Izdebski and Ronald de Wolf. Improved Quantum Boosting. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{izdebski_et_al:LIPIcs.ESA.2023.64,
  author =	{Izdebski, Adam and de Wolf, Ronald},
  title =	{{Improved Quantum Boosting}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.64},
  URN =		{urn:nbn:de:0030-drops-187178},
  doi =		{10.4230/LIPIcs.ESA.2023.64},
  annote =	{Keywords: Learning theory, Boosting algorithms, Quantum computing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.101
Improved Algorithms for Distance Selection and Related Problems

Authors: Haitao Wang and Yiming Zhao

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
In this paper, we propose new techniques for solving geometric optimization problems involving interpoint distances of a point set in the plane. Given a set P of n points in the plane and an integer 1 ≤ k ≤ binom(n,2), the distance selection problem is to find the k-th smallest interpoint distance among all pairs of points of P. The previously best deterministic algorithm solves the problem in O(n^{4/3} log² n) time [Katz and Sharir, 1997]. In this paper, we improve their algorithm to O(n^{4/3} log n) time. Using similar techniques, we also give improved algorithms on both the two-sided and the one-sided discrete Fréchet distance with shortcuts problem for two point sets in the plane. For the two-sided problem (resp., one-sided problem), we improve the previous work [Avraham, Filtser, Kaplan, Katz, and Sharir, 2015] by a factor of roughly log²(m+n) (resp., (m+n)^ε), where m and n are the sizes of the two input point sets, respectively. Other problems whose solutions can be improved by our techniques include the reverse shortest path problems for unit-disk graphs. Our techniques are quite general and we believe they will find many other applications in future.
Cite as

Haitao Wang and Yiming Zhao. Improved Algorithms for Distance Selection and Related Problems. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 101:1-101:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ESA.2023.101,
  author =	{Wang, Haitao and Zhao, Yiming},
  title =	{{Improved Algorithms for Distance Selection and Related Problems}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{101:1--101:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.101},
  URN =		{urn:nbn:de:0030-drops-187544},
  doi =		{10.4230/LIPIcs.ESA.2023.101},
  annote =	{Keywords: Geometric optimization, distance selection, Fr\'{e}chet distance, range searching}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2023.16
Constraint Based Compiler Optimization for Energy Harvesting Applications

Authors: Yannan Li and Chao Wang

Published in: LIPIcs, Volume 263, 37th European Conference on Object-Oriented Programming (ECOOP 2023)

Abstract
We propose a method for optimizing the energy efficiency of software code running on small computing devices in the Internet of Things (IoT) that are powered exclusively by electricity harvested from ambient energy in the environment. Due to the weak and unstable nature of the energy source, it is challenging for developers to manually optimize the software code to deal with mismatch between the intermittent power supply and the computation demand. Our method overcomes the challenge by using a combination of three techniques. First, we use static program analysis to automatically identify opportunities for precomputation, i.e., computation that may be performed ahead of time as opposed to just in time. Second, we optimize the precomputation policy, i.e., a way to split and reorder steps of a computation task in the original software to match the intermittent power supply while satisfying a variety of system requirements; this is accomplished by formulating energy optimization as a constraint satisfiability problem and then solving the problem using an off-the-shelf SMT solver. Third, we use a state-of-the-art compiler platform (LLVM) to automate the program transformation to ensure that the optimized software code is correct by construction. We have evaluated our method on a large number of benchmark programs, which are C programs implementing secure communication protocols that are popular for energy-harvesting IoT devices. Our experimental results show that the method is efficient in optimizing all benchmark programs. Furthermore, the optimized programs significantly outperform the original programs in terms of energy efficiency and latency, and the overall improvement ranges from 2.3X to 36.7X.
Cite as

Yannan Li and Chao Wang. Constraint Based Compiler Optimization for Energy Harvesting Applications. In 37th European Conference on Object-Oriented Programming (ECOOP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 263, pp. 16:1-16:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ECOOP.2023.16,
  author =	{Li, Yannan and Wang, Chao},
  title =	{{Constraint Based Compiler Optimization for Energy Harvesting Applications}},
  booktitle =	{37th European Conference on Object-Oriented Programming (ECOOP 2023)},
  pages =	{16:1--16:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-281-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{263},
  editor =	{Ali, Karim and Salvaneschi, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2023.16},
  URN =		{urn:nbn:de:0030-drops-182096},
  doi =		{10.4230/LIPIcs.ECOOP.2023.16},
  annote =	{Keywords: Compiler, energy optimization, constraint solving, cryptography, IoT}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.87
Simulating Markovian Open Quantum Systems Using Higher-Order Series Expansion

Authors: Xiantao Li and Chunhao Wang

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We present an efficient quantum algorithm for simulating the dynamics of Markovian open quantum systems. The performance of our algorithm is similar to the previous state-of-the-art quantum algorithm, i.e., it scales linearly in evolution time and poly-logarithmically in inverse precision. However, our algorithm is conceptually cleaner, and it only uses simple quantum primitives without compressed encoding. Our approach is based on a novel mathematical treatment of the evolution map, which involves a higher-order series expansion based on Duhamel’s principle and approximating multiple integrals using scaled Gaussian quadrature. Our method easily generalizes to simulating quantum dynamics with time-dependent Lindbladians. Furthermore, our method of approximating multiple integrals using scaled Gaussian quadrature could potentially be used to produce a more efficient approximation of time-ordered integrals, and therefore can simplify existing quantum algorithms for simulating time-dependent Hamiltonians based on a truncated Dyson series.
Cite as

Xiantao Li and Chunhao Wang. Simulating Markovian Open Quantum Systems Using Higher-Order Series Expansion. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 87:1-87:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ICALP.2023.87,
  author =	{Li, Xiantao and Wang, Chunhao},
  title =	{{Simulating Markovian Open Quantum Systems Using Higher-Order Series Expansion}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{87:1--87:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel 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.2023.87},
  URN =		{urn:nbn:de:0030-drops-181395},
  doi =		{10.4230/LIPIcs.ICALP.2023.87},
  annote =	{Keywords: Quantum algorithms, open quantum systems, Lindblad simulation}
}
Document
Artifact
DOI: 10.4230/DARTS.8.2.24
PEDroid: Automatically Extracting Patches from Android App Updates (Artifact)

Authors: Hehao Li, Yizhuo Wang, Yiwei Zhang, Juanru Li, and Dawu Gu

Published in: DARTS, Volume 8, Issue 2, Special Issue of the 36th European Conference on Object-Oriented Programming (ECOOP 2022)

Abstract
We propose an approach to automatically identify and extract patches from updated Android apps by comparing the updated versions and their predecessors. PEDroid, a prototype patch extraction tool against Android apps, consists of two phases: differential analysis and patch identification. We evaluated it with a set of popular open-source apps to demonstrate its effectiveness. PEDroid achieves a recall of 92% in differential analysis and successfully identifies 28 of 36 patches in patch identification. We also provide specific guidance on reproducing the experimental results.
Cite as

Hehao Li, Yizhuo Wang, Yiwei Zhang, Juanru Li, and Dawu Gu. PEDroid: Automatically Extracting Patches from Android App Updates (Artifact). In Special Issue of the 36th European Conference on Object-Oriented Programming (ECOOP 2022). Dagstuhl Artifacts Series (DARTS), Volume 8, Issue 2, pp. 24:1-24:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{li_et_al:DARTS.8.2.24,
  author =	{Li, Hehao and Wang, Yizhuo and Zhang, Yiwei and Li, Juanru and Gu, Dawu},
  title =	{{PEDroid: Automatically Extracting Patches from Android App Updates (Artifact)}},
  pages =	{24:1--24:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2022},
  volume =	{8},
  number =	{2},
  editor =	{Li, Hehao and Wang, Yizhuo and Zhang, Yiwei and Li, Juanru and Gu, Dawu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.8.2.24},
  URN =		{urn:nbn:de:0030-drops-162229},
  doi =		{10.4230/DARTS.8.2.24},
  annote =	{Keywords: Diffing, Patch Identification, Android App Analysis, App Evolution}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2022.21
PEDroid: Automatically Extracting Patches from Android App Updates

Authors: Hehao Li, Yizhuo Wang, Yiwei Zhang, Juanru Li, and Dawu Gu

Published in: LIPIcs, Volume 222, 36th European Conference on Object-Oriented Programming (ECOOP 2022)

Abstract
Identifying and analyzing code patches is a common practice to not only understand existing bugs but also help find and fix similar bugs in new projects. Most patch analysis techniques aim at open-source projects, in which the differentials of source code are easily identified, and some extra information such as code commit logs could be leveraged to help find and locate patches. The task, however, becomes challenging when source code as well as development logs are lacking. A typical scenario is to discover patches in an updated Android app, which requires bytecode-level analysis. In this paper, we propose an approach to automatically identify and extract patches from updated Android apps by comparing the updated versions and their predecessors. Given two Android apps (original and updated versions), our approach first identifies identical and modified methods by similarity comparison through code features and app structures. Then, it compares these modified methods with their original implementations in the original app, and detects whether a patch is applied to the modified method by analyzing the difference in internal semantics. We implemented PEDroid, a prototype patch extraction tool against Android apps, and evaluated it with a set of popular open-source apps and a set of real-world apps from different Android vendors. PEDroid identifies 28 of the 36 known patches in the former, and successfully analyzes 568 real-world app updates in the latter, among which 94.37% of updates could be completed within 20 minutes.
Cite as

Hehao Li, Yizhuo Wang, Yiwei Zhang, Juanru Li, and Dawu Gu. PEDroid: Automatically Extracting Patches from Android App Updates. In 36th European Conference on Object-Oriented Programming (ECOOP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 222, pp. 21:1-21:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ECOOP.2022.21,
  author =	{Li, Hehao and Wang, Yizhuo and Zhang, Yiwei and Li, Juanru and Gu, Dawu},
  title =	{{PEDroid: Automatically Extracting Patches from Android App Updates}},
  booktitle =	{36th European Conference on Object-Oriented Programming (ECOOP 2022)},
  pages =	{21:1--21:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-225-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{222},
  editor =	{Ali, Karim and Vitek, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2022.21},
  URN =		{urn:nbn:de:0030-drops-162498},
  doi =		{10.4230/LIPIcs.ECOOP.2022.21},
  annote =	{Keywords: Diffing, Patch Identification, Android App Analysis, App Evolution}
}
Document
Extended Abstract
DOI: 10.4230/OASIcs.Tokenomics.2021.10
Detecting and Quantifying Crypto Wash Trading (Extended Abstract)

Authors: Lin William Cong, Xi Li, Ke Tang, and Yang Yang

Published in: OASIcs, Volume 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)

Abstract
We introduce systematic tests exploiting robust statistical and behavioral patterns in trading to detect fake transactions on 29 cryptocurrency exchanges. Regulated exchanges feature patterns consistently observed in financial markets and nature; abnormal first-significant-digit distributions, size rounding, and transaction tail distributions on unregulated exchanges reveal rampant manipulations unlikely driven by strategy or exchange heterogeneity. We quantify the wash trading on each unregulated exchange, which averaged over 70% of the reported volume. We further document how these fabricated volumes (trillions of dollars annually) improve exchange ranking, temporarily distort prices, and relate to exchange characteristics (e.g., age and userbase), market conditions, and regulation.
Cite as

Lin William Cong, Xi Li, Ke Tang, and Yang Yang. Detecting and Quantifying Crypto Wash Trading (Extended Abstract). In 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, pp. 10:1-10:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cong_et_al:OASIcs.Tokenomics.2021.10,
  author =	{Cong, Lin William and Li, Xi and Tang, Ke and Yang, Yang},
  title =	{{Detecting and Quantifying Crypto Wash Trading}},
  booktitle =	{3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)},
  pages =	{10:1--10:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-220-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{97},
  editor =	{Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021.10},
  URN =		{urn:nbn:de:0030-drops-159072},
  doi =		{10.4230/OASIcs.Tokenomics.2021.10},
  annote =	{Keywords: Bitcoin, Cryptocurrency, FinTech, Forensic Finance, Fraud Detection, Regulation}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.39
Improving Local Search for Minimum Weighted Connected Dominating Set Problem by Inner-Layer Local Search

Authors: Bohan Li, Kai Wang, Yiyuan Wang, and Shaowei Cai

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
The minimum weighted connected dominating set (MWCDS) problem is an important variant of connected dominating set problems with wide applications, especially in heterogenous networks and gene regulatory networks. In the paper, we develop a nested local search algorithm called NestedLS for solving MWCDS on classic benchmarks and massive graphs. In this local search framework, we propose two novel ideas to make it effective by utilizing previous search information. First, we design the restart based smoothing mechanism as a diversification method to escape from local optimal. Second, we propose a novel inner-layer local search method to enlarge the candidate removal set, which can be modelled as an optimized version of spanning tree problem. Moreover, inner-layer local search method is a general method for maintaining the connectivity constraint when dealing with massive graphs. Experimental results show that NestedLS outperforms state-of-the-art meta-heuristic algorithms on most instances.
Cite as

Bohan Li, Kai Wang, Yiyuan Wang, and Shaowei Cai. Improving Local Search for Minimum Weighted Connected Dominating Set Problem by Inner-Layer Local Search. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.CP.2021.39,
  author =	{Li, Bohan and Wang, Kai and Wang, Yiyuan and Cai, Shaowei},
  title =	{{Improving Local Search for Minimum Weighted Connected Dominating Set Problem by Inner-Layer Local Search}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{39:1--39:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.39},
  URN =		{urn:nbn:de:0030-drops-153304},
  doi =		{10.4230/LIPIcs.CP.2021.39},
  annote =	{Keywords: Operations Research, NP-hard Problem, Local Search, Weighted Connected Dominating Set Problem}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.5
A Unified Framework of FPT Approximation Algorithms for Clustering Problems

Authors: Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
In this paper, we present a framework for designing FPT approximation algorithms for many k-clustering problems. Our results are based on a new technique for reducing search spaces. A reduced search space is a small subset of the input data that has the guarantee of containing k clients close to the facilities opened in an optimal solution for any clustering problem we consider. We show, somewhat surprisingly, that greedily sampling O(k) clients yields the desired reduced search space, based on which we obtain FPT(k)-time algorithms with improved approximation guarantees for problems such as capacitated clustering, lower-bounded clustering, clustering with service installation costs, fault tolerant clustering, and priority clustering.
Cite as

Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang. A Unified Framework of FPT Approximation Algorithms for Clustering Problems. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ISAAC.2020.5,
  author =	{Feng, Qilong and Zhang, Zhen and Huang, Ziyun and Xu, Jinhui and Wang, Jianxin},
  title =	{{A Unified Framework of FPT Approximation Algorithms for Clustering Problems}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.5},
  URN =		{urn:nbn:de:0030-drops-133495},
  doi =		{10.4230/LIPIcs.ISAAC.2020.5},
  annote =	{Keywords: clustering, approximation algorithms, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.47
Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension

Authors: Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
We present two efficient classical analogues of the quantum matrix inversion algorithm [Harrow et al., 2009] for low-rank matrices. Inspired by recent work of Tang [Tang, 2019], assuming length-square sampling access to input data, we implement the pseudoinverse of a low-rank matrix allowing us to sample from the solution to the problem Ax = b using fast sampling techniques. We construct implicit descriptions of the pseudo-inverse by finding approximate singular value decomposition of A via subsampling, then inverting the singular values. In principle, our approaches can also be used to apply any desired "smooth" function to the singular values. Since many quantum algorithms can be expressed as a singular value transformation problem [András Gilyén et al., 2019], our results indicate that more low-rank quantum algorithms can be effectively "dequantised" into classical length-square sampling algorithms.
Cite as

Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang. Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.ISAAC.2020.47,
  author =	{Chia, Nai-Hui and Gily\'{e}n, Andr\'{a}s and Lin, Han-Hsuan and Lloyd, Seth and Tang, Ewin and Wang, Chunhao},
  title =	{{Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.47},
  URN =		{urn:nbn:de:0030-drops-133916},
  doi =		{10.4230/LIPIcs.ISAAC.2020.47},
  annote =	{Keywords: sublinear algorithms, quantum-inspired, regression, importance sampling, quantum machine learning}
}
  • Refine by Author
  • 4 Wang, Haitao
  • 3 Wang, Chunhao
  • 2 Chia, Nai-Hui
  • 2 Feng, Qilong
  • 2 Gu, Dawu
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Computational geometry
  • 2 Computing methodologies → Knowledge representation and reasoning
  • 2 Software and its engineering → Software evolution
  • 2 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 2 Android App Analysis
  • 2 App Evolution
  • 2 Diffing
  • 2 Patch Identification
  • 1 API migration
  • Show More...

  • Refine by Type
  • 30 document

  • Refine by Publication Year
  • 7 2020
  • 7 2023
  • 4 2016
  • 3 2017
  • 3 2022
  • Show More...

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