A Query-Driven Approach to Space-Efficient Range Searching
We initiate a study of a query-driven approach to designing partition trees for range-searching problems. Our model assumes that a data structure is to be built for an unknown query distribution that we can access through a sampling oracle, and must be selected such that it optimizes a meaningful performance parameter on expectation. Our first contribution is to show that a near-linear sample of queries allows the construction of a partition tree with a near-optimal expected number of nodes visited during querying. We enhance this approach by treating node processing as a classification problem, leveraging fast classifiers like shallow neural networks to obtain experimentally efficient query times. Our second contribution is to develop partition trees using sparse geometric separators. Our preprocessing algorithm, based on a sample of queries, builds a balanced tree with nodes associated with separators that minimize query stabs on expectation; this yields both fast processing of each node and a small number of visited nodes, significantly reducing query time.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
LaSTR: Language-Driven Time-Series Segment Retrieval
Effectively searching time-series data is essential for system analysis, but existing methods often require expert-designed similarity criteria or rely on global, series-level descriptions. We study language-driven segme…
The "AI+R"-tree: An Instance-optimized R-tree
The emerging class of instance-optimized systems has shown potential to achieve high performance by specializing to a specific data and query workloads. Particularly, Machine Learning (ML) techniques have been applied su…
Multi-Label ClassificationMUlTI-LABEL-ClASSIFICATIONSearching in the Penn Discourse Treebank Using the PML-Tree Query
The PML-Tree Query is a general, powerful and user-friendly system for querying richly linguistically annotated treebanks. The paper shows how the PML-Tree Query can be used for searching for discourse relations in the P…
Sparse Attention as a Range Searching Problem: Towards an Inference-Efficient Index for KV Cache
Sparse attention improves LLM inference efficiency by selecting a subset of key-value entries, but at the cost of potential accuracy degradation. In particular, omitting critical KV entries can induce substantial errors …
A Network-Aware Approach for Searching As-You-Type in Social Media (Extended Version)
We present in this paper a novel approach for as-you-type top-$k$ keyword search over social media. We adopt a natural "network-aware" interpretation for information relevance, by which information produced by users who …
Retrieval