Efficient Direct-Access Ranked Retrieval

Mohsen Dehghankar, Raghav Mittal, Suraj Shetiya, Abolfazl Asudeh, Gautam Das · 2025

Read Efficient Direct-Access Ranked Retrieval by Mohsen Dehghankar, Raghav Mittal, Suraj Shetiya, Abolfazl Asudeh, Gautam Das (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-01108.txt.

Introduction

Mohsen Dehghankar and co-authors extend a basic database trick, jumping straight to any item, to search results that are ranked on the fly, in this 2025 arXiv paper. In ranked retrieval and similarity search, the order of results depends on a query across many features, so landing directly on the item at a given rank is hard. The team formalizes the problem and builds two families of methods.

One method answers in logarithmic time but needs huge storage in high dimensions. The second samples the data, uses linear space, and returns a small set guaranteed to hold the target item. Tests on real and synthetic data reached millions of records and hundreds of features, with bounds the authors prove near optimal.

Catalog record

CREATORMohsen Dehghankar, Raghav Mittal, Suraj Shetiya, Abolfazl Asudeh, Gautam Das
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-01108

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Direct-Access Ranked Retrieval Mohsen Dehghankar, Raghav Mittal, Suraj Shetiya, Abolfazl Asudeh, Gautam Das Abstract . We study the problem of Direct-Access Ranked Retrieval ( DAR ) for interactive data tooling, where evolving data exploration practices, combined with large-scale and high-dimensional datasets, create new challenges. DAR concerns the problem of enabling efficient access to arbitrary rank positions according to a ranking function, without enumerating all preceding tuples. To address this need, we formalize the DAR problem and propose a theoretically efficient algorithm based on geometric arrangements, achieving logarithmic query time. However, this method suffers from exponential space complexity in high dimensions. Therefore, we develop a second class of algorithms based on ε \varepsilon -sampling, which consume a linear space. Since exactly locating the tuple at a specific rank is challenging due to its connection to the range counting problem, we introduce a relaxed variant called Conformal Set Ranked Retrieval ( CSR ), which returns a small subset guaranteed to contain the target tuple. To solve the CSR problem efficiently, we define an intermediate problem, Stripe Range Retrieval ( SRR ), and design a hierarchical sampling data structure tailored for narrow-range queries. Our method achieves practical scalability in both data size and dimensionality. We prove near-optimal bounds on the efficiency of our algorithms and validate their performance through extensive experiments on real and synthetic datasets, demonstrating scalability to millions of tuples and hundreds of dimensions. 1. Introduction While recent advances in data tooling have significantly transformed the landscape of data science, the challenges of the AI era have posed new obstacles in data exploration and visual analytics ( Bikakis et al. 2025 ) . Modern human-centered tools, such as spreadsheets, data science notebooks, visual analytics platforms, and interactive data science libraries, empower users with intuitive interfaces for seamless data exploration and manipulation ( Chen et al. 2023 ; Rahman et al. 2020 ; Shankar et al. 2022 ; Zhao et al. 2023 ) . However, the exponential growth of data sizes due to the widespread adoption of big data technologies has placed unprecedented demands on the efficiency and responsiveness of these tools. As datasets scale to massive volumes, ensuring efficient and interactive user experiences becomes a critical yet challenging task. A common practice in interactive data exploration is ranked retrieval , where data is ordered according to a user-defined or algorithmically generated ranking function, while the user may be interested in accessing specific rank positions or a window of ranked tuples. To further clarify this, let us consider the following example. Example 0. In spreadsheet applications ( Rebman Jr et al. 2023 ; Ma et al. 2024 ) , data scientists frequently create new attributes as weighted sums of existing ones. Subsequently, they may “jump” to tuples at specific rank positions without explicitly enumerating preceding entries. Similar examples can be made for other applications. For instance, in Jupyter notebooks ( Kluyver et al. 2016 ) , analysts may need to directly retrieve tuples at particular ranks, effectively skipping over earlier-ranked items. Furthermore, recommendation systems frequently employ ranked retrieval for paged access, allowing users to directly navigate to specific result pages determined by complex ranking criteria. In all these scenarios, the ability to perform efficient direct-access ranked retrieval , i.e., to quickly access the tuple at an arbitrary rank position i , without the overhead of enumerating the entire dataset up to that position, is crucial for maintaining the interactivity and responsiveness expected by users. Particularly, the large number of attributes in datasets within domains such as AI creates a high-dimensional space of possible ranking functions , potentially encompassing up to tens or hundreds of dimensions, particularly when ranking functions are machine-generated. Traditionally, the interest of the data management community in ranked retrieval has been on top- k query processing, with the objective of finding the top-ranked tuples ( Ilyas et al. 2008a ) . Such approaches, however, are tailored for a small value of k , and are ineffective for direct-access queries, with the goal of efficiently retrieving the tuple at an arbitrary ranking position i , where i can be in O(n) . Direct access to conjunctive queries has recently been studied to directly access a specific position in the join result, without fully materializing the join ( Tziavelis et al. 2024 ; Carmeli et al. 2023 ; Eldar et al. 2023 ) . These works, however, consider an prespecified ordering of the tuples (e.g., lexicographic order on an attribute), and focus on skipping the join operation. As a result, such approaches are not suitable for ranked-retrieval settings where the ranking function is part of the input query. Therefore, in this paper, we formalize and study the direct-access ranked retrieval ( DAR ) problem. We also introduce the notion of conformal set for ranked retrieval as a small set that contains the tuple at the queried rank i . Next, focusing on linear ranking functions, we propose efficient algorithms for each of the proposed problems. Specifically, our first algorithm uses the computational geometric concepts of duality, arrangements, and levels of arrangements for answering the DAR problem. This algorithm, however, suffers from the curse of dimensionality, and its space complexity increases exponentially with the number of attributes. Consequently, we propose several algorithms with a linear space complexity, even for a large number of attributes. Specifically, starting from d=2 , we propose our algorithm based on the concept of \varepsilon -samples, and extend it to high-dimensional settings by combining it with the stripe-range searching. This approach offers an efficient solution for finding a conformal set for an arbitrary rank position. Finally, combining our approach with range counting, we extend it for the exact version ( DAR problem). Efficiently finding the tuples within a narrow stripe range is fundamental in the development of our \varepsilon -sampling based solution. We formulate this as the problem of stripe range retrieval ( SRR ), with a focus on developing efficient algorithms for the challenging narrow ranges that only contain a small number of tuples. Inspired by the Hierarchical Navigable Small World graphs for approximate nearest neighbor problems ( Malkov and Yashunin 2018 ; Dehghankar and Asudeh 2025 ) , our practical and scalable algorithm constructs a hierarchical sampling structure for stripe range searching, maintaining the neighborhood regions of points in the hierarchy using smallest enclosing balls. Theoretically, we show the near-optimal efficiency of our algorithms up to a logarithmic factor. Besides, we conduct extensive experiments on real-world and synthetic datasets to evaluate the performance of our algorithms in practice and compare them against the existing baselines. Our experiments confirm the efficiency and scalability of our proposed algorithms. In particular, the \varepsilon -sampling algorithm, when combined with the hierarchical structure, achieves the best scalability with respect to both dimension and dataset size in terms of query time and index size, whereas the baseline methods are mostly affected by the curse of dimensionality. Summary of Contributions • (Section 2 ) We introduce and formalize the problems of (i) direct-access ranked retrieval ( DAR ), (ii) conformal set ranked retrieval ( CSR ), and (iii) stripe range retrieval ( SRR ). • (Section 4 ) We provide a lower bound on the DAR problem as well as proving the

Read the complete text