4 Search Results for "Martin, Graham R."


Document
The Importance of Parameters in Database Queries

Authors: Martin Grohe, Benny Kimelfeld, Peter Lindner, and Christoph Standke

Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)


Abstract
We propose and study a framework for quantifying the importance of the choices of parameter values to the result of a query over a database. These parameters occur as constants in logical queries, such as conjunctive queries. In our framework, the importance of a parameter is its SHAP score. This score is a popular instantiation of the game-theoretic Shapley value to measuring the importance of feature values in machine learning models. We make the case for the rationale of using this score by explaining the intuition behind SHAP, and by showing that we arrive at this score in two different, apparently opposing, approaches to quantifying the contribution of a parameter. The application of the SHAP score requires two components in addition to the query and the database: (a) a probability distribution over the combinations of parameter values, and (b) a utility function that measures the similarity between the result for the original parameters and the result for hypothetical parameters. The main question addressed in the paper is the complexity of calculating the SHAP score for different distributions and similarity measures. We first address the case of probabilistically independent parameters. The problem is hard if we consider a fragment of queries that is hard to evaluate (as one would expect), and even for the fragment of acyclic conjunctive queries. In some cases, though, one can efficiently list all relevant parameter combinations, and then the SHAP score can be computed in polynomial time under reasonable general conditions. Also tractable is the case of full acyclic conjunctive queries for certain (natural) similarity functions. We extend our results to conjunctive queries with inequalities between variables and parameters. Finally, we discuss a simple approximation technique for the case of correlated parameters.

Cite as

Martin Grohe, Benny Kimelfeld, Peter Lindner, and Christoph Standke. The Importance of Parameters in Database Queries. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.ICDT.2024.14,
  author =	{Grohe, Martin and Kimelfeld, Benny and Lindner, Peter and Standke, Christoph},
  title =	{{The Importance of Parameters in Database Queries}},
  booktitle =	{27th International Conference on Database Theory (ICDT 2024)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-312-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{290},
  editor =	{Cormode, Graham and Shekelyan, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.14},
  URN =		{urn:nbn:de:0030-drops-197966},
  doi =		{10.4230/LIPIcs.ICDT.2024.14},
  annote =	{Keywords: SHAP score, query parameters, Shapley value}
}
Document
RANDOM
Subset Sum in Time 2^{n/2} / poly(n)

Authors: Xi Chen, Yaonan Jin, Tim Randolph, and Rocco A. Servedio

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


Abstract
A major goal in the area of exact exponential algorithms is to give an algorithm for the (worst-case) n-input Subset Sum problem that runs in time 2^{(1/2 - c)n} for some constant c > 0. In this paper we give a Subset Sum algorithm with worst-case running time O(2^{n/2} ⋅ n^{-γ}) for a constant γ > 0.5023 in standard word RAM or circuit RAM models. To the best of our knowledge, this is the first improvement on the classical "meet-in-the-middle" algorithm for worst-case Subset Sum, due to Horowitz and Sahni, which can be implemented in time O(2^{n/2}) in these memory models [Horowitz and Sahni, 1974]. Our algorithm combines a number of different techniques, including the "representation method" introduced by Howgrave-Graham and Joux [Howgrave-Graham and Joux, 2010] and subsequent adaptations of the method in Austrin, Kaski, Koivisto, and Nederlof [Austrin et al., 2016], and Nederlof and Węgrzycki [Jesper Nederlof and Karol Wegrzycki, 2021], and "bit-packing" techniques used in the work of Baran, Demaine, and Pǎtraşcu [Baran et al., 2005] on subquadratic algorithms for 3SUM.

Cite as

Xi Chen, Yaonan Jin, Tim Randolph, and Rocco A. Servedio. Subset Sum in Time 2^{n/2} / poly(n). In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2023.39,
  author =	{Chen, Xi and Jin, Yaonan and Randolph, Tim and Servedio, Rocco A.},
  title =	{{Subset Sum in Time 2^\{n/2\} / poly(n)}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{39:1--39:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  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.2023.39},
  URN =		{urn:nbn:de:0030-drops-188641},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.39},
  annote =	{Keywords: Exact algorithms, subset sum, log shaving}
}
Document
Fast Implementation of the Scalable Video Coding Extension of the H.264/AVC Standard

Authors: Xin Lu and Graham R. Martin

Published in: OASIcs, Volume 35, 2013 Imperial College Computing Student Workshop


Abstract
In order to improve coding efficiency in the scalable extension of H.264/AVC, an inter-layer prediction mechanism is incorporated. This exploits as much lower layer information as possible to inform the process of coding the enhancement layer(s). However it also greatly increases the computational complexity. In this paper, a fast mode decision algorithm for efficient implementation of the SVC encoder is described. The proposed algorithm not only considers inter-layer correlation but also fully exploits both spatial and temporal correlation as well as an assessment of macroblock texture. All of these factors are organised within a hierarchical structure in the mode decision process. At each level of the structure, different strategies are implemented to eliminate inappropriate candidate modes. Simulation results show that the proposed algorithm reduces encoding time by up to 85% compared with the JSVM 9.18 implementation. This is achieved without any noticeable degradation in rate distortion.

Cite as

Xin Lu and Graham R. Martin. Fast Implementation of the Scalable Video Coding Extension of the H.264/AVC Standard. In 2013 Imperial College Computing Student Workshop. Open Access Series in Informatics (OASIcs), Volume 35, pp. 65-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{lu_et_al:OASIcs.ICCSW.2013.65,
  author =	{Lu, Xin and Martin, Graham R.},
  title =	{{Fast Implementation of the Scalable Video Coding Extension of the H.264/AVC Standard}},
  booktitle =	{2013 Imperial College Computing Student Workshop},
  pages =	{65--72},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-63-7},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{35},
  editor =	{Jones, Andrew V. and Ng, Nicholas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2013.65},
  URN =		{urn:nbn:de:0030-drops-42737},
  doi =		{10.4230/OASIcs.ICCSW.2013.65},
  annote =	{Keywords: Fast mode selection, Inter-layer prediction, Scalable Video Coding (SVC), SVC extension of H.264/AVC.}
}
Document
Improved Rate Control Algorithm for Scalable Video Coding

Authors: Xin Lu and Graham R. Martin

Published in: OASIcs, Volume 35, 2013 Imperial College Computing Student Workshop


Abstract
In the Scalable Video Coding (SVC) standard, a multi-layer based structure is utilised to support scalability. However in the latest Joint Scalable Video Model (JSVM) reference software, the rate control algorithm is implemented only in the base layer, and the enhancement layers are not equipped with a rate control scheme. In this work, a novel rate control algorithm is proposed for when inter-layer prediction is employed. Firstly, a Rate-Quantisation (R-Q) model, which considers the coding properties of different prediction modes, is described. Secondly, an improved Mean Absolute Difference (MAD) prediction model for the spatial enhancement layers is proposed, in which the encoding results from the base layer are used to assist the linear MAD prediction in the spatial/CGS enhancement layers. Simulation results show that, on average, rate control accuracy is maintained to within 0.07%. Compared with the default JVT-G012 rate control scheme employed in SVC, the proposed rate control algorithm achieves higher coding efficiency, namely an improvement of up to 0.26dB in PSNR and a saving of 4.66% in bitrate.

Cite as

Xin Lu and Graham R. Martin. Improved Rate Control Algorithm for Scalable Video Coding. In 2013 Imperial College Computing Student Workshop. Open Access Series in Informatics (OASIcs), Volume 35, pp. 73-80, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{lu_et_al:OASIcs.ICCSW.2013.73,
  author =	{Lu, Xin and Martin, Graham R.},
  title =	{{Improved Rate Control Algorithm for Scalable Video Coding}},
  booktitle =	{2013 Imperial College Computing Student Workshop},
  pages =	{73--80},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-63-7},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{35},
  editor =	{Jones, Andrew V. and Ng, Nicholas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2013.73},
  URN =		{urn:nbn:de:0030-drops-42744},
  doi =		{10.4230/OASIcs.ICCSW.2013.73},
  annote =	{Keywords: Inter-layer prediction, MAD prediction, Rate control, Scalable Video Coding (SVC), SVC extension of H.264/AVC}
}
  • Refine by Author
  • 2 Lu, Xin
  • 2 Martin, Graham R.
  • 1 Chen, Xi
  • 1 Grohe, Martin
  • 1 Jin, Yaonan
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Database query languages (principles)
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 2 Inter-layer prediction
  • 2 Scalable Video Coding (SVC)
  • 1 Exact algorithms
  • 1 Fast mode selection
  • 1 MAD prediction
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2013
  • 1 2023
  • 1 2024

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