Skip to content

Faceted Search

The Faceted Search extension for HNSW allows you to filter search results based on facets or attributes. This is particularly useful for applications where you need to narrow down search results based on categorical or numerical attributes, such as product categories, price ranges, or document types.

Features

  • Filter search results based on facets (attributes)
  • Support for multiple facet types (string, numeric, boolean, array)
  • Efficient filtering without compromising search performance
  • Combining multiple filters with AND/OR logic
  • Seamless integration with the core HNSW API

Installation

The Faceted Search extension is included in the HNSW package and can be imported as follows:

import (
    "github.com/TFMV/hnsw"
    "github.com/TFMV/hnsw/hnsw-extensions/facets"
)

Basic Usage

Creating a Faceted Graph

To create a graph with faceted search support, use the NewFacetedGraph function:

// Create a new graph with faceted search support
graph := facets.NewFacetedGraph[int]()

Adding Vectors with Facets

To add a vector with facets to the graph:

// Create a vector
vector := []float32{0.1, 0.2, 0.3, 0.4, 0.5}

// Create facets
facetValues := map[string]interface{}{
    "category":    "electronics",
    "price":       199.99,
    "inStock":     true,
    "tags":        []string{"smartphone", "5G", "camera"},
    "releaseYear": 2023,
}

// Add the vector with facets to the graph
err := graph.Add(hnsw.Node[int]{
    Key:   1,
    Value: vector,
}, facetValues)

Searching with Filters

To search for vectors and filter the results based on facets:

// Create a query vector
query := []float32{0.15, 0.25, 0.35, 0.45, 0.55}

// Create a filter
filter := facets.Eq("category", "electronics")

// Search for the 5 nearest neighbors that match the filter
results, err := graph.SearchWithFilter(query, 5, filter)
if err != nil {
    // Handle error
}

// Process the results
for _, result := range results {
    fmt.Printf("Key: %d, Distance: %f\n", result.Key, result.Dist)
}

Filter Types

The Faceted Search extension supports several types of filters:

Exact Match Filter

Matches facets with an exact value:

// Match products in the "electronics" category
filter := facets.Eq("category", "electronics")

Numerical Range Filter

Matches facets within a numerical range:

// Match products with a price between 100 and 300
filter := facets.Range("price", 100.0, 300.0)

Boolean Match Filter

Matches facets with a boolean value:

// Match products that are in stock
filter := facets.Eq("inStock", true)

Array Contains Filter

Matches facets that contain a specific value in an array:

// Match products with the "smartphone" tag
filter := facets.Contains("tags", "smartphone")

Combining Filters

You can combine multiple filters using AND and OR operators:

// Match products in the "electronics" category with a price between 100 and 300
filter := facets.And(
    facets.Eq("category", "electronics"),
    facets.Range("price", 100.0, 300.0),
)

// Match products in either the "electronics" or "accessories" category
filter := facets.Or(
    facets.Eq("category", "electronics"),
    facets.Eq("category", "accessories"),
)

// Complex filter: (category = "electronics" AND price between 100 and 300) OR (category = "accessories" AND inStock = true)
filter := facets.Or(
    facets.And(
        facets.Eq("category", "electronics"),
        facets.Range("price", 100.0, 300.0),
    ),
    facets.And(
        facets.Eq("category", "accessories"),
        facets.Eq("inStock", true),
    ),
)

Advanced Usage

Batch Operations

The Faceted Search extension supports batch operations for adding and deleting nodes with facets:

// Create nodes with facets
nodes := []hnsw.Node[int]{
    {Key: 1, Value: []float32{0.1, 0.2, 0.3}},
    {Key: 2, Value: []float32{0.2, 0.3, 0.4}},
    {Key: 3, Value: []float32{0.3, 0.4, 0.5}},
}

facets := []map[string]interface{}{
    {"category": "electronics", "price": 199.99},
    {"category": "accessories", "price": 29.99},
    {"category": "electronics", "price": 299.99},
}

// Add the nodes with facets to the graph
err := graph.BatchAdd(nodes, facets)
if err != nil {
    // Handle error
}

Searching with Negative Examples

The Faceted Search extension supports searching with negative examples, which allows you to find vectors that are similar to a positive example but dissimilar to a negative example:

// Create a positive and negative query vector
positiveQuery := []float32{0.1, 0.2, 0.3, 0.4, 0.5}
negativeQuery := []float32{0.5, 0.4, 0.3, 0.2, 0.1}

// Create a filter
filter := facets.Eq("category", "electronics")

// Search for the 5 nearest neighbors that match the filter
results, err := graph.SearchWithNegativeAndFilter(positiveQuery, negativeQuery, 5, 0.5, filter)
if err != nil {
    // Handle error
}

Custom Facet Store

By default, the Faceted Search extension uses an in-memory store for facets. However, you can implement your own facet store by implementing the FacetStore interface:

type FacetStore[K comparable] interface {
    Add(key K, facets map[string]interface{}) error
    Get(key K) (map[string]interface{}, error)
    Delete(key K) error
    Filter(filter Filter) ([]K, error)
}

For example, you could implement a facet store that uses a database or a file system to store facets.

Performance Considerations

The Faceted Search extension is designed to be efficient, but filtering can add overhead to the search process. Consider the following tips:

  • Keep the number of facets per node reasonable
  • Use batch operations for better performance when adding or retrieving multiple nodes
  • Consider implementing a custom facet store for very large datasets or when persistence is required
  • Complex filters (with many AND/OR conditions) may slow down the search process

Next Steps