Database Paper Browser

Back to papers

Efficient Searching with Linear Constraints (Extended Abstract)

Summary: External-memory data structures for reporting points satisfying a linear constraint a·x ∈ [α,β] in R^d, with focus on I/O cost. For d=2: first near-linear-space structure with optimal I/Os, plus a linear-size worst-case-efficient structure, space/query tradeoffs, and extensions to higher dimensions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1142
Venue
PODS
Year
1998
Pagerank
0.00011643406
Overall Rank
1,502 | 89.56%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank Citing Paper Year Venue Pagerank
430 The Onion Technique: Indexing for Linear Optimization Queries 2000 SIGMOD 0.00023463938
631 Indexing the Positions of Continuously Moving Objects 2000 SIGMOD 0.00018935493
1,002 On Indexing Mobile Objects 1999 PODS 0.00014702555
1,182 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013455963
1,766 Indexing Moving Points (Extended Abstract) 2000 PODS 0.000106236
1,926 Efficient Numerical Error Bounding for Replicated Network Services 2000 VLDB 0.00010067514
2,976 Processing a Large Number of Continuous Preference Top-k Queries 2012 SIGMOD 7.789303e-05
3,463 Towards Robust Indexing for Ranked Queries 2006 VLDB 7.069675e-05
4,711 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 5.9790683e-05
5,555 On Obtaining Stable Rankings 2019 VLDB 5.4386174e-05
5,935 Indexing Uncertain Data 2009 PODS 5.2657009e-05
5,979 External Memory Algorithms 1998 PODS 5.2450009e-05
9,453 Towards Indexing Functions: Answering Scalar Product Queries 2014 SIGMOD 4.339214e-05
11,825 Efficient Top-k Indexing via General Reductions 2016 PODS 4.1945683e-05
12,167 FIFO Indexes for Decomposable Problems 2011 PODS 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032169493
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083378538
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.0004429571
354 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00026137988
1,172 Processing Queries By Linear Constraints 1997 PODS 0.00013505441
1,183 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00013455596
1,997 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 9.8322994e-05
2,013 Path Caching: A Technique for Optimal External Searching (Extended Abstract) 1994 PODS 9.7928688e-05
2,851 On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract) 1997 PODS 8.0155027e-05
3,795 OODB Indexing by Class-Division 1995 SIGMOD 6.7604747e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
6,215 New Results on Two-dimensional Orthogonal Range Aggregation in External Memory 2011 PODS 5.153674e-05
8,647 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4768766e-05
2,013 Path Caching: A Technique for Optimal External Searching (Extended Abstract) 1994 PODS 9.7928688e-05
7,226 Efficient Search in Very Large Databases 1988 VLDB 4.7953551e-05
8,546 I/O-Efficient Planar Range Skyline and Attrition Priority Queues 2013 PODS 4.4937074e-05
8,919 Efficient Indexes for Diverse Top-k Range Queries 2020 PODS 4.427232e-05
12,294 Worst-Case Efficient Range Search Indexing 2009 PODS 4.1945683e-05
12,106 Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility 2012 PODS 4.1945683e-05
1,766 Indexing Moving Points (Extended Abstract) 2000 PODS 0.000106236
1,182 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013455963