Decomposable Searching Problems I: Static-to-Dynamic Transformation

No abstract is available for this paper.

• Publication year

  1980

• Venue

  J. Algorithms

• Publication date

  1980-12-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0196-6774(80)90015-2
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On a Greedy Heuristic for Complete Matching

  1981cited by this paper
• A New Approach to Planar Point Location

  1981cited by this paper
• Dynamization of Decomposable Searching Problems

  1980cited by this paper
• An Alphard Specification of a Correct and Efficient Transformation on Data Structures

  1980cited by this paper
• A transformation for adding range restriction capability to dynamic data structures for decomposable

  1979cited by this paper
• Decomposable Searching Problems

  1979cited by this paper
• A data structure for orthogonal range queries

  1978influential reference
• Two Papers on Range Searching: A Survey of Algorithms and Data Structures for Range Searching. Efficient Worst-Case Data Structures for Range Searching.

  1978cited by this paper
• A data structure for manipulating priority queues

  1978cited by this paper
• Predicate-Oriented Database Search Algorithms

  1978cited by this paper
• A Problem in Multivariate Statistics: Algorithm, Data Structure and Applications.

  1978cited by this paper
• Applications of a planar separator theorem

  1977cited by this paper
• Partial-Match Retrieval Algorithms

  1976cited by this paper
• Divide and conquer algorithms for closest point problems in multidimensional space.

  1976cited by this paper
• Multidimensional Searching Problems

  1976cited by this paper
• The Art of Computer Programming, Vol. 3: Sorting and Searching

  1974cited by this paper
• The Art of Computer Programming

  1968cited by this paper

• Dynamic and Streaming Algorithms for Union Volume Estimation

  2026cites this paper
• A Generic Framework for Fair Consensus Clustering in Streams

  2026cites this paper
• Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings

  2025cites this paper
• Single-Source Shortest Path Problem in Weighted Disk Graphs

  2025cites this paper
• Parallel Batch-Dynamic Algorithms for Spanners, and Extensions

  2025influential citation
• Incremental Planar Nearest Neighbor Queries with Optimal Query Time

  2025cites this paper
• Efficient Query Repair for Aggregate Constraints

  2025cites this paper
• Simpler is Faster: Practical Distance Reporting by Sorting Along a Space-Filling Curve

  2025cites this paper
• Arcs with increasing chords in $\mathbf{R}^d$

  2025cites this paper
• Nearest Neighbor Searching in a Dynamic Simple Polygon

  2025cites this paper
• Turning Big Data Into Tiny Data: Coresets for Unsupervised Learning Problems

  2025cites this paper
• Enhancing SR-Tree for Nearest Neighbor Search

  2025cites this paper
• Decentralized Data Archival: New Definitions and Constructions

  2025influential citation
• The General Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends

  2025cites this paper
• Minimal and Simplified Analysis of Hierarchical Density-Based Spatial Clustering

  2025cites this paper
• How to Grow an LSM-tree? Towards Bridging the Gap Between Theory and Practice

  2025cites this paper
• On the Costs and Benefits of Learned Indexing for Dynamic High-Dimensional Data: Extended Version

  2025cites this paper
• Towards Systematic Index Dynamization

  2024influential citation
• Fully Dynamic k-Means Coreset in Near-Optimal Update Time

  2024cites this paper
• Rapidash: Efficient Detection of Constraint Violations

  2024cites this paper
• Turnstile ℓp leverage score sampling with applications

  2024influential citation
• Settling Time vs. Accuracy Tradeoffs for Clustering Big Data

  2024cites this paper
• Segment Proximity Graphs and Nearest Neighbor Queries Amid Disjoint Segments

  2024cites this paper
• μWheel: Aggregate Management for Streams and Queries

  2024cites this paper
• Dynamic Geometric Connectivity in the Plane with Constant Query Time

  2024cites this paper
• Piano: Extremely Simple, Single-Server PIR with Sublinear Server Computation

  2024cites this paper
• FAST-LIO2: Fast Direct LiDAR-Inertial Odometry

  2024cites this paper
• LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR

  2024cites this paper
• First Tree-like Quantum Data Structure: Quantum B+ Tree

  2024cites this paper
• Plinko: Single-Server PIR with Efficient Updates via Invertible PRFs

  2024cites this paper
• Information-Theoretic Multi-Server PIR with Global Preprocessing

  2024cites this paper
• Rapidash: Efficient Constraint Discovery via Rapid Verification

  2023cites this paper
• Data Structures for Data-Intensive Applications: Tradeoffs and Design Guidelines

  2023cites this paper
• SWAT: A System-Wide Approach to Tunable Leakage Mitigation in Encrypted Data Stores

  2023cites this paper
• An Efficient Dynamic Version of the Distal Spatial Approximation Trees

  2023cites this paper
• Streaming Euclidean k-median and k-means with o(log n) Space

  2023cites this paper
• Massively parallel and streaming algorithms for balanced clustering

  2023cites this paper
• Range (Rényi) Entropy Queries and Partitioning

  2023cites this paper
• On the Rectangles Induced by Points

  2023cites this paper
• Differentially Private L2-Heavy Hitters in the Sliding Window Model

  2023cites this paper
• Stronger Coreset Bounds for Kernel Density Estimators via Chaining

  2023influential citation
• Fully Dynamic $k$-Clustering in $\tilde O(k)$ Update Time

  2023cites this paper
• Shortest Paths in Portalgons

  2023cites this paper
• Fully-Dynamic Decision Trees

  2022cites this paper
• Fast Streaming <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="zhang-ieq1-3018744.gif"/></alternatives></inline-formula>-Means Clustering With Coreset Caching

  2022cites this paper
• Polylogarithmic Sketches for Clustering

  2022cites this paper
• Fully Persistent Spatial Data Structures for Efficient Queries in Path-Dependent Motion Planning Applications

  2022cites this paper
• JanusAQP: Efficient Partition Tree Maintenance for Dynamic Approximate Query Processing

  2022cites this paper
• A Dynamic Low-Rank Fast Gaussian Transform

  2022cites this paper
• Approximate Range Thresholding

  2022cites this paper
• ParGeo: A Library for Parallel Computational Geometry

  2022influential citation
• Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window)

  2022cites this paper
• Single-Server Private Information Retrieval with Sublinear Amortized Time

  2022cites this paper
• Coresets for Decision Trees of Signals

  2021cites this paper
• ikd-Tree: An Incremental K-D Tree for Robotic Applications

  2021cites this paper
• Buffering updates enables efficient dynamic de Bruijn graphs

  2021cites this paper
• An Incrementally Updatable and Scalable System for Large-Scale Sequence Search using LSM Trees

  2021cites this paper
• Covering geometric domains

  2021cites this paper
• At-the-time and Back-in-time Persistent Sketches

  2021cites this paper
• Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems

  2021cites this paper
• Robust Coreset for Continuous-and-Bounded Learning (with Outliers)

  2021cites this paper
• A Framework for Private Matrix Analysis in Sliding Window Model

  2021cites this paper
• Dynamic layers of maxima with applications to dominating queries

  2021cites this paper
• Oblivious Sketching for Logistic Regression

  2021cites this paper
• Dynamic Connectivity in Disk Graphs

  2021cites this paper
• Metric k-median clustering in insertion-only streams

  2021cites this paper
• Volume-Hiding Dynamic Searchable Symmetric Encryption with Forward and Backward Privacy

  2021cites this paper
• Optimal Coresets for Gaussian Kernel Density Estimates

  2021cites this paper
• Sampling Hyperplanes and Revealing Disks ∗

  2021cites this paper
• Private Blocklist Lookups with Checklist

  2021cites this paper
• Parallel Batch-Dynamic kd-Trees

  2021influential citation
• Coresets for the Average Case Error for Finite Query Sets

  2021cites this paper
• Dynamic Enumeration of Similarity Joins

  2021cites this paper
• Introduction to Coresets: Approximated Mean

  2021cites this paper
• Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space

  2021cites this paper
• FAST-LIO2: Fast Direct LiDAR-Inertial Odometry

  2021cites this paper
• Dynamic Geometric Set Cover, Revisited

  2021cites this paper
• Further Results on Colored Range Searching

  2020cites this paper
• The optimal algorithm for dynamic support of the Voronoi Diagram for a set of points

  2020cites this paper
• Faster Approximation Algorithms for Geometric Set Cover

  2020cites this paper
• Fully-Dynamic Coresets

  2020cites this paper
• Dynamic Generalized Closest Pair: Revisiting Eppstein's Technique

  2020cites this paper
• Lecture Notes of CSCI5610 Advanced Data Structures

  2020influential citation
• Coresets for the Nearest-Neighbor Rule

  2020cites this paper
• Competitive Data-Structure Dynamization

  2020cites this paper
• Efficient independent set approximation in unit disk graphs

  2020cites this paper
• Small Summaries for Big Data

  2020cites this paper
• An Clue-Based Route Search on Road Networks Using Keywords and Spatial Relations

  2020cites this paper
• Introduction to Core-sets: an Updated Survey

  2020influential citation
• Fast LP-based Approximations for Geometric Packing and Covering Problems

  2020cites this paper
• Streaming statistical models via Merge & Reduce

  2020cites this paper
• New Nearly-Optimal Coreset for Kernel Density Estimation

  2020cites this paper
• Optimal Coreset for Gaussian Kernel Density Estimation

  2020cites this paper
• Mapless-Planner: A Robust and Fast Planning Framework for Aggressive Autonomous Flight without Map Fusion

  2020cites this paper
• On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications

  2020cites this paper
• Deterministic Coresets for k-Means of Big Sparse Data †

  2020cites this paper
• Automated clustering of EM side-channel emissions to detect anomalous device behavior

  2020cites this paper
• Faster PAC Learning and Smaller Coresets via Smoothed Analysis

  2020cites this paper
• A Framework for Private Matrix Analysis

  2020cites this paper
• D S ] 9 A pr 2 01 9 Lower Bounds for Oblivious Near-Neighbor Search

  2019cites this paper