People who code: we want your input. Take the Survey

# 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.

330 questions
Filter by
Sorted by
Tagged with
94 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 ...
81 views

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. ...
286 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 ...
594 views

### Multiple-sources dominator trees: compact representation and fast algorithm?

I recently learnt about the concept of dominator trees and was fascinated by it. I was wondering how the problem extends to computing dominators from multiple sources, or even from all vertices in ...
206 views

### Give a simple way to augment Van emde boas tree, to find/delete median in O(log log u) time

I need a simple augmentation to support median/order statistic queries in O(log log n) time,without increasing the time for other operations.
426 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.
888 views

### How fast can we compute the set inclusion poset of a set family?

Given a set family $\mathcal{F}$ of subsets of a universe $U$. Let $S_1,S_2 \in \mathcal F$ and we want to answer is $S_1 \subseteq S_2$. I am looking for a data-structure that will allow me to ...
210 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 ...
356 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 ? ...
288 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 ...
380 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 ...
318 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. ...
380 views

127 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 (...
461 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 ...
324 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 ...
527 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 ...
3k 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 ...
1k 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 ...
384 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 ...
611 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 ...
381 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 ...
598 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 ...
237 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) = {...
381 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 ...
3k views

### What is a zipper, and how does it relate to a tree-like structure?

I was reading a chapter in LYAH which didn't really make sense to me. I understand that zippers can arbitrarily traverse a tree-like structure, but I need some clarification on it. Also, can zippers ...
762 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 ...
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 ...
351 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 ...
245 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 ...
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 ...
164 views

### On aB-trees and its practical implementation

I'm reading the paper Succincter by M. Patrascu (link). It introduces on page 7 the aB-tree. This is a regular B-ary tree that represents an array of values. It stores the element of the array in the ...
249 views

### Dynamic and/or practical succinct data structures for triangulations

Does anybody know of any results on succinct data structures for triangulations that can be constructed efficiently, and preferably also updated efficiently? Does anybody know of practical ...
191 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 ...
7k views

### Most efficient algorithm to compute set difference?

What is the most efficient algorithm to compute the difference between two set data structures? In particular, the algorithm should efficiently discover elements in the first set that are also in the ...
371 views

### Formal Representation of Haskell Data-Types

I come from Haskell programming and currently writing my (Diploma/Master) thesis. I'm having trouble finding a formal/mathematical notation for a Haskell data-type. The Haskell data type is: ...
168 views

### Minimal rare subgraphs

I am looking for any related work to the following problem. Say you have a large directed graph $G$ and you want to find rare (or unique) subgraphs of minimal size that are not isomorphic to any other ...
760 views

### Name this list-of-lists data structure

Is there a canonical name for the following data structure for list of lists? Suppose we have got a list of length $Z$ of finite lists $[a_0,\dots,a_n], [b_0,\dots,b_m], [c_0,\dots,c_o], \dots$ of ...
606 views

### Continuity vs Uniformity when designing Hash functions

Reading available literature (yep, including wikipedia), I see that hash functions should have (continuity) and map values that differ very little to similar/same hash codes, in particular for (hash ...
154 views

### Combining multiple time-based datasources with different periods

I have two time-based data sources (one providing data by month and the other by week) that must be combined to create a third daily source (recognizing that at best we're getting one possible ...
526 views

### Lock-free, constant update-time concurrent tree data-structures?

I've been reading a bit of the literature lately, and have found some rather interesting data-structures. I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
876 views

### Simple k-nearest-neighbor algorithm for euclidean data with highly variable density?

An elaboration on this question, but with more constraints. The idea is the same, to find a simple, fast algorithm for k-nearest-neighbors in 2 euclidean dimensions. The bucketing grid seems to work ...
75 views

### Load-balancing; Alternate methods of keeping track of nodes?

Reading various articles in the literature have given me only a few decent methods of keeping track of nodes before->after load-balancing them on a very large network. One popular method uses virtual-...
295 views

### Is there a name for a hashtable with a tree for each bin instead of a list?

It is well-known that the worst case performance for a chaining hashtable, is O(n), where n is the number of objects in the table. The normal assumption is that the hash is either uniform, or secure, ...
200 views

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

A dynamic predecessor data structure supporting findPredecessor, insert, and delete over ...
223 views

### Relational model for data structure reasoning

I am trying to find out if there is any work on applying the Codd's relational model (underlying relational databases) for reasoning about linked data structures. Any connections with UML models and ...
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 ...