Questions tagged [ds.data-structures]

Properties and applications of data structures, such as space lower bounds, or time complexity of insertion and deletion of objects.

Filter by
Sorted by
Tagged with
8
votes
0answers
121 views

Purely Functional Representations of Catenable Sorted Lists question

Good day. I'm currently reading the paper "Purely Functional Representations of Catenable Sorted Lists" by Tarjan and Kaplan[link to the paper]. But I have a question about the modified 2-3 finger ...
14
votes
1answer
4k views

Need a good overview for Succinct Data Structure algorithms

(already asked on main site, but asking also here for better coverage, sorry) Since I knew about Succinct Data Structures I'm in a desperate need of a good overview of most recent developments in ...
6
votes
1answer
193 views

Split find-min data structure that finds several small elements?

The split find-min data structure is initialized with a sequence of elements $e_1,\ldots,e_n$, each associated with a key. The data structure supports three operations: (1) $Split(e_i)$ that splits ...
4
votes
1answer
261 views

Defintion of a Data Structure? [closed]

Lately I have been looking around for a formal definition of a what a data structure is. I cannot find neither a paper, nor a book with such a definition. Even the famous "The Art of Computer ...
2
votes
1answer
141 views

Set query in a universe with overlapping sets

Suppose we have a universe $U$ of $n$ items $u_1,u_2,u_3,...,u_n$. And a collection of sets (no restriction on being disjoint or exhaustive etc.) which cover some items. Size of each set is bounded by ...
13
votes
2answers
380 views

Data structure for updates on intervals and querying number of zeros

I am looking for a data structure that would maintain an integer table $t$ of size $n$, and allowing the following operations in time $O(\log n)$. $\text{increase}(a,b)$, which increases $t[a],t[a+1],...
4
votes
0answers
448 views

Dynamic shortest path data structure for DAG

Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted. I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed ...
1
vote
1answer
218 views

How can I formalize key value stores with set theory? [closed]

I'm currently developing a simple key-value NoSQL store and want to build its formal model. I'm interested in knowing if there some work about formalization of key-value stores outside of category ...
3
votes
0answers
402 views

worst case external fragmentation in buddy memory systems

Unfortunately, I can't find any freely available text with an estimation of exact upper bound of (external) fragmentation overhead for (binary) buddy memory allocator. Estimation $M(1+ \log 2 m)$ (...
3
votes
0answers
249 views

Atomic snapshot algorithms on tree-structured shared registers

Background: Atomic snapshot memory is a shared memory partitioned into words written (updated) by individual processes, or instantaneously read (scanned) in its entirety. The Gang of Six algorithm ...
11
votes
2answers
605 views

Fun with inverse Ackermann

The inverse Ackermann function occurs often when analyzing algorithms. A great presentation of it is here: http://www.gabrielnivasch.org/fun/inverse-ackermann. $$\alpha_1(n) = [n/2]$$ $$\alpha_2(n) = ...
6
votes
1answer
835 views

Array implementation of dictionary data structure

Is there a data structure that supports searching, inserting, deletion in worst-case O(log n) time and that satisfies the following "array implementation" property: at any point in time, the data ...
16
votes
1answer
822 views

Splay tree potential function: why sum the logs of the sizes?

I'm teaching a course on data structures and will be covering splay trees early next week. I've read the paper on splay trees many times and am familiar with the analysis and intuition behind the data ...
3
votes
1answer
3k views

Search for all nearest neighbors within a certain radius of a point in 3D?

I have about 80 million spatial points(3D) and I want to find all the nearest neighbors of a query point which lie under a sphere of a certain radius(can be given as input) with the query point as ...
14
votes
1answer
314 views

How much independence is required for separate chaining?

If $n$ balls are placed into $n$ bins uniformly at random, the heaviest loaded bin has $O(\lg n/\lg \lg n)$ balls in it with high probability. In "The Power of Simple Tabulation Hashing", Pătraşcu and ...
3
votes
1answer
279 views

Sorted intervals query

I'm in search for a data structure which efficiently operates over closed intervals with the following properties: dynamically add or remove an interval set, and anytime change, a number ("depth") ...
2
votes
1answer
229 views

Persistent data structures in RAM computational model

Always when I read about any efficient persistent data structures they use pointer computational model. I'm wondering if you know any efficient implementation which uses power of RAM model?
4
votes
1answer
363 views

Array-like data structure with O(1) worst-case concatenate/join?

I am looking for a data structure $D$ which supports the following operations (preferably a (binary) tree-like structure): $D$ is indexed, i.e. there is a mapping from $\{1, \ldots, n\}$ to items ...
4
votes
1answer
224 views

Concurrent algorithm for strongly connected components (SCCs)

Is anybody aware of a concurrent version of Tarjan's SCCs algorithm, Kosaraju's algorithm or any other fast, O(|V| + |E|) algorithm for finding SCCs? Neither of those algorithms seem to be very hard ...
5
votes
0answers
206 views

Rebalancing balanced binary search tree when decreasing all keys to the right of a path?

Given a balanced binary search tree, suppose I have an operation decrease-right-keys(k, s) that operates as follows: when I call this operation on a tree $T$, I decrease all keys by $s$ in the right ...
10
votes
1answer
248 views

Fingerprinting for dynamic sets

Does there exist a w-bit word-RAM data structure with O(1) time per operation for the following problem?: Maintain a set of w-bit non-negative integers that supports the operations add(x) : add x to ...
7
votes
0answers
687 views

Is there a purely functional vector with O(1) access to the front and back but O(log n) concatenation?

Context: For fun and perhaps for actual use, I'm making my own programming language that would compile to Typed Racket, a statically-typed Lisp dialect. One of the major features I want to implement ...
12
votes
1answer
222 views

Integer priority queue with distribution-sensitive deleteMin

Is there in an integer priority queue that uses $O(n)$ words of space with the following operations, all in worst-case time and without access to randomness: ...
8
votes
1answer
556 views

Does a universal index exist?

Given a data table containing a very large number $N$ of rows, with each row containing a large number $k$ of fields, with each field containing a large but fixed number of bits, there are a number of ...
5
votes
1answer
590 views

Heap with $O(1)$ delete-key

Fibonacci heaps have $O(1)$ insertion and $O(\log n)$ delete-min and delete-key (under amortized complexity). Is there a heap data structure with $O(1)$ insertion and delete-key and $O(\log n)$ ...
1
vote
0answers
99 views

What is the name of this data structure? (hash table with a limit on the number of entries)

Denote $[n] \triangleq \{1,2,\ldots,n\}$. Assume we would like to have a data structure $S$ which kinda works as a dictionary from $[k]$ to $[v]$, and supports add/remove/update/query functionality, ...
0
votes
1answer
145 views

Data structure that allows moving groups of elements into buckets

I'm looking for a data structure that can do the following geometric operation: Suppose there are a set of buckets $b_0, b_1..., b_n$ each of which contains some elements. Suppose I want to move all ...
7
votes
1answer
194 views

Simple succinct dynamic predecessor with $O(\sqrt{n})$ redundancy in contiguous space

A dynamic predecessor data structure supporting findPredecessor, insert, and delete over ...
2
votes
0answers
49 views

2-dimensional dynamic set retrieval

For the following, $(w,x) >= (y,z)$ iff $w >= y$ and $x >= z$. I have a list, $L$, of $k$ points with integer coordinates ranging from $0$ to $n-1$. Each point has an associated set. I ...
9
votes
2answers
420 views

Efficient algorithms for searching a collection of trees

I have a large dataset of trees and I would like to search it by specifying a treelet (connected subgraph). The query should return all the occourrences of the treelet in the dataset. Are there ...
9
votes
0answers
187 views

References for de-amortization

I've been interested in looking into the area of de-amortization recently (i.e. finding data structures with matching worst-case and amortized running time bounds, or exhibiting lower bounds against ...
6
votes
0answers
163 views

Purely functional uniquely-represented deques

There are a number of purely functional deques that support $O(1)$ operations at each end. None that I know of are "uniquely represented" - deques with the same number of items can have different ...
3
votes
1answer
122 views

How to find the first $k$ points of high enough level using a priority search tree?

In reading Chan's paper, Closest Point Problems Simplified on a RAM, the following came up as a sub-problem: Given a set $P$ of points in the plane, and a query point $q$, find the first $k$ points (...
-3
votes
1answer
89 views

tagging and graph “compression”

I have a question on stack-overflow about "compressing" a graph. Suppose I have tags from a finite set $T$ and objects from a finite set $O$. Moreover there are (uni-directional) links from elements ...
0
votes
1answer
554 views

Is the running time of Boyer-Moore linear?

With pattern length $M$, text length $N$, and alphabet $\Sigma$, is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$ (even when $M$ grows larger than $|\Sigma|$)? Are there any sublinear ...
3
votes
0answers
223 views

efficient data structures for generalized tensor products

The usual tensor product of vectors is a matrix. There has been tons of research into efficiently storing and operating on matrices in computers. But we can generalize the tensor product quite a bit....
8
votes
1answer
200 views

what is known about efficient set intersections

Say you have a number of sets of integers ($S_1, S_2 ... S_n$), and you want to calculate intersections of some of them ($\cap S_1, S_3, S_7$ might be a query, but you want to support many such ...
0
votes
0answers
67 views

On a property of random rooted trees with $n$ nodes and of height $h$

I am working on a proof that require the result of the following problem: Let, $T$ be a rooted directed tree with height $h (\ge \lceil{log_d{n}}\rceil )$ and having $n$ nodes. Each internal node of $...
1
vote
1answer
556 views

Why does the construction step of Aho-Corasick take linear time in the number of nodes?

The original paper's analysis of this, as far as I can tell is this: "THEOREM 3. Algorithm 2 requires time linearly proportional to the sum of the lengths of the keywords. PROOF. Straightforward." ...
3
votes
1answer
233 views

Concurrent data structures vs. Distributed data structures

In the context of multi-processor/multi-threaded systems, there are plenty of well-studied concurrent data structures, including stacks, queues, linked lists, etc. Here is an excellent survey on ...
5
votes
2answers
310 views

Isomorphism between algebraic data-types

I have two types of trees in Haskell, defined as the least solution of the following equations: $T_1(A) \cong 1 + A + T_1(A) \times T_1(A)$ $T_2(A) \cong 1 + A \times T_2(A) + T_2(A) \times T_2(A)$ ...
3
votes
1answer
171 views

Number of bits required for encoding variables with fixed sum?

Assume we'd like to be able to encode variables $x_1,x_2,\cdots,x_r\in \mathbb{N}$, such that $\forall i\in[r]:1\leq x_i\leq N$ and $$\sum_{i=1}^{r}x_i=M$$ It's easy to store the variables using $r\...
4
votes
2answers
221 views

Minimal encoding of a set (unordered collection of elements)?

Assume you have universe $\mathcal{U}=\{e_1,e_2,\ldots e_N\}$. If we like to encode an ordered sequence of $k$ elements from $\mathcal{U}$, it's not hard to argue that $k\log |\mathcal{U}|$ bits are ...
1
vote
1answer
84 views

Are there published algorithms for on-line creation of AVL trees from ordered streams?

Given an ordered stream of n items (n unknown in advance), it is well-known how to construct a red-black tree from them in O(n)-time. More specifically this is possible using only O(log n) additional ...
25
votes
3answers
3k views

Nontrivial algorithm for computing a sliding window median

I need to calculate the running median: Input: $n$, $k$, vector $(x_1, x_2, \dotsc, x_n)$. Output: vector $(y_1, y_2, \dotsc, y_{n-k+1})$, where $y_i$ is the median of $(x_i, x_{i+1}, \dotsc, x_{i+k-...
5
votes
0answers
131 views

Why is it necessary to maintain a collection of forests in the dynamic graph data structure?

In their paper "Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity", Holm, de Lichtenberg, and Thorup describe a data structure ...
6
votes
2answers
495 views

Would a purely topological computational model be useful in decision problems in topology?

If one were to develop a purely topological computational model based upon the equivalence of information in knots and the model would perform transformations of that information. This would be the ...
21
votes
9answers
13k views

What is the recommended software for drawing data structures such as graphs and trees?

When putting together results, it's often desirable to have some professional looking diagrams, rather than diagrams put together in MS Paint. What is the standard for drawing data structures?
1
vote
0answers
54 views

What should I read to learn about the different models of computation used in algorithm and especially data structure analysis?

Are there any good surveys? Courses? Lecture notes? I'm especially interested in material with practice exercises, if any is available. Thanks!
1
vote
1answer
157 views

Asymmetry in converting Burrows-Wheeler transform to suffix array?

Given a suffix array of a string $w$, it's possible to construct the Burrows-Wheeler transform of $w$ by subtracting one from the indices of the suffix array (wrapping around if necessary), then ...

1 2
3
4 5
7