Efficient Query Processing on Unstructured Tetrahedral Meshes

Summary: Unstructured tetrahedral meshes indexed via Directed Local Search (DLS) exploit topology, not geometry, to accelerate queries. A new data-layout and PostgreSQL integration yield 25%–4× faster queries than space-filling curves, beating existing indexes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3843
Venue: SIGMOD
Year: 2006
Pagerank: 5.093636e-05
Overall Rank: 12,690 | 12.94%
DOI: 10.1145/1142473.1142535

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Stratos Papadomanolakis (Carnegie Mellon University)
2. Anastassia Ailamaki (Carnegie Mellon University)
3. Julio C. Lopez (Carnegie Mellon University)
4. Tiankai Tu (Carnegie Mellon University)
5. David R. O'Hallaron (Carnegie Mellon University)
6. Gerd Heber (Cornell University)

BibTeX Citation

@inproceedings{papadomanolakis_sigmod06,
        title = {{Efficient Query Processing on Unstructured Tetrahedral Meshes}},
        author = {Papadomanolakis, Stratos and Ailamaki, Anastassia and Lopez, Julio C. and Tu, Tiankai and O'Hallaron, David R. and Heber, Gerd},
        series = {{SIGMOD} '06},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1142473.1142535},
        url = {https://dl.acm.org/doi/10.1145/1142473.1142535},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,679	SCOUT: Prefetching for Latent Structure Following Queries	2012	VLDB	6.1240538e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.0003221055
253	A Class of Data Structures for Associative Searching	1984	PODS	0.00023200431
1,019	Redundancy in Spatial Databases	1989	SIGMOD	0.00012622386
1,901	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.5068846e-05
3,593	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	7.2750277e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,765	Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads	2015	VLDB
2	12,944	Algorithms for Querying by Spatial Structure	1998	VLDB
3	9,887	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
4	8,655	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD
5	1,441	Efficient Processing of Top-k Spatial Preference Queries	2011	VLDB
6	8,532	New Lower and Upper Bounds for Shortest Distance Queries on Terrains	2016	VLDB
7	13,782	Spatial Indexing of Large Multidimensional Databases	2007	CIDR
8	96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD
9	13,776	Organizing and Indexing Non-Convex Regions	2008	VLDB
10	8,442	Efficient Geometry-based Similarity Search of 3D Spatial Databases	1999	SIGMOD