16 Search Results for "Jensen, Christian S."

Document
DOI: 10.4230/OASIcs.ATMOS.2024.2
Indexing Graphs for Shortest Beer Path Queries

Authors: David Coudert, Andrea D'Ascenzo, and Mattia D'Emidio

Published in: OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)

Abstract
A beer graph is an edge-weighted graph G = (V,E,ω) with beer vertices B ⊆ V. A beer path between two vertices s and t of a beer graph is a path that connects s and t and visits at least one vertex in B. The beer distance between two vertices is the weight of a shortest beer path, i.e. a beer path having minimum total weight. A graph indexing scheme is a two-phase method that constructs an index data structure by a one-time preprocessing of an input graph and then exploits it to compute (or accelerate the computation of) answers to queries on structures of the graph dataset. In the last decade, such indexing schemes have been designed to perform, effectively, many relevant types of queries, e.g. on reachability, and have gained significant popularity in essentially all data-intensive application domains where large number of queries have to be routinely answered (e.g. journey planners), since they have been shown, through many experimental studies, to offer extremely low query times at the price of limited preprocessing time and space overheads. In this paper, we showcase that an indexing scheme, to efficiently execute queries on beer distances or shortest beer paths for pairs of vertices of a beer graph, can be obtained by adapting the highway labeling, a recently introduced indexing method to accelerate the computation of classical shortest paths. We design a preprocessing algorithm to build a whl index, i.e. a weighted highway labeling of a beer graph, and show how it can be queried to compute beer distances and shortest beer paths. Through extensive experimentation on real networks, we empirically demonstrate its practical effectiveness and superiority, in terms of offered trade-off between preprocessing time, space overhead and query time, with respect to the state-of-the-art.
Cite as

David Coudert, Andrea D'Ascenzo, and Mattia D'Emidio. Indexing Graphs for Shortest Beer Path Queries. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{coudert_et_al:OASIcs.ATMOS.2024.2,
  author =	{Coudert, David and D'Ascenzo, Andrea and D'Emidio, Mattia},
  title =	{{Indexing Graphs for Shortest Beer Path Queries}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{2:1--2:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.2},
  URN =		{urn:nbn:de:0030-drops-211907},
  doi =		{10.4230/OASIcs.ATMOS.2024.2},
  annote =	{Keywords: Graph Algorithms, Indexing Schemes, Beer Distances, Algorithms Engineering}
}
Document
DOI: 10.4230/LIPIcs.AFT.2024.10
Optimal RANDAO Manipulation in Ethereum

Authors: Kaya Alpturer and S. Matthew Weinberg

Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)

Abstract
It is well-known that RANDAO manipulation is possible in Ethereum if an adversary controls the proposers assigned to the last slots in an epoch. We provide a methodology to compute, for any fraction α of stake owned by an adversary, the maximum fraction f(α) of rounds that a strategic adversary can propose. We further implement our methodology and compute f(⋅) for all α. For example, we conclude that an optimal strategic participant with 5% of the stake can propose a 5.048% fraction of rounds, 10% of the stake can propose a 10.19% fraction of rounds, and 20% of the stake can propose a 20.68% fraction of rounds.
Cite as

Kaya Alpturer and S. Matthew Weinberg. Optimal RANDAO Manipulation in Ethereum. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{alpturer_et_al:LIPIcs.AFT.2024.10,
  author =	{Alpturer, Kaya and Weinberg, S. Matthew},
  title =	{{Optimal RANDAO Manipulation in Ethereum}},
  booktitle =	{6th Conference on Advances in Financial Technologies (AFT 2024)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-345-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{316},
  editor =	{B\"{o}hme, Rainer and Kiffer, Lucianna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.10},
  URN =		{urn:nbn:de:0030-drops-209467},
  doi =		{10.4230/LIPIcs.AFT.2024.10},
  annote =	{Keywords: Proof of Stake, Consensus, Blockchain, Ethereum, Randomness manipulation}
}
Document
DOI: 10.4230/LIPIcs.AFT.2024.29
Transaction Fee Mechanism Design in a Post-MEV World

Authors: Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden

Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)

Abstract
The incentive-compatibility properties of blockchain transaction fee mechanisms have been investigated with passive block producers that are motivated purely by the net rewards earned at the consensus layer. This paper introduces a model of active block producers that have their own private valuations for blocks (representing, for example, additional value derived from the application layer). The block producer surplus in our model can be interpreted as one of the more common colloquial meanings of the phrase "maximal extractable value (MEV)." We first prove that transaction fee mechanism design is fundamentally more difficult with active block producers than with passive ones: With active block producers, no non-trivial or approximately welfare-maximizing transaction fee mechanism can be incentive-compatible for both users and block producers. These results can be interpreted as a mathematical justification for augmenting transaction fee mechanisms with additional components such as order flow auctions, block producer competition, trusted hardware, or cryptographic techniques. We then consider a more fine-grained model of block production that more accurately reflects current practice, in which we distinguish the roles of "searchers" (who actively identify opportunities for value extraction from the application layer and compete for the right to take advantage of them) and "proposers" (who participate directly in the blockchain protocol and make the final choice of the published block). Searchers can effectively act as an "MEV oracle" for a transaction fee mechanism, thereby enlarging the design space. Here, we first consider a TFM that is inspired by how searchers have traditionally been incorporated into the block production process, with each transaction effectively sold off to a searcher through a first-price auction. We then explore the TFM design space with searchers more generally, and design a mechanism that circumvents our impossibility results for TFMs without searchers. Our mechanism (the "SAKA" mechanism) is incentive-compatible (for users, searchers, and the block producer), sybil-proof, and guarantees roughly 50% of the maximum-possible welfare when transaction sizes are small relative to block sizes. We conclude with a matching negative result: even when transaction sizes are small, no DSIC and sybil-proof deterministic TFM can guarantee more than 50% of the maximum-possible welfare.
Cite as

Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden. Transaction Fee Mechanism Design in a Post-MEV World. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 29:1-29:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bahrani_et_al:LIPIcs.AFT.2024.29,
  author =	{Bahrani, Maryam and Garimidi, Pranav and Roughgarden, Tim},
  title =	{{Transaction Fee Mechanism Design in a Post-MEV World}},
  booktitle =	{6th Conference on Advances in Financial Technologies (AFT 2024)},
  pages =	{29:1--29:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-345-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{316},
  editor =	{B\"{o}hme, Rainer and Kiffer, Lucianna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.29},
  URN =		{urn:nbn:de:0030-drops-209658},
  doi =		{10.4230/LIPIcs.AFT.2024.29},
  annote =	{Keywords: MEV, Transaction Fee Mechanisms, Auctions}
}
Document
DOI: 10.4230/LIPIcs.AFT.2024.30
Profitable Manipulations of Cryptographic Self-Selection Are Statistically Detectable

Authors: Linda Cai, Jingyi Liu, S. Matthew Weinberg, and Chenghan Zhou

Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)

Abstract
Cryptographic Self-Selection is a common primitive underlying leader-selection for Proof-of-Stake blockchain protocols. The concept was first popularized in Algorand [Jing Chen and Silvio Micali, 2019], who also observed that the protocol might be manipulable. [Matheus V. X. Ferreira et al., 2022] provide a concrete manipulation that is strictly profitable for a staker of any size (and also prove upper bounds on the gains from manipulation). Separately, [Maryam Bahrani and S. Matthew Weinberg, 2024; Aviv Yaish et al., 2023] initiate the study of undetectable profitable manipulations of consensus protocols with a focus on the seminal Selfish Mining strategy [Eyal and Sirer, 2014] for Bitcoin’s Proof-of-Work longest-chain protocol. They design a Selfish Mining variant that, for sufficiently large miners, is strictly profitable yet also indistinguishable to an onlooker from routine latency (that is, a sufficiently large profit-maximizing miner could use their strategy to strictly profit over being honest in a way that still appears to the rest of the network as though everyone is honest but experiencing mildly higher latency. This avoids any risk of negatively impacting the value of the underlying cryptocurrency due to attack detection). We investigate the detectability of profitable manipulations of the canonical cryptographic self-selection leader selection protocol introduced in [Jing Chen and Silvio Micali, 2019] and studied in [Matheus V. X. Ferreira et al., 2022], and establish that for any player with α < (3-√5)/2 ≈ 0.38 fraction of the total stake, every strictly profitable manipulation is statistically detectable. Specifically, we consider an onlooker who sees only the random seed of each round (and does not need to see any other broadcasts by any other players). We show that the distribution of the sequence of random seeds when any player is profitably manipulating the protocol is inconsistent with any distribution that could arise by honest stakers being offline or timing out (for a natural stylized model of honest timeouts).
Cite as

Linda Cai, Jingyi Liu, S. Matthew Weinberg, and Chenghan Zhou. Profitable Manipulations of Cryptographic Self-Selection Are Statistically Detectable. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 30:1-30:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.AFT.2024.30,
  author =	{Cai, Linda and Liu, Jingyi and Weinberg, S. Matthew and Zhou, Chenghan},
  title =	{{Profitable Manipulations of Cryptographic Self-Selection Are Statistically Detectable}},
  booktitle =	{6th Conference on Advances in Financial Technologies (AFT 2024)},
  pages =	{30:1--30:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-345-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{316},
  editor =	{B\"{o}hme, Rainer and Kiffer, Lucianna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.30},
  URN =		{urn:nbn:de:0030-drops-209660},
  doi =		{10.4230/LIPIcs.AFT.2024.30},
  annote =	{Keywords: Blockchain, Cryptocurrency, Proof-of-Stake, Strategic Mining, Statistical Detection}
}
Document
DOI: 10.4230/LIPIcs.COSIT.2024.5
Spatial Nudging: Converging Persuasive Technologies, Spatial Design, and Behavioral Theories

Authors: Ayda Grisiute and Martin Raubal

Published in: LIPIcs, Volume 315, 16th International Conference on Spatial Information Theory (COSIT 2024)

Abstract
This paper presents the Spatial Nudging framework - a theory-based framework that maps out nudging strategies in the mobility domain and refines its existing definitions. We link these strategies by highlighting the role of perceived affordances across physical and digital interventions based on the Nudge Theory and the Theory of Affordances. Furthermore, we propose to use graph representation techniques as a supportive methodology to better align perceived and actual environments, thereby enhancing the intervention strategies' effectiveness. We illustrate the applicability of the Spatial Nudging framework and the supportive methodology in the context of an E-bike City vision. This paper lays the foundation for future research on theoretically integrating physical and digital interventions to promote sustainable mobility.
Cite as

Ayda Grisiute and Martin Raubal. Spatial Nudging: Converging Persuasive Technologies, Spatial Design, and Behavioral Theories. In 16th International Conference on Spatial Information Theory (COSIT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 315, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{grisiute_et_al:LIPIcs.COSIT.2024.5,
  author =	{Grisiute, Ayda and Raubal, Martin},
  title =	{{Spatial Nudging: Converging Persuasive Technologies, Spatial Design, and Behavioral Theories}},
  booktitle =	{16th International Conference on Spatial Information Theory (COSIT 2024)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-330-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{315},
  editor =	{Adams, Benjamin and Griffin, Amy L. and Scheider, Simon and McKenzie, Grant},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2024.5},
  URN =		{urn:nbn:de:0030-drops-208206},
  doi =		{10.4230/LIPIcs.COSIT.2024.5},
  annote =	{Keywords: spatial nudging, active mobility, Nudge Theory, Theory of Affordances, cognitive graphs}
}
Document
DOI: 10.4230/LIPIcs.SEA.2024.6
Faster Treewidth-Based Approximations for Wiener Index

Authors: Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit Jitendra Motwani

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
The Wiener index of a graph G is the sum of distances between all pairs of its vertices. It is a widely-used graph property in chemistry, initially introduced to examine the link between boiling points and structural properties of alkanes, which later found notable applications in drug design. Thus, computing or approximating the Wiener index of molecular graphs, i.e. graphs in which every vertex models an atom of a molecule and every edge models a bond, is of significant interest to the computational chemistry community. In this work, we build upon the observation that molecular graphs are sparse and tree-like and focus on developing efficient algorithms parameterized by treewidth to approximate the Wiener index. We present a new randomized approximation algorithm using a combination of tree decompositions and centroid decompositions. Our algorithm approximates the Wiener index within any desired multiplicative factor (1 ± ε) in time O(n ⋅ log n ⋅ k³ + √n ⋅ k/ε²), where n is the number of vertices of the graph and k is the treewidth. This time bound is almost-linear in n. Finally, we provide experimental results over standard benchmark molecules from PubChem and the Protein Data Bank, showcasing the applicability and scalability of our approach on real-world chemical graphs and comparing it with previous methods.
Cite as

Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit Jitendra Motwani. Faster Treewidth-Based Approximations for Wiener Index. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{conrado_et_al:LIPIcs.SEA.2024.6,
  author =	{Conrado, Giovanna Kobus and Goharshady, Amir Kafshdar and Hudec, Pavel and Li, Pingjiang and Motwani, Harshit Jitendra},
  title =	{{Faster Treewidth-Based Approximations for Wiener Index}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.6},
  URN =		{urn:nbn:de:0030-drops-203718},
  doi =		{10.4230/LIPIcs.SEA.2024.6},
  annote =	{Keywords: Computational Chemistry, Treewidth, Wiener Index}
}
Document
DOI: 10.4230/DagMan.10.1.1
Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282)

Authors: James P. Delgrande, Birte Glimm, Thomas Meyer, Miroslaw Truszczynski, and Frank Wolter

Published in: Dagstuhl Manifestos, Volume 10, Issue 1 (2024)

Abstract
Knowledge Representation and Reasoning is a central, longstanding, and active area of Artificial Intelligence. Over the years it has evolved significantly; more recently it has been challenged and complemented by research in areas such as machine learning and reasoning under uncertainty. In July 2022,sser a Dagstuhl Perspectives workshop was held on Knowledge Representation and Reasoning. The goal of the workshop was to describe the state of the art in the field, including its relation with other areas, its shortcomings and strengths, together with recommendations for future progress. We developed this manifesto based on the presentations, panels, working groups, and discussions that took place at the Dagstuhl Workshop. It is a declaration of our views on Knowledge Representation: its origins, goals, milestones, and current foci; its relation to other disciplines, especially to Artificial Intelligence; and on its challenges, along with key priorities for the next decade.
Cite as

James P. Delgrande, Birte Glimm, Thomas Meyer, Miroslaw Truszczynski, and Frank Wolter. Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282). In Dagstuhl Manifestos, Volume 10, Issue 1, pp. 1-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{delgrande_et_al:DagMan.10.1.1,
  author =	{Delgrande, James P. and Glimm, Birte and Meyer, Thomas and Truszczynski, Miroslaw and Wolter, Frank},
  title =	{{Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282)}},
  pages =	{1--61},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2024},
  volume =	{10},
  number =	{1},
  editor =	{Delgrande, James P. and Glimm, Birte and Meyer, Thomas and Truszczynski, Miroslaw and Wolter, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagMan.10.1.1},
  URN =		{urn:nbn:de:0030-drops-201403},
  doi =		{10.4230/DagMan.10.1.1},
  annote =	{Keywords: Knowledge representation and reasoning, Applications of logics, Declarative representations, Formal logic}
}
Document
Survey
DOI: 10.4230/TGDK.2.1.4
Logics for Conceptual Data Modelling: A Review

Authors: Pablo R. Fillottrani and C. Maria Keet

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
Information modelling for databases and object-oriented information systems avails of conceptual data modelling languages such as EER and UML Class Diagrams. Many attempts exist to add logical rigour to them, for various reasons and with disparate strengths. In this paper we aim to provide a structured overview of the many efforts. We focus on aims, approaches to the formalisation, including key dimensions of choice points, popular logics used, and the main relevant reasoning services. We close with current challenges and research directions.
Cite as

Pablo R. Fillottrani and C. Maria Keet. Logics for Conceptual Data Modelling: A Review. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 4:1-4:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{fillottrani_et_al:TGDK.2.1.4,
  author =	{Fillottrani, Pablo R. and Keet, C. Maria},
  title =	{{Logics for Conceptual Data Modelling: A Review}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{4:1--4:30},
  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.4},
  URN =		{urn:nbn:de:0030-drops-198616},
  doi =		{10.4230/TGDK.2.1.4},
  annote =	{Keywords: Conceptual Data Modelling, EER, UML, Description Logics, OWL}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.TIME.2018.2
Database Technology for Processing Temporal Data (Invited Paper)

Authors: Michael H. Böhlen, Anton Dignös, Johann Gamper, and Christian S. Jensen

Published in: LIPIcs, Volume 120, 25th International Symposium on Temporal Representation and Reasoning (TIME 2018)

Abstract
Despite the ubiquity of temporal data and considerable research on processing such data, database systems largely remain designed for processing the current state of some modeled reality. More recently, we have seen an increasing interest in processing historical or temporal data. The SQL:2011 standard introduced some temporal features, and commercial database management systems have started to offer temporal functionalities in a step-by-step manner. There has also been a proposal for a more fundamental and comprehensive solution for sequenced temporal queries, which allows a tight integration into relational database systems, thereby taking advantage of existing query optimization and evaluation technologies. New challenges for processing temporal data arise with multiple dimensions of time and the increasing amounts of data, including time series data that represent a special kind of temporal data.
Cite as

Michael H. Böhlen, Anton Dignös, Johann Gamper, and Christian S. Jensen. Database Technology for Processing Temporal Data (Invited Paper). In 25th International Symposium on Temporal Representation and Reasoning (TIME 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 120, pp. 2:1-2:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bohlen_et_al:LIPIcs.TIME.2018.2,
  author =	{B\"{o}hlen, Michael H. and Dign\"{o}s, Anton and Gamper, Johann and Jensen, Christian S.},
  title =	{{Database Technology for Processing Temporal Data}},
  booktitle =	{25th International Symposium on Temporal Representation and Reasoning (TIME 2018)},
  pages =	{2:1--2:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-089-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{120},
  editor =	{Alechina, Natasha and N{\o}rv\r{a}g, Kjetil and Penczek, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2018.2},
  URN =		{urn:nbn:de:0030-drops-97674},
  doi =		{10.4230/LIPIcs.TIME.2018.2},
  annote =	{Keywords: Temporal databases, temporal query processing, sequenced semantics, SQL}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.47
Path-Contractions, Edge Deletions and Connectivity Preservation

Authors: Gregory Gutin, M. S. Ramanujan, Felix Reidl, and Magnus Wahlström

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We study several problems related to graph modification problems under connectivity constraints from the perspective of parameterized complexity: (Weighted) Biconnectivity Deletion, where we are tasked with deleting k edges while preserving biconnectivity in an undirected graph, Vertexdeletion Preserving Strong Connectivity, where we want to maintain strong connectivity of a digraph while deleting exactly k vertices, and Path-contraction Preserving Strong Connectivity, in which the operation of path contraction on arcs is used instead. The parameterized tractability of this last problem was posed in [Bang-Jensen and Yeo, Discrete Applied Math 2008] as an open question and we answer it here in the negative: both variants of preserving strong connectivity are W[1]-hard. Preserving biconnectivity, on the other hand, turns out to be fixed parameter tractable (FPT) and we provide an FPT algorithm that solves Weighted Biconnectivity Deletion. Further, we show that the unweighted case even admits a randomized polynomial kernel. All our results provide further interesting data points for the systematic study of connectivitypreservation constraints in the parameterized setting.
Cite as

Gregory Gutin, M. S. Ramanujan, Felix Reidl, and Magnus Wahlström. Path-Contractions, Edge Deletions and Connectivity Preservation. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gutin_et_al:LIPIcs.ESA.2017.47,
  author =	{Gutin, Gregory and Ramanujan, M. S. and Reidl, Felix and Wahlstr\"{o}m, Magnus},
  title =	{{Path-Contractions, Edge Deletions and Connectivity Preservation}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.47},
  URN =		{urn:nbn:de:0030-drops-78270},
  doi =		{10.4230/LIPIcs.ESA.2017.47},
  annote =	{Keywords: connectivity, strong connectivity, vertex deletion, arc contraction}
}
Document
DOI: 10.4230/DagSemProc.05421.1
05421 Abstracts Collection – Data Always and Everywhere – Management of Mobile, Ubiquitous, Pervasive, and Sensor Data

Authors: Gustavo Alonso, Christian S. Jensen, and Bernhard Mitschang

Published in: Dagstuhl Seminar Proceedings, Volume 5421, Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data (2006)

Abstract
From 16.10.05 to 21.10.05, the Dagstuhl Seminar 05421, Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data, was held in the International Conference and Research Center, Schloss Dagstuhl. During the seminar, all participants were given the opportunity to present their current research, and ongoing activities and open problems were discussed. This document is a collection of the abstracts of the presentations given during the seminar. Some abstracts offer links to extended abstracts, full papers, and other supporting documents. A separate companion document summarizes the seminar. The authors wish to acknowledge Victor Teixeira de Almeida, who served as collector for the seminar and thus played a key role in collecting materials from the seminar participants.
Cite as

Gustavo Alonso, Christian S. Jensen, and Bernhard Mitschang. 05421 Abstracts Collection – Data Always and Everywhere – Management of Mobile, Ubiquitous, Pervasive, and Sensor Data. In Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data. Dagstuhl Seminar Proceedings, Volume 5421, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{alonso_et_al:DagSemProc.05421.1,
  author =	{Alonso, Gustavo and Jensen, Christian S. and Mitschang, Bernhard},
  title =	{{05421 Abstracts Collection – Data Always and Everywhere – Management of Mobile, Ubiquitous, Pervasive, and Sensor Data}},
  booktitle =	{Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5421},
  editor =	{Gustavo Alonso and Christian S. Jensen and Bernhard Mitschang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05421.1},
  URN =		{urn:nbn:de:0030-drops-7966},
  doi =		{10.4230/DagSemProc.05421.1},
  annote =	{Keywords: Mobile ubiquitous and pervasive computing, sensor data, data streams, content integration, replication, caching, and consistency, service orientation, query and update processing, indexing, tracking process models, peer-to-peer computing, mobile ad-hoc networking, context awareness and preferences, moving objects, location--based mobile services,}
}
Document
DOI: 10.4230/DagSemProc.05421.2
05421 Executive Summary – Data Always and Everywhere – Management of Mobile, Ubiquitous, and Pervasive Data

Authors: Gustavo Alonso, Christian S. Jensen, and Bernhard Mitschang

Published in: Dagstuhl Seminar Proceedings, Volume 5421, Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data (2006)

Abstract
This report summarizes the important aspects of the workshop on "Management of Mobile, Ubiquitous, and Pervasive Data", which took place from October 16th to October 21st, 2005. Thirty-seven participants from thirteen countries met during that week and discussed a broad range of topics related to the management of data in relation to mobile, ubiquitous, and pervasive applications of information technology. The wealth of the contributions is available at the seminar page at the Dagstuhl server. Here, we provide a short overview.
Cite as

Gustavo Alonso, Christian S. Jensen, and Bernhard Mitschang. 05421 Executive Summary – Data Always and Everywhere – Management of Mobile, Ubiquitous, and Pervasive Data. In Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data. Dagstuhl Seminar Proceedings, Volume 5421, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{alonso_et_al:DagSemProc.05421.2,
  author =	{Alonso, Gustavo and Jensen, Christian S. and Mitschang, Bernhard},
  title =	{{05421 Executive Summary – Data Always and Everywhere – Management of Mobile, Ubiquitous, and Pervasive Data}},
  booktitle =	{Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5421},
  editor =	{Gustavo Alonso and Christian S. Jensen and Bernhard Mitschang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05421.2},
  URN =		{urn:nbn:de:0030-drops-7947},
  doi =		{10.4230/DagSemProc.05421.2},
  annote =	{Keywords: Mobile Data Management, Ubiquitous Computing, Pervasive Computing, Streaming Data, Middleware, Data Integration, Data Placement, Ad-hoc Networking, Mi}
}
Document
DOI: 10.4230/DagSemProc.05421.3
B-tree indexes for high update rates

Authors: Goetz Graefe

Published in: Dagstuhl Seminar Proceedings, Volume 5421, Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data (2006)

Abstract
In some applications, data capture dominates query processing. For example, monitoring moving objects often requires more insertions and updates than queries. Data gathering using automated sensors often exhibits this imbalance. More generally, indexing streams apparently is considered an unsolved problem. For those applications, B-tree indexes are reasonable choices if some trade-off decisions are tilted towards optimization of updates rather than of queries. This paper surveys techniques that let B-trees sustain very high update rates, up to multiple orders of magnitude higher than tradi-tional B-trees, at the expense of query processing performance. Perhaps not surprisingly, some of these techniques are reminiscent of those employed during index creation, index rebuild, etc., while others are derived from other well known technologies such as differential files and log-structured file systems.
Cite as

Goetz Graefe. B-tree indexes for high update rates. In Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data. Dagstuhl Seminar Proceedings, Volume 5421, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{graefe:DagSemProc.05421.3,
  author =	{Graefe, Goetz},
  title =	{{B-tree indexes for high update rates}},
  booktitle =	{Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5421},
  editor =	{Gustavo Alonso and Christian S. Jensen and Bernhard Mitschang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05421.3},
  URN =		{urn:nbn:de:0030-drops-7632},
  doi =		{10.4230/DagSemProc.05421.3},
  annote =	{Keywords: B-tree, high update rates}
}
Document
DOI: 10.4230/DagSemProc.05421.4
Media Distribution in a Pervasive Computing Environment

Authors: Alexander Sinitsyn, Winfried A. H. Berkvens, Arjan Claassen, and Joep P. van Gassel

Published in: Dagstuhl Seminar Proceedings, Volume 5421, Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data (2006)

Abstract
Distribution of media in the fast growing world of digital stored content and multimedia supporting devices with connectivity, calls for a new media distribution architecture. The user should be provided with the experience of having an overview of his full media collection, regardless of the time, the place, and the connectivity. Transparent distributed data management is crucial to Ambient Intelligent applications. The proposed media distribution architecture offers a possible solution. It provides the user with the experience of having all his media collections available at any time, in any place, and managing them regardless of connection availability in the heterogeneous environment. This experience is enabled in our system by the separation of metadata and content handling. Other features are efficient handling of snapshots, usage of various database technologies, and leveraging device and service discovery mechanisms.
Cite as

Alexander Sinitsyn, Winfried A. H. Berkvens, Arjan Claassen, and Joep P. van Gassel. Media Distribution in a Pervasive Computing Environment. In Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data. Dagstuhl Seminar Proceedings, Volume 5421, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{sinitsyn_et_al:DagSemProc.05421.4,
  author =	{Sinitsyn, Alexander and Berkvens, Winfried A. H. and Claassen, Arjan and van Gassel, Joep P.},
  title =	{{Media Distribution in a Pervasive Computing Environment}},
  booktitle =	{Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5421},
  editor =	{Gustavo Alonso and Christian S. Jensen and Bernhard Mitschang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05421.4},
  URN =		{urn:nbn:de:0030-drops-7622},
  doi =		{10.4230/DagSemProc.05421.4},
  annote =	{Keywords: Data management}
}
Document
DOI: 10.4230/DagSemProc.04441.6
04441 Working Group – Research Issues in Mobile Querying

Authors: Martin Breunig and Christian S. Jensen

Published in: Dagstuhl Seminar Proceedings, Volume 4441, Mobile Information Management (2005)

Abstract
This document reports on key aspects of the discussions conducted within the working group. In particular, the document aims to offer a structured and somewhat digested summary of the group's discussions. The document first offers concepts that enable characterization of "mobile queries'' as well as the types of systems that enable such queries. It explores the notion of context in mobile queries. The document ends with a few observations, mainly regarding challenges.
Cite as

Martin Breunig and Christian S. Jensen. 04441 Working Group – Research Issues in Mobile Querying. In Mobile Information Management. Dagstuhl Seminar Proceedings, Volume 4441, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{breunig_et_al:DagSemProc.04441.6,
  author =	{Breunig, Martin and Jensen, Christian S.},
  title =	{{04441 Working Group – Research Issues in Mobile Querying}},
  booktitle =	{Mobile Information Management},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4441},
  editor =	{Margaret H. Dunham and Birgitta K\"{o}nig-Ries and Evaggelia Pitoura and Peter Reiher and Can T\"{u}rker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04441.6},
  URN =		{urn:nbn:de:0030-drops-1651},
  doi =		{10.4230/DagSemProc.04441.6},
  annote =	{Keywords: Mobile Queries}
}
  • Refine by Author
  • 5 Jensen, Christian S.
  • 2 Alonso, Gustavo
  • 2 Breunig, Martin
  • 2 Mitschang, Bernhard
  • 2 Weinberg, S. Matthew
  • Show More...

  • Refine by Classification
  • 2 Security and privacy → Distributed systems security
  • 2 Theory of computation → Algorithmic game theory and mechanism design
  • 1 Applied computing → Computer-aided design
  • 1 Applied computing → Digital cash
  • 1 Computing methodologies → Artificial intelligence
  • Show More...

  • Refine by Keyword
  • 2 Blockchain
  • 1 Ad-hoc Networking
  • 1 Algorithms Engineering
  • 1 Applications of logics
  • 1 Auctions
  • Show More...

  • Refine by Type
  • 16 document

  • Refine by Publication Year
  • 8 2024
  • 4 2006
  • 2 2005
  • 1 2017
  • 1 2018

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