Questions tagged [data-structures]

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

394 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
19
votes
1answer
840 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
97 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
574 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
466 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
338 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
813 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
277 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
277 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
123 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
296 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
106 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
0answers
28 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
76 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
2k 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
1answer
61 views

How do 2-3 FingerTrees generalize to bigger branching factors?

FingerTrees as implemented by Haskell's Data.Sequence use a branching factor of 2-3 for Nodes, and have Digits of size 1-4. Imagine we want to make the branching factor much wider -- perhaps to ...
4
votes
0answers
154 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
55 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
189 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
613 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
578 views

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

Below is the code, ...
4
votes
0answers
277 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
405 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
225 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
31 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
56 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
60 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
0answers
88 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, Do ...
3
votes
1answer
33 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
86 views

Data structure to query intersection of a line and a set of line segments

We want to pre-process a set $S$ of $n$ line segments into a data structure, such that we can answer some queries: Given a query line $l$, report how many line segments in $S$ does it intersect. It ...
3
votes
0answers
245 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
227 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
46 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
170 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
83 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
122 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
0answers
59 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
1answer
214 views

minimum and maximum nodes of MultiWay tree of height h

I know that it doesn’t have to be balanced so in theory given that the height of the tree is $h$, the minimal number of nodes is obtained when each node has 1 key and 1 child, and since the first ...
3
votes
0answers
40 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
93 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
48 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
285 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
38 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
164 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
863 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 ...
3
votes
0answers
253 views

Generalization of XOR Linked Lists

Are there any results generalizing XOR Linked Lists to other types of data structures? For example, just like an XOR Linked List requires two pointers and can iterate a 1 dimensional list, I can ...
3
votes
0answers
98 views

Describe data structure using equations

Good afternoon. At work I'm currently developing a system which takes user input (well structured) and then stores it in memory to do some processing. The input is basically a dataset formed by ...
3
votes
0answers
1k views

Which machine learning algorithm is appropriate for predicting a vector?

I have a very large set of animal migration data, consisting of many series of vectors - each series is basically a path of a single animal. The dataset I'm using consists of 244 of these series. I ...
3
votes
0answers
178 views

Finding the distance to the nearest neighbor for each point in a set of points in $R^n$

I have a list of points in $R^n$, and for each point I want to find the Euclidean distance to the nearest other point in the list. I don't need to know the coordinates of the nearest neighbor; I only ...

1
2 3 4 5
8