  There is an increasing adoption of machine learning for encoding data into
vectors to serve online recommendation and search use cases. As a result,
recent data management systems propose augmenting query processing with online
vector similarity search. In this work, we explore vector similarity search in
the context of Knowledge Graphs (KGs). Motivated by the tasks of finding
related KG queries and entities for past KG query workloads, we focus on hybrid
vector similarity search (hybrid queries for short) where part of the query
corresponds to vector similarity search and part of the query corresponds to
predicates over relational attributes associated with the underlying data
vectors. For example, given past KG queries for a song entity, we want to
construct new queries for new song entities whose vector representations are
close to the vector representation of the entity in the past KG query. But
entities in a KG also have non-vector attributes such as a song associated with
an artist, a genre, and a release date. Therefore, suggested entities must also
satisfy query predicates over non-vector attributes beyond a vector-based
similarity predicate. While these tasks are central to KGs, our contributions
are generally applicable to hybrid queries. In contrast to prior works that
optimize online queries, we focus on enabling efficient batch processing of
past hybrid query workloads. We present our system, HQI, for high-throughput
batch processing of hybrid queries. We introduce a workload-aware vector data
partitioning scheme to tailor the vector index layout to the given workload and
describe a multi-query optimization technique to reduce the overhead of vector
similarity computations. We evaluate our methods on industrial workloads and
demonstrate that HQI yields a 31x improvement in throughput for finding related
KG queries compared to existing hybrid query processing approaches.
