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.00011643887
Overall Rank
1,499 | 89.59%
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
428 The Onion Technique: Indexing for Linear Optimization Queries 2000 SIGMOD 0.0002349868
628 Indexing the Positions of Continuously Moving Objects 2000 SIGMOD 0.00018957327
1,004 On Indexing Mobile Objects 1999 PODS 0.00014694512
1,183 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013444058
1,764 Indexing Moving Points (Extended Abstract) 2000 PODS 0.0001062234
1,929 Efficient Numerical Error Bounding for Replicated Network Services 2000 VLDB 0.00010060709
2,967 Processing a Large Number of Continuous Preference Top-k Queries 2012 SIGMOD 7.7975455e-05
3,447 Towards Robust Indexing for Ranked Queries 2006 VLDB 7.082382e-05
4,718 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 5.9664602e-05
5,558 On Obtaining Stable Rankings 2019 VLDB 5.4375292e-05
5,937 Indexing Uncertain Data 2009 PODS 5.2606762e-05
5,987 External Memory Algorithms 1998 PODS 5.2399221e-05
9,377 Towards Indexing Functions: Answering Scalar Product Queries 2014 SIGMOD 4.344689e-05
11,833 Efficient Top-k Indexing via General Reductions 2016 PODS 4.1905499e-05
12,175 FIFO Indexes for Decomposable Problems 2011 PODS 4.1905499e-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.0032118946
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083300888
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00044255276
356 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00026091196
1,171 Processing Queries By Linear Constraints 1997 PODS 0.00013507216
1,180 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00013455619
2,001 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 9.8275076e-05
2,018 Path Caching: A Technique for Optimal External Searching (Extended Abstract) 1994 PODS 9.7852268e-05
2,857 On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract) 1997 PODS 8.009743e-05
3,794 OODB Indexing by Class-Division 1995 SIGMOD 6.7556886e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,645 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4725847e-05
6,214 New Results on Two-dimensional Orthogonal Range Aggregation in External Memory 2011 PODS 5.1487236e-05
2,018 Path Caching: A Technique for Optimal External Searching (Extended Abstract) 1994 PODS 9.7852268e-05
7,225 Efficient Search in Very Large Databases 1988 VLDB 4.7910249e-05
8,761 I/O-Efficient Planar Range Skyline and Attrition Priority Queues 2013 PODS 4.4520434e-05
8,921 Efficient Indexes for Diverse Top-k Range Queries 2020 PODS 4.4229886e-05
12,302 Worst-Case Efficient Range Search Indexing 2009 PODS 4.1905499e-05
12,114 Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility 2012 PODS 4.1905499e-05
1,764 Indexing Moving Points (Extended Abstract) 2000 PODS 0.0001062234
1,183 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013444058