Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
4.1
1.8
Journals
Algorithms
Special Issues
Efficient Data Structures
share announcement

Efficient Data Structures

A special issue of Algorithms (ISSN 1999-4893). This special issue belongs to the section "Databases and Data Structures".

Deadline for manuscript submissions: closed (30 November 2018) | Viewed by 41227

Special Issue Editor

Dr. Jesper Jansson

E-Mail Website
Guest Editor
Department of Communications and Computer Engineering, Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, Japan
Interests: graph algorithms; bioinformatics; computational complexity; data structures
Special Issues, Collections and Topics in MDPI journals

Special Issue Information

Dear Colleagues,

Data structures provide ways of compactly organizing and efficiently retrieving various kinds of information. Over the years, they have been used effectively in countless practical and conceptual applications. For example, a nineteenth-century data structure known as the phylogenetic tree, nowadays routinely used for representing the evolutionary history of a set of biological species, has helped scientists to understand the mechanisms of evolution. As another example, a twenty-first-century data structure known as the blockchain, which aims at achieving decentralized consensus, has many potentially important applications involving the creation of permanent ledgers for sharing information over the Internet and automated contracts. For this Special Issue of Algorithms, we would like to invite articles dealing with the design, formal analysis, implementation, and experimental evaluation of efficient data structures for all kinds of computational problems. Of particular interest are algorithms for constructing data structures and extracting information from them efficiently. Articles focusing on complexity aspects of data structures related to time-space tradeoffs, information-theoretic entropy, and lower bounds in various models of computation are also welcome.

Dr. Jesper Jansson
Guest Editor

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Algorithms is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 1600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

  • Succinct data structures for strings, trees, and graphs
  • Probabilistic data structures
  • Dynamic data structures
  • Geometric data structures
  • Distributed data structures
  • Classic data structures
  • Lower bounds
  • Implementations

Benefits of Publishing in a Special Issue

  • Ease of navigation: Grouping papers by topic helps scholars navigate broad scope journals more efficiently.
  • Greater discoverability: Special Issues support the reach and impact of scientific research. Articles in Special Issues are more discoverable and cited more frequently.
  • Expansion of research network: Special Issues facilitate connections among authors, fostering scientific collaborations.
  • External promotion: Articles in Special Issues are often promoted through the journal's social media, increasing their visibility.
  • e-Book format: Special Issues with more than 10 articles can be published as dedicated e-books, ensuring wide and rapid dissemination.

Further information on MDPI's Special Issue polices can be found here.

Published Papers (7 papers)

Download All Papers
Order results
Result details
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:

Editorial

Jump to: Research

2 pages, 154 KiB  
Editorial
Editorial: Special Issue on Efficient Data Structures
by Jesper Jansson
Algorithms 2019, 12(7), 136; https://doi.org/10.3390/a12070136 - 5 Jul 2019
Viewed by 3214
Abstract
This Special Issue of Algorithms is focused on the design, formal analysis, implementation, and experimental evaluation of efficient data structures for various computational problems. Full article
(This article belongs to the Special Issue Efficient Data Structures)

Research

Jump to: Editorial

14 pages, 305 KiB  
Article
A Selectable Sloppy Heap
by Adrian Dumitrescu
Algorithms 2019, 12(3), 58; https://doi.org/10.3390/a12030058 - 6 Mar 2019
Cited by 5 | Viewed by 4741
Abstract
We study the selection problem, namely that of computing the ith order statistic of n given elements. Here we offer a data structure called selectable sloppy heap that handles a dynamic version in which upon request (i) a new element is inserted [...] Read more.
We study the selection problem, namely that of computing the ith order statistic of n given elements. Here we offer a data structure called selectable sloppy heap that handles a dynamic version in which upon request (i) a new element is inserted or (ii) an element of a prescribed quantile group is deleted from the data structure. Each operation is executed in constant time—and is thus independent of n (the number of elements stored in the data structure)—provided that the number of quantile groups is fixed. This is the first result of this kind accommodating both insertion and deletion in constant time. As such, our data structure outperforms the soft heap data structure of Chazelle (which only offers constant amortized complexity for a fixed error rate 0 < ε ≤ 1 / 2 ) in applications such as dynamic percentile maintenance. The design demonstrates how slowing down a certain computation can speed up the data structure. The method described here is likely to have further impact in the field of data structure design in extending asymptotic amortized upper bounds to same formula asymptotic worst-case bounds. Full article
(This article belongs to the Special Issue Efficient Data Structures)
24 pages, 440 KiB  
Article
Space-Efficient Fully Dynamic DFS in Undirected Graphs †
by Kengo Nakamura and Kunihiko Sadakane
Algorithms 2019, 12(3), 52; https://doi.org/10.3390/a12030052 - 27 Feb 2019
Cited by 6 | Viewed by 5374
Abstract
Depth-first search (DFS) is a well-known graph traversal algorithm and can be performed in O ( n + m ) time for a graph with n vertices and m edges. We consider the dynamic DFS problem, that is, to maintain a DFS tree [...] Read more.
Depth-first search (DFS) is a well-known graph traversal algorithm and can be performed in O ( n + m ) time for a graph with n vertices and m edges. We consider the dynamic DFS problem, that is, to maintain a DFS tree of an undirected graph G under the condition that edges and vertices are gradually inserted into or deleted from G. We present an algorithm for this problem, which takes worst-case O ( m n · polylog ( n ) ) time per update and requires only ( 3 m + o ( m ) ) log n bits of space. This algorithm reduces the space usage of dynamic DFS algorithm to only 1.5 times as much space as that of the adjacency list of the graph. We also show applications of our dynamic DFS algorithm to dynamic connectivity, biconnectivity, and 2-edge-connectivity problems under vertex insertions and deletions. Full article
(This article belongs to the Special Issue Efficient Data Structures)
►▼ Show Figures

Figure 1

23 pages, 508 KiB  
Article
DenseZDD: A Compact and Fast Index for Families of Sets †
by Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Shin-ichi Minato and Kunihiko Sadakane
Algorithms 2018, 11(8), 128; https://doi.org/10.3390/a11080128 - 17 Aug 2018
Cited by 3 | Viewed by 4875
Abstract
In this article, we propose a succinct data structure of zero-suppressed binary decision diagrams (ZDDs). A ZDD represents sets of combinations efficiently and we can perform various set operations on the ZDD without explicitly extracting combinations. Thanks to these features, ZDDs have been [...] Read more.
In this article, we propose a succinct data structure of zero-suppressed binary decision diagrams (ZDDs). A ZDD represents sets of combinations efficiently and we can perform various set operations on the ZDD without explicitly extracting combinations. Thanks to these features, ZDDs have been applied to web information retrieval, information integration, and data mining. However, to support rich manipulation of sets of combinations and update ZDDs in the future, ZDDs need too much space, which means that there is still room to be compressed. The paper introduces a new succinct data structure, called DenseZDD, for further compressing a ZDD when we do not need to conduct set operations on the ZDD but want to examine whether a given set is included in the family represented by the ZDD, and count the number of elements in the family. We also propose a hybrid method, which combines DenseZDDs with ordinary ZDDs. By numerical experiments, we show that the sizes of our data structures are three times smaller than those of ordinary ZDDs, and membership operations and random sampling on DenseZDDs are about ten times and three times faster than those on ordinary ZDDs for some datasets, respectively. Full article
(This article belongs to the Special Issue Efficient Data Structures)
►▼ Show Figures

Figure 1

11 pages, 446 KiB  
Article
Sliding Suffix Tree
by Andrej Brodnik and Matevž Jekovec
Algorithms 2018, 11(8), 118; https://doi.org/10.3390/a11080118 - 3 Aug 2018
Cited by 4 | Viewed by 6482
Abstract
We consider a sliding window W over a stream of characters from some alphabet of constant size. We want to look up a pattern in the current sliding window content and obtain all positions of the matches. We present an indexed version of [...] Read more.
We consider a sliding window W over a stream of characters from some alphabet of constant size. We want to look up a pattern in the current sliding window content and obtain all positions of the matches. We present an indexed version of the sliding window, based on a suffix tree. The data structure of size Θ(|W|) has optimal time queries Θ(m+occ) and amortized constant time updates, where m is the length of the query string and occ is its number of occurrences. Full article
(This article belongs to the Special Issue Efficient Data Structures)
►▼ Show Figures

Figure 1

20 pages, 7896 KiB  
Article
Distributed Combinatorial Maps for Parallel Mesh Processing
by Guillaume Damiand, Aldo Gonzalez-Lorenzo, Florence Zara and Florent Dupont
Algorithms 2018, 11(7), 105; https://doi.org/10.3390/a11070105 - 13 Jul 2018
Cited by 4 | Viewed by 5109
Abstract
We propose a new strategy for the parallelization of mesh processing algorithms. Our main contribution is the definition of distributed combinatorial maps (called n-dmaps), which allow us to represent the topology of big meshes by splitting them into independent parts. Our mathematical [...] Read more.
We propose a new strategy for the parallelization of mesh processing algorithms. Our main contribution is the definition of distributed combinatorial maps (called n-dmaps), which allow us to represent the topology of big meshes by splitting them into independent parts. Our mathematical definition ensures the global consistency of the meshes at their interfaces. Thus, an n-dmap can be used to represent a mesh, to traverse it, or to modify it by using different mesh processing algorithms. Moreover, an nD mesh with a huge number of elements can be considered, which is not possible with a sequential approach and a regular data structure. We illustrate the interest of our solution by presenting a parallel adaptive subdivision method of a 3D hexahedral mesh, implemented in a distributed version. We report space and time performance results that show the interest of our approach for parallel processing of huge meshes. Full article
(This article belongs to the Special Issue Efficient Data Structures)
►▼ Show Figures

Figure 1

34 pages, 1710 KiB  
Article
Linking and Cutting Spanning Trees
by Luís M. S. Russo, Andreia Sofia Teixeira and Alexandre P. Francisco
Algorithms 2018, 11(4), 53; https://doi.org/10.3390/a11040053 - 19 Apr 2018
Cited by 4 | Viewed by 6579
Abstract
We consider the problem of uniformly generating a spanning tree for an undirected connected graph. This process is useful for computing statistics, namely for phylogenetic trees. We describe a Markov chain for producing these trees. For cycle graphs, we prove that this approach [...] Read more.
We consider the problem of uniformly generating a spanning tree for an undirected connected graph. This process is useful for computing statistics, namely for phylogenetic trees. We describe a Markov chain for producing these trees. For cycle graphs, we prove that this approach significantly outperforms existing algorithms. For general graphs, experimental results show that the chain converges quickly. This yields an efficient algorithm due to the use of proper fast data structures. To obtain the mixing time of the chain we describe a coupling, which we analyze for cycle graphs and simulate for other graphs. Full article
(This article belongs to the Special Issue Efficient Data Structures)
►▼ Show Figures

Figure 1

Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
 
Displaying articles 1-7
Back to TopTop