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.

Filter by
Sorted by
Tagged with
1
vote
0answers
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 ...
3
votes
1answer
81 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
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 ...
4
votes
1answer
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 ...
1
vote
1answer
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.
1
vote
2answers
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.
20
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ? ...
9
votes
1answer
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 ...
2
votes
1answer
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 ...
4
votes
1answer
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. ...
13
votes
2answers
380 views

Data structure for updates on intervals and querying number of zeros

I am looking for a data structure that would maintain an integer table $t$ of size $n$, and allowing the following operations in time $O(\log n)$. $\text{increase}(a,b)$, which increases $t[a],t[a+1],...
9
votes
2answers
332 views

Almost universal string hashing in $Z_{2^n}$ and sublinear space

Here are two families of hash functions on strings $\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$: For $p$ prime and $x_i \in \mathbb{Z_p}$, $h^1_{a}(\vec{x}) = \sum a^i x_i \bmod p$ for $a \in \...
3
votes
1answer
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 (...
4
votes
0answers
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 ...
14
votes
1answer
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 ...
3
votes
1answer
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 ...
4
votes
2answers
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 ...
4
votes
1answer
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 ...
8
votes
1answer
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 ...
11
votes
4answers
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 ...
4
votes
1answer
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 ...
15
votes
2answers
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 ...
5
votes
1answer
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) = {...
12
votes
1answer
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 ...
15
votes
2answers
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 ...
20
votes
1answer
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 ...
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 ...
2
votes
1answer
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 ...
7
votes
0answers
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 ...
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 ...
4
votes
0answers
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 ...
5
votes
2answers
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 ...
5
votes
1answer
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 ...
-1
votes
2answers
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 ...
4
votes
1answer
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: ...
12
votes
0answers
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 ...
2
votes
0answers
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 ...
6
votes
1answer
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 ...
0
votes
1answer
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 ...
13
votes
0answers
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)$ ...
1
vote
1answer
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 ...
3
votes
0answers
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-...
4
votes
3answers
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, ...
7
votes
1answer
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 ...
7
votes
0answers
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 ...
14
votes
1answer
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 ...
15
votes
1answer
622 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 ...
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 ...

1 2 3
4
5
7