zbMATH — the first resource for mathematics

Towards optimal two-dimensional indexing for constraint databases. (English) Zbl 1337.68085
Summary: We address the problem of indexing conjunctions of linear constraints with two variables. We show how containment and intersection selection problems for constraint databases can be reduced to the point location problem by using a dual transformation. The proposed representation is then used to develop an efficient secondary storage solution for one important particular indexing case.

68P15 Database theory
68P05 Data structures
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDF BibTeX Cite
Full Text: DOI
[1] Arge, L.; Vitter, J.S., Optimal dynamic interval management in external memory, (), 560-569
[2] Brodsky, A.; Lassez, C.; Lassez, J.L.; Maher, M., Separability of polyhedra and a new approach to spatial storage, (), 54-65
[3] Comer, D., The ubiquitous B-tree, Comput. surveys, 11, 2, 121-138, (1979) · Zbl 0419.68034
[4] Edelsbrunner, H., Algorithms in combinatorial geometry, () · Zbl 0634.52001
[5] Kanellakis, P.C.; Kuper, G.M.; Revesz, P.Z., Constraint query languages, J. comput. system sci., 51, 1, 26-52, (1995)
[6] Kanellakis, P.C.; Ramaswamy, S.; Vengroff, D.E.; Vitter, J.S., Indexing for data models with constraints and classes, (), 233-243
[7] Preparata, F.P.; Shamos, M.I., Computational geometry, an introduction, (1985), Springer New York · Zbl 0759.68037
[8] Srivastava, D., Subsumption and indexing in constraint query languages with linear arithmetic constraints, Ann. math. artif. intell., 8, 3-4, 315-343, (1993) · Zbl 1034.68516
[9] Ramaswamy, S., Efficient indexing for constraints and temporal databases, (), 419-431
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.