Wikia

Scratchpad

DSzoo

217,518pages on
this wiki
Discuss this page0

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


Introduction

Welcome to the DataStructures Zoo. This project was inspired by the success of the Complexity Zoo and the need to systematize data-structure knowledge.

Mission Statement

  • spelling of lower-bounds and data-structures
  • we study problems, not implementations (eg predecessor vs van Emde Boas)

Concepts

  • 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

Exact Search

Aka dictionaries, membership, hashing.

  • derandomization
  • 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, 1 \frac{1}{2}-dimensional searching)
  • maintaining rank space: ordered file maintenance


Geometry in Low Dimensions

Problem types:

  • static
  • dynamic
  • incremental
  • decremental
  • fully decremental


Query types:

  • unique answer
  • optimization answer:
    • list best
    • iterate in order
  • aggregation queries:
    • (semi)group laws
    • existential
    • report
    • count, weighted sum
    • max
    • 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


Point-shape problems:

  • 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
  • angles
  • 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:
    • aggregate
    • 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 \ell_1, \ell_2 and Hamming norms

Derandomization leads to challenging problems.

  • partial match
  • near neighbors in \ell_\infty and geometric alignment problems.


String Searching

  • 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


Static Graphs

Construction time is usually interesting (graph theoretically).

  • standard representation problems: below n^2 space (connectivity, reachability, shortest paths, s-t mincut)
  • spanners and approximate distance oracles: better than storing the graph
  • systematic data structures


Dynamic Graphs

Fully dynamic problems:

  • 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:

Around Wikia's network

Random wikia