Range query

As explained in Advanced Algorithms and Data Structures

A region query retrieves the data points within a specified radius of a given point.

A range query retrieves points satisfying a spatial constraint, such as lying within a radius of a center or within independent coordinate bounds. Multidimensional trees prune branches whose regions cannot intersect the query region. section 9.3.6

Common forms differ by the geometry of the requested region:

• A spherical query returns points within a specified Euclidean distance of a center; recursive search checks the nearer branch and visits the other when the splitting boundary intersects the sphere. section 9.3.6
• A rectangular query tests every coordinate against a minimum and maximum, then recursively explores only branches intersecting the hyper-rectangle. section 9.3.6
• A region with constraints that mix features is harder than an axis-aligned rectangle and may require a more complex optimization method. section 9.3.6

Performance depends on the region. A small region may follow one path in O(h), or O(log n) in a balanced tree; a region containing all points traverses the tree in O(n), which is the worst-case bound. section 9.3.6

DBSCAN neighborhoods

DBSCAN uses a range query to find every point within radius eps of each point. An indexing structure can reduce the overall work from O(n²) toward O(n log n) when queries typically cost O(log n), although individual queries still have an O(n) worst case. section 12.3.3

Figure 9.26 Region search on a k-d tree returns all the points in a k-d tree within a given hyper-rectangle. This means looking for points that, for each coordinate, satisfy two inequalities: each coordinate must be within a range. For instance, in this 2-D example, the points’ x coordinates need to be between -2 and 3.5, and y coordinates between -4 and 2.

Visualizes a two-dimensional hyper-rectangle by showing independent bounds for each coordinate and the points returned by the query. section 9.3.6

How Advanced Algorithms and Data Structures covers it

How deep it goes

Explains spherical and rectangular recursion, branch pruning, and complexity, while deferring mixed-feature regions to more complex methods.

Examples

Uses salary-and-tenure rectangles, particle interactions within a force radius, and DBSCAN hypersphere neighborhoods.

What it assumes

Assumes multidimensional points and tree-based indexing, while defining spherical and rectangular constraints through concrete search procedures.

What you can do after

Apply it via k-d trees or SS-trees to implement neighborhood, similarity, particle-interaction, or clustering queries.

How it connects

Connects range queries with k-d trees, SS-trees, nearest neighbor search, similarity search, DBSCAN, and clustering.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  MongoDB 8.0 in Action, Third EditionA range query selects records whose indexed or comparable values fall within specified lower and upper bounds or ordering conditions.
• 

  liveBookmanning.com
  Elasticsearch in Action, Second EditionA query that retrieves documents whose field values fall within specified lower and upper bounds.

Compare how 3 books explain range query →

Related concepts

• less-than-or-equal operatoruses · The less-than-or-equal operator compares values and tests whether one value is less than or equal to another.
• must_not clauseused by · A Boolean query clause in Elasticsearch that excludes documents matching its inner query.
• DBSCANused by · DBSCAN is a density-based clustering algorithm that groups observations in dense regions and identifies observations in lower-density regions as noise or outliers.
• deletionused by · Deletion is an operation that removes an item, association, or resource from a collection or system, or requests or marks it for removal.
• similarity searchkind of · Similarity search is a retrieval technique that finds or ranks items by comparing their representations with a query according to a similarity or distance measure.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.