Questions tagged [data-structures]

Questions about ways of storing data so that it can be used advantageously by algorithms.

425 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
19
votes
1answer
894 views

Why hasn't functional programming researched dynamic trees?

Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging ...
11
votes
0answers
1k views

Alternative to Bloom filter for extreme parameters

A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below). I am interested in a ...
8
votes
0answers
104 views

Data Structures for Non-Orientable Manifolds

I am looking for a data structure to represent non-orientable manifolds (i.e. meshes like Moebius Strip, but without self-intersection). I will then implement other algorithms using this DS such as, ...
8
votes
0answers
580 views

Predecessor query where the insertion order is known

Assume I want to insert elements $1$ to $n$ into a data structure exactly once, and perform predecessor queries while inserting these elements (so insert(x) and <...
8
votes
2answers
896 views

Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?

I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in ...
7
votes
0answers
342 views

What was the first public reference to bloom filters where the number of hash functions vary?

In traditional bloom filters, each item is hashed some fixed number of locations. One variant of this is to hash items a varying number of locations within the same bloom filter. This idea is ...
7
votes
0answers
881 views

Double Hashing and Variations for Bloom Filters

I am reading a few papers on Bloom Filters – Bloom Filters in Probabilistic Verification (Dillinger and Manolios) suggests the following allocations for double and triple hashing respectively ...
6
votes
0answers
303 views

Why most purely functional red-black trees are left-leaning?

Is there any particular reason for picking a left-leaning red-black tree over a regular red-black tree when trying to do a purely functional implementation? I've not researched very deeply into this ...
6
votes
0answers
288 views

Prove/disprove the existance of a data structure that has O(log N) inserts/deletes and get k-th largest element in O(1)

Consider a sorted array. We can get the $k$-th largest element in $O(1)$, but insertions and deletions cost $O(n)$. Consider an order statistic tree. Insertions and deletions cost $O(\log{N})$, but ...
5
votes
0answers
132 views

What is the intuition behind the Geometric Burrows-Wheeler Transform?

What is the intuition behind the Geometric Burrows-Wheeler Transform? And how can I use a GBWT with blocking factor $d$ to match a given pattern $P$ of length $|P| = m$ with $m \ge d$ $m < d$ ...
5
votes
0answers
348 views

Efficient deletion in Fenwick tree

Suppose there is an array of nonzero integer values A[n], which has a Fenwick tree representation F[n]. The most simplistic way ...
4
votes
0answers
209 views

Data structures for quantum computers

In classical computers we have List,Queue,Tree & etc data structures, since classical computers using 1's & 0's on those data structures. Then what happens when it comes to quantum computers, ...
4
votes
0answers
155 views

Is there a data structure that can perform range modulo additions and range minimum queries?

It is well-known that the Segment Tree performs range additions and range minimum queries in O(logN) each. Let each element in the array have value V[i], M[i]. We define a "range modulo add" as the ...
4
votes
1answer
52 views

Can we find the largest intersecting subfamily of convex polygons in quadratic time?

Let $\mathcal{F} = \{P_1, P_2,\ldots,P_m\}$ be a family of (closed) convex polygons in the plane, each represented by their vertices in (say) clockwise order. Let $n$ be the total number of vertices (...
4
votes
0answers
30 views

Data structure for identifying elements while keeping track of relation

I'm looking for a data structure representing a finite set $I$ and a $d$-relation $R \subseteq I^d$ such that the following operations can be implemented efficiently: Add a new element $i$ to $I$. ...
4
votes
0answers
91 views

Distribution of pointer keys in a Skip-list node

Suppose we have a list of $N$ keys where the distribution of keys follows $f(x)$. We construct a skip list over the keys. Now if I pick a key (e.g. 31 in the ...
4
votes
0answers
3k views

How to find the maximum size of a B+ tree?

I came across this paper (page 16) which explains how to calculate the size of B+ trees. According to it the maximum number of nodes at level $i$ is $2(n/2)^{i-1}$ for a B+ tree of order $n$. Thus a ...
4
votes
0answers
158 views

Data structure for a Rete in production rule system

Example of Data This is the data for one monkey. There are many similar but different monkeys. ...
4
votes
0answers
56 views

How to realize a distributed queue with unreliable participants?

I want to build an application that relies on a distributed queue with participants in a decentralized (peer-to-peer) network. The participants cannot be relied on to correctly follow a protocol. I ...
4
votes
0answers
190 views

Data structures for ordering noisy data

In a certain robotics application, I encountered a problem in which we need to determine the order of positions of several robots on $\mathbb{R}$. Each measurement that we take of robot positions is ...
4
votes
1answer
684 views

Optimal Binary Search Trees Knuth

Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289 Please have a look at this paper, specifically page 18 in which he tries to prove his ...
4
votes
0answers
601 views

Why does a first-child-next-sibling tree implementation have parent pointers?

Below is the code, ...
4
votes
0answers
280 views

Concurrent priority queue with lazy increase-key

I could use a priority queue supporting the find-and-delete-min, and lazy-increase-key operations. The last term is my "...
4
votes
0answers
419 views

Counting Graphs (Minimum Number of Bits Required To Encode Certain Graphs)

Background: I am interested in finding succinct data structures for certain types of graph classes, particularly partial k-trees. For general graphs, there are $\binom{\binom{n}{2}}{m}$ graphs on $n$ ...
4
votes
0answers
231 views

Updating the Cheriton-Tarjan MST algorithm to use binomial heaps?

The Cheriton-Tarjan MST algorithm finds MSTs in time O(m log log n) in arbitrary graphs by using a cleverly-modified version of a leftist heap data structure to store edges. It was developed in 1976. ...
3
votes
0answers
77 views

Remove a subsequence from a string and append it at the end

Consider the following operation on strings: pick a (not necessarily contiguous) subsequence, remove it and then append all the characters in the same order at the end. This operation preserves the ...
3
votes
0answers
74 views

How to find the Expected height of a randomly built binary tree

I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or ...
3
votes
0answers
34 views

What's the best non-amortized disjoint set?

In practice, the amortized O(α(n)) data structure is good for every case. But if I want to be pedantic and require each operation to be under a certain time complexity, what's the currently known best ...
3
votes
0answers
60 views

Data structure to determine vertex membership after edge removal from a tree in sub-linear time?

Consider a tree $T = (V,E)$ and its induced disjoint trees $T_1 = (V_1, E_1), T_2=(V_2, E_2)$ by the removal of an edge $e \in E$. Is there a data structure that enables the immediate determination of ...
3
votes
0answers
116 views

Minimum number of nodes to select such that every node is at most k nodes away

I received this problem on an exam a few months ago, and have kept thinking about how to solve it with no luck. Given a binary tree where each node in the tree can either be selected or unselected, ...
3
votes
0answers
63 views

Is this dynamic graph problem solvable?

I came up with following subproblem while working on another problem. Can someone confirm if its a recognized problem. I have spent months but couldn't make any progress. Design a data structure that ...
3
votes
1answer
40 views

Space-efficient data structure for analytical querying of multiple branching evolutions of a dataset

Problem Description I have a data state space: a set of data sets, each of which can be modelled as a collection of arbitrary key-value pairs. These data sets are each a branch of evolution of a ...
3
votes
0answers
450 views

What's the number of leaves in AVL tree

How can I prove that the number of leaves in a balanced BST is $\Omega (N)$ where $N$ is the number of nodes in the tree? I tried somehow to prove that an AVL/Fibonacci tree should have $\Omega (N)$ ...
3
votes
0answers
408 views

Making an array increasing by modifying elements

I am trying to solve a problem on codeforces. Given an integer array $a_1,\ldots,a_n$, our goal is to find the minimal number of instructions, each of which increments or decrements a single entry, ...
3
votes
0answers
48 views

Forbidden Sequence Dynamic Programming

Given a finite set $\Omega$, I have the following problem. Say there is a list of forbidden subsequences $F \subset \Omega \cup \Omega^2 \cup \Omega^3 \dots \Omega^\infty$, while we do not know the ...
3
votes
0answers
185 views

Algorithm for answering queries of the type "largest interval contained in the given interval"

I have been wondering over the following problem: Given a set $S$ of intervals on the number line. We can do two operations on them: Add a new interval $[l_i,r_i]$ to $S$ Given an interval $[l_j, ...
3
votes
0answers
95 views

DCEL with dynamic graph

Is doubly-connected edge list a good data-structure for planar graph which vertices can be moved freely? I experienced DCEL as a very good structure when it comes to add/delete some vertex or edge. ...
3
votes
0answers
174 views

Interesting applications of union-find

I've been trying to find interesting applications of union-find that are lesser known. Here are some popular algorithms based on union-find that I know: Kruskal's algorithm for MST Tarjan's off-line ...
3
votes
1answer
272 views

Tree traversal with conditional summing values from nodes

Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can ...
3
votes
0answers
66 views

Probability of a double cycle in cuckoo graph

I have read Chater 17. Balanced Allocations and Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
3
votes
0answers
34 views

If we could use electrons as information storage, how would we model a database?

It's not completely incredible that electrons are accessible information storage units. So let's say there is a breakthrough and we suddenly have read/write access to every electron on the planet. ...
3
votes
0answers
42 views

Proving an upper-bound on the cost of all calls to rebuild() during a sequence of m operations in a scapegoat tree

I'm reading through Open Data Structures by Pat Morin and am currently looking at scapegoat trees. The book is free and can be downloaded from here: http://opendatastructures.org/ods-java.pdf On page ...
3
votes
0answers
2k views

What are efficient data-structures for insert/delete by index?

First of all, a definition of the operations: Insert by index: insert element e at index n, increasing the index of all ...
3
votes
0answers
96 views

effective, efficient algorithms on antichains

In a partially ordered set L, an antichain is a subset A of L such that no two elements of A are comparable. Antichains are commonly used to represent upward-closed subsets of L, that is, sets S such ...
3
votes
0answers
49 views

What data structure should I use for storing my data?

I am currently looking for a way in which I can store my data, and quickly look it up. What currently seem to be the best idea is to use a hash map. reasons: To identify what item I am looking for, ...
3
votes
0answers
633 views

Finding multi word anagrams from a set of words

Finding all anagrams for a word $w$ from a set of words is a problem with many well-known solutions (for example make a hash table mapping from the bag of letters of a word to the word). But what ...
3
votes
0answers
309 views

What is the intuition behind balancing in AVL trees?

I am not sure that my question is clear from the first sight. But I will try to explain what I mean. For now, I am learning balancing the trees on the example of AVL trees. We know that to balance ...
3
votes
0answers
39 views

Dominator tree with edges annotated by min-cut size

Consider the dominator tree of, say, the graph of objects in memory, computed by a memory profiler - one of the most powerful memory leak debugging features, I believe. The dominator tree tells you "...
3
votes
0answers
168 views

Data Structure for k Nearest Neighbour Search in D dimension using only point cloud as query points

I have a point cloud of N points in D-dimensional space with periodic boundary conditions, where N can range from 500 to 10^8 and D can range from 1 to 20. The distribution of points varies wildly, ...
3
votes
0answers
913 views

Tree of Despair: Collecting Data from a Tree with Multiple Types of Branching

Provided is a tree with three types of node. The structure of the tree cannot be modified and traversal of the tree is limited to querying a node for its children or its parent. The objective of the ...

1
2 3 4 5
9