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: hc95e13c8a6706436
Venue: SIGMOD
Year: 2006
Pagerank: 4.9793485e-05
Overall Rank: 12,980 | 12.73%
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,807	SCOUT: Prefetching for Latent Structure Following Queries	2012	VLDB	5.987891e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045337853
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00031645463
264	A Class of Data Structures for Associative Searching	1984	PODS	0.00022757762
1,035	Redundancy in Spatial Databases	1989	SIGMOD	0.00012393393
1,956	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.3169059e-05
3,669	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	7.1125618e-05

Semantically Similar Papers

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