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

learn more… | top users | synonyms (2)

0
votes
1answer
91 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
25 views

Cheapest route in graph under time constraints

Here is my question: I have to find the cheapest path on a graph containing vertices as cities and edges as flights. Each flight has associated with it: departure time,arrival time,city of departure ...
6
votes
1answer
110 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 ...
10
votes
2answers
461 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) = ...
8
votes
1answer
147 views

Data structure for dynamic memory allocation

Think of the cell-probe model. Is there a data structure that can allocate contiguous chunks of memory of any length (like e.g. malloc in C), and free them, while avoiding memory segmentation, and ...
5
votes
1answer
89 views

Looking for easy applications of fractional cascading

I want to give a couple of talks on fractional cascading, one of which will focus on applications. I'm looking for applications that make use of the full version of fractional cascading, not just the ...
3
votes
1answer
181 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
55 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
179 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 ...
5
votes
0answers
165 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 ...
5
votes
0answers
117 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 ...
1
vote
0answers
81 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
101 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 ...
2
votes
0answers
38 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
1answer
170 views

Implementation of partition trees?

Have partition trees ever been implemented? Here, I'm talking about the partition trees from computational geometry. The earliest (near-)optimal versions of which were due to Matousek and others, ...
9
votes
0answers
97 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
72 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
72 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 ...
2
votes
0answers
87 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 ...
-1
votes
1answer
189 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 ...
7
votes
1answer
168 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
56 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 ...
0
votes
0answers
42 views

Sparse matrix-vector multiplication materials needed

I've been assigned a project at school, the theme is the influence on cache memory when doing sparse matrix-vector multiplications. I've been searching for materials for quite some time but all I can ...
3
votes
1answer
118 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 ...
8
votes
2answers
502 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 ...
3
votes
2answers
141 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
132 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 ...
3
votes
2answers
109 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
69 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 ...
1
vote
1answer
56 views

Lower bounds on simple hash table operations?

There are a variety of hash tables that support worst-case O(1)-time lookups and deletions and expected O(1)-time lookups. Is there a known lower-bound on hashing that says that there cannot be a hash ...
5
votes
0answers
102 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 ...
5
votes
2answers
359 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 ...
1
vote
1answer
140 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." ...
1
vote
0answers
47 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
107 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 ...
4
votes
2answers
182 views

Shortest distance/path between two households

If you wanted to know the shortest distance/path between two household addresses, which data structure(s) would you use to return the answer efficiently? Say you are considering the set of all ...
11
votes
1answer
275 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 ...
1
vote
0answers
141 views

What can be done with unsorted binary trees

Where can I find work on self-balancing unsorted binary trees? (ie using binary trees as a substitute for lists or arrays?)
1
vote
0answers
67 views

What are some examples where the Catalan numbers show up in algorithms/data structures?

For some variants of RMQ data structures, the number of Cartesian trees (i.e. the Catalan numbers) is a part of the running-time analysis. What are some other examples where the Cataln numbers show up ...
16
votes
2answers
2k views

Is the traditional analysis of Bloom filters wrong?

This paper claims that the traditional analysis of the error rate in Bloom filters is incorrect, then provides a lengthy and nontrivial analysis of the actual error rate. The linked paper was ...
4
votes
1answer
190 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)$ ...
23
votes
3answers
2k 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, ...
4
votes
0answers
45 views

Has there been any work done on incremental connectivity in path graphs?

This set of lecture notes describes a data structure for decremental connectivity in path graphs that supports queries and removals in amortized O(1) each. Has there been any work done on incremental ...
5
votes
0answers
262 views

Data structures for Finite Automata

I am a Control Engineer and I have been working on Discrete Event Systems and Supervisory Control, based on Finite Automata Theory. My problem is to represent large automata (about $2 \times 10^6$ ...
-3
votes
1answer
161 views

Isn't weakly universal hashing even a stronger than truly random? [closed]

So as far as I know the weakly universal hashing is defined as: for any $x, y \subset U, Pr(h(x) = h(y)) \le \frac{1}{m}$ where m is a smaller number than the cardinality of $U$, and h are chosen ...
1
vote
0answers
91 views

Binary Search Tree DELETE survey

In helping out @bapi-chatterjee on a BST question , when it came to teasing out the combinatorics of BST_DELETE(i) I ran into a wall where even under the conservative assumption that the parent tree ...
2
votes
0answers
108 views

Height of randomly built binary search tree by insert and delete?

In Introduction to algorithm (CLRS), even in its third edition (published in 2009) it is noted in Sec 12.4 that little is known about height of randomly built binary search tree using insert and ...
3
votes
1answer
213 views

Algorithm to Bulk Delete nodes from a Treap

I have a Treap, and want to bulk delete nodes in a given key range (i.e. the nodes to be deleted are consecutive nodes in an in-order walk of the tree). If I have $n$ nodes in the Treap, and $k$ nodes ...
3
votes
0answers
82 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 ...
7
votes
2answers
265 views

Testing boolean vectors orthogonality with fast query-time

Consider the following problems, Problem1: INPUT: a set $S:=\{s_1, \ldots, s_n\}$ of vectors in $d$-dimensional boolean vector space $\{0,1\}^d$ over $\mathbb{F}_2$ TASK: preprocess INPUT in such a ...