DBScholar

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
1141
Venue
PODS
Year
1998
Pagerank
0.00010361147
Overall Rank
1,561 | 89.30%
DOI
10.1145/275487.275506

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{agarwal_pods98,
        address = {New York, NY, USA},
        series = {{PODS} '98},
        title = {{Efficient Searching with Linear Constraints (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/275487.275506},
        doi = {10.1145/275487.275506},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Agarwal, Pankaj K. and Arge, Lars and Erickson, Jeff and Franciosa, Paolo G. and Vitter, Jeffrey Scott},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank Citing Paper Year Venue Pagerank
333 The Onion Technique: Indexing for Linear Optimization Queries 2000 SIGMOD 0.0002089582
560 Indexing the Positions of Continuously Moving Objects 2000 SIGMOD 0.00016525569
896 On Indexing Mobile Objects 1999 PODS 0.0001334014
1,529 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00010482997
1,611 Indexing Moving Points (Extended Abstract) 2000 PODS 0.00010218339
2,427 Processing a Large Number of Continuous Preference Top-k Queries 2012 SIGMOD 8.5915976e-05
2,676 Efficient Numerical Error Bounding for Replicated Network Services 2000 VLDB 8.2705376e-05
3,007 Towards Robust Indexing for Ranked Queries 2006 VLDB 7.8583548e-05
4,587 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 6.6170389e-05
5,465 On Obtaining Stable Rankings 2019 VLDB 6.2075408e-05
5,764 Indexing Uncertain Data 2009 PODS 6.0955299e-05
6,289 External Memory Algorithms 1998 PODS 5.9261616e-05
9,525 Towards Indexing Functions: Answering Scalar Product Queries 2014 SIGMOD 5.2555551e-05
12,028 Efficient Top-k Indexing via General Reductions 2016 PODS 5.093636e-05
12,363 FIFO Indexes for Decomposable Problems 2011 PODS 5.093636e-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.0020210012
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.001157935
42 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00046170812
85 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00035405879
329 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00021068647
1,137 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00012027131
1,219 Processing Queries By Linear Constraints 1997 PODS 0.00011620957
2,135 Path Caching: A Technique for Optimal External Searching (Extended Abstract) 1994 PODS 9.1133971e-05
2,168 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 9.0469646e-05
3,544 On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract) 1997 PODS 7.3264444e-05
3,790 OODB Indexing by Class-Division 1995 SIGMOD 7.1239529e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 6,160 New Results on Two-dimensional Orthogonal Range Aggregation in External Memory 2011 PODS
2 8,655 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD
3 2,135 Path Caching: A Technique for Optimal External Searching (Extended Abstract) 1994 PODS
4 7,342 Efficient Search in Very Large Databases 1988 VLDB
5 8,750 I/O-Efficient Planar Range Skyline and Attrition Priority Queues 2013 PODS
6 9,073 Efficient Indexes for Diverse Top-k Range Queries 2020 PODS
7 12,489 Worst-Case Efficient Range Search Indexing 2009 PODS
8 12,303 Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility 2012 PODS
9 1,611 Indexing Moving Points (Extended Abstract) 2000 PODS
10 1,529 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS