Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

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
1
vote
0answers
103 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
194 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 ...
6
votes
4answers
1k views

What are the most known database disk storage layout algorithms?

I can list for example algorithms used in databases: append only b-trees (MVCC like used in CouchDB) merged logs (like used in Big Table, Hbase, Cassandra) paged storages grouped in extents (like in ...
7
votes
2answers
320 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 ...
4
votes
1answer
197 views

Deterministic dynamic dictionary on a small universe

We want to maintain a dictionary of $m$ elements with insert/delete and lookup in the word RAM model. Assume $m=O(n)$ at all times, so there can't be too many inserts without deletions. The universe ...
7
votes
2answers
2k views

Efficient synchronization of two instances of an ordered list

What data structure or algorithm can be used to efficiently synchronize two nearly identical ordered lists? Two offline systems start with the same ordered list and each edit, insert, delete and move ...
5
votes
0answers
93 views

Dynamic 2-dimensional orthogonal range reporting in external memory and linear space

Orthogonal 2-dimensional range reporting is the problem of storing a set of values from $U \times V$, where $U$ and $V$ are totally ordered universes, subject to queries of the form "Return all stored ...
5
votes
1answer
189 views

Local updates in weight-balanced search trees

In Kurt Mehlhorn's monograph "Data Structures and Algorithms 1: Sorting and Searching", he poses the following question (III.9.22): Design a balanced tree scheme where the worst case rebalancing ...
2
votes
0answers
155 views

How can an R+ tree extend its coverage?

In the original article on R+ tree, Algorithm Insert recursively searches for all leaf nodes that overlap the given input rectangle ...
14
votes
3answers
562 views

Associative hash mixing

Consider the lowly singly-linked list in a purely functional setting. Its praises have been sung from the mountain tops and will continue to be sung. Here I will address one among its many strengths ...
7
votes
3answers
7k views

Split or merge Binary Search Trees in O(log n)

We need to have an efficient operation of merging or splitting two binary search trees $S_1$ and $S_2$. There are given the following. The element with the largest value in $S_1$ is smaller than the ...
52
votes
13answers
3k views

For which algorithms is there a large gap between the theoretical analysis and reality?

Two ways of analyzing the efficiency of an algorithm are to put an asymptotic upper bound on its runtime, and to run it and collect experimental data. I wonder if there are known cases where there ...
5
votes
1answer
5k views

Is it possible to convert a Max heap to a Min heap in place?

I was just wondering if this was possible? Surely there maybe some naive methods of doing so, but I was just wondering if someone can suggest efficient ways to do so.
2
votes
1answer
270 views

Why isn't the decrease key operation in a pairing heap $O(1)$

According to the paper (1986) Decrease-key is implemented by first by removing the node from the tree $O(1)$, decreasing the key $O(1)$, then linking it with the root node $O(1)$. The paper admits ...
1
vote
3answers
618 views

Is there an array structure that allows for O(1) complexity for reverse, zip, slice etc operations?

Many operations on arrays have $O(n)$ complexity. If we represent arrays as accessors methods, many of them could be done in $O(1)$. For example, the $i$th item in the reverse of an array $A$ of ...
9
votes
2answers
434 views

Select two numbers that sum to $p$, using sub-linear query time

Here is a nearest neighbor problem. Given reals $a_1, \ldots, a_n$ (very large $n$!), plus target real $p$, find $a_i$ and $a_j$ whose SUM is closest to $p$. We allow reasonable pre-processing/...
0
votes
2answers
290 views

Is it possible to convert any tree to a B-tree or an R-tree?

I have a tree structure representing sentences. My tree's nodes are characterized by a type (sentence, phrase, or word), unique ID, text value and an arbitrary number of features. Each node has an ...
2
votes
1answer
130 views

Bloom filter for predecessor queries?

Given a threshold $k$ is it possible to make a succinct data structure $S$ to answer queries of the form, given query $x$ does there exist a value $s$ in $S$ such that $s-k \leq x \leq s+k$? Like a ...
7
votes
1answer
669 views

Can we perform an n-d range search over an arbitrary box without resorting to simplex methods?

Suppose I have some set of points in d-dimensional space, each with some mass. Our problem size will be the number of points in this set. After some roughly (within polylog factors) linear ...
13
votes
4answers
744 views

Reference for fundamental theorem on tree rotations

Two binary search trees are said to be linearly equivalent when they agree in their in-order traversals. The following theorem explains why tree rotations are so fundamental: Let A and B be binary ...
-2
votes
1answer
270 views

Find all items which are subsets of an item

I have a problem that I think should have been studied. I am looking for algorithms for it. Each item is a set of key-value pairs. Let $x$ be an item and $F$ be a set of items. Each key and each ...
1
vote
0answers
93 views

Linear time algorithm for computing the labels of leaves in a recursively defined tree [closed]

The original copy of the question on MSE. Let $S=(s_0, ..., s_{N-1})$ be a sequence of $N=2^p$ numbers. We consider a labelled binary tree of height $p$ as follows: The root has label $S$, for each ...
3
votes
1answer
77 views

Persistant bag/set with direct access to known elements

I'm looking for a bag or set data structure that will allow for the following operations: Add an element to the set, and get a "pointer" to that element. ...
8
votes
1answer
270 views

Storing a bit vector in uninitialized memory and minimal space

A well-known trick for storing bit vectors using uninitialized memory can allocate a bit vector of size $n$ in which all of the bits are set to $0$ by allocating $(2 n + 1)\lceil \lg n \rceil$ bits of ...
4
votes
2answers
2k views

Efficient algorithm to find overlapping circles of various sizes

I have a collection of N circles in the plane with various position and radius. Circles move around according to one force and become bound to each other once they overlap. I need a fast way to ...
1
vote
2answers
415 views

How do top researchers keep track new results in datastructures

Is there any twitter or some feed,which constantly sends new results which are being published to your mail.
10
votes
4answers
777 views

Costs of performing approx. nearest neighbor search in a skip quadtree

NOTE: The question has been restated in my answers: Assuming now that we can find the lowest sibling ancestors in $O(1)$ time, can the ANN be really performed in $O(\log n)$? Quadtrees are efficient ...
3
votes
1answer
201 views

Outer part of Voronoi diagram in 3D

Given a set of points $V \subset \mathbb{R}^d$, the Voronoi diagram divides $\mathbb{R}^d$ into $|V|$ parts such that for every $v \in V$, the part of $\mathbb{R}^d$ for which $v$ is closer than any ...
3
votes
1answer
312 views

Optimal insertion times in insertion-only data structures beyond Bentley-Saxe

The Bentley-Saxe trick allows us to go from a static decomposable problem to a problem admitting insertions, where the insertion time is off the optimal time by a factor of $\log n$. Is this tight ? ...
4
votes
1answer
300 views

What is the fastest deterministic algorithm for incremental dynamic tree reachability?

As the title. The dynamic algorithm maintains the transitive closure of a tree when the tree undergoes a series of edge insertions (but no deletions)? And the algorithm supports constant query time. ...
9
votes
1answer
265 views

Heapsort:Heaps =~ Quicksort:BSTs =~ Mergesort:___?

Please excuse the terseness of the title, I may have sacrificed clarity on the altar of conciseness. One can see that inserting elements of an array into a binary search tree and reading them back ...
15
votes
1answer
273 views

Maintaining order in a list in $AC^0$ in $O(1)$ time

The order maintenance problem (or "maintaining order in a list") is to support the operations: singleton: creates a list with one item, returns a pointer to it <...
2
votes
1answer
333 views

Verifying consistency of strict and non-strict partial orders constraints

I am building a set of constraints of the kind $x < y$ and $x \leq y$, where $<$ is a strict order and $\leq$ is a non-strict order on the same set, and $x$ and $y$ are abstract variables ...
3
votes
1answer
501 views

Breadth first search and Eppstein K shortest paths algorithm

I'm trying to understand the algorithm for finding K shortest paths in a graph described by Eppstein in this paper: http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf I have trouble particularly ...
4
votes
1answer
369 views

Multidimensional B+ tree

I've got an idea for indexing multidimensional data. I haven't been able to find anything equivalent and am wondering if it is indeed a novel approach. The idea is a 'stacked' B+ tree implementation ...
11
votes
4answers
580 views

Shortest number of editing move between two words

I am looking for a data structure and an algorithm to compute the minimum number of changes required to transform one word into another, given the two words as inputs, where the only allowed changes ...
4
votes
1answer
577 views

Dynamic Data structure for All nearest smaller values

I need a data structure that stores a sequence of numbers and supports the following operations. The input to each operation includes the position of an item in the current sequence (not the value or ...
8
votes
1answer
370 views

logic in the presence of doubt, uncertainty, lies

I was reading Harry Frankfurt's On Bulls*t, a 1986 philosophical essay about this blurry notion between truth and falsity. This is not a gratuitous exercise. This may have applications to computer ...
15
votes
2answers
572 views

Exponential Speedup in External Memory

Background The external memory, or DAM model, defines the cost of an algorithm by the number of I/Os it performs (essentially, the number of cache misses). These running times are generally given in ...
12
votes
1answer
336 views

Minimal elements of a monotonic predicate over the powerset $2^{|n|}$

Consider a monotonic predicate $P$ over the powerset $2^{|n|}$ (ordered by inclusion). By "monotonic" I mean: $\forall x, y \in 2^{|n|}$ such that $x \subset y$, if $P(x)$ then $P(y)$. I am looking ...
5
votes
1answer
235 views

Revision Tracking Graph

Define the Revision Tracking Graph (RTG), which is an oriented graph (without circles) where each node x has a set C(x) associated with it. C(x) contains all edges on all paths from a node 0 ( C(0) = {...
28
votes
5answers
3k views

Binary search generalizations for posets?

Suppose I have a poset "S" and a monotonic predicate "P" on S. I want to find one or all maximal elements of S satisfying P. EDIT: I'm interested in minimizing the number of evaluations of P. What ...
6
votes
1answer
242 views

Self-referentially defined graph structures

It is possible to define graphs $G$ such that whether an edge exists between two vertices $v_1$ and $v_2$ depends on non-local properties of $G$. In particular, I am interested in directed graphs ...
15
votes
1answer
585 views

Bloom filter hashes: more or bigger?

In implementing a Bloom filter, the traditional approach calls for multiple independent hash functions. Kirsch and Mitzenmacher showed that you actually only need two, and can generate the rest as ...
21
votes
1answer
739 views

How close can we get to linear multiply, add, and compare (on integers)?

Accoring to K. W. Regan's article "Connect the Stars", he mentions at the end that it is still an open problem to find a representation of integers such that the addition, multiplication, and ...
0
votes
0answers
123 views

Efficient update of the keys in associative container

I need to maintain a set $\langle(k_1, v_1), (k_2, v_2), \dots, (k_N, v_N)\rangle$ of key-value pairs subject to the following update operation. Given two keys $a < b$ and a "shift" value $C$ as ...
-6
votes
1answer
5k views

What is the advantage of red/black trees in comparison with unbalanced trees? [closed]

In which situations would I use a red/black tree instead of an unbalanced tree?
6
votes
0answers
242 views

Data structures lower bounds on Turing machines

Have there been any results on lower bounds for implementing data structures on Turing machines, e.g. stacks, queues, etc ? I guess that people are mostly interested in models with random access, but ...
2
votes
1answer
331 views

Does the order of insertion affect the topology of an R-Tree

Say I have 2 permutations of the the same set of elements. I create 2 R-Trees, one for each permutation. Do I end up with 2 structurally identical R-Trees or not? PS: My elements are rectangles on a ...
24
votes
4answers
2k views

Handbook of advanced data structures

I am looking for a book on advanced data structures that goes beyond what is covered in standard textbooks like Cormen, Leiserson, Rivest, and Stein's "Introduction to Algorithms". A book that can be ...