Welcome to the DSzoo mini wiki at Scratchpad!
You can use the box below to create new pages for this mini-wiki. Make sure you type
[[Category:DSzoo]] on the page before you save it to make it part of the DSzoo wiki (preload can be enabled to automate this task, by clicking this link and saving that page. Afterwards, you may need to purge this page, if you still see this message).
Welcome to the DataStructures Zoo. This project was inspired by the success of the Complexity Zoo and the need to systematize data-structure knowledge.
- spelling of lower-bounds and data-structures
- we study problems, not implementations (eg predecessor vs van Emde Boas)
- models (cell-probe, RAM, pointer machine, comparison, algebraic)
- what is a problem? (static vs dynamic, language membership)
- lowerbounds (inc. communication complexity)
The Zoo Starts Here
Aka dictionaries, membership, hashing.
- small space
- smaller space: approximate membership (Bloom filters), perfect hashing (no membership at all)
- implementing hashing
- load balancing problems (offline, online, with moves, small-space deciders)
Problems in One Dimension
- priority queues
- search problems:
- predecessor search (longest prefix match on integers)
- segment stabbing (IP lookup, routing)
- range reporting
- problems in rank space (array problems):
- partial sums (rank and select, list indexing)
- range-minimum query, RMQ (priority range search, -dimensional searching)
- maintaining rank space: ordered file maintenance
Geometry in Low Dimensions
- fully decremental
- unique answer
- optimization answer:
- list best
- iterate in order
- aggregation queries:
- (semi)group laws
- count, weighted sum
- priority reporting
- color reporting
Point location (unique answer)
Searching among points:
- nearest neighbor (optimization)
- approximate nearest neighbor (unique answer)
- extreme point in a direction (optimization); aka LP / convex hull query
- extreme point to a rotation (optimization)
- special case: angle enclosing point, aka convex hull tangent
- range problems: aggregate over points in query shape
- stabbing problems: aggregate over shapes stabbed by a point
- special case: hierarchical shapes
- optimization answer: report minimal in hierarchical shapes
- unique answer: disjoint shapes
Approximation version where shapes are scaled by approximation.
Shapes can be:
- orthogonal rectangles. Special cases:
- dominance rectangles
- ranges on each coordinate are bit prefixes
- polygons, in particular triangles. Triangulation gives reduction to triangles, but it's multiplicative (additive may be possible)
- circles: near neighbor problems. Range/stabbing are equivalent. Approximate version is particularly meaningful.
Intersection problems: (ray shooting)
- shooting rays into segments:
- in order of intersection (optimization)
- segments intersected by segments (aggregate)
Special case of ray/segments being axis-parallel.
Geometry in High Dimensions
- near neighbors in and Hamming norms
Derandomization leads to challenging problems.
- partial match
- near neighbors in and geometric alignment problems.
- pattern matching and low space
- searching with wildcards
- approximate searching and edit distance
(Almost) Static Trees
- lowest common ancestor
- marked ancestor and path aggregation (sum, min)
- something about small labelings
Construction time is usually interesting (graph theoretically).
- standard representation problems: below space (connectivity, reachability, shortest paths, s-t mincut)
- spanners and approximate distance oracles: better than storing the graph
- systematic data structures
- dynamic trees (forests, actually)
- If the tree is only changed by inserting or deleting leaves, see "Almost Static Trees" above.
- "easy" problems on undirected graphs: connectivity, MST, mincut
- reachability in directed graphs
- hard problems: shortest paths, flow and s-t mincut
The following special cases are often considered: